Earliest Deadline First - Towson University

Earliest Deadline First - Towson University

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 singlecore CPU The similarities and differences between processes and threads The role of internal interrupts and of the interrupt handler

Understanding Operating Systems, 7e 2 Overview Processing Multiprogramming Programs (processes) 2+ Processors 1 Parallel / Multiprocessing

2+ 2+ Concurrent processing 1 2+ 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 programs (processes) running on a single processor Programs compete for CPU time 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 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 13 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 14 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 15 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 16 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 17 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 18 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 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 19 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 Understanding Operating Systems, 7e 20 Scheduling Algorithms Based on specific policy Allocates CPU and moves job through the system Most interactive 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 21

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 22

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

23 Priority Scheduling Nonpreemptive Preferential treatment for important jobs Highest priority programs processed first No interrupts until CPU cycles completed or natural wait occurs 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) Total CPU time: jobs having a long CPU cycle given lower priorities (vice versa) Amount of time already spent in the system (aging): increase priority if job in system unusually long time Understanding Operating Systems, 7e

24 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

25 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 26 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 27 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 28 Managing Interrupts Interrupt types Page interrupt (memory manager) Accommodate job requests 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; fixed-point operations resulting in overflow, etc. Illegal job instruction interrupt Attempting protected storage access, operating on invalid data, etc.

Understanding Operating Systems, 7e 29 Managing Interrupts (cont'd.) Interrupt handler Control program: handles interruption event sequence Non-recoverable 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 30 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 31 (table 4.3) Comparison of the scheduling algorithms discussed in this chapter. Cengage Learning 2014 Understanding Operating Systems, 7e 32 (table 4.3) (contd.) Comparison of the scheduling algorithms discussed in this chapter. Cengage Learning 2014

Understanding Operating Systems, 7e 33

Recently Viewed Presentations

  • PowerPoint-Präsentation

    PowerPoint-Präsentation

    Mehr als die Hälfte würde eine Arztpraxis bevorzugen, die per App zu Terminvereinbarungen oder Untersuchungsbefunden kommuniziert. Frage: Würden Sie einen Arzt, eine Praxis, eine Klinik oder eine Krankenkasse bevorzugen, wenn diese mittels einer App mit Ihnen enger kommunizieren, Ihnen Terminvorschläge-...
  • Bob Tabor | http://www.LearnVisualStudio.NET

    Bob Tabor | http://www.LearnVisualStudio.NET

    Processing Queues. To process (read) a queue, a reader will grab a bunch of messages (max: 32) off a queue in a single request. These are hidden - not removed - until the reader deletes (de-queues) them OR the reader...
  • Module 1: Introduction

    Module 1: Introduction

    Advanced SQL Assertions Triggers Stored Procedures Embedded & Dynamic SQL ODBC & JDBC Assertions An assertion is a predicate expressing a condition that we wish the database always to satisfy. Similar to DDL check constraints, but they can test conditions...
  • Lord, teach us how to pray ... - St. Mary, Ottawa

    Lord, teach us how to pray ... - St. Mary, Ottawa

    Saint Mary's Coptic Orthodox Church of Ottawa. We believe in One GodDOGMA-01. We believe in One God. God vs. no God(against Atheism) One. vs. Multi-gods(against . Polytheism) The One God of Christianity ... the one, only, true God, the Lover...
  • Topic of the Month September 2017 Flying After Inactivity

    Topic of the Month September 2017 Flying After Inactivity

    Faasafety.gov features Activities & Courses, Many For Free. You Can Browse or Search These Offerings. You Can Attend Seminars Like This One, Or Participate In Webinars. Flying After Inactivity. September Topic of the Month. An option for today's pilots return...
  • Royal Commission into Institutional Responses to Child Sexual ...

    Royal Commission into Institutional Responses to Child Sexual ...

    Responding to family violence in remote areas. Central Australian Women's Legal Service. Welcome.
  • Part I Poetry Haiku Cinquain Diamante Limerick Tanka

    Part I Poetry Haiku Cinquain Diamante Limerick Tanka

    Haiku Cinquain Diamante Limerick Tanka Haiku Has three non-rhyming lines. First line has 5 syllables. Second line has 7 syllables. Third line has 5 syllables. Often about something beautiful in nature.
  • Counting Coins - Plain Local Schools

    Counting Coins - Plain Local Schools

    Nickel The nickel is worth five cents. We write it like this, 5¢. It is silver in color. The nickel also has a head and a tail. head tail Thomas Jefferson, the 3rd President of the United States, is on...