Thread States - University of North Florida

Thread States - University of North Florida

Understanding Operating Systems Seventh Edition Chapter 4 Processor Management Learning Objectives After completing this chapter, you should be able to describe: The relationship between job scheduling and process scheduling The advantages and disadvantages of several process scheduling algorithms The goals of process scheduling policies using a single-core CPU

Understanding Operating Systems, 7e 2 Learning Objectives (contd.) The similarities and differences between processes and threads The role of internal interrupts and of the interrupt handler Understanding Operating Systems, 7e 3 Overview Simple system

Single user One processor: busy only when executing the users job or system software Multiprogramming environment: multiple processes competing to be run by a single CPU Requires fair and efficient CPU allocation for each job Single processor systems Addressed in this chapter Understanding Operating Systems, 7e 4 Definitions

Processor (CPU) Performs calculations and executes programs Program (job) Inactive unit, e.g., file stored on a disk Unit of work submitted by the user Process (task) Active entity Requires resources (processor, special registers, etc.) to perform function Executable program single instance Understanding Operating Systems, 7e

5 Definitions (contd.) Thread Portion of a process Runs independently Multithreading Allows applications to manage a separate process with several threads of control Example: Web browsers Multiprogramming Processor allocated to each job or each process for a time period Deallocated at appropriate moment: delicate task

Understanding Operating Systems, 7e 6 Definitions (contd.) Interrupt Call for help Activates higher-priority program Context switch Saving job processing information when interrupted Completed jobs Finished or terminated Single processor

May be shared by several jobs (processes) Requires scheduling policy and scheduling algorithm Understanding Operating Systems, 7e 7 About Multi-Core Technologies Dual-core, quad-core, or other multi-core CPU More than one processor (core): located on computer chip Single chip may contain multiple cores Multi-core engineering Resolves leakage and heat problems Multiple calculations may occur simultaneously

More complex Processor Manager handling: discussed in Chapter 6 Understanding Operating Systems, 7e 8 Scheduling Submanagers Processor Manager: composite of two submanagers Job Scheduler and Process Scheduler: hierarchical scheduling system 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 Understanding Operating Systems, 7e 9 Scheduling Submanagers (cont'd.) Job Scheduler functions Selects incoming job from queue Places in process queue Decides on job initiation criteria Process scheduling algorithm and priority Goal

Sequence jobs Efficient system resource utilization Balance I/O interaction and computation Keep most system components busy most of time Understanding Operating Systems, 7e 10 Process Scheduler Process Scheduler functions Determines job to get CPU resource When and how long Decides interrupt processing Determines queues for job movement during

execution Recognizes job conclusion Determines job termination Lower-level scheduler in the hierarchy Assigns CPU to execute individual actions: jobs placed on READY queue by the Job Scheduler Understanding Operating Systems, 7e 11 Process Scheduler (cont'd.) Exploits common computer program traits Programs alternate between two cycles CPU and I/O cycles Frequency and CPU cycle duration vary

General tendencies I/O-bound job Many brief CPU cycles and long I/O cycles (printing documents) CPU-bound job Many long CPU cycles and shorter I/O cycles (math calculation) Understanding Operating Systems, 7e 12 Process Scheduler (cont'd.) (figure 4.1) Distribution of CPU cycle

times. This distribution shows a greater number of jobs requesting short CPU cycles (the frequency peaks close to the low end of the CPU cycle axis), and fewer jobs requesting long CPU cycles. Cengage Learning 2014 Understanding Operating Systems, 7e 13 Process Scheduler (cont'd.) Middle-level scheduler: third layer Found in highly interactive environments

Handles overloading Removes active jobs from memory Reduces degree of multiprogramming Results in faster job completion Single-user environment No distinction between job and process scheduling One job active at a time Receives dedicated system resources for job duration Understanding Operating Systems, 7e 14 Job and Process States Status changes: as a job or process moves through

the system HOLD READY WAITING RUNNING FINISHED Referred to as job status or process status, respectively

Understanding Operating Systems, 7e 15 Job and Process States (cont'd.) (figure 4.2) A typical job (or process) changes status as it moves through the system from HOLD to FINISHED. Cengage Learning 2014 Understanding Operating Systems, 7e 16 Job and Process States (cont'd.)

User submits job Job accepted Put on HOLD and placed in queue Job state changes from HOLD to READY Indicates job waiting for CPU Job state changes from READY to RUNNING When selected for CPU and processing Job state changes from RUNNING to WAITING Requires unavailable resources: moves back to READY status Job state changes to FINISHED Job completed (successfully or unsuccessfully)

Understanding Operating Systems, 7e 17 Job and Process States (cont'd.) Job Scheduler or Process Scheduler incurs state transition responsibility HOLD to READY Job Scheduler initiates using predefined policy READY to RUNNING Process Scheduler initiates using predefined algorithm RUNNING back to READY Process Scheduler initiates according to predefined time limit or other criterion

RUNNING to WAITING Process Scheduler initiates by instruction in job Understanding Operating Systems, 7e 18 Job and Process Status (cont'd.) Job Scheduler or Process Scheduler incurs state transition responsibility (cont'd.) WAITING to READY Process Scheduler initiates by signal from I/O device manager Signal indicates I/O request satisfied; job continues

RUNNING to FINISHED Process Scheduler or Job Scheduler initiates upon job completion Satisfactorily or with error Understanding Operating Systems, 7e 19 Thread States Five states as a thread moves through the system

READY RUNNING WAITING DELAYED BLOCKED Thread transitions Application creates a thread: placed in READY queue READY to RUNNING: Process Scheduler assigns it to a processor Understanding Operating Systems, 7e 20

(figure 4.3) A typical thread changes states from READY to FINISHED as it moves through the system. Cengage Learning 2014 Understanding Operating Systems, 7e 21 Thread States (contd.) Thread transitions Application creates a thread: placed in READY queue READY to RUNNING: Process Scheduler assigns it to a processor RUNNING to WAITING: when dependent on an

outside event, e.g., mouse click, or waiting for another thread to finish WAITING to READY: outside event occurs or previous thread finishes Understanding Operating Systems, 7e 22 Thread States (contd.) Thread transitions (contd.) RUNNING to DELAYED: application that delays thread processing by specified amount of time DELAYED to READY: prescribed time elapsed RUNNING to BLOCKED: I/O request issued BLOCKED to RUNNING: I/O completed

RUNNING to FINISHED: exit or termination All resources released Understanding Operating Systems, 7e 23 Thread States (contd.) Operating systems must be able to: Create new threads Set up a thread so it is ready to execute Delay, or put to sleep, threads for a specified amount of time Block, or suspend, threads waiting for I/O to be completed Set threads to a WAIT state until a specific event

occurs Schedule threads for execution Understanding Operating Systems, 7e 24 Thread States (contd.) Operating systems must be able to: Synchronize thread execution using semaphores, events, or conditional variables Terminate a thread and release its resources Understanding Operating Systems, 7e 25

Control Blocks Process Control Block (PCB): data structure for each process in the system Thread Control Block (TCB): data structure for each thread Understanding Operating Systems, 7e 26 (figure 4.4) Comparison of a typical Thread Control Block (TCB) vs. a Process Control Block (PCB). Cengage Learning 2014 Understanding Operating Systems, 7e

27 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 or TCBs: requires orderly management of queues Determined by process scheduling policies and algorithms Understanding Operating Systems, 7e 28 Control Blocks and Queuing (cont'd.) (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 Understanding Operating Systems, 7e

29 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) Some resources cannot be shared once allocated (printers) Some resources require operator intervention before reassigning

Understanding Operating Systems, 7e 30 Scheduling Policies (cont'd.) Good process scheduling policy criteria Maximize throughput Run as many jobs as possible in given amount of time Minimize response time Quickly turn around interactive requests Minimize turnaround time Move entire job in and out of system quickly Minimize waiting time

Move job out of READY queue quickly Understanding Operating Systems, 7e 31 Scheduling Policies (cont'd.) Good process scheduling policy criteria (cont'd.) Maximize CPU efficiency Keep CPU busy 100 percent 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

Understanding Operating Systems, 7e 32 Scheduling Policies (cont'd.) 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 Understanding Operating Systems, 7e 33 Scheduling Policies (cont'd.) Types of scheduling policies Preemptive Used in time-sharing environments Interrupts job processing Transfers CPU to another job Nonpreemptive Functions without external interrupts

Infinite loops interrupted in both cases Understanding Operating Systems, 7e 34 Scheduling Algorithms Based on specific policy Allocates CPU and moves job through the system Most systems emphasize fast user response time Several algorithms

First-come, first-served (FCFS) Shortest job next (SJN) Priority scheduling Shortest remaining time (SRT) Round robin Multiple-level queues Earliest deadline first (EDF) Understanding Operating Systems, 7e 35

First-Come, First-Served Nonpreemptive 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 Understanding Operating Systems, 7e

36 (figure 4.6) Timeline for job sequence A, B, C using the FCFS algorithm. Cengage Learning 2014 Note: Average turnaround time: 16.67 (figure 4.7) Timeline for job sequence C, B, A using the FCFS algorithm. Cengage Learning 2014 Note: Average turnaround time: 7.3 Understanding Operating Systems, 7e

37 Shortest Job Next Nonpreemptive 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 Understanding Operating Systems, 7e 38 Shortest Job Next (cont'd.) (figure 4.8) Timeline for job sequence B, D, A, C using the SJN algorithm. Cengage Learning 2014 Understanding Operating Systems, 7e 39

Priority Scheduling Nonpreemptive Preferential treatment for important jobs Highest priority programs processed first No interrupts until CPU cycles completed or natural wait occurs Process Scheduler: manages multiple READY queues System administrator or Processor Manager use different methods of assigning priorities Understanding Operating Systems, 7e 40

Priority Scheduling (cont'd.) 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) Understanding Operating Systems, 7e 41 Priority Scheduling (cont'd.) Processor Manager priority assignment methods

(cont'd.) 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 Understanding Operating Systems, 7e 42 Shortest Remaining Time 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 Understanding Operating Systems, 7e 43 (figure 4.9)

Timeline for job sequence A, B, C, D using the preemptive SRT algorithm. Each job is interrupted after one CPU cycle if another job is waiting with less CPU time remaining. Cengage Learning 2014 Understanding Operating Systems, 7e 44 Round Robin

Preemptive Used extensively in interactive systems Based on predetermined time slice (time quantum) Each job assigned time quantum 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 Understanding Operating Systems, 7e 45 Round Robin (cont'd.) Job placed on READY queue (FCFS scheme)

Process Scheduler selects first job Sets timer to time quantum Allocates CPU Timer expires If job CPU cycle > time quantum Job preempted and placed at end of READY queue Information saved in PCB Understanding Operating Systems, 7e 46 Round Robin (cont'd.) If job CPU cycle < time quantum Job finished: allocated resources released and job

returned to user Interrupted by I/O request: information saved in PCB and linked to I/O queue Once I/O request satisfied Job returns to end of READY queue and awaits CPU Understanding Operating Systems, 7e 47 Round Robin (cont'd.) (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 Understanding Operating Systems, 7e 48 Round Robin (cont'd.) Efficiency Depends on time quantum size In relation to average CPU cycle Quantum too large (larger than most CPU cycles) Algorithm reduces to FCFS scheme Quantum too small Context switching occurs

Job execution slows down Overhead dramatically increased Understanding Operating Systems, 7e 49 Round Robin (cont'd.) (figure 4.12) Context switches for three different time quantums. In (a), Job A (which requires only 8 cycles to run to completion) finishes before the time quantum of 10 expires. In (b) and (c), the time quantum expires first, interrupting the jobs. Cengage Learning 2014 Understanding Operating Systems, 7e

50 Round Robin (cont'd.) Best quantum time size Depends on system Interactive: response time key factor Archival system: 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 Understanding Operating Systems, 7e

51 Multiple-Level Queues Works in conjunction with several other schemes 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

Four primary methods of moving jobs Understanding Operating Systems, 7e 52 Case 1: No Movement Between Queues Simple Rewards high-priority jobs Processor allocated using FCFS Processor allocated to lower-priority jobs Only when high-priority queues empty Good environment Few high-priority jobs Spend more time with low-priority jobs

Understanding Operating Systems, 7e 53 Case 2: Movement Between Queues Processor adjusts priorities assigned to each job High-priority jobs Initial priority favorable Treated like all other jobs afterwards Quantum interrupt Job preempted Moved to next lower queue May have priority increased

Good environment Jobs handled by cycle characteristics (CPU or I/O) Interactive systems Understanding Operating Systems, 7e 54 Case 3: Variable Time Quantum Per Queue Case 2 variation: movement between queues Each queue given time quantum size Size twice as long as previous queue Fast turnaround for CPU-bound jobs CPU-bound jobs execute longer and given longer time periods Improves chance of finishing faster

Understanding Operating Systems, 7e 55 Case 4: Aging Ensures lower-level queue jobs eventually complete execution System keeps track of job wait time If too old: System moves job to next highest queue Continues until old job reaches top queue May drastically move old job to highest queue Advantage Guards against indefinite postponement

Major problem: discussed further in Chapter 5 Understanding Operating Systems, 7e 56 Earliest Deadline First 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 respective deadlines

Understanding Operating Systems, 7e 57 Earliest Deadline First (contd.) 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 Understanding Operating Systems, 7e 58 Managing 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 interrupt) Result from arithmetic operation or job instruction

Illegal arithmetic operation interrupt Dividing by zero; bad floating-point operation, fixedpoint operations resulting in overflow or underflow Understanding Operating Systems, 7e 59 Managing Interrupts (cont'd.) Interrupt types (cont'd.) Illegal job instruction interrupt Attempting protected storage access, operating on invalid data, etc. Interrupt handler Control program Handles interruption event sequence

Understanding Operating Systems, 7e 60 Managing Interrupts (cont'd.) Nonrecoverable error detected by operating system Interrupt handler sequence 1. 2. 3. 4. Interrupt type described and stored Interrupted process state saved Interrupt processed

Processor resumes normal operation Understanding Operating Systems, 7e 61 Conclusion Processor Manager allocates CPU among all users Job scheduling Based on characteristics Process and thread scheduling Instant-by-instant allocation of CPU Interrupt handler: generates and resolves interrupts Each scheduling algorithm is unique

Characteristics, objectives, and applications System designer selects best policy and algorithm After careful strengths and weaknesses evaluation Understanding Operating Systems, 7e 62 (table 4.3) Comparison of the scheduling algorithms discussed in this chapter. Cengage Learning 2014 Understanding Operating Systems, 7e 63

(table 4.3) (contd.) Comparison of the scheduling algorithms discussed in this chapter. Cengage Learning 2014 Understanding Operating Systems, 7e 64

Recently Viewed Presentations

  • 3rd Edition: Chapter 3 - University of Central Arkansas

    3rd Edition: Chapter 3 - University of Central Arkansas

    TransportLayer. 3-Principles of Reliable data transfer. important in app., transport, link layers. top-10 list of important networking topics! characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)
  • Mechanics of Materials Engr 350 - Q and rectangular/circular ...

    Mechanics of Materials Engr 350 - Q and rectangular/circular ...

    The maximum transverse shear occurs at the middle of the beam (y=0). Substituting y=0 into the shear stress formula for rectangular beams yields. A fine point regarding the shear stress: Remember our derivation of shear on perpendicular faces of an...
  • Chapter 10 Business Research and Report Writing

    Chapter 10 Business Research and Report Writing

    Chapter 10 Business Research and Report Writing 10 Why are executive summaries included in formal reports? Executive summaries are included because they provide brief overviews of report contents. Compare and contrast the terms executive summary and conclusion. Both are summaries...
  • Georgia and the American Experience

    Georgia and the American Experience

    Sherman's March to the Sea. Why was Sherman's March to the Sea important to the Civil War and to the state of Georgia? Sherman wrote to Abraham Lincoln that Savannah was his Christmas present (along with about twenty-five thousand bales...
  • Lord Byron E. Napp But words are things,

    Lord Byron E. Napp But words are things,

    -Opens with an analytical, clear, comprehensive thesis-Deals with all relevant parts of the question: comparisons, chronology, causation, connections, themes, interactions, content-Gives ample historical evidence to back up thesis-Links comparisons to larger global context-Draws several direct comparisons
  • ARC200 - download.microsoft.com

    ARC200 - download.microsoft.com

    ARC 200 微软RFID开发平台及前景 杨枫 ([email protected]) 项目经理 微软中国技术中心 微软有限公司 议程 RFID(射频标签)简介 微软 RFID 发展与前景 微软 RFID 服务开发平台 以合作伙伴为中心的商业生态环境 微软中国技术中心RFID实验室 Q & A RFID(射频标签)简介 RFID=Radio Frequency + Identification (射频 ...
  • Management of Posterior Smooth Surface Caries

    Management of Posterior Smooth Surface Caries

    * Advantages of Reverse-S curve Conservative tooth preparation / Preserve tooth structure Maintain retention form: Maintain resistance form: angle of departure ~ 90º * * * 2-Yr Clinical Behavior of Unrestored Smooth Surface lesions From: Neilson A, Pitts NB (1991),...
  • Feedback Systems and Driving Clinton Matney AT Workshop

    Feedback Systems and Driving Clinton Matney AT Workshop

    The motor EMC uses is a set speed - motor at full power will only turn so fast, I can turn the wheel/joystick faster than the motor will turn. This is not something that would happen in normal driving. Why...