Operating system chapter 10

صفحه 1:
Multiprocessor and Real- Time Scheduling Chapter 10 

صفحه 2:
Classifications of Multiprocessor Systems * Loosely coupled or distributed multiprocessor, or cluster ~ Each processor has its own memory and 1/O channels ° Functionally specialized processors ~ Such as I/O processor ~ Controlled by a master processor ° Tightly coupled multiprocessing ~ Processors share main memory ~ Controlled by operating system 

صفحه 3:
Independent Parallelism ° Separate application or job * No synchronization among processes ° Example is time-sharing system 

صفحه 4:
Coarse ana Very Coarse-Grained elism 9 ‏هه‎ Beahlelis ong processes at a very gross level ° Good for concurrent processes running on a multiprogrammed uniprocessor ~ Can by supported ona multiprocessor with little change 

صفحه 5:
Medium-Grained Parallelism ° Single application is a collection of threads ° Threads usually interact frequently 

صفحه 6:
Fine-Grained Parallelism ° Highly parallel applications ° Specialized and fragmented area 

صفحه 7:
Scheduling ° Assignment of processes to processors ° Use of multiprogramming on individual processors ° Actual dispatching of a process 

صفحه 8:
Assignment of Processes to Processors * Treat processors as a pooled resource and assign process to processors on demand * Permanently assign process to a processor ~ Known as group or gang scheduling ~ Dedicate short-term queue for each processor ~ Less overhead ~ Processor could be idle while another processor has a backlog 

صفحه 9:
Assignment of Processes to Processors ۰ Global queue ~ Schedule to any available processor * Master/slave architecture ~ Key kernel functions always run on a particular processor Master is responsible for scheduling Slave sends service request to the master Disadvantages Failure of master brings down whole system * Master can become a performance bottleneck ۱ ۱ ۱ 

صفحه 10:
Assignment of Processes to Processors ° Peer architecture ~- Operating system can execute on any processor ~ Each processor does self- scheduling ~ Complicates the operating system * Make sure two processors do not choose the same process 

صفحه 11:
11 Table 10.1 Synchronization Granularity and Processes Synchronization Interval (Instructions) 2 20-200 7200-2000 2000-1M way Description Pacalletism inherent in a single instruction steam. Parallel processing or multitasking. ‘within a single application ‘Mattiprocessing of concurrent processes ina naliprogramming environment ‘Distiomted processing across ‏اج‎ ‎odes to form a single computing ‘environment ‘Multiple uarelated processes Grain Size 5 Medina مومع ‎Comse‏ ری ‎۳ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 12:
Process Scheduling ° Single queue for all processes ° Multiple queues are used for priorities ° All queues feed to the common pool of processors 

صفحه 13:
Thread Scheduling ° Executes separate from the rest of the process ° An application can be a set of threads that cooperate and execute concurrently in the same address space ° Threads running on separate processors yields a dramatic gain in performance 

صفحه 14:
Multiprocessor Thread Scheduling ۰ Load sharing ~ Processes are not assigned to a particular processor ° Gang scheduling ~ A set of related threads is scheduled to run on a set of processors at the same time 

صفحه 15:
Multiprocessor Thread Scheduling ° Dedicated processor assignment ~ Threads are assigned to a specific processor ° Dynamic scheduling ~ Number of threads can be altered during course of execution 

صفحه 16:
Load Sharing ° Load is distributed evenly across the processors ° No centralized scheduler required ° Use global queues 

صفحه 17:
Disadvantages of Load Sharing * Central queue needs mutual exclusion May be a bottleneck when more than one processor looks for work at the same time ° Preemptive threads are unlikely resume execution on the same processor Cache use is less efficient ° If all threads are in the global queue, all threads of a program will not gain access to the processors at the same time 17 

صفحه 18:
Gang Scheduling * Simultaneous scheduling of threads that make up a single process ° Useful for applications where performance severely degrades when any part of the application is not running * Threads often need to synchronize with each other 

صفحه 19:
Scheduling Groups Uniform Divifon Divison by Weights ‏الست‎ Group? Group Group? PEL PEL pe 3 ۳3 prs ae Pres cs Pes 13 Pes ile Time 72 2 ‏که‎ us 15% Waste ample of Scheduling Gri ps with Four and One Threads [FF 19 

صفحه 20:
Dedicated Processor Assignment ° When application is scheduled, its threads are assigned to a processor ° Some processors may be idle ° No multiprogramming of processors 

صفحه 21:
21 Naber of press ‘Figure 10.3 Application Speedup as a Function of Number of Processes [TUCK89] 

صفحه 22:
Dynamic Scheduling ۰ Number of threads in a process are altered dynamically by the application * Operating system adjust the load to improve utilization Assign idle processors New arrivals may be assigned to a processor that is used by a job currently using more than one processor - Hold request until processor is available Assign processor a jog in the list that currently has no processors (i.e., to all waiting new arrivals) 22 

صفحه 23:
Real-Time Systems * Correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced ° Tasks or processes attempt to control or react to events that take place in the outside world ° These events occur in “real time” and tasks must be able to keep up with them 

صفحه 24:
Real-Time Systems ۰ Control of laboratory experiments * Process control in industrial plants * Robotics ۰ Air traffic control ° Telecommunications ° Military command and control systems 

صفحه 25:
Cnaracteristics OF Neal- Time Operating _ systems ° Deterministic ~ Operations are performed at fixed, predetermined times or within predetermined time intervals ~ Concerned with how long the operating system delays before acknowledging an interrupt and there is sufficient capacity to handle all the requests within the required time 

صفحه 26:
Characteristics OF heal- Time Operating کی نمده ومد 9 ~ How long, after acknowledgment, it takes the operating system to service the interrupt - Includes amount of time to begin execution of the interrupt ~ Includes the amount of time to perform the interrupt ~ Effect of interrupt nesting 

صفحه 27:
Cnaracteristics OF Neal- Time Operating ° User comeystems ~ User specifies priority ~ Specify paging ~ What processes must always reside in main memory ~ Disks algorithms to use ~ Rights of processes 

صفحه 28:
Cnaracteristics OF Neal- Time Operating 8 Reliabilin? Y SteMS ~ Degradation of performance may have catastrophic consequences ° Fail-soft operation ~ Ability of a system to fail in sucha way as to preserve as much capability and data as possible ~ Stability 

صفحه 29:
Features of Real-Time Operating Systems ° Fast process or thread switch ° Small size * Ability to respond to external interrupts quickly ° Multitasking with interprocess communication tools such as semaphores, signals, and events 

صفحه 30:
Features of Real-Time Operating Systems ° Use of special sequential files that can accumulate data at a fast rate * Preemptive scheduling base on priority ° Minimization of intervals during which interrupts are disabled ° Delay tasks for fixed amount of time * Special alarms and timeouts 

صفحه 31:
Scheduling of a Real-Time Process 

صفحه 32:
Scheduling of a Real-Time Process Figure 10.4 Scheduling of Real-Time Process 

صفحه 33:
Real-Time Scheduling ° Static table-driven ~ Determines at run time when a task begins execution ° Static priority-driven preemptive - Traditional priority-driven scheduler is used * Dynamic planning-based ~ Feasibility determined at run time ° Dynamic best effort ~ No feasibility analysis is performed 33 

صفحه 34:
Deadline Scheduling ° Real-time applications are not concerned with speed but with completing tasks 

صفحه 35:
Deadline Scheduling ° Information used ~ Ready time ~ Starting deadline ~ Completion deadline ~ Processing time ~ Resource requirements ~ Priority ~ Subtask scheduler 

صفحه 36:
36 ‘Table 10.2 Execution Profile of Two Periodic Tasks Ending Deadline 26 0 5 80 100) 30 1۳ Two Tasks “Fxecution Time 10 10 1 10 11 Avvival Time 20 0 50 

صفحه 37:
cei sas Time(s) A has priority - ‏را‎ sehen ‘B has priority > ‏اس هه سس‎ ‏سس‎ i ‏ا‎ Figure 105. Scheduling of Periodic Real-thne Tasks with Compheidon Deadlines chased on Table 102) 37 

صفحه 38:
120 110 100 90 80 70 و6 | ۱ ۱ | 9 Requirements < Starting deadline Service Starting deine Arsival ines Service ‘Starting deadine Artal ines Service Starting deal 8 (missed) K (missed) D. A Figure 10.6 Scheduling of Aperiodic Real-time Tasks with Starting Deadlines 38 

صفحه 39:
Table 10.3. Execution Profile of Five Aperiodic Tasks ‘Sarting Dendline 1 20 30, 90 11 39 Execution Time 20) 20 20 20 26 1 16 20 a0 30 Process لت مه | 

صفحه 40:
Rate Monotonic Scheduling ° Assigns priorities to tasks on the basis of their periods ° Highest-priority task is the one with the shortest period 

صفحه 41:
Periodic Task Timing Diagram هد ‎ete‏ هج سم تسه Figure 10.7 Periodic Task Timing Diagram 

صفحه 42:
Highest rate and ‏و‎ tek یوم موس + lowest ‏رام‎ Low Rate (Hz) Figure 10.8 A Task Set with RMS [WARR91] 42 

صفحه 43:
Priority Inversion ° Can occur in any priority-based preemptive scheduling scheme ° Occurs when circumstances within the system force a higher priority task to wait for a lower priority task 

صفحه 44:
Unbounded Priority Inversion * Duration of a priority inversion depends on unpredictable actions of other unrelated tasks 

صفحه 45:
Priority Inheritance * Lower-priority task inherits the priority of any higher priority task pendina on a resource thev share ictal 6 1 2 

صفحه 46:
Linux Scheduling ° Scheduling classes - SCHED FIFO: First-in-first-out real-time threads ~ SCHED _RR: Round-robin real-time threads ~ SCHED OTHER: Other, non-real- time threads ° Within each class multiple priorities may be used 

صفحه 47:
47 A| minimum BI middie p—>p—>c—-a. c| middle D| maximum (a) Relative thread provtes (b) Flow with FIFO scheduling D—>R—>c—> 8c a ‎Flow with RR schedaling‏ رم ‎Figure 10.10 Example of Linux Real-Time Scheduling ‎ ‎ ‎ ‎ ‎ 

صفحه 48:
۱ 21- © Scheduling ° Linux 2.6 uses a new scheduler the O(1) scheduler ° Time to select the appropriate process and assign it toa processor is constant ~ Regardless of the load on the system or number of processors 

صفحه 49:
وف سییر ‎neo oe‏ ‎athe ght‏ ینمی | | cv Ques 10 ques by px: (pouty 19) a. pry areas for acne ques api ‏بعصي‎ ‏اميه اس‎ ‘Sa ih pi hoe مس ماود حاسمت Figure 10.11 Linux Scheduling Data Structures for Each Processor 49 

صفحه 50:
UNIX SVR4 Scheduling ° Highest preference to real-time processes ° Next-highest to kernel-mode processes ° Lowest preference to other user-mode processes 

صفحه 51:
UNIX SVR4 Scheduling ° Preemptable static priority scheduler ° Introduction of a set of 160 priority levels divided into three priority classes ° Insertion of preemption points 

صفحه 52:
SVR4 Priority Classes Figure 10.12, SVR4 Priority Classes 

صفحه 53:
53 SVR4 Priority Classes ° Real time (159 - 100) ~ Guaranteed to be selected to run before any kernel or time-sharing process - Can preempt kernel and user processes ° Kernel (99 - 60) ~ Guaranteed to be selected to run before any time-sharing process ¢ Time-shared (59-0) ~ Lowest-priority 

صفحه 54:
SVR4 Dispatch Queues Figure 10.13 SVR4 Dispatch Queues 

صفحه 55:
Windows Scheduling ° Priorities organized into two bands or classes ~ Real time ~ Variable ° Priority-driven preemptive scheduler 

صفحه 56:
aE ‏تست‎ اس ‎+SEE‏ سسه ‏میت تسم ‎ee SS ‏حا‎ ‎Priority ‎Canes ‎ ‎ ‎Figure 10.14 Windows Thread Dispat 

صفحه 57:
ty Relationship i Dave normal ‏سور‎ ‎‘low normal ba pio Example of Windows Pr 

Multiprocessor and RealTime Scheduling Chapter 10 1 Classifications of Multiprocessor Systems • Loosely coupled or distributed multiprocessor, or cluster – Each processor has its own memory and I/O channels • Functionally specialized processors – Such as I/O processor – Controlled by a master processor • Tightly coupled multiprocessing – Processors share main memory – Controlled by operating system 2 Independent Parallelism • Separate application or job • No synchronization among processes • Example is time-sharing system 3 Coarse and Very Coarse-Grained Parallelism • Synchronization among processes at a very gross level • Good for concurrent processes running on a multiprogrammed uniprocessor – Can by supported on a multiprocessor with little change 4 Medium-Grained Parallelism • Single application is a collection of threads • Threads usually interact frequently 5 Fine-Grained Parallelism • Highly parallel applications • Specialized and fragmented area 6 Scheduling • Assignment of processes to processors • Use of multiprogramming on individual processors • Actual dispatching of a process 7 Assignment of Processes to Processors • Treat processors as a pooled resource and assign process to processors on demand • Permanently assign process to a processor – Known as group or gang scheduling – Dedicate short-term queue for each processor – Less overhead – Processor could be idle while another processor has a backlog 8 Assignment of Processes to Processors • Global queue – Schedule to any available processor • Master/slave architecture – Key kernel functions always run on a particular processor – Master is responsible for scheduling – Slave sends service request to the master – Disadvantages • Failure of master brings down whole system • Master can become a performance bottleneck 9 Assignment of Processes to Processors • Peer architecture – Operating system can execute on any processor – Each processor does selfscheduling – Complicates the operating system • Make sure two processors do not choose the same process 10 11 Process Scheduling • Single queue for all processes • Multiple queues are used for priorities • All queues feed to the common pool of processors 12 Thread Scheduling • Executes separate from the rest of the process • An application can be a set of threads that cooperate and execute concurrently in the same address space • Threads running on separate processors yields a dramatic gain in performance 13 Multiprocessor Thread Scheduling • Load sharing – Processes are not assigned to a particular processor • Gang scheduling – A set of related threads is scheduled to run on a set of processors at the same time 14 Multiprocessor Thread Scheduling • Dedicated processor assignment – Threads are assigned to a specific processor • Dynamic scheduling – Number of threads can be altered during course of execution 15 Load Sharing • Load is distributed evenly across the processors • No centralized scheduler required • Use global queues 16 Disadvantages of Load Sharing • Central queue needs mutual exclusion – May be a bottleneck when more than one processor looks for work at the same time • Preemptive threads are unlikely resume execution on the same processor – Cache use is less efficient • If all threads are in the global queue, all threads of a program will not gain access to the processors at the same time 17 Gang Scheduling • Simultaneous scheduling of threads that make up a single process • Useful for applications where performance severely degrades when any part of the application is not running • Threads often need to synchronize with each other 18 Scheduling Groups 19 Dedicated Processor Assignment • When application is scheduled, its threads are assigned to a processor • Some processors may be idle • No multiprogramming of processors 20 21 Dynamic Scheduling • Number of threads in a process are altered dynamically by the application • Operating system adjust the load to improve utilization – Assign idle processors – New arrivals may be assigned to a processor that is used by a job currently using more than one processor – Hold request until processor is available – Assign processor a jog in the list that currently has no processors (i.e., to all waiting new arrivals) 22 Real-Time Systems • Correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced • Tasks or processes attempt to control or react to events that take place in the outside world • These events occur in “real time” and tasks must be able to keep up with them 23 Real-Time Systems • • • • • • Control of laboratory experiments Process control in industrial plants Robotics Air traffic control Telecommunications Military command and control systems 24 Characteristics of RealTime Operating Systems • Deterministic – Operations are performed at fixed, predetermined times or within predetermined time intervals – Concerned with how long the operating system delays before acknowledging an interrupt and there is sufficient capacity to handle all the requests within the required time 25 Characteristics of RealTime Operating Systems • Responsiveness – How long, after acknowledgment, it takes the operating system to service the interrupt – Includes amount of time to begin execution of the interrupt – Includes the amount of time to perform the interrupt – Effect of interrupt nesting 26 Characteristics of RealTime Operating Systems • User control – User specifies priority – Specify paging – What processes must always reside in main memory – Disks algorithms to use – Rights of processes 27 Characteristics of RealTime Operating Systems • Reliability – Degradation of performance may have catastrophic consequences • Fail-soft operation – Ability of a system to fail in such a way as to preserve as much capability and data as possible – Stability 28 Features of Real-Time Operating Systems • Fast process or thread switch • Small size • Ability to respond to external interrupts quickly • Multitasking with interprocess communication tools such as semaphores, signals, and events 29 Features of Real-Time Operating Systems • Use of special sequential files that can accumulate data at a fast rate • Preemptive scheduling base on priority • Minimization of intervals during which interrupts are disabled • Delay tasks for fixed amount of time • Special alarms and timeouts 30 Scheduling of a Real-Time Process 31 Scheduling of a Real-Time Process 32 Real-Time Scheduling • Static table-driven – Determines at run time when a task begins execution • Static priority-driven preemptive – Traditional priority-driven scheduler is used • Dynamic planning-based – Feasibility determined at run time • Dynamic best effort – No feasibility analysis is performed 33 Deadline Scheduling • Real-time applications are not concerned with speed but with completing tasks 34 Deadline Scheduling • Information used – – – – – – – Ready time Starting deadline Completion deadline Processing time Resource requirements Priority Subtask scheduler 35 Two Tasks 36 37 38 39 Rate Monotonic Scheduling • Assigns priorities to tasks on the basis of their periods • Highest-priority task is the one with the shortest period 40 Periodic Task Timing Diagram 41 42 Priority Inversion • Can occur in any priority-based preemptive scheduling scheme • Occurs when circumstances within the system force a higher priority task to wait for a lower priority task 43 Unbounded Priority Inversion • Duration of a priority inversion depends on unpredictable actions of other unrelated tasks 44 Priority Inheritance • Lower-priority task inherits the priority of any higher priority task pending on a resource they share 45 Linux Scheduling • Scheduling classes – SCHED_FIFO: First-in-first-out real-time threads – SCHED_RR: Round-robin real-time threads – SCHED_OTHER: Other, non-realtime threads • Within each class multiple priorities may be used 46 47 Non-Real-Time Scheduling • Linux 2.6 uses a new scheduler the O(1) scheduler • Time to select the appropriate process and assign it to a processor is constant – Regardless of the load on the system or number of processors 48 49 UNIX SVR4 Scheduling • Highest preference to real-time processes • Next-highest to kernel-mode processes • Lowest preference to other user-mode processes 50 UNIX SVR4 Scheduling • Preemptable static priority scheduler • Introduction of a set of 160 priority levels divided into three priority classes • Insertion of preemption points 51 SVR4 Priority Classes 52 SVR4 Priority Classes • Real time (159 – 100) – Guaranteed to be selected to run before any kernel or time-sharing process – Can preempt kernel and user processes • Kernel (99 – 60) – Guaranteed to be selected to run before any time-sharing process • Time-shared (59-0) – Lowest-priority 53 SVR4 Dispatch Queues 54 Windows Scheduling • Priorities organized into two bands or classes – Real time – Variable • Priority-driven preemptive scheduler 55 56 57