Generic System Types As far as scheduling is concerned there are basically three different kinds of systems CSCI 8530 Advanced Operating Systems Real Time Scheduling Multiprocessing with single threading Multiple concurrent processes are supported but each has only a single thread VAX VMS Windows 3 1 and UNIX before Pthreads are of this type Single processing with multithreading This type of system has only a single process conceptually but can have many threads Tempo C fits in this category even though the threads are called processes Multiprocessing with multithreading Each of the concurrent processes can have multiple threads Most modern systems fit in this category e g Win 2000 XP QNX UNIX with Pthreads 2 Why Use Multithreading Quick Review Support for multithreading is not free surprise Since processes already provide for concurrent execution why would you want the additional burden of multithreading support Threads within the same process share the same global address space eliminating some IPC requirements e g shared memory Context switches between threads are much faster than context switches between processes System design is easier especially when the system includes a wide variety of operations Failure of one thread doesn t necessarily bring down the entire system It might be possible to correct the problem and restart the faulting thread while the remainder of the system continues operating Tasks which can be processes or threads can be in one of three basic states which can be embellished in some systems Running currently using the CPU Ready add CPU and run Blocked waiting on a resource generic term e g semaphore timer I O completion Each task has its state and other information saved in a unique structure e g process control block that includes register contents when not running resources allocated privilege etc Switching the CPU between tasks requires selecting the new task saving the state of the old task and restoring the state of the new task 3 4 Priorities Scheduling Selecting the Next Task Many scheduling algorithms are available and many of these have or should have been seen before Shortest job first batch First in first out Round robin Shortest remaining time to completion For real time systems the algorithm must be deterministic That is it must always be possible to predict which task will run next Many real time operating systems use round robin since it s simple and predictable 5 All tasks are not created equal some are more important than others for a variety of reasons Some non real time systems may boost the priority of low priority tasks to ensure they get some CPU time This is not appropriate in real time systems It is absolutely necessary that the system designer programmer who assigns task priorities be assured that the tasks and thus the system meets it real time deadlines 6 1 The Priority Principle Example When a system assigns priorities to tasks the scheduling algorithm has two rules The task that is selected to run is the highest priority ready task in the system If a blocked task with a high priority becomes ready and a lower priority task is running that lower priority task is preempted and the higher priority task is executed If multiple ready tasks have the same priority then the basic scheduling algorithm used in the system is applied to them Thus if round robin is used and two tasks have the same priority they are run in round robin fashion Suppose a high priority process H is blocked waiting on a mutex held by a low priority process L which is running Suppose L releases unlocks the mutex As a result of L releasing the mutex H becomes ready Since H is now the highest priority ready process it preempts the execution of L and begins running 7 Blocked Processes 8 Priority Inversion Queues associated with limited resources are ordered by priority in a real time system This means that if a high priority and a low priority process are both blocked waiting for a resource e g something controlled by a semaphore the high priority task will be allowed to use the resource before the low priority process This is in distinct contrast to many simple systems e g Tempo C that use strict FIFO task queuing for resources Priority inversion is a situation that can occur in systems that use priority scheduling In this situation a low priority task can act as though it has a higher priority than a high priority task For priority inversion to occur there must be at least three tasks involved 9 Example 10 Priority Inversion Illustration Suppose the priority of three tasks T1 T2 and T3 is such that T1 T2 T3 Suppose T1 and T2 are blocked and T3 is running T3 requests and is granted a lock on mutex M T1 becomes unblocked and preempts T3 T1 requests a lock on mutex M which can t be granted since T3 has it locked so T1 becomes blocked and T3 runs with M still locked T2 becomes unblocked and preempts T3 The system is now exhibiting priority inversion 11 Request M T1 T2 T3 Lock M T1 Unblocked T2 T1 Blocked Unblocked 12 2 What Happened Priority Inheritance At the end of the last example T1 was blocked waiting on mutex M which it can only acquire when T3 releases it But T3 cannot run since T2 is ready and has a higher priority T1 is thus preventing from running until T2 either blocks or terminates To deal with the problem of priority inversion some real time systems support a technique called priority inheritance In this scheme a low priority task that locks a resource temporarily inherits the priority of the highest priority task blocked by that resource This allows the lower priority task to complete its use of the locked resource return to its lower priority and the higher priority task to preempt it 13 Example 14 A Real World Example Assume the same three tasks as in the last example After the first few steps T1 is running T2 is blocked and T3 is ready with a lock on M T1 tries to lock M fails and becomes blocked At this point T3 temporarily inherits the priority of T1 and begins running T2 as before becomes ready But since T3 has a priority higher than T2 T2 is not allowed to preempt T3 and cause priority inversion Instead T3 continues to run until it releases M at which point its priority returns to its lower level and T1 no longer blocked not T2 is selected for execution Priority inversion is not theoretical The Mars Pathfinder mission had a computer that used shared memory with a mutex controlling access to it A low priority meteorological task used the