CPU Scheduling

Question 1

Describe first come first serve (fcfs) scheduling.

Answer 1

• Simplest type of scheduling. Process that arrives first gets cpu time and run until completion.
• This is non-preemptive and very easy to understand and implement.
• Unfortunately have bad characteristics such as long average wait time if processes with long cpu bursts come before ones with short cpu bursts.

Question 2

Describe shortest time first (stf) scheduling.

Answer 2

• Processes that has the shortest next cpu burst get run first. This helps minimize average waiting time.
• Unfortunately, there’s no way for short term scheduler to know how long the next cpu burst for each process will be.
• Short term schedulers usually estimate next cpu burst based on previous cpu bursts time of the process, putting more weight on more recent bursts than older ones.
• SJF can be either preemptive or nonpreemptive. If preemptive, new process with smaller predicted next cpu burst will interrupt the current running process and gets run first.

Question 3

Describe priority scheduling.

Answer 3

• Processes with the highest priority gets run first. Each process gets a priority number between 1 and n. And the process with either the highest or lowest number gets run first.
• Shortest time first is a specialized form of priority scheduling. Just map next predicted burst time to a priority.
• This can also be either preemptive or non preemptive.
• One issue with this is some process may never run if new higher priority processes come in all the time. A way around this is to age processes by giving them higher and higher priority as time goes on.

Question 4

Describe round robin scheduling.

Answer 4

• Similar to first in first out scheduling, but each process gets a time limit to run. If the process does not finish its cpu burst in that time limit, it gets interrupted and put back at the end of the queue.
• The time limit should be longer than most cpu bursts but not too long lest it becomes first in first out.
• Time limit should also be a lot longer than time to context switch so that context switch doesn’t add too much time.

Question 5

Describe multilevel queue scheduling.

Answer 5

• Multiple queues for processes exist and the processes get put in one of these queues.
• Different queues have different scheduling algorithms.
• Must also decide on how to schedule which queue to run first. One way is to have one queue have absolute priority over another. Another way is to have each queue gets certain percentage of cpu time and have the queue divide out that cpu time among processes.
• Must also decide on when to move processes from one queue to another.

Question 6

Explain what process scheduling is and some issues.

Answer 6

• Modern OS allow multiple processes to run at the same time. CPU scheduling is the task of deciding which of the processes should be given CPU time.
• CPU scheduling can be either non-preemptive or preemptive. Nonpreemptive scheduling lets a process run to completion without interrupt while a preemptive scheduling can be interrupted. Preemptive scheduling can be a bit tricky since the process that is about to be preempted maybe in the middle of modifying some data structure either in user space or kernel space. Sometimes this is prevented by disabling interrupt or some of the concurrency methods we talked about previously.
• There’s also the issue of switching context between processes to consider.