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.
