O perating s ystems t hree e asy p ieces

Homework

This program, lottery.py, allows you to see how a lottery scheduler

works. See the README for details.

Questions

1. Compute the solutions for simulations with 3 jobs and random seeds

of 1, 2, and 3.

2. Now run with two specific jobs: each of length 10, but one (job 0)

with just 1 ticket and the other (job 1) with 100 (e.g., -l 10:1,10:100).

What happens when the number of tickets is so imbalanced? Will

job 0 ever run before job 1 completes? How often? In general, what

does such a ticket imbalance do to the behavior of lottery schedul-

ing?

3. When running with two jobs of length 100 and equal ticket alloca-

tions of 100 (-l 100:100,100:100), how unfair is the scheduler?

Run with some different random seeds to determine the (probabilis-

tic) answer; let unfairness be determined by how much earlier one

job finishes than the other.

4. How does your answer to the previous question change as the quan-

tum size (-q) gets larger?

5. Can you make a version of the graph that is found in the chapter?

What else would be worth exploring? How would the graph look

with a stride scheduler?

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

10

Multiprocessor Scheduling (Advanced)

This chapter will introduce the basics of multiprocessor scheduling. As

this topic is relatively advanced, it may be best to cover it after you have

studied the topic of concurrency in some detail (i.e., the second major

“easy piece” of the book).

After years of existence only in the high-end of the computing spec-

trum, multiprocessor systems are increasingly commonplace, and have

found their way into desktop machines, laptops, and even mobile de-

vices. The rise of the multicore processor, in which multiple CPU cores

are packed onto a single chip, is the source of this proliferation; these

chips have become popular as computer architects have had a difficult

time making a single CPU much faster without using (way) too much

power. And thus we all now have a few CPUs available to us, which is a

good thing, right?

Of course, there are many difficulties that arise with the arrival of more

than a single CPU. A primary one is that a typical application (i.e., some C

program you wrote) only uses a single CPU; adding more CPUs does not

make that single application run faster. To remedy this problem, you’ll

have to rewrite your application to run in parallel, perhaps using threads

(as discussed in great detail in the second piece of this book). Multi-

threaded applications can spread work across multiple CPUs and thus

run faster when given more CPU resources.

A

SIDE

: A