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