This is a sample assignment with questions about scheduling.
Solutions are available as a plain ASCII file.
Consider an OS that schedules jobs with a single Round-Robin queue. The context-switching overhead is o=0.1ms. We represent the execution timeline of a job mix on this system by indicating 1ms of computation for a job via an uppercase letter (we assume that the time quantum and all CPU bursts are integral numbers of ms). For example, the following string:
means that job A executes for 3ms, then job B for 1ms, then job C for 1ms, then job A again for 2ms, then job D for 3ms, with appropriate context-switches in between. This example execution lasts 10ms + 4x0.1ms = 10.4ms (10ms of actual job execution, .4ms of context-switching overhead).
Consider the following execution:
DDDDDDoBBBBBBoCoAAAAAAoDDDDDDoBBBoCoDDDDDDoBBBoCoDDDDDDoAAAAAAoBBBBBBoCoDDDDDDo...Answer the following questions:
[q1] Knowing that there is exactly one job in the mix that consists of just one infinitely long CPU burst, which job is it? Explain.
[q2] Knowing that one of these jobs is a text editor, which job do you think it is? Explain.
[q3] Assuming that the time-quantum is 6ms, what is maximum number and what is the minimum number of I/O bursts initiated by job B in the above sequence? Explain. (Your answer should be two integers)
Assume a job mix with 3 I/O-bound jobs and 1 fully CPU-bound job. The fully CPU-bound job is just one infinitely long CPU burst. Each I/O-bound job has a CPU burst of 2ms and then an I/O burst of 4ms, and repeats this burst cycle ad infinitum. The time quantum is 5ms.
We reason on steady-state execution (i.e., we consider the behavior of the workload in the long run). We assume that, initially, the ready queue contains the I/O jobs followed by the CPU job (i.e., the first time around, all I/O jobs will run before the CPU job).
Answer these questions:
[q1] Write the ASCII representation of the execution of the job mix as in Question #1, using I to denote 1ms of execution of any of the I/O-bound jobs, and C to denote 1ms of execution of the CPU-bound job, and o to denote a 0.1ms context-switching overhead. Your answer should look like this “IoIICoCCoIoIoCo” (this is a very wrong answer). Even though the execution is infinite, you should identify a repeating pattern. Your answer should only show this pattern once, finishing with a “o”.
[q2] What is the number of consecutive milliseconds an I/O-bound job spends in the READY state? Show your work.
[q3] What should the context-switching overhead be, in milliseconds, so that 1% of the time is spent doing context-switching when this job mix executes? Show your work.
Consider an OS that uses an MLFQ Scheme with 3 Round-Robin Queues:
Consider a job mix in which all jobs go through sequences of CPU bursts and I/O bursts, and that all I/O bursts last 1ms (somehow, all jobs place similar, short I/O requests, to different devices). We assume that the context-switching overhead is zero (and we never show o’s in ASCII representations).
We can now describe a job by a single number: a CPU burst duration. For instance, a job with CPU burst duration of 10ms is simply: compute for 10ms, I/O for 1ms, compute for 10ms, I/O for 1ms, … ad infinitum.
We thus describe a job mix as a list of X-y notations, which means job X with CPU burst duration y. For instance, “A-5, B-9, C-3, D-1” describes a job mix with 4 jobs such that:
Consider the following job mix: “A-6, B-2, C-9, D-7, E-10”. Answer the following questions:
[q1] Assuming that the scheduler does not implement any priority boosting, for each job say in which queue it eventually ends up (forever)
[q2] Initially, as you know, all jobs are in the top-priority queue. Say that they are in the order A, B, C, D, E (i.e., A will be scheduled first, then B, etc.). Assuming A begins its CPU burst at time 0, at what time does B begin executing its second CPU burst? Don’t just give a single number without any explanation. Explain your reasoning in English, and/or give the time as a sum of terms, and/or give an execution sequence as in Exercise #1 (e.g., “AABBABABAAABABAAA” or with spaces for better readability ““AA BBA B AB AAA B A B AAA).
Consider the following job mix: “A-3, B-∞”. Answer the following questions:
[q1] Assume that the scheduler does not implement any priority boosting Write the execution sequence on the CPU as in Exercise #1 (e.g., “AABCDBBABDBAEEEE” or with spaces for better readability “AA B C D BB A B D B A EEEE”). There is a simple repeating pattern at some point. Your answer should show the execution until this pattern has repeated twice and then just “…”.
[q2] In the long-run, does the CPU run job B more than 20% of the time? Explain by referring to the answer to the previous question.
[q3] Assume that the scheduler implements priority boosting every 16ms starting at time 16ms (i.e., there is a priority boost to the top queue at times 16, 32, 48, etc.). Write the execution sequence in this case. There is again a simple repeating pattern. Your answer should show the execution from time 0 to time 40, included (i.e., 41 ASCII characters).