a) What are two of the roles of an Operating System? Give one example for each role.
Roles: Illusionist, referee, glue. Also acceptable, abstraction level, resource
Reasonable examples will be considered for merit. (infinite memory, scheduling, files
not blocks on disk but as we see them in our desktops, etc.)
b) Consider the following processes, their arrival times and the CPU burst times they
need in order to complete. Assume no process interrupts for I/O.
Arrival Time Burst Time
P1 0 3
P2 2 6
P3 3 2
P4 5 1
P5 6 2
i) Create the Gantt chart for a First Come First Served (FCFS) and for a Shortest
Job First (SJF) scheduling.
ii) Calculate the average wait time and the average completion time for FCFS and
for SJF scheduling.
P1 P2 P3 P4 P5
0 3 9 11 12 14
Wait: (respectively): 0, 1, 6, 6, 6, so avg. wait: 19/5 = 3.8
Completion times: 3+9+11+12+14 = 49/5 = 9.8
P1 P3 P4 P5 P2
0 3 5 6 8 14
Wait: (respectively): 0, 6, 0, 0, 0 so average wait time = 6/5 = 1.2
Completion times: 3+5+6+8+14 = 35/5 = 7
c) Answer the following:
i) What do the terms interactive (or I/O bound) and batch (or CPU bound) mean
when used to describe a process? What are the typical profiles of each type of
process in terms of CPU bursts for preemptive scheduling?
ii) Should schedulers that use time slicing (e.g. Round Robin) use very short time
slices (e.g. 2ms) or relatively longer ones (e.g. 20 ms)? Briefly explain your
iii) Briefly explain how scheduling based on multi-level feedback queues tries to
make sure that batch (CPU-bound) processes do not suffer starvation.
i) Batch processes (CPU intensive): Computationally intensive, throughput matters
most (last digit of 𝑝𝑖). Long burst times, likely to use full time slice q.
Interactive processes (I/O intensive): Response time matters most (e.g. a process
that keeps stopping for I/O, perhaps with the user). Frequently interrupting for I/O so likely
to not be using full time slice q. Short bursts.
ii) Relatively longer ones. The key is to be in reasonable proportion to context switch
overheads (around 1% overhead). If time slice too short, little actual progress in
process work will be done as proportionally we end up spending too much time
swapping processes in and out of the CPU.
iii) Short answer: by dynamic priorities and by increasing CPU time as process is
moved to lower priority queues.
Longer version (not really required to this much level of detail):
Priorities are recomputed taking into account the consumed CPU, and hence an I/O-
bound process will end up having a higher priority than a process that started at the
same priority level and which used more CPU cycles.
Even a process with low priority will be scheduled eventually, since the priority of
processes that are continually scheduled eventually also receive a low or lower
Also note that the recorded amount of CPU consumed (that is used to calculate
priority) is aged (reduced) over time, and hence CPU-bound processes also increase
in priority if they are not scheduled.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx