Deadlock Prevention

• Disallow one of the four necessary conditions for deadlock
• Preventing deadlocks by constraining how requests for resources can be made in the system and how they are handled (system design).
• The goal is to ensure that at least one of the necessary conditions for deadlock can never hold.

Deadlock Detection

• Always grant resource request when possible. Periodically check for deadlocks. If a deadlock exists, recover from it.

Deadlock Recovery

• Abort all deadlock processes and release resource - too drastic - will lead to loss of work.
• Abort one process at a time - releasing resources until no deadlockHow do we determine which process to abort first ? - priority ordering, process which has done least work.
• Selectively restart processes from a previous checkpoint i.e. before it claimed any resources difficult to achieve - sometimes impossible.
• Successively withdraw resources from a process and give to another process until deadlock is broken. How to choose which processes and which resources ?

1. Complex decisions due to the large number of processes present within a system.
2. Difficult to automate.
3. Use Operator to resolve conflicts - BUT this requires the operator to have skill and understanding of what processes are actually doing.

Deadlock Characterization

Necessary conditions:

1) Mutual exclusion:
• at least one shared resource is held
2) Hold and wait:
• a process must be holding at least one resource and
waiting for another
3) No preemption:
• cannot steal a resource away from a process
4) Circular wait:
• E.g., A is waiting for B who is waiting for C who is
waiting for A.

Real Time Scheduling

• Correctness of the system may depend not only on the logical result of the computation but also on the time when these results are produced, e.g.

–> Tasks attempt to control events or to react to events that take place in the outside world
–> These external events occur in real time and processing must be able to keep up
–> Processing must happen in a timely fashion,• neither too late, nor too early


Thread Scheduling

->Distinction between user-level and kernel-level threads
OS only schedules kernel-level threads. User-level threads are scheduled through a direct or indirect (LWP) mapping
->Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP
->Known as process-contention scope (PCS) since scheduling competition is within the process
->Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system
->Typically – PCS is priority based. Programmer can set user-level thread priorities

thread scheduling criteria:

-> a priority, or in fact usually multiple "priority" settings that we'll discuss below;
-> a quantum, or number of allocated timeslices of CPU, which essentially determines the amount of CPU time a thread is allotted before it is forced to yield the CPU to another thread of the same or lower priority
-> a state, notably "runnable" vs "waiting";
-> metrics about the behaviour of threads, such as recent CPU usage or the time since it last ran (i.e. had a share of CPU), or the fact that it has "just received an event it was waiting for".


Multiprocessor Scheduling

-> is an NP-Complete optimization problem.
-> Given a set of runnable threads, and a set of CPUs, assign threads to CPUs
-> Same considerations as uniprocessorscheduling
(Fairness, efficiency, throughput, response time…)
-> But also new considerations:
* Load balancing
* Processor affinity
-> Will consider only shared memory multiprocessor
Central queue – queue can be a bottleneck
Distributed queue – load balancing between queue

CPU Scheduling Algorithms

Scheduling Algorithms
1.First-come, first-served (FCFS) scheduling
2.Shortest-job first (SJF) scheduling
3.Priority scheduling
4.Round-robin scheduling
5.Multilevel queue scheduling
6.Multilevel feedback queue scheduling

-> First-come, First-served (FCFS) scheduling is the simplest scheduling algorithm, but it can cause short processes to wait for very long processes.
-> Shortest-job-first (SJF) scheduling is provably optimal, providing the shortest average waiting time. Implementing SJF scheduling is difficult because predicting the length of the next CPU burst is difficult. The SJF algorithm is a special case of the general priority-scheduling algorithm, which simply allocates the CPU to the highest-priority process. Both priority and SJF scheduling may suffer from starvation. Aging is a technique to prevent starvation.
->Priority Based Scheduling Run highest-priority processes first, use round-robin among processes of equal priority. Re-insert process in run queue behind all processes of greater or equal priority.Allows CPU to be given preferentially to important processes.Scheduler adjusts dispatcher priorities to achieve the desired overall priorities for the processes, e.g. one process gets 90% of the CPU.Comments: In priority scheduling, processes are allocated to the CPU on the basis of an externally assigned priority. The key to the performance of priority scheduling is in choosing priorities for the processes.
-> Round-robin (RR) scheduling is more appropriate for a time-shared (interactive) system. RR scheduling allocates the CPU to the first process in the ready queue for q time units, where q is the time quantum. After q time units, if the process has not relinquished the CPU, it is preempted and the process is put at the tail of the ready queue. The major problem is the selection of the time quantum. If the quantum is too large, RR scheduling degenerates to FCFS scheduling; if the quantum is too small, scheduling overhead in the form of context-switch time becomes excessive.The FCFS algorithm is nonpreemptive, the RR algorithm is preemptive. The SJF and priority algorithms may be either preemptive or nonpreemptive.
-> Multilevel queue algorithms allow different algorithms to be used for various classes of processes. The most common is a foreground interactive queue which uses RR scheduling, and a background batch queue, which uses FCFS scheduling. Multilevel feedback queues allow processes to move from one queue to another.

Because such a wide variety of scheduling algorithms are available, we need methods to select among them. Analytic methods use mathematical analysis to determine the performance of an algorithm. Simulation methods determine performance by imitating the scheduling algorithm on a “representative” sample of processes, and computing the resulting performance.

Operating Systems supporting threads at the kernel level must schedule threads - not processes - for execution. This is the case with Solaris 2 and Windows 2000 where both systems schedule threads using preemptive priority based on scheduling algorithm including support for real-time threads. The Linux process scheduler also uses a priority-based algorithm with real-time supports as well. The scheduling algorithms for these three operating systems typically favor interactive over batch and CPU-bound processes.systems typically favor interactive over batch and CPU-bound processes.

Substantial Information about Threads of atleast three OS

WINDOWS XP THREAD

Implements the one-to-one mapping
Each thread contains
-> A thread id
-> Register set
-> Separate user and kernel stacks
-> Private data storage area
The register set, stacks, and private storage area are known as the context of the threads
The primary data structures of a thread include:
-> ETHREAD (executive thread block)
-> KTHREAD (kernel thread block)
-> TEB (thread environment block)

JAVA THREADS

-> Java threads are managed by the JVM
-> Java threads may be created by:

Extending Thread class
Implementing the Runnable interface

Windows 2000

Implements the one-to-one mapping

Each thread contains

->A thread ID

->Register set

->Separate user and kernel stacks for user and kernel modes

->Private data storage area used by various run-time libraries and dynamic link libraries (DDLs)

->The latter three are known as the context of the thread and are architecture-specific to HW.