Operating System

• V is partitioned into to two types:

1. P= {P1,P2,...,Pn}, the set consisting of all the processes in the system.
   
2. R={R1,R2,...,Rm}, the set consisting of all resource types in the system.

-request edge-directed edge P1 [] Rj

-assignment edge-directed edge Rj[]Pi

_Process

_Resource typeb with 4 instances

_Pi requests instance of Rj

_Pi is holding an instance of Rj

• if graph contains no cycle => no deadlock
• if graph contains a cycle,

---if only one instance per resource type, then deadlock

---if several instances per resource type, possibility of deadlock.

(0)A Resource Allocation Graph

_This RAG shows a cycle of 3 processes and 4 resource types.

(0) Resource Allocation Graph with deadlock.

-First P1 have a request to R1.The instance of R1 has been hold by P2. This process then sends request to R3 , and P3 is holding its instance. When P3 sends request to R2, which consists of 2 instances. One instance holds by P2 while the other one holds by P1. There exist the deadlock when the instances of two different resource type are been holds by one Process(P2) at the same time.

(0) Resource allocation graph with a cycle but no deadlock

- The graph contains a cycle. Each processes holds an instance of the resource. First, P1 sends request to R1, which contains 2 instances. P2 and P3 are holding these instances . Then, P3 sends request to R2 which also contains 2 instances and each of these are holds by P4 and P1.

• Recovery through preemption

• Recovery through rollback

• Recovery through killing processes

• Process Termination
• Abort all deadlocked processes:
  -Fast
  -A lot of process work is lost.
• Abort one deadlocked process at a time and check for deadlocks again:
  -More work to resolve a deadlock.
  -Better in terms of process work.
  -What is a good order to abort processes?
• Resource Preemption
  what is a good way to select a victim
  How can we rollback and then recover from preemption?
  How can we protect from starvation

(0) deadlock detection

Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS.

Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock.

Deadlock detection attempts to find and resolve actual deadlocks. These strategies rely on a Wait-For-Graph (WFG) that in some schemes is explicitly built and analyzed for cycles. In the WFG, the nodes represent processes and the edges represent the blockages or dependencies. Thus, if process A is waiting for a resource held by process B, there is an edge in the WFG from the node for process A to the node for process B.

In the AND model (resource model), a cycle in the graph indicates a deadlock. In the OR model, a cycle may not mean a deadlock since any of a set of requested resources may unblock the process. A knot in the WFG is needed to declare a deadlock. A knot exists when all nodes that can be reached from some node in a directed graph can also reach that node.

In a centralized system, a WFG can be constructed fairly easily. The WFG can be checked for cycles periodically or every time a process is blocked, thus potentially adding a new edge to the WFG. When a cycle is found, a victim is selected and aborted.

(0)Deadlock Prevention

Restrain the ways requests can be made to break one of the four necessary conditions for deadlocks

• We try to ensure that one of the four necessary conditions cannot hold, then we can prevent it
• Mutual Exclusion:
  -If it is shareable resource, then we can break the mutual exclusion (such as: Read-only file)
  -If it is not a shareable resource, then mutual exclusion must hold (such as: Printer)
• Some devices (such as printer) can be spooled

– only the printer daemon uses printer resource

– thus deadlock for printer eliminated

• Not all devices can be spooled

• Hold and wait: two methods
  1. Require process to request and be allocated all its resources before it begins execution.
  2. allow process to request resources only when the process has none.

• NO preemption:

• If a process that is holding some resources requests
  another resource that cannot be immediately to
  allocated it, then all resources currently being held are
  released.
• Preempted resources are added to the list of resources
  for which the process is waiting.
  Process will be restarted only when it can regain its old
  resources, as well as the new ones that it is requesting.
  
• Attacking the No Preemption Condition:
• Preemption– when a process is holding some resources and waiting for others, its resources may be preempted to be used by others
• Problem– Many resources may not allow preemption; i.e., preemption will cause process to fail

• Attacking the Circular Wait Condition:

• impose a total order of all resource types; and require that all processes request resources in the same order

(0) Methods for handling deadlock

• 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.

1. Ignore the problem and pretend that deadlocks would never occur
2. Ensure that the system will never enter a deadlock state (prevention or avoidance)
3. Allow the system to enter a deadlock state and then detect/recover

(0)deadlock characterization

Deadlock can arise if four conditions hold simultaneously:

1.Mutual Exclusion

• only one process at a time can use a resource.
• If another process requests that resource, the requesting process must be delayed until the resource has been released
  

• there exists a set {P0, P1, …, P0} of waiting processes such that
  P0 is waiting for a resource that is held by P1,
  P1is waiting for a resource that is held by P2, …, Pn–1is waiting for a resource that is held by Pn, and P0is waiting for a resource that is held by P0.

(0) thread scheduling

>the thread scheduler, part of the OS (usually) that is responsible for sharing the available CPUs out between the various threads. How exactly the scheduler works depends on the individual platform, but various modern operating systems (notably Windows and Linux) use largely similar techniques that we'll describe here. We'll also mention some key varitions between the platforms.

>Across platforms, thread scheduling1 tends to be based on at least the following 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 (the system will keep track of the remaining quantum at any given time, plus its default quantum, which could depend on thread type and/or system configuration);]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".

(0)Real Time Scheduling

• Many real time systems run a known collection of tasks. The execution time of the tasks is frequently known ahead of time.
• Tasks have deadlines by which they must complete.
• If a task that runs for 3 time units must be done at time 10, it must start by time 7.
• If two tasks that runs for 3 time units each must be done at time 10, one must start by time 4.

(0) Multiprocessor Scheduling

• Very little has to be done to schedule a multiprocessor system.
• Whenever a CPU needs a process to run, it takes the next task from the ready list.
• The scheduling queue must be accessed in a critical section.
• Busy waiting is usually used.

In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, 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.

• Windows NT(New Technology) threads
  

Figure 2: The relationships of a process and its threads and fibers in Windows NT.

• Solaris Threads

Light weight process (LWP) is Solaris's smallest kernel-level object of execution. A Solaris process consists of one or more light weight processes. Like NT's thread, each LWP shares its address space and system resources with LWPs of the same process and has its own context. However, unlike NT, Solaris allows programmers to exploit parallelism through a user-level object that is built on light weight processes. In Solaris, a thread is the smallest user-level object of execution. Like Windows NT's fiber, they are not executable alone. A Solaris thread must execute in the context of a light weight process. Unlike NT's fibers, which are controlled by the application programmer, Solaris's threads are implemented and controlled by a system library. The library controls the mapping and scheduling of threads onto LWPs automatically. One or more threads can be mapped to a light weight process. The mapping is determined by the library or the application programmer. Since the threads execute in the context of a light weight process, the operating system kernel is unaware of their existence.

Figure 3: The relationships of a process and its LWPs and threads in Solaris.

• MacOS threads
  
  Mac OS 9 Threading

This section describes threading on Mac OS 9. Mac OS 9 has two threading APIs.

• Thread Manager provides cooperatively scheduled threads within a process.


• MP tasks are preemptively scheduled by the nanokernel.

In addition to these threading APIs, it's impossible to understand Mac OS 9 threading without also understanding Mac OS 9 process scheduling, as implemented by the Process Manager.

IMPORTANT:Threading terminology can get confusing, especially on a system like Mac OS X that inherits terminology from many different sources. One particularly confusing term is "task." The MP API uses the term "MP task" to describe a thread of execution with a process. On the other hand, Mach uses the term "Mach task" to describe a collection of resources such as threads, memory, and ports (an idea more commonly known as a process). This technote always uses either "MP task" or "Mach task" to differentiate between these two concepts, and never uses the term "task" unqualified.

Figure 1. Mac OS 9 threading.

(0) CPU Scheduling algorothms

CPU scheduling algorithms simulates the scheduling of a CPU, calculate waiting time & average and turnaround time.

• First In First Out (FIFO)

This is a Non-Premptive scheduling algorithm. FIFO strategy assigns priority to processes in the order in which they request the processor.The process that requests the CPU first is allocated the CPU first.When a process comes in, add its PCB to the tail of ready queue. When running process terminates, dequeue the process (PCB) at head of ready queue and run it.

Solution: Limit the amount of time a process can run without a context switch. This time is called a time slice.

• Round Robin

Round Robin calls for the distribution of the processing time equitably among all processes requesting the processor.Run process for one time slice, then move to back of queue. Each process gets equal share of the CPU. Most systems use some variant of this.

Choosing Time Slice
What happens if the time slice isnt chosen carefully?

• For example, consider two processes, one doing 1 ms computation followed by 10 ms I/O, the other doing all computation. Suppose we use 20 ms time slice and round-robin scheduling: I/O process runs at 11/21 speed, I/O devices are only utilized 10/21 of time.

• Suppose we use 1 ms time slice: then compute-bound process gets interrupted 9 times unnecessarily before I/O-bound process is runnable

Problem: Round robin assumes that all processes are equally important; each receives an equal portion of the CPU. This sometimes produces bad results. Consider three processes that start at the same time and each requires three time slices to finish. Using FIFO how long does it take the average job to complete (what is the average response time)? How about using round robin?
Round Robin is fair, but uniformly enefficient.
Solution: Introduce priority based scheduling.

• 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.
Problem: Priority scheduling may cause low-priority processes to starve
Solution: (AGING) This starvation can be compensated for if the priorities are internally computed. Suppose one parameter in the priority assignment function is the amount of time the process has been waiting. The longer a process waits, the higher its priority becomes. This strategy tends to eliminate the starvation problem.

• Shortest Job First

Maintain the Ready queue in order of increasing job lengths. When a job comes in, insert it in the ready queue based on its length. When current process is done, pick the one at the head of the queue and run it.
This is provably the most optimal in terms of turnaround/response time.
But, how do we find the length of a job?

Comments: SJF is proven optimal only when all jobs are available simultaneously.
Problem: SJF minimizes the average wait time because it services small processes before it services large ones. While it minimizes average wiat time, it may penalize processes with high service time requests. If the ready list is saturated, then processes with large service times tend to be left in the ready list while small processes receive service. In extreme case, where the system has little idle time, processes with large service times will never be served. This total starvation of large processes may be a serious liability of this algorithm.
Solution: Multi-Level Feedback Queques

• Multi-Level Feedback Queue

Several queues arranged in some priority order.
Each queue could have a different scheduling discipline/ time quantum.
Lower quanta for higher priorities generally.

Defined by:

• # of queues
• scheduling algo for each queue
• when to upgrade a priority
• when to demote

Attacks both efficiency and response time problems.

• Give newly runnable process a high priority and a very short time slice. If process uses up the time slice without blocking then decrease priority by 1 and double its next time slice.
• Often implemented by having a separate queue for each priority.
• How are priorities raised? By 1 if it doesn't use time slice? What happens to a process that does a lot of computation when it starts, then waits for user input? Need to boost priority a lot, quickly.