Scheduling Flashcards
What is a scheduler?
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.
A process may leave the CPU for one the following reasons:
- Completes execution
- Requests a resource
- Voluntarily release CPU
- Involuntarily releases CPU
(preempted)
Scheduling Policy
decides when thread leaves and
which thread is selected to replace it
Scheduling Mechanism
determines how the process
manager carries out its duties
Scheduling Mechanism has 3 parts
- Enqueuer
- Dispatcher
- Context switcher
- Enqueuer
Places a pointer to thread descriptor into ready list (priority placement may happen then or later when thread is selected) - Dispatcher Selects one ready thread and allocates CPU to that thread by performing context switch
- 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.
What does a CPU scheduler do
Selects from among the processes in ready queue, and allocates a CPU core to one of them
CPU scheduling decisions may take place when a process:
- Switches from running to waiting state
- Switches from running to ready state
- Switches from waiting to ready
- 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.
The dispatcher
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
Dispatch latenc
Time it takes for the dispatcher to stop one process and start another running
Preemptive and Nonpreemptive Scheduling
Ponpreemptive no choice (1 and 4)
Preemptive have a choice (2 and 3)
Register Overhead:
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.
Context Switch Phases:
- Save process 1’s context
- Load dispatcher’s context
- Save dispatcher’s context
- Load process 2’s context
Switching Cost
- 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)
Preemptive Scheduling and Race Conditions
- 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.
Scheduling Algorithm Optimization Criteria
- Max CPU utilization
- Max throughput
- Min turnaround time
- Min waiting time
- Min response time
Scheduling Criteria
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)
First Come First Served (FCFS) Scheduling
FCFS is the simplest scheduling algorithm. There is a single rule; schedule the first process to arrive, and let it run to completion.
PCB
Process Control Block
IS FCFS a Preemptive or Nonpreemptive?
Nonpreemptive
Shortest Job Next (SJN)
Is a scheduling policy that selects for execution the waiting process with the smallest execution time
Shortest Job Next (SJN) Preemptive or Nonpreemptive?
It can be both a preemptive and non-preemptive algorithm.
Waiting Time equation
=Total waiting time- time process executed- Arrival time
Priority Scheduling
Scheduling algorithm that schedules processes according to the priority assigned to each of the processes. Higher priority processes are executed before lower priority processes.
What is Aging
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.
Round Robin (RR) Scheduling
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.
Round Robin (RR) explained
- 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
Multilevel queue scheduling
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
Multilevel Queue Ready queue:
Partitioned into separate queues, eg:
* foreground (interactive)
* background (batch)
- Each queue has its own scheduling algorithm:
- foreground – RR
- background – FCFS
Scheduling must be done between the queues:
- 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
Multilevel Feedback Queue
- A process can move between the various queues
Multilevel-feedback-queue scheduler defined by the following parameters:
- 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
