Operating System Design - CPU Scheduling

Basic Concepts

 

Maximum CPU utilization obtained with multiprogramming

In CPU–I/O Burst Cycle, during I/O burst processing, CPU can handle other process

 

CPU Scheduler

 

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

CPU scheduling decisions may take place when a process:

   1. Switches from running to waiting state

   2. Switches from running to ready state

   3. Switches from waiting to ready

   4. Terminates

Scheduling under 1 and 4 is nonpreemptive (If the process is allocated resources, allow it to continue to use them until it returns them to itself)

All other scheduling is preemptive (When the priority process is occurred, CPU take resource back from the current execution process)

 

Dispatcher

 

Dispatcher module gives control of the CPU to the process selected by the short-term scheduler (switching context, switching to user mode, jumping to the proper location in the user program to restart that program)

Dispatch latency : time it takes for the dispatcher to stop one process and start another running

 

Scheduling Criteria

 

CPU utilization : keep the CPU as busy as possible (Max is good)

Throughput : number of processes that complete their execution per time unit (Max is good)

Turnaround time : amount of time to execute a particular process (Min is good)

Waiting time : amount of time a process has been waiting in the ready queue (Min is good)

Response time : amount of time it takes from when a request was submitted until the first response is produced, not output (Min is good)

 

Scheduling Algorithms

 

FCFS Scheduling : First- Come, First-Served, Convoy effectshort (process behind long process)

If arrive order is P2, P3, P1

SJF Scheduling : Shortest-Job-First

Associate with each process the length of its next CPU burst (Use these lengths to schedule the process with the shortest time)

Gives minimum average waiting time for a given set of processes but, it is difficult to know the length of the next CPU request

 

Shortest-remaining-time-first : Preemptive version of SJF called shortest-remaining-time-first

Round Robin : 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

q large => FIFO

q small => q must be large with respect to context switch, otherwise overhead is too high

q should be large compared to context switch time

Higher average turnaround than SJF, but better response

Priority Scheduling : The CPU is allocated to the process with the highest priority (smallest integer is highest priority)

Problem : Starvation (low priority processes may never execute)

Solution : Aging (increase the priority of the process)

Multilevel Queue : With priority scheduling, have separate queues for each priority (Schedule the process in the highest-priority queue)

Multiple-Processor Scheduling

 

Multicore CPUs, Multithreaded cores, NUMA systems, Heterogeneous multiprocessing

 

Multicore Processors : Multiple threads per core also growing, Takes advantage of memory stall to make progress on another thread while memory retrieve happens

Multithreaded Multicore System : Each core has more than 1 hardware threads. If one thread has a memory stall, switch to another thread

 

Load balancing : keep workload evenly distributed

Push migration : periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs

Pull migration : idle processors pulls waiting task from busy processor

 

Processor Affinity : When a thread has been running on one processor, the cache contents of that processor stores the memory accesses by that thread

 

Real-Time CPU Scheduling

 

Interrupt latency : time from arrival of interrupt to start of routine that services interrupt

 

 

Dispatch latency : time for schedule to take current process off CPU and switch to another

Preemption of any process running in kernel mode

Release by lowpriority process of resources needed by highpriority processes

Priority-based Scheduling : For real-time scheduling, scheduler must support preemptive, prioritybased scheduling

Rate Montonic Scheduling : Shorter periods = higher priority, Longer periods = lower priority

Missed Deadline

Earliest Deadline First Scheduling :

the earlier the deadline, the higher the priority

the later the deadline, the lower the priority