���WEEK 5��process Synchronization��

Introduction

• A cooperating process is one that can affect or be affected by the other processes executing in the system.
• Cooperating processes may either directly share a logical address space or be allowed to share data only through files.

​

Background

• Concurrent processes executing in the operating system are cooperating processes, if it can affect or be affected by the other processes executing in the system.
• Concurrent execution that requires cooperation among the processes requires mechanisms to allow processes to communicate with each other and to synchronize their actions.

​

​

​

Race Conditions

• A race condition is a situation where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.
• The part of the program, in which race conditions can occur, is called critical section.

​

The Critical Section Problem

• A critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution.
• When one process is executing in the critical section, no other process is to be allowed to execute in its critical section. Thus the execution of critical of critical section by the process is mutually exclusive in time.

​

​

• Consider a system consisting of ‘n’ processes P₀,P₁,…..P_n-1
• Each process has a segment of code called a critical section
• An important feature of the system is that, when one process is executing in the critical section, no other process is to be allowed to execute in its critical section.
• Thus, the execution of critical section by the processes is mutually exclusive in time
• A Critical Section Environment contains:
• Entry Section Code requesting entry into the critical section.
• Critical Section Code in which only one process can execute at any one time.
• Exit Section The end of the critical section, releasing or allowing others in.
• Remainder Section Rest of the code AFTER the critical section

​

Solution to Critical-Section Problem

A solution to the critical-section problem must satisfy the following requirements:

1.Mutual Exclusion- If process P₁ is executing in its critical section, then no other processes can be executing in their critical sections

2.Progress- If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely

3.Bounded Waiting- A bound, or limit must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted

• Assume that each process executes at a nonzero speed
• No assumption concerning relative speed of the N processes

Semaphore

• Semaphore: a synchronization tool.
• A Semaphore is a synchronization object that controls access by multiple process to a common resource in a parallel programming environment.
• Semaphores are widely used to control access to files and shared memory.
• The 3 basic functionalities associated with Semaphores are set, check and wait until it clears to set it again.
• Two types:
• Counting semaphore – integer value can range over an unrestricted domain
• Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement
• Also known as mutex locks (they are locks that provide mutual exclusion)

​

​

Introduction to Deadlock

• Is a situation which occurs in a multiprogramming environment when several processes compete for a finite number of resources.
• A process requests resources if the resources are not available at that time, the process enters a wait state.
• It can happen that waiting processes will never again change state because the resources they requested are held by other waiting processes.
• The OS has to deal with the deadlock problem. This problem can be increased if there are large number of processes and having many resources.

System Model

• System consists of resources. Each resources consists of several number of identical instances.
• Resource types R₁, R₂, . . ., R_m CPU cycles, memory space, I/O devices

​

​

​

​

​

• When process requests an instance of a resource type then the allocation of any instance of that type will satisfy the request. But if request is not satisfied, then the instances are not identical and the resource type classes have not been defined properly.
• Each process utilizes a resource as follows:
• request
• use
• release
• Request and Release of other resources can be accomplished through the wait and signal operations on semaphores.
• A System table records whether each resource is free or allocated and if a resource is allocated to which process.
• If process requests a resource i,e currently allocated to another process it can be added to a queue of processes waiting for the resource.

• A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused by only another process in the set.

​

Deadlock Characterization

• Deadlock are undesirable.
• In a deadlock, processes never finish executing and system resources are tied up, preventing other jobs from starting anytime.

​

Necessary Conditions

• Deadlock can arise if four conditions hold simultaneously.
• Mutual exclusion
• Hold and Wait
• No preemption
• Circular wait

​

​

​

• Mutual exclusion: only one process at a time can use a resource
• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task
• Circular wait: there exists a set {P₀, P₁, …, P_n} of waiting processes such that P₀ is waiting for a resource that is held by P₁, P₁ is waiting for a resource that is held by P₂, …, P_n–1 is waiting for a resource that is held by P_n, and P_n is waiting for a resource that is held by P₀.

​

Resource-Allocation Graph

• Deadlocks can be described more precisely in terms of a directed graph – system resource allocation graph
• Graph consists of a set of vertices V and a set of edges E.

​

​

​

• V is partitioned into two types of nodes:
• P = {P₁, P₂, …, P_n}, the set consisting of all the processes in the system
• R = {R₁, R₂, …, R_m}, the set consisting of all resource types in the system
• request edge – directed edge P_i → R_j
• assignment edge – directed edge R_j → P_i
• Process�
• Resource Type with 4 instances

​

• P_i requests instance of R_j

​

• P_i is holding an instance of R_j

​

P_i

R_j

P_i

R_j

• In the fig, Process P_i is represented as a circle and each resource type R_j as square.
• A request edge is inserted in the resource-allocation graph, when process P_i requests an instance of resource type R_j
• If this request can be fulfilled, the request edge is instantaneously changed to an assignment edge.
• The sets P,R,E

P={P1,P2,P3}

R={R1,R2,R3,R4}

E={P1 R1, P2 R3, R1 P2, R2 P1,R2 P2,R3 P3}

• Resource instances
• One instance of resource type R1
• Two instances of resource type R2
• One instance of resource type R3
• Three instances of resource type R4

• Process states
• Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1
• Process P2 is holding an instance of resource type R1 and R2 and is waiting for an instance of resource type R3
• Process P3 is holding an instance of R3.
• If the graph has no cycles, then no process in the system is deadlocked, but if the graph contains a cycle, then a deadlock may exist.
• If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred

​

​

​

Methods for Handling Deadlocks

• Ensure that the system will never enter a deadlock state:
• Deadlock prevention
• Deadlock avoidance
• A protocol can be used to ensure that the system will never enter a deadlock state
• Allow the system to enter a deadlock state and then recover
• Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX
• Deadlock prevention is a set of methods for ensuring that atleast one of the necessary conditions cannot hold.

​

Deadlock Prevention

By ensuring that atleast one of these conditions cannot occur can prevent the occurrence of a deadlock

​

Mutual Exclusion

Hold and Wait

No Preemption

Circular Wait

​

Deadlock Avoidance

• Requires that the system has some additional a priori information �available
• Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
• The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
• Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes

Safe State

• A state is safe if the system can allocate resources to each process in an order and avoid deadlock
• When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state

Basic Facts

• If a system is in safe state ⇒ no deadlocks
• If a system is in unsafe state ⇒ possibility of deadlock
• Avoidance ⇒ ensure that a system will never enter an unsafe state.

​

Safe, Unsafe, Deadlock State

Deadlock Detection

• If the deadlock-prevention or a deadlock-avoidance algorithm is not employed in a system than a deadlock situation may occur in this environment the system must provide
• An algorithm that examines the state of the system to determine whether a deadlock has occurred.
• An algorithm to recover from the deadlock

​

Recovery from Deadlock

• Possibility is to inform the operator that a deadlock has occurred and to let the operator to deal with the deadlock normally.
• Another possibility is to let the system to recover from the deadlock automatically.

Breaking deadlock

• One solution is to abort one or more processes to break the circular wait.
• To preempt some resources from one or more of the deadlock processor

​

THREADS

​

• A thread is also called a lightweight process.
• Threads provide a way to improve application performance through parallelism.
• Threads represent a software approach to improving performance of operating system by reducing the overhead thread is equivalent to a classical process.
• Each thread belongs to exactly one process and no thread can exist outside a process.
• Each thread represents a separate flow of control.
• Threads have been successfully used in implementing network servers and web servers.
• They also provide a suitable foundation for parallel execution of applications on shared memory multiprocessors. The following figure shows the working of a single-threaded and a multithreaded process.

Fig.: Working of single-threaded and multithreaded process

Difference between Process and Thread

Advantages of Thread

​

• Threads minimize the context switching time.
• Use of threads provides concurrency within a process.
• Efficient communication.
• It is more economical to create and context switch threads.
• Threads allow utilization of multiprocessor architectures to a greater scale and efficiency.

TYPES OF THREADS - KERNEL LEVEL AND USER LEVEL

​

Threads are implemented in following two ways −

​

User Level Threads − User managed threads.

Kernel Level Threads − Operating System managed threads acting on kernel, an operating system core.

USER LEVEL THREADS

• In user level threads, the thread management kernel is not aware of the existence of threads.
• The thread library contains code for creating and destroying threads, for passing message and data between threads, for scheduling thread execution and for saving and restoring thread contexts.
• The application starts with a single thread. Figure illustrates a user level thread.

Advantages

Thread switching does not require Kernel mode privileges.

User level thread can run on any operating system.

Scheduling can be application specific in the user level thread.

User level threads are fast to create and manage.

Disadvantages

In a typical operating system, most system calls are blocking.

Multithreaded application cannot take advantage of multiprocessing.

KERNEL LEVEL THREADS

• In kernel level thread, thread management is done by the Kernel.
• There is no thread management code in the application area. Kernel threads are supported directly by the operating system.

​

• Any application can be programmed to be multithreaded.
• All of the threads within an application are supported within a single process.
• The Kernel maintains context information for the process as a whole and for individual threads within the process.
• Scheduling by the Kernel is done on a thread basis.
• The Kernel performs thread creation, scheduling and management in Kernel space.
• Kernel threads are slower to create and manage than the user threads.

​

Advantages

• Kernel can simultaneously schedule multiple threads from the same process on multiple processes.
• If one thread in a process is blocked, the Kernel can schedule another thread of the same process.
• Kernel routines themselves can be multithreaded.

Disadvantages

• Kernel threads are slower to create and manage than the user threads.
• Transfer of control from one thread to another within the same process requires a mode switch to the Kernel.

Difference between User-Level & Kernel-Level Thread

MULTITHREADING MODELS

• Some operating systems provide a combined user level thread and Kernel level thread facility.
• Solaris is a good example of this combined approach.
• In a combined system, multiple threads within the same application can run in parallel on multiple processors and a blocking system call need not block the entire process.

​

Multithreading models are three types

• Many to many relationship.
• Many to one relationship.
• One to one relationship.

Many to Many Model

• The many-to-many model multiplexes any number of user threads onto an equal or smaller number of kernel threads.
• The following diagram in figure shows the many-to-many threading model where 6 user level threads are multiplexing with 6 kernel level threads.
• In this model, developers can create as many user threads as necessary and the corresponding Kernel threads can run in parallel on a multiprocessor machine.
• This model provides the best accuracy on concurrency and when a thread performs a blocking system call, the kernel can schedule another thread for execution.

Fig.: Many-to-many Relationship Model

Many to One Model

​

• Many-to-one model maps many user level threads to one Kernel-level thread.
• Thread management is done in user space by the thread library.
• When thread makes a blocking system call, the entire process will be blocked.
• Only one thread can access the Kernel at a time, so multiple threads are unable to run in parallel on multiprocessors.
• If the user-level thread libraries are implemented in the operating system in such a way that the system does not support them, then the Kernel threads use the many-to-one relationship modes.

Fig.: illustrates many-to-one model.

One to One Model

​

• There is one-to-one relationship of user-level thread to the kernel-level thread.
• This model provides more concurrency than the many-to-one model.
• It also allows another thread to run when a thread makes a blocking system call.
• It supports multiple threads to execute in parallel on microprocessors.

Disadvantage of this model is that creating user thread requires the corresponding Kernel thread.

​

OS/2, Windows NT and Windows 2000 use one to one relationship model.

Fig.: illustrates one-to-one model

Assignment Questions

1. Define the following
1. Cooperating Process
2. Race condition
3. Semaphore
4. Deadlock
5. Synchronization

2.Write a note on Critical Section Problem.

3. Explain the 3 requirements for the solution to critical-section problem.

4. Write a note on Semaphore.

5. Explain the necessary conditions for deadlock.

6. Explain with an example, Resource allocation Graph.

7. Explain with an example, Resource allocation Graph with no deadlock.

8. How deadlock can be prevented? Explain.

9. Explain, How Deadlock can be avoided.

10. Write a note on safe state.

11. Describe Resource allocation Graph Scheme.

12. Explain the banker’s algorithm.

13. How deadlock can be detected? Explain.

14. How to recover from Deadlock.

​

15.What is a thread?

16.Compare thread and Process.

17.Explain single threaded and multi -threaded process.

18.List the advantages of thread.

19.With figure, explain user level thread.

20.Compare user level and kernel level thread.

21.Mention advantages and disadvantages of user level threads.

22.Mention advantages and disadvantages of kernel level threads.

23.What is a multithreading model?

24.With neat figures, explain the three types of multithreading models.