Please enable JavaScript.
Coggle requires JavaScript to display documents.
CPU Scheduling (Scheduling Criteria (CPU Utilization (The goal is to keep…
CPU Scheduling
Scheduling Criteria
Each scheduling algorithm has different properties. When choosing an algorithm we must consider certain properties.
-
-
-
-
Response Time
Used in interactive systems. It is the time of the submission of a request until the first response is produced. Measures the time it takes a process to start responding.
Scheduling Algorithms
First Come, First Serve
It is the simplest CPU scheduling algorithm. The process the request the CPU first is the one that receives it. Can be implemented with a FIFO queue
It is easy to implement and to understand the code. On the other side the waiting time under this algorithm is very long. There is a convoy effect as all the other processes wait for the one big process to get off the CPU
Shortest Job First
Schedules processes based on their next CPU burst time. If two processes have the shortest next CPU burst time then FCFS is used to schedule this processes.
It is optimal as it gives minimum average waiting time for a set of processes. Frequently used in long term scheduling. Cannot be implemented at a level of short term scheduling.
SJFA
SJF approach for short term scheduling. As it is not possible to know the length of the next CPU burst we can approximate it. This is based on the proposition that the next CPU will be similar to the previous ones.
Calculated by the formula: NT = aAH + (1 - a)PH. The a stands for an alpha that defines how much weight is assign to PH: past history and AH: actual history.
PSFJ
This is the preemptive version of the SJF. This solution arises for processes that arrive to the ready queue and their next CPU burst is shorter than the one executing. If this happens then the preemptive approach will empty the executing process and give the CPU to the new shorter process.
Round Robin
Designed for time sharing systems. It uses a time slice called quantum that is defined by the programmer. The ready queue is managed as a circular queue. The CPU allocates to each process 1 quantum of time. The processes access the ready queue as a FIFO.
Depends fully on the quantum defined. If the quantum is too big for the processes then it works the same as a FCFS, and if it is too small then it will do a exceeding amount of context switches between processes.
CPU - IO Bursts
-
Process execution begins with a CPU burst then an IO burst , which is followed by another CPU burst and so on.
Depending is the processes to be scheduled are CPU-bounded or IO-bounded the desired scheduling algorithm bay change.
Real Time CPU Scheduling
Soft real time systems provide no guarantee as to when a critical process will be scheduled. Hard real time systems are more strict, a task must be serviced by its deadline otherwise is the same as no service.
Minimizing Latency
Event latency is the amount of time that elapses from when an event occurs to when it is serviced. There are two types of latency, interrupt and dispatch.
Interrupt Latency
Time from the arrival of an interruption to the CPU to the start of the routine that services the interrupt. When this happens the OS most finish the instruction executing and address the interruption.
Dispatch Latency
The amount of time required for scheduling dispatcher to stop one process and start another. The most effective technique is to provide preemptive kernels.
Thread Scheduling
Contention Scope
User and kernel threads are scheduled differently. On systems implementing many-to-one or many-to-many models the thread library schedules user thread to run on an LWP. This scheme is known as process contention scope.
To decide which kernel thread to schedule into CPU the kernel uses system contention scope. Competition for the CPU on this SCS scheduling takes place in all threads on the system.