Processor Management Principles and Scheduling Algorithms
Fundamentals of Processor Management and Multiprogramming
Processor management is a core function of the operating system that deals with the allocation of the central processing unit (CPU) among multiple competing tasks. In a simple system characterized by a single user and one processor, the CPU remains busy only when executing that specific user's job or necessary system software. However, in a multiprogramming environment, multiple processes compete to be executed by a single CPU, necessitating a fair and efficient allocation strategy. This chapter focuses specifically on single processor systems and the mechanisms used to ensure system resources are utilized effectively.
Several key definitions are essential to understanding processor management. The processor, or CPU, is the hardware component that performs calculations and executes programs. A program, also referred to as a job, is an inactive unit, such as a file stored on a disk, representing the unit of work submitted by a user. Once a program is initiated, it becomes a process, or task, which is an active entity. A process requires specific resources, including the processor and special registers, to perform its function; it is essentially a single instance of an executable program. A thread is a smaller portion of a process that can run independently. Multithreading allows an application, such as a web browser, to manage a single process using several threads of control. Multiprogramming involves the delicate task of allocating and deallocating the processor to each job or process for specific time periods.
Additional concepts include the interrupt, which serves as a call for help that activates a higher-priority program to address a specific event. A context switch occurs when the system saves the current job processing information when an interrupt happens, allowing it to resume later. Jobs that are completed are considered finished or terminated. Because a single processor may be shared by several jobs, the system must utilize a scheduling policy and a scheduling algorithm to manage access to the CPU. While this chapter focuses on single processors, multi-core technologies like dual-core and quad-core CPUs involve multiple processors located on a single chip. Multi-core engineering helps resolve leakage and heat problems while allowing multiple calculations to occur simultaneously.
The Hierarchy of Scheduling Submanagers
The Processor Manager is a composite of two primary hierarchical submanagers: the Job Scheduler and the Process Scheduler. The Job Scheduler acts as the higher-level scheduler. Its responsibilities include selecting incoming jobs from a queue and placing them into the process queue based on specific initiation criteria. The primary goal of the Job Scheduler is to sequence jobs to ensure efficient system resource utilization. This involves balancing I/O interaction with computation to keep most system components busy the majority of the time.
The Process Scheduler serves as the lower-level scheduler in the hierarchy. It determines which specific job from the READY queue will receive the CPU resource, when it will receive it, and for how long. It is responsible for deciding interrupt processing, determining the queues for job movement during execution, and recognizing when a job has reached its conclusion for termination. The Process Scheduler exploits the fact that computer programs typically alternate between two cycles: CPU cycles and I/O cycles. The frequency and duration of these cycles vary. An I/O-bound job is characterized by many brief CPU cycles followed by long I/O cycles, such as printing documents. Conversely, a CPU-bound job involves many long CPU cycles and shorter I/O cycles, such as complex mathematical calculations. Data shows that a greater number of jobs typically request short CPU cycles, while fewer jobs request long cycles.
In highly interactive environments, a third layer known as the middle-level scheduler may be present to handle system overloading. This scheduler can remove active jobs from memory to reduce the degree of multiprogramming, which can actually result in faster overall job completion. In a single-user environment, there is no practical distinction between job and process scheduling because only one job is active at a time and receives dedicated resources for its duration.
Job, Process, and Thread Status Transitions
As a job or process moves through the system, it undergoes several status changes. These states include HOLD, READY, WAITING, RUNNING, and FINISHED. When a user submits a job, it is accepted and placed on HOLD in a queue. It transitions from HOLD to READY once it is ready to wait for the CPU. The Process Scheduler moves a job from READY to RUNNING when it is selected for processing. If a job requires a resource that is currently unavailable, it moves from RUNNING to WAITING and then eventually back to READY. Once a job is completed successfully or unsuccessfully, it transitions to the FINISHED state.
The Job Scheduler is responsible for the transition from HOLD to READY using a predefined policy. The Process Scheduler handles the transition from READY to RUNNING using a scheduling algorithm. It also manages the transition from RUNNING back to READY based on time limits or other criteria, and from RUNNING to WAITING when a job instruction requires it. The transition from WAITING to READY is triggered by a signal from the I/O device manager indicating a request has been satisfied. Finally, either scheduler may handle the transition to FINISHED upon job completion.
Threads follow a similar but distinct set of five states: READY, RUNNING, WAITING, DELAYED, and BLOCKED. When an application creates a thread, it is placed in the READY queue. The Process Scheduler assigns it to a processor to move it to RUNNING. A thread moves to WAITING if it depends on an outside event like a mouse click or another thread. It moves to DELAYED if the application specifies a set amount of time to wait. If an I/O request is issued, it moves to BLOCKED until the I/O is completed. Upon an exit or termination signal, the thread moves to FINISHED, and all its resources are released. The operating system must be able to create, delay, block, synchronize (using semaphores, events, or conditional variables), and terminate threads.
Control Blocks and Queuing Management
The operating system tracks processes and threads using specialized data structures. Each process has a Process Control Block (PCB), and each thread has a Thread Control Block (TCB). The TCB contains thread identification, thread state, CPU information (including the program counter and register contents), thread priority, a pointer to the parent process, and pointers to sibling threads. The PCB contains process identification, process status, process state (including the process status word and register contents), main memory information, resources, process priority, and accounting data.
The PCB is created when the Job Scheduler accepts a job and is updated throughout its execution. Queues use these PCBs to track jobs; the PCBs are linked to form queues, while the actual jobs are not linked. Efficient management of these queues is determined by the specific process scheduling policies and algorithms implemented by the system. The Job and Processor Schedulers are responsible for releasing resources when a job departs the RUNNING state.
Scheduling Policies and Evaluation Criteria
In a multiprogramming environment, there are typically more jobs than available resources. The operating system must manage finite resources, non-shareable resources (like printers), and resources requiring operator intervention. To manage this, designers use scheduling policies. A good policy should maximize throughput by running as many jobs as possible in a given time, minimize response time for interactive requests, minimize turnaround time (the time for a job to move entirely through the system), and minimize waiting time in the READY queue. Additionally, it should maximize CPU efficiency toward a goal of , while ensuring fairness for all jobs by providing equal CPU and I/O time.
A problem arises when a job claims the CPU for a long duration, building up the READY queue and emptying I/O queues. This is corrected by an interrupt used by the Process Scheduler when a time slice expires, suspending the job and rescheduling it into the READY queue. Scheduling policies are categorized as either preemptive or nonpreemptive. Preemptive policies, used in time-sharing environments, can interrupt job processing to transfer the CPU to another job. Nonpreemptive policies function without external interrupts, though infinite loops are interrupted in both cases.
Process Scheduling Algorithms
Several algorithms are used to implement scheduling policies. The First-Come, First-Served (FCFS) algorithm is nonpreemptive and handles jobs based on their arrival time using a First-In, First-Out (FIFO) queue. While easy to implement, it is unacceptable for interactive systems due to unpredictable turnaround times. For example, one sequence might result in an average turnaround time of while another results in . The Shortest Job Next (SJN) algorithm is also nonpreemptive and handles jobs based on the shortest CPU cycle time. It is optimal when all jobs are available at the same time and CPU estimates are accurate, but it can lead to indefinite postponement of longer jobs.
Priority Scheduling is a nonpreemptive scheme that gives preferential treatment to important jobs. Priorities are assigned based on memory requirements, the number of peripheral devices, total CPU time, or aging (increasing priority based on the total time a job has spent in the system). The Shortest Remaining Time (SRT) algorithm is the preemptive version of SJN. It allocates the processor to the job closest to completion. This involves more overhead than SJN because the system must monitor CPU time and perform context switching.
Round Robin is a preemptive algorithm used extensively in interactive systems. It is based on a predetermined time slice, or time quantum, which usually ranges from to . The CPU is shared equally; if a job's CPU cycle exceeds the quantum, it is preempted, information is saved in the PCB, and it is placed at the end of the READY queue. If the cycle is shorter than the quantum, the job finishes and resources are released. Efficiency depends on the quantum size; too large a quantum reduces the system to FCFS, while too small a quantum increases context switching overhead. A general rule is that the quantum should be long enough for of CPU cycles to finish and at least longer than the time required for a context switch.
Multiple-Level Queues work with other schemes and group jobs by characteristics like priority or cycle type (CPU-bound vs. I/O-bound). There are four primary cases for moving jobs: Case 1 involves no movement between queues, rewarding high-priority jobs. Case 2 allows movement, where a quantum interrupt moves a job to a lower-priority queue. Case 3 uses a variable time quantum per queue, often doubling the size for lower queues to help CPU-bound jobs finish. Case 4 utilizes aging to move "old" jobs to higher queues to prevent indefinite postponement. Finally, Earliest Deadline First (EDF) is a preemptive dynamic priority algorithm often used in real-time systems. It adjusts priorities so jobs with the closest absolute deadlines are processed first. However, it suffers from high overhead and unpredictable throughput.
Interrupt Management
The Processor Manager must handle various types of interrupts. These include page interrupts from the memory manager, time quantum expiration interrupts, and I/O interrupts resulting from READ or WRITE commands. Internal interrupts, or synchronous interrupts, result from internal job instructions. Illegal arithmetic operation interrupts occur during division by zero or floating-point overflows and underflows. Illegal job instruction interrupts happen when a process attempts to access protected storage or operates on invalid data.
The interrupt handler is a control program that manages the sequence of events during an interruption. When a nonrecoverable error is detected, the handler describes and stores the interrupt type, saves the state of the interrupted process, processes the interrupt, and then allows the processor to resume normal operations. Ultimately, the system designer selects the best policy and algorithm after evaluating the specific strengths and weaknesses relative to the system's intended application.