Operating Systems 2014F: Assignment 3

Please submit the answers to the following questions via CULearn by midnight on Wednesday, September 24, 2014. There 10 points in 7 questions.

Submit your answers as a single text file named "<username>-comp3000-assign3.txt" (where username is your MyCarletonOne username). The first four lines of this file should be "COMP 3000 Assignment 3", your name, student number, and the date of submission. You may wish to format your answers in Markdown to improve their appearance.

No other formats will be accepted. Submitting in another format will likely result in your assignment not being graded and you receiving no marks for this assignment. In particular do not submit an MS Word or OpenOffice file as your answers document!

Don't forget to include what outside resources you used to complete each of your answers, including other students, man pages, and web resources. You do not need to list help from the instructor, TA, or information found in the textbook.

Questions

1. [1] For what types of workloads does SJF deliver the same turnaround times as FIFO?
2. [1] For what types of workloads and quantum lengths does SJF deliver the same response times as RR?
3. [1] What happens to response time with SJF as job lengths increase?
4. [2] What happens to response time with RR as quantum lengths increase? Explain in words and write an equation that gives the worst-case response time, given N jobs.
5. [2] "Preemptive schedulers are always less efficient than non-preemptive schedulers." Explain how this statement can be true if you define efficiency one way and how it is false if you define efficiency another way.
6. [2] Explain two ways in which standard OS schedulers (such as those in Linux or Windows) are not fair to processes and why this is a good thing!
7. [1] MLFQ-type schedulers are more common in systems with single users while systems that support multiple users tend to use more proportional share-type schedulers. Why might this be?

Solutions

5. If you define efficiency as the ratio between the amount of CPU time spent on OS services versus time spent running userspace programs, preemptive schedulers are always less efficient because they switch between processes more often and hence run the scheduler and do context switches more often. Time spent running the scheduler and doing context switches is pure overhead. If you define efficiency in terms of response time - how long it takes the system to respond to input - preemptive schedulers are always more efficient than non-preemptive schedulers because preemptive schedulers can quickly switch to the process/thread that needs to process the input.
6. Standard OS schedulers are not fair because they give more resources more quickly to some processes over others. Fairness in scheduling is normally defined as giving equal shares of CPU time to each process. With prioritization we have unfairness due to policy: some processes are marked as being more important than others, thus they get more resources in a more timely fashion. Schedulers are also unfair in that they tend to prioritize interactive processes over other processes that have the same priority level. We want schedulers to be unfair because some processes should be prioritized: when I am playing a game, I do not want a background virus check to cause the game to slow down.
7. MLFQ-type schedulers allocate resources on a per-process basis. On a system that has only one user this isn't a factor; on a system with multiple users, however, it can be a problem because any user can increase their share of resources simply by running more processes. Fair-share schedulers can allocate a fixed proportion of resources to each user, no matter how many processes they choose to run. Traditionally fair share schedulers are not so good for interactive performance, however, because they do not normally boost the priority of processes that have received input. Note that the current Linux schedule, CFS, is a weighted fair share scheduler that does special accounting for blocked processes.