Operating Systems: Processor Management - PDF

Department of Computer Science Operating Systems OPS611S 2025 - Semester 1 Event Specific Picture – Chapter 4 behind red graphic Processor Management  Outline  Overview  Scheduling sub-ma...

Department of Computer Science Operating Systems OPS611S 2025 - Semester 1 Event Specific Picture – Chapter 4 behind red graphic Processor Management  Outline  Overview  Scheduling sub-managers – Job Scheduler – Process Scheduler  Process States  Process Control Block  Process Scheduling Policies: – Two types: => Preemptive and non-preemptive scheduling  Process Scheduling Algorithms – First-Come First-Served – Shortest Job Next – Priority Scheduling – Shortest Remaining Time – Round Robin – Multiple-Level Queues – Earliest Deadline First  Interrupts  Overview  Program (job) – Inactive unit. E.g. File stored on a disk – A unit of work submitted by a user (not a process)  Process (task) – A program in execution – Active entity Requires resources to perform function. E.g. Processor, special registers, etc.  Process management - keeping track of processes and the states they are in.  Thread – Portion of a process – Runs independently  Processor (CPU) – Performs calculations and executes programs.  Overview  Multiprogramming environment – Multiple processes competing to be run by a single processor (CPU). – Requires fair and efficient CPU allocation for each job  Multitasking – One user running many programs – Still, resources must be shared by several programs  Interrupt – Call for help – Activates higher-priority program  Context Switch – Saving job processing information when interrupted  Overview  In this chapter, we will see how a Processor Manager manages a system with a single CPU (examining single-central processing unit CPU systems).  The same concepts are used in multi-CPU systems, with a higher-level scheduler that coordinates each CPU.  Systems with multiple processors and multi-core systems are not explored in this chapter.  Scheduling Sub-managers  Processor Manager: – Made up of two sub-managers  Job Scheduler: higher-level scheduler – Job scheduling responsibilities – Job initiation based on certain criteria  Process Scheduler: lower-level scheduler – Process scheduling responsibilities – Determines execution steps – Process scheduling based on certain criteria  Job Scheduling  Job Scheduler functions – Selects incoming job from queue – Places the job in process queue – Decides on job initiation criteria  Goal – Sequence jobs Efficient system resource utilization – Balance I/O interaction and computation – Keep most system components busy most of time  Process Scheduling  Process Scheduler functions: – Determines which job to get CPU resource(s) When and how long – Decides interrupt processing – Determines queues for process movement during execution – Recognizes process conclusion / termination  Process Scheduling (cont.)  Make use of common computer program traits – Programs alternate between two cycles CPU and I/O cycles Frequency and CPU cycle duration vary  General tendencies exists: – I/O-bound job Performs lots of I/O operations Many brief CPU cycles and long I/O cycles (printing documents) – CPU-bound job Performs lots of computation and do little O/I Many long CPU cycles and shorter I/O cycles (math calculation)  Process States  CPU / Processor Scheduling Determining which process in the ready state should be moved to the running state – Many processes may be in the ready state – Only one process can be in the running state, actually running at any one time  Process States (figure 4.2) A typical job (or process) changes status as it moves through the system from HOLD to FINISHED. © Cengage Learning 2014  Process Control Block (PCB)  The operating system must manage a large amount of data for each active process in the system.  Usually that data is stored in RAM in a data structure called a process control block (PCB)  The OS maintains one PCB for each process Process Control Block Attributes  Process ID (unique)  Processor status information (indicates the current state of the job. E.g. HOLD, READY, RUNNING, WAITING)  Processor state information (contains all information needed to indicate the current state of the job. E.g. Process Status Word, register contents, main memory info, process priority, resources)  Accounting (contains information used for billing purposes and performance measurement, as well as what kind of  Control Blocks and Queuing  Job PCB – Created when Job Scheduler accepts job – Updated as job executes – Queues use PCBs to track jobs – Contains all necessary job management processing data – PCBs linked to form queues (jobs not linked)  PCBs requires orderly management of queues – Determined by process scheduling policies and algorithms  Control Blocks and Queuing  Queues: – Queues use control blocks to track jobs the same way customs officials review passports to track international visitors. – These control blocks contain all of the data needed by the operating system to manage the processing of the job. – As the job move through the system, its progress is noted in the control block. In this way, the data in the PCB make it possible fro interrupted processes to be resumed after a delay.  PCB and Queuing Queues use PCBs to track jobs (figure 4.5) Queuing paths from HOLD to FINISHED. The Job and Processor schedulers release the resources when the job leaves the RUNNING state. © Cengage Learning 2014  CPU Context Switch  There is only one CPU and therefore only one set of CPU registers – These 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  Multiprogramming environment – More jobs than resources at any given time  Operating system pre-scheduling task – Resolve three system limitations: Finite number of resources (disk drives, printers, tape drives, memory, etc.) Some resources cannot be shared once allocated (printers) Some resources require operator intervention before reassigning (tape drives)  “Some” Definitions  CPU utilization – keep the CPU as busy as possible  Turnaround time – the amount of time when process arrives in the ready state the first time and 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 it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) Process Scheduling Policies (cont.)  Good process scheduling policy criteria: – Maximize throughput Run as many jobs as possible in given amount of time Minimize overhead (context switch time) as well as efficient use of resources (CPU, disk, memory, etc.) – Minimize response time Elapsed time to do an operation (job) Response time is what the user sees Time to echo keystroke in editor Time to compile a program Quickly turn around interactive requests – Minimize turnaround time amount of time to execute a particular process Move entire job in and out of system quickly Process Scheduling Policies (cont.)  Good process scheduling policy criteria (cont.): – Minimize waiting time amount of time a process has been waiting in the ready queue Move job out of READY queue quickly – Maximize CPU efficiency Keep CPU busy 100 % of time – Ensure fairness for all jobs Give every job equal CPU and I/O time  Final policy criteria decision lies with system designer or administrator’s hands! Process Scheduling Policies (cont.)  Problem – Job claims CPU for very long time before I/O request issued Builds up READY queue and empties I/O queues Creates unacceptable system imbalance  Corrective measure – Interrupt Used by Process Scheduler upon predetermined expiration of time slice Current job activity suspended Reschedules job into READY queue Process Scheduling Policies (cont.)  Two types of scheduling policies:  Non-preemptive scheduling The currently executing process gives up the CPU voluntarily – Once CPU has been allocated to a process, the process keeps the CPU until Process exits OR Process switches to waiting state  Preemptive scheduling The operating system decides to favor another process, preempting the currently executing process. (Interruption). – Transfers CPU to another job – Used in time-sharing environments  Process Scheduling Algorithms  Six algorithm types – First-come, first-served (FCFS) – Shortest job next (SJN) – Priority scheduling – Shortest remaining time (SRT) – Round robin – Multiple-level queues – Earliest deadline first (EDF)  Current / most systems emphasize interactive use and response time (use preemptive policies)  First Come First Served (FCFS)  Non-preemptive  Job handled based on arrival time – Earlier job arrives, earlier served  Simple algorithm implementation – Uses first-in, first-out (FIFO) queue  Good for batch systems  Unacceptable in interactive systems – Unpredictable turnaround time  Disadvantages – Average turnaround time varies seldom minimized First Come First Served (FIFO) What is the average turn- around time? (140+215+535+815+940)/5 = 529  Shortest Job Next (SJN)  Non-preemptive  Also known as shortest job first (SJF)  Job handled based on length of CPU cycle time  Easy implementation in batch environment – CPU time requirement known in advance  Does not work well in interactive systems  Optimal algorithm – All jobs are available at same time – CPU estimates available and accurate Shortest Job Next (SJN) What is the average turn-around time? (75+200+340+620+940)/5 = 435  Priority Scheduling  Non-preemptive  Preferential treatment for important jobs – Highest priority programs processed first – No interrupts until CPU cycles completed or natural wait occurs  READY queue may contain two or more jobs with equal priority – Uses FCFS policy within priority  System administrator or Processor Manager use different methods of assigning priorities  Priority Scheduling (cont.)  Processor Manager priority assignment methods: – Memory requirements Jobs requiring large amounts of memory Allocated lower priorities (vice versa) – Number and type of peripheral devices Jobs requiring many peripheral devices Allocated lower priorities (vice versa)  Priority Scheduling (cont.)  Processor Manager priority assignment methods (cont.) – Total CPU time Jobs having a long CPU cycle Given lower priorities (vice versa) – Amount of time already spent in the system (aging) Total time elapsed since job accepted for processing Increase priority if job in system unusually long time  Shortest Remaining Time (SRT)  Preemptive version of SJN  Processor allocated to job closest to completion – Preemptive if newer job has shorter completion time  Often used in batch environments – Short jobs given priority  Cannot implement in interactive system – Requires advance CPU time knowledge  Involves more overhead than SJN – System monitors CPU time for READY queue jobs – Performs context switching  Shortest Remaining Time (SRT) Arrival 0 1 2 3 Time Job A B C D CPU Cycle 6 3 1 4  Round Robin  Preemptive  Distributes the processing time equitably among all ready processes  The algorithm establishes a particular time slice (quantum), which is the amount of time each process receives before being preempted and returned to the ready state to allow another process its turn  Time quantum size: – Crucial to system performance – Varies from 100 ms to 1-2 seconds  CPU equally shared among all active processes – Not monopolized by one job  Used extensively in interactive systems  Round Robin (cont.) Suppose the time slice is 50 What is the average turn-around time? (515+325+940+920+640)/5 = 668  Round Robin (cont.) Suppose the time quantum is 4 Arrival Time 0 1 2 3 Job A B C D CPU Cycle 8 4 9 5 (figure 4.11) Timeline for job sequence A, B, C, D using the preemptive round robin algorithm with time slices of 4 ms. © Cengage Learning 2014  Round Robin (cont.)  Efficiency – Depends on time quantum size In relation to average CPU cycle  Quantum too large (larger than most CPU cycles) – Response time suffers – Algorithm reduces to FCFS scheme  Quantum too small – Throughput suffers – Context switching occurs Job execution slows down Overhead dramatically increased  Information saved in PCB  Round Robin (RR) (cont.)  Best quantum time size: – Depends on system Interactive: response time key factor Batch: turnaround time key factor – General rules of thumb Long enough for 80% of CPU cycles to complete At least 100 times longer than context switch time requirement  Process Scheduling Algorithms Are they preemptive or non-preemptive? Explain.  First-Come, First-Served?  Shortest Job Next?  Shortest Remaining Time?  Round Robin?  Multiple-Level Queues  A class of scheduling algorithms that categorise processes by some characteristic and can be used in conjunction with other policies. – Processes can be categorised by: memory size, process type, their response time, their externally assigned priorities, etc.  A multilevel queue-scheduling algorithm divides the ready queue into several separate queues to which processes are assigned. – Each queue is associated with one particular scheduling algorithm  Examples: – Interactive processes: Round Robin – Background processes: FCFS and SRT  Multiple-Level Queues  Not really a separate scheduling algorithm  Works in conjunction with several other schemes  It is found in systems with jobs that can be grouped according to common characteristics  Works well in systems with jobs grouped by common characteristic – Priority-based Different queues for each priority level – CPU-bound jobs in one queue and I/O-bound jobs in another queue – Hybrid environment Batch jobs in background queue Interactive jobs in foreground queue  Scheduling policy based on predetermined scheme  Multiple-Level Queues (cont.)  Four primary methods of moving jobs: – Case 1: No Movement Between Queues – Case 2: Movement Between Queues – Case 3: Variable Time Quantum Per Queue – Case 4: Aging Find out about these cases on your own...  Earliest Deadline First (EDF)  Dynamic priority algorithm  Preemptive  Addresses critical processing requirements of real-time systems: deadlines  Job priorities can be adjusted while moving through the system  Primary goal: – Process all jobs in order most likely to allow each to run to completion before reaching their Earliest Deadline First (EDF) (cont.)  Initial job priority: inversely proportional to its absolute deadline – Jobs with same deadlines: another scheme applied  Priority can change as more important jobs enter the system  Problems – Missed deadlines: total time required for all jobs greater than allocated time until final deadline – Impossible to predict job throughput: changing priority nature – High overhead: continual evaluation of deadlines  Interrupts  Interrupt Types – Page interrupt (memory manager) Accommodate job requests – Time quantum expiration interrupt – I/O interrupt Result from READ or WRITE command issuance – Internal interrupt Synchronous Result from arithmetic operation or job instruction – Illegal arithmetic operation interrupt Dividing by zero; bad floating-point operation  Interrupts  Interrupt Types (cont.): – Illegal job instruction interrupt Protected storage or non-existent access attempt Attempts to use an undefined operation code, operating on invalid data, etc.  Interrupt handler – Control program that handles the interruption event sequence. When the OS detects a non-recoverable error, the interrupt hander follows this 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. End