CPU SCHEDULING

Question 1

Define a CPU burst

Answer 1

The amount of time a process uses the processor
before it is no longer ready (aka Execution time)

Question 2

What are the different types of CPU bursts

Answer 2

• long bursts – process is CPU bound (i.e. array work)
• short bursts – process I/O bound

Question 3

What are the different scheduling criteria to compare scheduling algorithms

Answer 3

CPU Utilization
Throughput
Turnaround time
Waiting time
Response time

Question 4

Describe CPU utilization as a criterion

Answer 4

Ideally the CPU would be busy 100% of the time, so as to waste
0 CPU cycles. On a real system CPU usage should range from
40% ( lightly loaded ) to 90% ( heavily loaded. )

Question 5

Describe throughput as a criterion

Answer 5

Number of processes completed per unit time. May range from 10 / second to 1 / hour depending on the specific processes.

Question 6

Describe Turnaround time as a criterion

Answer 6

Time required for a particular process to complete, from
submission time to completion. ( Wall clock time. )

Question 7

Describe waiting time as a scheduling criterion

Answer 7

-How much time processes spend in the ready queue
waiting their turn to get on the CPU.
-( Load average - The average number of processes sitting in the ready queue waiting their turn to get into the CPU. Reported in 1-minute, 5-minute, and 15-minute averages by “uptime” and “who”. )

Question 8

Describe response time as a scheduling criterion

Answer 8

The time taken in an interactive program from the
issuance of a command to the commence of a response
to that command.

Question 9

List 6 examples of CPU scheduling algorithms

Answer 9

First-Come, First-Served (FCFS) Scheduling Algorithm Shortest-Job-Next (SJN) Scheduling Algorithm
Priority Scheduling Algorithm
Shortest Remaining Time First (SRTF) Scheduling Algorithm
Round Robin(RR) Scheduling Algorithm
Multiple-Level Queues Scheduling Algorithm
* Multi-level feedback Queues Scheduling Algorithm

Question 10

Differentiate between preemptive and non-preemptive algorithms

Answer 10

Non-preemptive algorithms are designed so that once a
process enters the running state, it cannot be preempted
until it completes its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state

Question 11

Describe the First Come Firs Serve algorithm

Answer 11

• Jobs are executed on first come, first serve basis.
• It is a non-preemptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.
• Poor in performance as average wait time is high.

Question 12

Describe the Shortest Job Next algorithm

Answer 12

-This algorithm picks a process based on the next shortest CPU burst,
- This is a non-preemptive, pre-emptive scheduling algorithm.
- Best approach to minimize waiting time.
- Easy to implement in Batch systems where required CPU time is known in advance.
- Impossible to implement in interactive systems where required CPU time is not known.
- The processer should know in advance how much time process will take.

Question 13

Describe priority based algorithm

Answer 13

• Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems.
• Each process is assigned a priority. Process with highest priority is to be executed first and so on.

Question 14

How is priority determined? What happens when processes have the same priority

Answer 14

• Priority can be decided based on memory requirements, time requirements or any other resource requirement.
• Processes with same priority are executed on first come first served basis.

Question 15

Describe the round robin algorithm

Answer 15

CPU bursts are assigned with a small unit of CPU time
called time quantum.
- When a process is given the CPU, a timer is set for whatever value has been set for a time quantum.
- If the process finishes its burst before the time quantum
timer expires, then it is swapped out of the CPU just like the normal FCFS algorithm.
- If the timer goes off first, then the process is swapped out of the CPU and moved to the back end of the ready queue.
- The ready queue is maintained as a circular queue, so when all processes have had a turn, then the scheduler gives the first process another turn, and so on.

Question 16

How does the time quantum affect the performance of the round robin algorithm

Answer 16

• The performance of RR is sensitive to the time quantum selected. If the quantum is large enough, then RR reduces to the FCFS algorithm; If it is very small, then each process gets 1/nth of the processor time and share the CPU equally.
• BUT, a real system invokes overhead for every context switch, and the smaller the time quantum the more context switches there are.
  -Most modern systems use time quantum between 10 and 100 milliseconds, and context switch times on the order of 10 microseconds, so the overhead is small relative to the time quantum.

Question 17

Describe Shortest Remaining Time First (SRTF) Scheduling Algorithm

Answer 17

• This Algorithm is the preemptive version of SJF scheduling.
  -In SRTF, the execution of the process can be stopped after a certain amount of time.
  -At the arrival of every process, the short term scheduler schedules the process with the least remaining burst time among the list of available processes
  and the running process.
• Once all the processes are available in the ready queue, no preemption will be done and the algorithm will work as SJF scheduling.

Question 18

Describe the Multilevel Queue Scheduling algorithm

Answer 18

When processes can be readily categorized, then multiple separate queues can be established, each implementing whatever scheduling algorithm is most appropriate for that type of job, and/or with different parametric adjustments.

Note that under this algorithm jobs cannot switch from
queue to queue - Once they are assigned a queue, that is their queue until they finish.

Question 19

How is scheduling done between queues in multilevel queue algorithm

Answer 19

Two common options are strict priority (no job in a lower
priority queue runs until all higher priority queues are empty) and round-robin (each queue gets a time slice in turn, possibly of different sizes.)

Question 20

Describe Multilevel Feedback-Queue Scheduling Algorithm, its advantage and disadvantage

Answer 20

-Multilevel feedback queue scheduling is similar to the ordinary multilevel queue scheduling described above, except jobs may be moved from one queue to another
-Multilevel feedback queue scheduling is the most flexible, because it can be tuned for any situation. But it is also the most complex to implement because of all the adjustable parameters.

Question 21

What are some of the possible reasons why a job may be moved from one queue to another in the Multilevel Feedback-Queue Scheduling Algorithm

Answer 21

• If the characteristics of a job change between CPU-intensive and I/O intensive, then it may be appropriate to switch a job from one queue to another.
• Aging can also be incorporated, so that a job that has waited for a long time can get bumped up into a higher priority queue for a while.

Question 22

What are some of the parameters considered in the Multilevel Feedback-Queue Scheduling Algorithm

Answer 22

-The number of queues.
- The scheduling algorithm for each queue.
- The methods used to upgrade or demote processes from one queue to another. ( Which may be different. )
- The method used to determine which queue a process
enters initially.