CPU Scheduling (Plat Tech)

multiprogramming

Maximum CPU utilization obtained with

CPU I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait

CPU burst

followed by I/O burst

CPU burst distribution

is of main concern

CPU scheduler

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

nonpreemptive

When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is

1. Switches from running to waiting state

4. Terminates

preemptive

When scheduling takes place only under circumstances 2 and 3, the scheduling scheme is

2. Switches from running to ready state

3. Switches from waiting to ready

Windows, MacOS, Linux, and UNIX

use preemptive scheduling algorithms.

race conditions

Preemptive scheduling can result in ______ when data are shared among several processes.

Dispatcher module

gives control of the CPU to the process selected by the CPU scheduler

Dispatch latency

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

CPU utilization

keep the CPU as busy as possible

Throughput

number of processes that complete their execution per time unit

Turnaround time

amount of time to execute a particular process

Waiting time

amount of time a process has been waiting in the ready queue

Response time

amount of time it takes from when a request was submitted until the first response is produced.

▪ Max CPU utilization

▪ Max throughput

▪ Min turnaround time

▪ Min waiting time

▪ Min response time

Scheduling Algorithm Optimization Criteria

First- Come, First-Served (FCFS) Scheduling

automatically executes the queued processes and requests in the order of their arrival

Convoy effect

short process behind long process

is a phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to a few slow processes.

Shortest-Job-First (SJF) Scheduling

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

is a scheduling policy that selects the waiting process with the smallest execution time to execute next. SJN, also known as Shortest Job Next (SJN), can be preemptive or non-preemptive.  

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.

time quantum

small unit of CPU time

FIFO

q large

RR

q small

Reponse

Typically RR has a higher average turnaround than SJF, but better ____.

Priority Scheduling

A priority number (integer) is associated with each process

highest priority

The CPU is allocated to the process with the _____

(smallest integer = highest priority)

inverse

SJF is priority scheduling where priority is the _____ of predicted next CPU burst time

Starvation

Problem = ______ – low priority processes may never execute.

Aging

Solution = ____ – as time progresses increase the priority of the process.

same priority

Run the process with the highest priority. Processes with the ______ run round-robin.

Multilevel Queue

The ready queue consists of multiple queues.

highest-priority

Multilevel Queue schedule the process in the ______ queue!

Multilevel Queue Prioritization based upon process type:

real-time processes

system processes

interactive processes

batch processes

Multilevel Feedback Queue

A process can move between the various queues.

Aging can be implemented using multilevel feedback queue.

Thread Scheduling

Distinction between user-level and kernel-level threads.

process-contention scope (pcs)

Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP. Since scheduling competition is within the process.

system-contention scope (SCS)

Kernel thread scheduled onto available CPU is _____ – competition among all threads in system.

Pthread Scheduling

API allows specifying either PCS or SCS during thread creation

Multiple-Processor Scheduling

CPU scheduling more complex when multiple CPUs are available

Symmetric multiprocessing (SMP)

is where each processor is self scheduling.

Multicore Processors

Recent trend to place multiple processor cores on same physical chipFaster and consumes less power

Multithreaded Multicore System

Each core has > 1 hardware threads.

If one thread has a memory stall, switch to another thread!

Chip-multithreading (CMT)

_____ assigns each core multiple hardware threads. (Intel refers to this as hyperthreading.)

8

On a quad-core system with 2 hardware threads per core, the operating system sees ____ logical processors.

1. The operating system deciding which software thread to run on a logical CPU.

2. How each core decides which hardware thread to run on the physical core.

Two levels of scheduling:

Load balancing

attempts to 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.

We refer to this as a thread having affinity for a processor

Soft affinity

the operating system attempts to keep a thread running on the same processor, but no guarantees.

Hard affinity

allows a process to specify a set of processors it may run on.

NUMA-aware

If the operating system is ______, it will assign memory close to the CPU the thread is running on.

Real-Time CPU Scheduling

Can present obvious challenges

Soft real-time systems

Critical real-time tasks have the highest priority, but no guarantee as to when tasks will be scheduled

Hard real-time systems

task must be serviced by its deadline.

Event latency

the amount of time that elapses from when an event occurs to when it is serviced.

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

Priority-based Scheduling

For real-time scheduling, scheduler must support preemptive, prioritybased scheduling

Rate Monotonic Scheduling

A priority is assigned based on the inverse of its period.

Earliest Deadline First Scheduling (EDF)

Priorities are assigned according to deadlines: • The earlier the deadline, the higher the priority • The later the deadline, the lower the priority

Proportional Share Scheduling

T shares are allocated among all processes in the system

POSIX Real-Time Scheduling

The POSIX.1b standard

API provides functions for managing real-time threads

Linux Scheduling Through Version 2.5

Prior to kernel version 2.5, ran variation of standard UNIX scheduling algorithm

Completely Fair Scheduler (CFS)