CS 354: MIDTERM EXAM STUDY GUIDE QUESTIONS WITH
ANSWERS.
1) Why do we use XINU? -- Answer ✔✔ It is small, complete, elegant, powerful, and
t t t t t t t t t t t t t t t
practical. We can also run it on real hardware, which gets rid of any work done by
t t t t t t t t t t t t t t t t t
VM.
2) What is an operating system? -- Answer ✔✔ It provides an abstract computing
t t t t t t t t t t t t t
environment, supplies services, manages resources, hides low-level hardware.
t t t t t t t
3) What is the equation of context switch overhead? -- Answer ✔✔ Xoverhd% =
t t t t t t t t t t t t t
100*(X/T) where X is cntxsw time and T is quantum time.
t t t t t t t t t t
4) Why are CPU bursts important? -- Answer ✔✔ Help us decide on quantum length.
t t t t t t t t t t t t t t
90% of CPU bursts are smaller than 10 ms, which is crucial to consider.
t t t t t t t t t t t t t
5) What is an adaptive scheduling policy? -- Answer ✔✔ Changing policy based on past
t t t t t t t t t t t t t t
behavior. This normally works because programs have predictable behavior.
t t t t t t t t
6) What is shortest job first? -- Answer ✔✔ Run whatever job has the least amount of
t t t t t t t t t t t t t t t t
computation to do (have to know future). t t t t t t
7) What is shortest remaining time first? -- Answer ✔✔ Preemptive version of SJF:
t t t t t t t t t t t t t
requires knowledge of future and run times.
t t t t t t t
Can lead to starvation if many small jobs are queued, leaving large jobs in the back.
t t t t t t t t t t t t t t t
Pros: Optimal (average response time)
t t t t
Cons: Hard to predict future, unfair
t t t t t
, 8) What are the benefits and challenges of SJF/SRTF? -- Answer ✔✔ They are vest at
t t t t t t t t t t t t t t t
minimizing average completion time. However, you have to be able to accurately
t t t t t t t t t t t t
predict future. t
If all jobs are same length: Just like FCFS
t t t t t t t t
9) What is a multilevel feedback queue? -- Answer ✔✔ It is another method for
t t t t t t t t t t t t t t
exploiting past behavior. Multiple queues each with different priorities and scheduling
t t t t t t t t t t t
algorithms. As time goes on, you can change the priority to move it to different
t t t t t t t t t t t t t t t
queues.
10) What is the fairness tradeoff? -- Answer ✔✔ Fairness gained by hurting completion
t t t t t t t t t t t t t
response time. We could give each queue some fraction of the CPU, or increase
t t t t t t t t t t t t t t
priority of jobs that don't get service.
t t t t t t
11) What is scheduling? What are the key steps? -- Answer ✔✔ It is a fundamental part of
t t t t t t t t t t t t t t t t t
process management, performed by the OS. Three steps: Examine processes that are
t t t t t t t t t t t t
eligible, select a process, switch to selected process.
t t t t t t t
12) How is scheduling implemented? -- Answer ✔✔ We need to pick a scheduling policy
t t t t t t t t t t t t t t
that specifies which process to select. Then, we must build one that selects the
t t t t t t t t t t t t t t
process, updates the process table, and calls context switch.
t t t t t t t t
13) What is the scheduling process in XINU? -- Answer ✔✔ Each process is assigned a
t t t t t t t t t t t t t t t
priority, which is a non-negative integer value. The scheduler always chooses to run
t t t t t t t t t t t t t
an eligible process with the highest priority.
t t t t t t
14) What is the XINU scheduling invariant? -- Answer ✔✔ At any time, the processor
t t t t t t t t t t t t t t
must be executing a highest priority eligible process. Among processes with equal
t t t t t t t t t t t t
priority, scheduling is round robin. t t t t
This must be enforced when the set of processes changes, and the priority changes
t t t t t t t t t t t t t t
(only within syscalls or interrupts.
t t t t
15) What is deferred rescheduling? How is it implemented? -- Answer ✔✔ It delays the
t t t t t t t t t t t t t t
enforcement of the scheduling invariant. We use it by accessing t t t t t t t t t t
ANSWERS.
1) Why do we use XINU? -- Answer ✔✔ It is small, complete, elegant, powerful, and
t t t t t t t t t t t t t t t
practical. We can also run it on real hardware, which gets rid of any work done by
t t t t t t t t t t t t t t t t t
VM.
2) What is an operating system? -- Answer ✔✔ It provides an abstract computing
t t t t t t t t t t t t t
environment, supplies services, manages resources, hides low-level hardware.
t t t t t t t
3) What is the equation of context switch overhead? -- Answer ✔✔ Xoverhd% =
t t t t t t t t t t t t t
100*(X/T) where X is cntxsw time and T is quantum time.
t t t t t t t t t t
4) Why are CPU bursts important? -- Answer ✔✔ Help us decide on quantum length.
t t t t t t t t t t t t t t
90% of CPU bursts are smaller than 10 ms, which is crucial to consider.
t t t t t t t t t t t t t
5) What is an adaptive scheduling policy? -- Answer ✔✔ Changing policy based on past
t t t t t t t t t t t t t t
behavior. This normally works because programs have predictable behavior.
t t t t t t t t
6) What is shortest job first? -- Answer ✔✔ Run whatever job has the least amount of
t t t t t t t t t t t t t t t t
computation to do (have to know future). t t t t t t
7) What is shortest remaining time first? -- Answer ✔✔ Preemptive version of SJF:
t t t t t t t t t t t t t
requires knowledge of future and run times.
t t t t t t t
Can lead to starvation if many small jobs are queued, leaving large jobs in the back.
t t t t t t t t t t t t t t t
Pros: Optimal (average response time)
t t t t
Cons: Hard to predict future, unfair
t t t t t
, 8) What are the benefits and challenges of SJF/SRTF? -- Answer ✔✔ They are vest at
t t t t t t t t t t t t t t t
minimizing average completion time. However, you have to be able to accurately
t t t t t t t t t t t t
predict future. t
If all jobs are same length: Just like FCFS
t t t t t t t t
9) What is a multilevel feedback queue? -- Answer ✔✔ It is another method for
t t t t t t t t t t t t t t
exploiting past behavior. Multiple queues each with different priorities and scheduling
t t t t t t t t t t t
algorithms. As time goes on, you can change the priority to move it to different
t t t t t t t t t t t t t t t
queues.
10) What is the fairness tradeoff? -- Answer ✔✔ Fairness gained by hurting completion
t t t t t t t t t t t t t
response time. We could give each queue some fraction of the CPU, or increase
t t t t t t t t t t t t t t
priority of jobs that don't get service.
t t t t t t
11) What is scheduling? What are the key steps? -- Answer ✔✔ It is a fundamental part of
t t t t t t t t t t t t t t t t t
process management, performed by the OS. Three steps: Examine processes that are
t t t t t t t t t t t t
eligible, select a process, switch to selected process.
t t t t t t t
12) How is scheduling implemented? -- Answer ✔✔ We need to pick a scheduling policy
t t t t t t t t t t t t t t
that specifies which process to select. Then, we must build one that selects the
t t t t t t t t t t t t t t
process, updates the process table, and calls context switch.
t t t t t t t t
13) What is the scheduling process in XINU? -- Answer ✔✔ Each process is assigned a
t t t t t t t t t t t t t t t
priority, which is a non-negative integer value. The scheduler always chooses to run
t t t t t t t t t t t t t
an eligible process with the highest priority.
t t t t t t
14) What is the XINU scheduling invariant? -- Answer ✔✔ At any time, the processor
t t t t t t t t t t t t t t
must be executing a highest priority eligible process. Among processes with equal
t t t t t t t t t t t t
priority, scheduling is round robin. t t t t
This must be enforced when the set of processes changes, and the priority changes
t t t t t t t t t t t t t t
(only within syscalls or interrupts.
t t t t
15) What is deferred rescheduling? How is it implemented? -- Answer ✔✔ It delays the
t t t t t t t t t t t t t t
enforcement of the scheduling invariant. We use it by accessing t t t t t t t t t t
