Methods for handling Deadlocks

Deadlock Prevention.

• Disallow one of the four necessary conditions for deadlock.

Deadlock Avoidance.

• Do not grant a resource request if this allocation have the potential to lead to a deadlock.

Deadlock Detection.

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

Ignore the problem...

• Makes sense if the likelihood is very low.

Deadlock Characterization


• All four conditions must existsimultaneously for deadlock to occur.
• If we can prevent any one of theconditions, we prevent deadlock

1. Mutual exclusion: only one process at a time can use a resource.

2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.

3. No preemption: a resource can be released only voluntarily by the process holding it, after that process has Completed its task.

4. Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.Deadlock can arise if four conditions hold simultaneously

Multiprocessor Scheduling

In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job j_i has length l_i and a number of processors m_i, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.

• Will consider only shared memory multiprocessor

Real Time Scheduling

A multitasking operating system intended for real-time applications. Such applications include embedded systems (programmable thermostats, household appliance controllers), industrial robots, spacecraft, industrial control (see SCADA), and scientific research equipment.
A RTOS facilitates the creation of a real-time system, but does not guarantee the final result will be real-time; this requires correct development of the software. An RTOS does not necessarily have high throughput; rather, an RTOS provides facilities which, if used properly, guarantee deadlines can be met generally or deterministically (known as soft or hard real-time, respectively). An RTOS will typically use specialized scheduling algorithms in order to provide the real-time developer with the tools necessary to produce deterministic behavior in the final system. An RTOS is valued more for how quickly and/or predictably it can respond to a particular event than for the amount of work it can perform over a given period of time. Key factors in an RTOS are therefore a minimal interrupt latency and a minimal thread switching latency.
An early example of a large-scale real-time operating system was Transaction Processing Facility developed by American Airlines and IBM for the Sabre Airline Reservations System.

Real-Time Review

• Real time is not just “real fast”
  Real time means that correctness of result depends on both functional correctness and time that the result is delivered
  
• Soft real time
  Utility degrades with distance from deadline
  
• Hard real time
  System fails if deadline window is missed
  
• Firm real time
  Result has no utility outside deadline window, but system can withstand a few missed results

Type of Real-Time Scheduling

• Dynamic vs. Static
  Dynamic schedule computed at run-time based on tasks really executing
  Static schedule done at compile time for all possible tasks
  
• Preemptive permits one task to preempt another one of lower priority
  

• Thread Scheduling

The thread of a parent process forks a child process. The child process inherits the scheduling policy and priority of the parent process. As with the parent thread, it is the child thread whose scheduling policy and priority will be used.

The following figure illustates the flow of creation.

Figure 1-35 Inheritance of Scheduling policy and priority

• Each thread in a process is independently scheduled.
  
• Each thread contains its own scheduling policy and priority
  
• Thread scheduling policies and priorities may be assigned before a thread is created (in the threads attributes object) or set dynamically while a thread is running.
  
• Each thread may be bound directly to a CPU.
  
• Each thread may be suspended (and later resumed) by any thread within the process.

The following scheduling attributes may be set in the threads attribute object. The newly created thread will contain these scheduling attributes:

• contentionscope
  PTHREAD_SCOPE_SYSTEM specifies a bound (1 x 1, kernel-spacel) thread. When a bound thread is created, both a user thread and a kernel-scheduled entity are created.
  PTHREAD_SCOPE_PROCESS will specify an unbound (M x N, combination user- and kernel-space) thread. (Note, HP-UX release 10.30 does not support unbound threads.)
  
• inheritsched
  PTHREAD_INHERIT_SCHED specifies that the created thread will inherit its scheduling values from the creating thread, instead of from the threads attribute object.
  PTHREAD_EXPLICIT_SCHED specifies that the created thread will get its scheduling values from the threads attribute object.
  
• schedpolicy
  The scheduling policy of the newly created thread
  
• schedparam
  The scheduling parameter (priority) of the newly created thread.

Different CPU Scheduling Algorithms

• Treats ready queue as FIFO.

• Simple, but typically long/varying waiting time.

Shortest Job First (SJF)

• Give CPU to the process with the shortest next burst

• If equal, use FCFS

• Better name: shortest next cpu burst first

Round-Robin (RR)

• FCFS with Preemption

• Time quantum (or time slice)

• Ready Queue treated as circular queue

Shortest Remaining Time (SRT)

• Preemptive version of shortest process next policy

• Must estimate processing time

Single Threaded Process




Multi-Threaded Process

• Benefits of Multi-threaded Programming

Responsiveness - Parts of a program can continue running even if parts of it are blocked. Book points out that a multi-threaded web browser could still allow user interaction in one thread while downloading a gif in another thread…
*Resource Sharing – pros and cons here. By sharing memory or other resources (files, etc.) the threads share the same address space. (there are issues here…)
*Economy – since threads share resources, it is easier to context-switch threads than context-switching processes. This should be clear.
*Utilization of MP Architectures – there will be significant increases in performance in a multiprocessor system, where different threads may be running simultaneously (in parallel) on multiple processors.
*Of course, there’s never ‘a free lunch,’ as we will see later. (There’s always a cost…; nothing this good comes free.

• User Thread

..Thread management done by user-level threads library
..Three primary thread libraries:
-POSIX Pthreads
-Win32 threads

• Kernel Thread

*Supported by the Kernel
*Examples
-Windows XP/2000
-Solaris
-Linux
-Tru64 UNIX
-Mac OS X

• Thread Library

Programmers need help and receive development help via thread libraries germane to specific development APIs..
*A thread library provides an API for creating and managing threads. Java has an extensive API for thread creation and management.
-There are two primary ways to implement thread libraries:
1. Provide thread library entirely in user space – no kernel support
-All code and data structures for the library exist in user space.
-And, invoking a local function call to the library in user space is NOT a system call, but rather a local function call. (this is good).

2. Implement a kernel-level library supported by the OS.
-Here, code and data structures exist in kernel space.
-Unfortunately, in invoking a function call to the library, there is a system call to the kernel for support.

• Multi Models

Many-to-one Model

Each user thread maps to one kernel thread
•Is this implementation good (concurrency vs. efficiency)?
–Good concurrency, why? (blocking syscall does not affect other threads)
–Expensive, why? (user-thread creation -> kernel-thread creation)
•How to have both good concurrency and efficiency?

One-to-one Model

*Each user-level thread maps to kernel thread
*Examples
-Windows NT/XP/2000
-Linux

-Solaris 9 and later

Many-to-Many model

Many user threads are mapped to a smaller or equal number of kernel threads. –Why is this better than Many-to-one? (concurrency & multi-processor) –Why is this better than one-to-one? (efficiency) •Like one-to-one concurrency? –Two-level model.