[IOS] Ch5 Process scheduling

Basic concept

• In a single-processor system, only one process can run at a time
• Any others must wait until the CPU is free and can be rescheduled.

• Multiprogramming is to have some process running at all times to maximize CPU utilization. 
• A process is executed until it must wait, typically for the completion of some I/O request. 
• Several processes are kept in memory at one time, when one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. 
• Every time one process has to wait, another process can take over use of the CPU.
• Scheduling of this kind is a fundamental operating-system function.
• Almost all computer resources are scheduled before use. The CPU is, of course, one of the primary computer resources. Thus, its scheduling is central to operating-system design.

CPU - I/O Burst Cycle

• The success of CPU scheduling depends on an observed property of processes: process execution consists of a cycle of CPU execution and I/O wait. 

• Processes alternate between these two states, execution begins with a CPU burst.

• Followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on, the final CPU burst ends with a system request to terminate execution.

• The durations of CPU bursts have been measured extensively, tend to have a frequency curve

• The curve is generally characterized as exponential or hyper-exponential, with a large number of short CPU bursts and a small number of long CPU bursts.

• An I/O-bound program typically has many short CPU bursts, a few long CPU bursts. This distribution can be important in the selection of an appropriate CPU-scheduling algorithm.

CPU scheduler

• 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

• nonpreemptive scheduler uses 1 and 4

• Preemptive scheduler kicks in for all four time points

Preemptive scheduling

• CPU-scheduling decisions may take place under the following four circumstances:
• When a process switches from the running state to the waiting state 
• For example, as the result of an I/O request or an invocation of wait for the termination of one of the child processes
• When a process switches from the running state to the ready state 
• For example, when an interrupt occurs
• When a process switches from the waiting state to the ready state 
• For example, at completion of I/O
• When a process 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. 
• There is a choice, however, for situations 2 and 3.
• When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is nonpreemptive or cooperative;  
• otherwise, it is preemptive. 
• Under nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. 
• This scheduling method was used by Microsoft Windows 3.x; 
• Windows 95 introduced preemptive scheduling, and all subsequent versions of Windows operating systems have used preemptive scheduling. 
• The Mac OS X operating system for the Macintosh also uses preemptive scheduling; previous versions of the Macintosh operating system relied on cooperative scheduling. 
• Cooperative scheduling is the only method that can be used on certain hardware platforms, because it does not require the special hardware (for example, a timer) needed for preemptive scheduling.
• Unfortunately, preemptive scheduling incurs a cost associated with access to shared data. 
• Consider the case of two processes that share data. 
• While one 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. 
• In such situations, we need new mechanisms to coordinate access to shared data;
• Preemption also affects the design of the operating-system kernel. 
• During the processing of a system call, the kernel may be busy with an activity on behalf of a process. 
• Such activities may involve changing important kernel data (for instance, I/O queues). 
• If the process is preempted in the middle of these changes and the kernel (or the device driver) needs to read or modify the same structure, Chaos ensues. 
• Certain operating systems, including most versions of UNIX, deal with this problem by waiting either for a system call to complete or for an I/O block to take place before doing a context switch. 
• This scheme ensures that the kernel structure is simple, since the kernel will not preempt a process while the kernel data structures are in an inconsistent state.  
• Unfortunately, this kernel-execution model is a poor one for supporting real-time computing and multiprocessing. 
• Because interrupts can, by definition, occur at any time, and because they cannot always be ignored by the kernel, the sections of code affected by interrupts must be guarded from simultaneous use. 
• The operating system needs to accept interrupts at almost all times; otherwise, input might be lost or output overwritten. 
• So that these sections of code are not accessed concurrently by several processes, they disable interrupts at entry and reenable interrupts at exit. 
• It is important to note that sections of code that disable interrupts do not occur very often and typically contain few instructions.

Dispatcher

• Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
• 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

• Should be as fast as possible, since it is invoked during every process switch.

Scheduling Criteria

• CPU utilization
• We want to keep the CPU as busy as possible. 
• Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).

• Throughput
• If the CPU is busy executing processes, then work is being done. 
• One measure of work is the number of processes that are completed per time unit, called throughput
• For long processes, this rate may be one process per hour; for short transactions, it may be ten processes per second.
• Higher is better

• Turnaround time 
• From the point of view of a particular process, the important criterion is how long it takes to execute that process. 
• The interval from the time of submission of a process to the time of completion is the turnaround time. 
• Sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
• Lower is better

• Waiting time 
• The CPU-scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue. 
• sum of the periods spent waiting in the ready queue.

• Response time 
• In an interactive system, turnaround time may not be the best criterion. 
• Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user. 
• Thus, another measure is the time from the submission of a request until the first response is produced. 
• time it takes to start responding, not the time it takes to output the response. 
• The turnaround time is generally limited by the speed of the output device.
• Lower is better
  

Scheduling Algorithm

First-Come, First-Served (FCFS) Scheduling

• The simplest CPU-scheduling algorithm

• process that requests the CPU first is allocated the CPU first. 

• Implementation
• easily managed with a FIFO queue. 
• When a process enters the ready queue, its PCB is linked onto the tail of the queue. 
• When the CPU is free, it is allocated to the process at the head of the queue. 
• The running process is then removed from the queue. 

• The code for FCFS scheduling is simple to write and understand.

• Average waiting time under the FCFS policy is often quite long.

•  nonpreemptive
• Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.

• Example:

• CPU bound jobs will hold CPU until exit or I/O
• I/O rare for CPU-bound thread
• Long periods where no I/O requests issued, and CPU held
• => poor I/O device utilization

• Example: one CPU-bound job, many I/O bound
• CPU bound runs (I/O device idle)
• CPU bound blocks
• I/O bound job(s) run, quickly block on I/O
• CPU bound runs again
•  I/O completes
• CPU bound still runs while I/O device idle (continue?)

Shortest-Job-First (SJF) Scheduling

• Associate with each process the length of its next CPU burst. 

• Use these lengths to schedule the process with the shortest time

• Process with shortest burst goes next

• If tie then use FCFS to break tie

• SJF is optimal – gives minimum average waiting time for a given set of processes
• The difficulty is knowing the length of the next CPU request
• Two schemes:
• Non-preemptive – once CPU assigned, process not preempted until its CPU burst completes
• Preemptive – if a process with CPU burst less than remaining time of current, preempt 
• Shortest-Remaining-Time-First (SRTF)

• Determining Length of Next CPU Burst
• Can only estimate the length
• Can be done by using the length of previous CPU bursts, using exponential averaging

Priority Scheduling

• A priority number (integer) is associated with each process

• The CPU is allocated to the process with the highest priority (smallest integer same as highest priority)
• Preemptive
• Non-preemptive

• SJF is a priority scheduling where priority is the predicted next CPU burst time

• Problem: Starvation – low priority processes may never execute

• Solution: Aging – as time progresses increase the priority of the process

Round Robin (RR)

• Each process gets a small unit of CPU time (time quantum), 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.

• Performance
• q large => FIFO
• q small => processor sharing (appears as dedicated processor with speed 1/n actual)
• q must be large with respect to context switch, otherwise overhead is too high

Multilevel Queue

• Created for situations in which processes are easily classified into different groups. 
• For example, a common division is made between foreground (interactive) processes and background (batch) processes. 
• These two types of processes have different response-time requirements and so may have different scheduling needs. 
• In addition, foreground processes may have priority (externally defined) over background processes.

• Partitions the ready queue into several separate queues 
• The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority, or process type. 
• Each queue has its own scheduling algorithm. 
• For example, separate queues might be used for foreground and background processes. 
• The foreground queue might be scheduled by an RR algorithm, while the background queue is scheduled by an FCFS algorithm.
• In addition, there must be scheduling among the queues, which is commonly implemented as fixed-priority preemptive scheduling. 
• For example, the foreground queue may have absolute priority over the background queue.

• five queues, listed below in order of priority:

• Each queue has absolute priority over lower-priority queues. No process in the batch queue could run unless the queues for system processes, interactive processes, and interactive editing processes were all empty. 
• If an interactive editing process entered the ready queue while a batch process was running, the batch process would be preempted.

• Another possibility is to time-slice among the queues. 
• Each queue gets a certain portion of the CPU time, which it can then schedule among its various processes. 
• foreground queue can be given 80 percent of the CPU time for RR scheduling among its processes, whereas the background queue receives 20 percent of the CPU to give to its processes on an FCFS basis.

Multilevel Feedback Queue

• The multilevel feedback queue scheduling algorithm, in contrast, allows a process to move between queues.(multilevel queue 是不能交換的)

• Separate processes according to the characteristics of their CPU bursts. 
• If a process uses too much CPU time, it will be moved to a lower-priority queue. 
• Leaves I/O-bound and interactive processes in the higher-priority queues. 
• Process that waits too long in a lower-priority queue may be moved to a higher-priority queue. 
• This form of aging prevents starvation.
• Consider a multilevel feedback queue scheduler with three queues, numbered from 0 to 2 (queue 0 queue 1 queue 2) 
• The scheduler first executes all processes in queue 0. 
• Only when queue 0 is empty will it execute processes in queue 1. (So as queue 1 and queue 2)
• A process that arrives for queue 1 will preempt a process in queue 2. 
• A process in queue 1 will in turn be preempted by a process arriving for queue 0.
• A process entering the ready queue is put in queue 0. 
• A process in queue 0 is given a time quantum of 8 milliseconds. 
• If it does not finish within this time, it is moved to the tail of queue 1. 
• If queue 0 is empty, the process at the head of queue 1 is given a quantum of 16 milliseconds. 
• If it does not complete, it is preempted and is put into queue 2. Processes in queue 2 are run on an FCFS basis but are run only when queues 0 and 1 are empty.
• This scheduling algorithm gives highest priority to any process with a CPU burst of 8 milliseconds or less. Such a process will quickly get the CPU, finish its CPU burst, and go off to its next I/O burst. 
• Processes that need more than 8 but less than 24 milliseconds are also served quickly, although with lower priority than shorter processes. 
• Long processes automatically sink to queue 2 and are served in FCFS order with any CPU cycles left over from queues 0 and 1.

• In general, a multilevel feedback queue scheduler is defined by the following parameters:
• The number of queues
• The scheduling algorithm for each queue
• The method used to determine when to upgrade a process to a higher-priority queue
• The method used to determine when to demote a process to a lower-priority queue
• The method used to determine which queue a process will enter when that process needs service

• The definition of a multilevel feedback queue scheduler makes it the most general CPU-scheduling algorithm. And it is also the most complex algorithm, since defining the best scheduler requires some means by which to select values for all the parameters.

 

Thread Scheduling

• On operating systems that support them, it is kernel-level threads (not processes)that are being scheduled by the operating system. 

• User-level threads are managed by a thread library, and the kernel is unaware of them. 

• To run on a CPU, user-level threads must ultimately be mapped to an associated kernel-level thread, although this mapping may be indirect and may use a lightweight process (LWP).

Contention Scope

• One distinction between user-level and kernel-level threads lies in how they are scheduled. 
• On systems implementing the many-to-one and many-to-many models, the thread library schedules user-level threads to run on an available LWP
• Known as process-contention scope (PCS), since competition for the CPU takes place among threads belonging to the same process. 
• When we say the thread library schedules user threads onto available LWPs, we do not mean that the thread is actually running on a CPU; this would require the operating system to schedule the kernel thread onto a physical CPU. 
• To decide which kernel thread to schedule onto a CPU, the kernel uses system-contention scope (SCS). 
• Competition for the CPU with SCS scheduling takes place among all threads in the system. 
• Systems using the one-to-one model, such as Windows XP, Solaris, and Linux, schedule threads using only SCS.

 

Multiple-Processor Scheduling

• f multiple CPUs are available, load sharing becomes possible, the scheduling problem becomes more complex.

Approach to Multiple-Processor Scheduling

• One approach to CPU scheduling in a multiprocessor system has all scheduling decisions, I/O processing, and other system activities handled by a single processor-the master server. The other processors execute only user code.

• This asymmetric multiprocessing is simple because only one processor accesses the system data structures, reducing the need for data sharing.

• A second approach uses symmetric multiprocessing (SMP), where each processor is self-scheduling. 
• All processes may be in a common ready queue, or each processor may have its own private queue of ready processes. 
• Regardless, scheduling proceeds by having the scheduler for each processor examine the ready queue and select a process to execute.
• if we have multiple processors trying to access and update a common data structure, the scheduler must be programmed carefully. 
• We must ensure that two processors do not choose the same process and that processes are not lost from the queue. 
• Virtually all modern operating systems support SMP, including Windows XP, Windows 2000, Solaris, Linux, and Mac OS X.

Processor Affinity

• Consider what happens to cache memory when a process has been running on a specific processor. 
• The data most recently accessed by the process populate the cache for the processor; and as a result, successive memory accesses by the process are often satisfied in cache memory. 

• Consider what happens if the process migrates to another processor. 
• The contents of cache memory must be invalidated for the first processor, and the cache for the second processor must be repopulated. 
• Because of the high cost of invalidating and repopulating caches, most SMP systems try to avoid migration of processes from one processor to another and instead attempt to keep a process runnung on the same processor. 
• This is known as processor affinity
• a process has an affinity for the processor on which it is currently rumting.

• Processor affinity takes several forms. 
• soft affinity
• When an operating system has a policy of attempting to keep a process running on the same processor (but not guaranteeing that it will do so)
• hard affinity 
• allowing a process to specify that it is not to migrate to other processors.

• The main-memory architecture of a system can affect processor affinity issues. 

An architecture featuring non-uniform memory access (NUMA), in which a CPU has faster access to some parts of main memory than to other parts

• Typically, this occurs in systems containing combined CPU and memory boards. 
• The CPUs on a board can access the memory on that board with less delay than they can access memory on other boards in the system.

• If the operating system's CPU scheduler and memory-placement algorithms work together, then a process that is assigned affinity to a particular CPU can be allocated memory on the board where that CPU resides. 

• This example also shows that operating systems are frequently not as cleanly defined and implemented as described in operating-system textbooks. 
• Rather, the "solid lines" between sections of an operating system are frequently only "dotted lines," with algorithms creating connections in ways aimed at optimizing performance and reliability.

Multicore Processors

• Traditionally, SMP systems have allowed several threads to run concurrently by providing multiple physical processors. 

• Recent trend in computer hardware has been to place multiple processor cores on the same physical chip, resulting in a multicore porcessor.

• Each core has a register set to maintain its architectural state and appears to the operating system to be a separate physical processor. 

• SMP systems that use multicore processors are faster and consume less power than systems in which each processor has its own physical chip.

• Multicore processors may complicate scheduling issues.
• When a processor accesses memory, it spends a significant amount of time waiting for the data to become available. 
• This situation, known as a memory stall (記憶體停頓) may occur for various reasons, such as a cache miss (accessing data that is not in cache memory).
• In this scenario, the processor can spend up to 50 percent of its time waiting for data to become available from memory.

• To remedy this situation, many recent hardware designs have implemented multithreaded processor cores in which two (or more) hardware threads are assigned to each core. 
• If one thread stalls while waiting for memory, the core can switch to another thread.

• From an operating-system perspective, each hardware thread appears as a logical processor that is available to run a software thread. 

• Thus, on a dual-threaded, dual-core system, four logical processors are presented to the operating system.

• In general, there are two ways to multithread a processor: 
• coarse-grained multithreading
• thread executes on a processor until a long-latency event such as a memory stall occurs.
• Because of the delay caused by the long-latency event, the processor must switch to another thread to begin execution.
• Cost of switching between threads is high
• as the instruction pipeline must be flushed before the other thread can begin execution on the processor core
• Once this new thread begins execution, it begins filling the pipeline with its instructions.
• fine-grained multithreading (interleaved multithreading)
• Switches between threads at a much finer level of granularity (typically at the boundary of an instruction cycle). 
• Architectural design of fine-grained systems includes logic for thread switching. 
• As a result, the cost of switching between threads is small.

• Notice that a multithreaded multicore processor actually requires two different levels of scheduling. 
• Chooses which software thread to run on each hardware thread (logical processor). 
• For this level of scheduling, the operating system may choose any scheduling algorithm, such as those described in previous.
• How each core decides which hardware thread to run. 
• There are several strategies to adopt in this situation.

Reference:  
Operating System Concepts 8th, by Silberschatz, Galvin, Gagne
Wikipedia