Single CPU Systems: Processes and Threads

Overview

• Processor management is examined within the context of single CPU systems.
• The concepts can be applied to multi-CPU systems, with a scheduler coordinating each CPU.
• Multiple processor and multi-core systems are not the focus.
• A program is an inactive unit, such as a file stored on a disk.
• A program is considered a job when submitted by a user.
• A process refers to a program in execution.
• A process is an active entity requiring resources.
• Process Management keeps track of processes and their states.
• A thread is a portion of a process that runs independently.
• The Processor or CPU performs calculations and executes programs.
• In a multiprogramming environment, multiple processes compete for a single CPU.
• This requires fair and efficient CPU allocation for each job.
• Multitasking involves one user running many programs.
• Multitasking requires resources to be shared.
• An interrupt is a call for help which activates a higher-priority program.
• Context switching saves job processing information for interrupted processes.

Scheduling Sub-managers

• The Processor Manager consists of two sub-managers: the Job Scheduler and the Process Scheduler.
• The Job Scheduler is a high-level scheduler responsible for job scheduling and initiation.
• The Process Scheduler is a lower-level scheduler with process scheduling responsibilities, determining execution steps.
• Job Scheduler’s functions include selecting incoming jobs, placing them in the process queue, and deciding on initiation criteria.
• The goal of job scheduling is to sequence jobs, balance I/O interaction and computation, and keep most system components busy.
• Process Scheduler functions involve determining which job gets CPU resources, deciding interrupt processing, and managing process movement during execution.
• The Process Scheduler recognizes process conclusion or termination

Process Scheduling

• Programs alternate between CPU and I/O cycles, varying in frequency and duration.
• There are general program tendencies: I/O-bound jobs and CPU-bound jobs.
• I/O-bound jobs perform many I/O operations with brief CPU cycles and long I/O cycles
• CPU-bound jobs perform lots of computation with long CPU cycles and shorter I/O cycles.

Process States

• CPU/Processor Scheduling determines which process in the ready state moves to the running state.
• States include Waiting, Ready, Running, New and Terminated
• Many processes can be in the ready state.
• Only one process can be in the running state at any time.
• A typical job changes status as it moves through the system via Hold State, Ready State, Running State, Waiting State and Finished.

Process Control Block (PCB)

• The operating system manages a large amount of data for each active process.
• Data is stored in RAM within a data structure called a Process Control Block (PCB).
• The OS maintains one PCB for each process.

Process Control Block Attributes

• The PCB includes Process ID (unique), Processor status information, Processor state information, and Accounting.
• Processor status includes the current state of the job (HOLD, READY, RUNNING, WAITING).
• Processor state information indicates the current state of the job, e.g. Process Status Word, register contents, main memory information, process priority, resources.
• Accounting provides billing and performance data and information about what resources the job used.
• Job PCBs are created and updated by the Job Scheduler.
• Queues use PCBs to track jobs, containing all necessary job management processing data
• PCBs are linked to form queues.
• PCBs require orderly management of queues that is determined by process scheduling policies and algorithms.
• Queues use control blocks to track jobs like customs officials review passports for international visitors.
• Control blocks contain data needed by the OS to manage job processing.
• Progress is noted in the control block so interrupted processes can be resumed.

CPU Context Switch

• There is only one CPU and therefore only one set of CPU registers.
• The registers contain the values for the currently executing process.
• Each time a process is moved to the running state:
  • Register values for the currently running process are stored into its PCB.
  • Register values of the new running state are loaded into the CPU.
  • This exchange of information is called a context switch.

Process Scheduling Policies

• A multiprogramming environment means more jobs than resources at any given time.
• The operating system must resolve three system limitations: finite resources, non-shareable resources (printers), and resources requiring operator intervention (tape drives).

Important Definitions

• CPU Utilization: keep the CPU as busy as possible.
• Turnaround time: amount of time from when a process arrives in the ready state for the first time to when it exits the running state for the last time.
• Throughput: the number of processes that complete their execution per time unit.
• Waiting time: amount of time a process has been waiting in the ready queue.
• Response time: amount of time from when a request was submitted until the first response is produced.

Good Process Scheduling Policy Criteria

• Maximize throughput by running as many jobs as possible per unit time
• Minimize overhead and use resources efficiently.
• Minimize response time by reducing elapsed time for operations and improving user experience.
• Minimize turnaround time to quickly execute processes and move jobs through the system.
• Minimize waiting time by moving jobs out of the READY queue quickly.
• Maximize CPU efficiency to keep the CPU busy.
• Ensure fairness by giving every job equal CPU and I/O time.
• The final policy decision lies with the system designer or administrator.
• A problem arises when a job claims CPU for a long time before issuing an I/O request.
  • The READY queue builds up and I/O queues are emptied, creating an imbalance.
• A corrective measure is to use interrupts to suspend job activity and reschedule the job into READY queue.
• Two types of scheduling policies: Preemptive and Non-preemptive

Scheduling Policies: Non-Preemptive

• Scheduling where the currently executing process gives up the CPU voluntarily.
• Once allocated, the process keeps the CPU until it exits or switches to the waiting state.

Scheduling Policies: Preemptive

• Scheduling where the OS chooses to favor another process, preempting the current one
• It transfers CPU to another job and is used in time-sharing environments.

Process Scheduling Algorithms

• The six algorithm types: First-come, first-served (FCFS), Shortest job next (SJN), Priority scheduling, Shortest remaining time (SRT), Round robin, Multiple-level queues and Earliest deadline first (EDF).
• Current systems emphasize interactive use and response time using preemptive policies.

First Come First Served (FCFS)

• Non-preemptive
• Jobs are handled based on arrival time.
• Simplicity is ensured through first-in, first-out (FIFO) queue implementation.
• It is suited for batch systems but unacceptable in interactive systems due to unpredictable turnaround time.
• Average turnaround time varies.

Shortest Job Next (SJN)

• Non-preemptive
• Jobs are handled based on length of CPU cycle time.
• Easy implementation for batch environment since CPU time requirements are known.
• It doesn't work for interactive systems.
• It ensures all jobs are available at the same time and that CPU estimates are available and accurate.

Priority Scheduling

• Non-preemptive
• It can ensure preferential treatment for important jobs and highest priority programs are processed first.
• Jobs run without interrupts until CPU cycles are completed or a natural wait occurs.
• If READY queues contain jobs of equal priority, FCFS policy is used within that priority.
• System administrators or Processor Managers use different methods of assigning priorities, e.g., memory requirements, device number and CPU time.

Shortest Remaining Time (SRT)

• Preemptive version of SJN.
• Processor allocated to job closest to completion.
• It is best suited for batch environments to give shorter jobs priority.
• Requires advance CPU time knowledge and cannot be implemented in interactive systems.
• More overhead than SJN because the system monitors CPU time and performs context switching.

Round Robin

• A preemptive algorithm.
• Distributes processing time equitably among all ready processes.
• Establishes a particular time slice (quantum) for each process.
• The time quantum size is crucial.
• The CPU is equally shared among all active processes and not monopolized by one job.
• It is used in interactive systems.
• Time quantum size:
  • Crucial to system performance
  • Varies from 100 ms to 1-2 seconds

Considerations for the Round Robin algorithm

• Efficiency depends on time quantum size in relation to the average CPU cycle.
• If the quantum is too large response time suffers, and it reduces to FCFS.
• If Quantum is too small throughput suffers, context switching occurs as well as job execution slows down.
• Overhead will be dramatically increased and information has to be saved in the PCB
• The best quantum time size depends on the system.
  • Interactive systems focus on response time
  • Batch systems focus on turnaround time.
• General rules of thumb for the Round Robin algorithms
  • Be long enough for 80% of CPU cycles to complete
  • At least 100 times longer than context switch time requirement

Process Scheduling Algorithms: Preemptive vs Non-Preemptive

• First-Come, First-Served: Non-preemptive
• Shortest Job Next: Non-preemptive
• Shortest Remaining Time: Preemptive
• Round Robin: Preemptive

Multiple-Level Queues

• Characterizes process-categorizing scheduling algorithms that can be used in conjunction with other policies.
• Processes can be categorized by memory size, process type, response time, externally assigned priorities, etc.
• Divides the ready queue into separate queues to which processes are assigned so that each queue is associated with one particular scheduling algorithm
• Interactive processes can use Round Robin, while background processes use FCFS and SRT.

Characteristics of Multiple-Level Queues

• It is not really a separate scheduling algorithm and can work in conjunction with other schemes and systems.
• Systems can group jobs according to common characteristics such as priority or whether or not the jobs are CPU bound or IO Bound.
  • Priority-based algorithms are categorized with different queues for each priority level
  • CPU-bound jobs in one queue and I/O-bound jobs in another queue.
  • Hybrid environments categorize Batch jobs in background queue and Interactive jobs in foreground queue.
• Generally a scheduling policy is based on a predetermined scheme.

Four primary methods of moving jobs in Multiple-Level Queues

• Case 1: No Movement Between Queues
• Case 2: Movement Between Queues
• Case 3: Variable Time Quantum Per Queue
• Case 4: Aging

Earliest Deadline First (EDF)

• It is a dynamic priority and preemptive algorithm.
• Addresses critical processing requirements of real-time systems: deadlines.
• Job priorities are adjusted while moving through the system to process jobs in order most likely to allow each to run to completion before reaching their respective deadlines.
• Initial job priority is inversely proportional to its absolute deadline.
• Another scheme applied if jobs have the same deadline.
• Priority may change as more important jobs enter the system.
• Problems include missed deadlines, impossible throughput prediction, and high overhead.

Types of Interrupts

• Page interrupt (memory manager): accommodate job requests.
• Time quantum expiration interrupt
• I/O interrupt: result from READ or WRITE command issuance.
• Internal interrupt: triggered by result from arithmetic operation or job instruction.
• Illegal arithmetic operation interrupt: dividing by zero; bad floating-point operation
• Illegal job instruction interrupt: protected storage or non-existent access attempt, attempts to use an undefined operation code/ invalid data.

Interrupt Handlers

• Control programs that handle the interruption event sequence.
• When the OS detects a non-recoverable error, the interrupt handler follows its sequence.
  • Type of interrupt is described and stored to be passed on to the user as an error message.
  • State of the interrupt process is saved.
  • The interrupt is processed.
  • Processor resumes normal operation.