Scheduling

Question 1

What is a scheduler?

Answer 1

A is a software that helps schedule the processes in an operating system. It helps to keep all computer resources busy and allows multiple users to share system resources effectively.

Question 2

A process may leave the CPU for one the following reasons:

Answer 2

1. Completes execution
2. Requests a resource
3. Voluntarily release CPU
4. Involuntarily releases CPU
   (preempted)

Question 3

Scheduling Policy

Answer 3

decides when thread leaves and
which thread is selected to replace it

Question 4

Scheduling Mechanism

Answer 4

determines how the process
manager carries out its duties

Question 5

Scheduling Mechanism has 3 parts

Answer 5

1. Enqueuer
2. Dispatcher
3. Context switcher
4. Enqueuer
   Places a pointer to thread descriptor into ready list (priority placement may happen then or later when thread is selected)
5. Dispatcher Selects one ready thread and allocates CPU to that thread by performing context switch
6. Context switcher Saves the contents of all CPU registers (PC, IR, condition status) for the thread being moved out and places the new thread in.

Question 6

What does a CPU scheduler do

Answer 6

Selects from among the processes in ready queue, and allocates a CPU core to one of them

Question 7

CPU scheduling decisions may take place when a process:

Answer 7

1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates

For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution.

Question 8

The dispatcher

Answer 8

Responsible for the context switch of the current task to a new task.

• This involves:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program

Question 9

Dispatch latenc

Answer 9

Time it takes for the dispatcher to stop one process and start another running

Question 10

Preemptive and Nonpreemptive Scheduling

Answer 10

Ponpreemptive no choice (1 and 4)
Preemptive have a choice (2 and 3)

Question 11

Register Overhead:

Answer 11

Each register must be saved and restored during a context switch to ensure that a process can resume execution exactly where it left off. This involves reading the current register values and storing them in a safe location (usually in the process’s control block in memory), then loading the next process’s saved register values back into the registers.

Question 12

Context Switch Phases:

Answer 12

1. Save process 1’s context
2. Load dispatcher’s context
3. Save dispatcher’s context
4. Load process 2’s context

Question 13

Switching Cost

Answer 13

• 50 nanoseconds to store 1 unit of data
• 32 bit bus / 50 nanoseconds for each register
• 32 general registers and 8 status registers
   40 x 50 nanaseconds = 2 microseconds
• 2 microseconds more to load another thread
• Total time: over 4 microseconds (including dispatch in and out)

Question 14

Preemptive Scheduling and Race Conditions

Answer 14

• Preemptive scheduling can result in race conditions when data are shared among several processes.
• Consider the case of two processes that share data. While one process is updating the data, it is preempted so that the second process can run. The second process then tries to read the data, which are in an inconsistent state.

Question 15

Scheduling Algorithm Optimization Criteria

Answer 15

• Max CPU utilization
• Max throughput
• Min turnaround time
• Min waiting time
• Min response time

Question 16

Scheduling Criteria

Answer 16

Service Time t(pi): amount of time a process needs to be in running state (allocated the CPU) before it is completed.

Wait time W(pi): total amount of time a process needed to wait in a non-running state from the moment it is ready until it is completed.

Response time R(pi): total amount of time from the moment the process is ready until it is considered for the first time by the CPU (allocated the CPU for the first time).

Turnaround time TAT(pi): the amount of time between the process first enters the ready state until the moment the process exits the running state for the last time (terminated)

Question 17

First Come First Served (FCFS) Scheduling

Answer 17

FCFS is the simplest scheduling algorithm. There is a single rule; schedule the first process to arrive, and let it run to completion.

Question 18

PCB

Answer 18

Process Control Block

Question 19

IS FCFS a Preemptive or Nonpreemptive?

Answer 19

Nonpreemptive

Question 20

Shortest Job Next (SJN)

Answer 20

Is a scheduling policy that selects for execution the waiting process with the smallest execution time

Question 21

Shortest Job Next (SJN) Preemptive or Nonpreemptive?

Answer 21

It can be both a preemptive and non-preemptive algorithm.

Question 22

Waiting Time equation

Answer 22

=Total waiting time- time process executed- Arrival time

Question 23

Priority Scheduling

Answer 23

Scheduling algorithm that schedules processes according to the priority assigned to each of the processes. Higher priority processes are executed before lower priority processes.

Question 24

What is Aging

Answer 24

Is a scheduling technique used to prevent starvation in operating systems. It involves gradually increasing the priority of processes that have been waiting for a long time.

Question 25

Round Robin (RR) Scheduling

Answer 25

Tasks are selected in a fixed sequence for execution. On each clock tick, the current task is discontinued and the next is allowed to start execution. in a circular queue fashion.

Question 26

Round Robin (RR) explained

Answer 26

• Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.

– Typically, higher average turnaround than SJF, but better response
* q should be large compared to context switch time
* q usually 10 milliseconds to 100 milliseconds,
* Context switch < 10 microseconds

Question 27

Multilevel queue scheduling

Answer 27

A type of CPU scheduling in which the processes in the ready state are divided into different groups, each group having its own scheduling needs

Question 28

Multilevel Queue Ready queue:

Answer 28

Partitioned into separate queues, eg:
* foreground (interactive)
* background (batch)

• Each queue has its own scheduling algorithm:
• foreground – RR
• background – FCFS

Question 29

 Scheduling must be done between the queues:

Answer 29

• Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.
• Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR
• 20% to background in FCFS

Question 30

Multilevel Feedback Queue

Answer 30

• A process can move between the various queues

Question 31

Multilevel-feedback-queue scheduler defined by the following parameters:

Answer 31

• Number of queues
• Scheduling algorithms for each queue
• Method used to determine when to upgrade a process
• Method used to determine when to demote a process
• Method used to determine which queue a process will enter when that process needs service