BEFORE STARTING

You will need to download the programs provided with the OSTEP textbook. This can be done by cloning the git repo that contains them with

git clone https://github.com/remzi-arpacidusseau/ostep-homework/

For this assignment, you will be using the following to answer questions.

  • cpu-sched-mlfq/mlfq.py

  • cpu-sched-lottery/lottery.py

Play around with these scripts to familiarize yourself before answering the below questions.

Questions

  1. mlfq.py: How would you run this script such that 3 jobs, that arrive at the same time, would run in a round robin fashion?

  2. mlfq.py: Craft a workload with two jobs and scheduler parameters such that one job games the older rules 4a and 4b (turned on with the -S flag) to get 99% of the CPU over a particular time interval.

  3. mlfq.py: Given a system, still using the -S flag, with a time-slice (quantum) length of 20 cycles in its highest queue, how often would we need to boost jobs to the highest priority (-B flag) to guarantee that any single non-interactive job gets at least 5% of the CPU?

  4. mlfq.py: One question that arises in scheduling is which end of a queue to add a job that just finished I/O; the -I flag changes this behavior. Play around with some workloads and identify the issue that can occur using this flag.

  5. lottery.py: Run two jobs each of length 10 but one has 1 ticket and the other has 100 tickets (-l 10:1,10:100). What happens when the number of tickets is so imbalanced? Will the job with a single ticket ever run before the other? If so, how often? Generalize what such a ticket imbalance does to the behavior of the lottery scheduler.

  6. lottery.py: When running with two jobs of length 100 and 100 tickets each (-l 100:100,100:100), how unfair is the scheduler? Run with 5 different seeds and determine the fairness.

  7. lottery.py: How does the fairness change as we change the time slice size (-q)?

  8. lottery.py: If we had a stride scheduler instead, how would that affect the runs in question 6?