Week 4

Question 1

First Come First Serve

Answer 1

Oldest and simplest method. Non-preemptive method. Good for large batch systems that need to be as busy as possible. Disadvantages: large average wait time, variance in throughput is large, poor for reactivity. The convoy effect is prominent with this solution.

Question 2

Convoy Effect

Answer 2

CPU job hogs CPU and many I/O jobs get queued up behind it.

Question 3

Shortest Job First

Answer 3

Scheduling order based on amount of time the burst will take. Queue is maintained in order upon entrance. Non-preemptive method. Convoy effect still applies and its difficult to know how long processes will take.

Question 4

Exponential average

Answer 4

Method used to estimate CPU burst lengths. Check picture in notes. Alpha is used to weight current and previous behavior. If alpha is low -> past behavior affects more and estimate moves slower. I alpha is high then most recent length matters more and behavior is fast to change. How alpha is chosen depends upon the system. Alpha*last length + (1-alpha) * previous estimate = current estimate.

Question 5

Disadvantages of using exponential average technique

Answer 5

Predicted time always lags the real time.

Question 6

Advantage of using exponential average technique

Answer 6

If the process spends a long time on the same size burst, the average will approach the true value.

Question 7

Shortest Remaining Time First

Answer 7

Preemptive version of SJF. After an interrupt occurs, calculate remaining time on process. If process in queue has shorter burst time, put it on scheduler.

Question 8

Starvation

Answer 8

Overcommitting resources to a CPU with too few resources

Question 9

Round Robin

Answer 9

FCFS with preemption. Designed for time sharing systems.

Question 10

Quantam

Answer 10

Maximum time the process gets to fun. A large enough quanta just become first come first serve. Small quanta is inefficient and will require lots of overhead

Question 11

Hyper exponential distribution with quanta

Answer 11

Ideally 80% of bursts should be shorter than q

Question 12

Priority Scheduling

Answer 12

Each process has a priority. Highest priority gets placed on CPU first and ready queue gets sorted based on this priority. Processes with same priority become first come first serve. Can be preemptive or non preemptive.

Question 13

Multilevel queues

Answer 13

Multiple queues with different purposes and different priorities (I/O queue is higher than experimental). Each queue will have its own scheduling algorithm. Scheduling between queues is fixed priority preemptive scheduling sometimes with quanta.

Question 14

Multi Level feedback.

Answer 14

Processes moving between queues. Processes that use entire quanta every time are bumped down and vice versa. Ideally, should sit on a queue that it sometimes exceeds but mostly doesn’t. Give small quanta to lower priority that guarantees it will run just not for long.

Question 15

Parameters for multi level feedback

Answer 15

Determine when to upgrade process and to downgrade. Previous behavior of programs decides initial queue placement.