In: Computers and Technology

Submitted By uche88
Words 1230
Pages 5
COS 318: Operating Systems

Today’s Topics
Conditions for a deadlock
 Strategies to deal with deadlocks


Last year’s midterm and solution is on the course web page


Use processes and threads interchangeably
 Resources

Use a resource

Request, Use, Release


Preemptable: CPU (can be taken away)
Non-preemptable: Disk, files, mutex, ... (can’t be taken away)

Processes wait indefinitely


A set of processes have a deadlock if each process is waiting for an event that only another process in the set can cause


Resource Allocation Graph

Process A is holding resource R



Process B requests resource S



A cycle in resource allocation graph ⇒ deadlock

If A requests for S while holding R, and B requests for
R while holding S, then





How do you deal with multiple instances of a resource?

An Example

A utility program



Copy a file from tape to disk
Print the file to printer


A deadlock

A holds tape and disk, then requests for a printer
B holds printer, then requests for tape and disk



Conditions for Deadlock

Mutual exclusion condition

Hold and Wait

Resources cannot be taken away

Circular chain of requests

Processes holding resources can request new resources

No preemption

Each resource is assigned to exactly one process

One process waits for another in a circular fashion


Are all conditions necessary?


Eliminate Competition for Resources?

If running A to completion and then running B, there will be no deadlock Generalize this idea for all processes? Is it a good idea to develop a
CPU scheduling algorithm that causes no deadlock?





Previous example



Similar Documents


...implemented does not support concurrent modi cation and hence cannot be used here directly. The linear hash index which is provided to you supports concurrent modi cations as is discussed later. The transaction processing system you will implement will have the following properties : 1. Transactions are never rolled back (undo is never necessary). 2. Transactions have 2 phases: A read phase followed by an atomic write phase. 3. We use shared locks for all reads, and exclusive locks for all writes. 4. We use strict 2 PL as a concurrency control protocol i.e. both shared and exclusive locks once acquired are not released till the transaction ends. 5. Transactions can be aborted due to deadlock. 6. A deadlock detector is executed periodically to analyze wait-for graph and resolve deadlock by aborting necessary transactions. Implemented Modules The following modules are already implemented for you. We discuss the interface for each of the modules here. The header les corresponding to them are provided to you. Linear Hash Index The hash index which you were taught in CS4320/CS5320 is not thread-safe i.e. there is no way to prevent concurrently running transactions (processes) to make changes to the index. This may result in race condi- tions rendering the index corrupt. In order to prevent this we need to use locking and latching to make all operations over the hash index thread safe. A transaction (process) that needs to make changes to the index structure,......

Words: 2665 - Pages: 11

Distributed Transaction

...from global deadlock, and, guar- antees fairness in the execution of the tmnsactions in the system. 1 Introduction A multidatabase system (MDBS) is a collection of pre-existing autonomous, and possibly heteroge- neous, local database systems (LDBSs). Transac- tions in an MDBS are of two types: Local transactions: Those transactions that only access data m,anaged by a single LDBS. Global transactions: Those transactions that ac- cess data managed by more than one LDBS. Transaction management in the MDBS is hierar- chical. Each LDBS controls the local transactions and the subtransactions of the global transactions at its site, and assures serializable execution at that site. The MDBS software controls the global trans- actions, and assures global serializability. Global serializability guarantees the correct con- current execution of global transactions [4]. Global serializability requires that the local serialisation or- ders of the subtransactions of global transactions be the same at all LDBSs where the global transactions execute. It is difficult to achieve this because the LDBSs do not release information concerning their local serialisation orders. TPransaction management in the MDBS also has to deal with the possibility of global deadlocks. Dead- lock detection in an MDBS is difficult and compli- cated [l]. Therefore, it is highly desirable to incorpo- rate methods assuring freedom from global deadlocks into a......

Words: 4732 - Pages: 19

Analysis of Development in the Dominican Republic

...(NationMaster 2012). Table 1: Real GDP Growth |2008 |2009 |2010 |2011 | |5.3% |3.5% |7.8% |5.5% | Source: Global Finance (2012). The constant fluctuations in the GDP are reflective of the chaotic situation in the Dominican. One of the many issues preventing the Dominican Republic from developing is the constant political conflict. Although the Dominican Republic presents a democratic system, corruption and deadlock prevents positive development. “A deadlock is an executive-legislative conflict that hampers the legislative process” (Marsteintredet 2008). Despite the fact deadlocks are often ignored in research pertaining to presidentialism and democracy, deadlocks are one of the primary causes of democratic breakdowns (Marsteintredet 2008). Deadlocks are increasingly more common when there is an individual from a minority party in the position of president. The persistence of deadlocks in the Dominican Republic often prevent politicians from making any changes. Additionally, the ongoing corruption has caused a number of disruptions throughout the country. “Increasingly angry amid the deepening economic crisis set off by last year’s bank fraud scandal, Dominicans staged a 48-hour national strike on January 28 that shut down businesses, schools and public transportation throughout the Dominican Republic” (Garland, 2004). This is just one example of the ongoing chaos. Although the......

Words: 1883 - Pages: 8

Computer Memory

...The Deadlock Problem Law passed by the Kansas Legislature in early 20th century: “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start upon again until the other has gone.” Neil Groundwater has the following to say about working with Unix at Bell Labs in 1972: ... the terminals on the development machine were in a common room ... when one wanted to use the line printer. There was no spooling or lockout. pr myfile > /dev/lp was how you sent your listing to the printer. If two users sent output to the printer at the same time, their outputs were interspersed. Whoever shouted. “line printer!” first owned the queue. 1 Deadlock or Deadly Embrace  Permanent blocking of a set of processes that either compete for system resources or communicate with each other – Several processes may compete for a finite set of resources – Processes request resources and if a resource is not available, enter a wait state – Requested resources may be held by other waiting processes – Require divine intervention to get out of this problem  A significant problem in real systems, because there is no efficient solution in the general case  Deadlock problem is more important because of increasing use of multiprocessing systems (like real-time, life support, vehicle monitoring, multicore utilization, grid processing)  Important in answering the question about the completion of a process  Deadlocks can occur with – Serially......

Words: 282 - Pages: 2


...sections Different solutions, on different levels of abstraction  „Correctness“ criteria (mut.ex., progress/non-starvation, fairness, bounded waiting)  Busy wait vs. Sleep   Classical synchronization problems  Bounded Buffers Readers/writers  Dining Philosophers   Atomic transactions (cf. databases)  Logging, UNDO/REDO recovery  Concurrency Control, Serializability, Locking Time-Stamping Operating System Principles Syllabus.6 Silberschatz, Galvin and Gagne ©2005 Chapter 7: Deadlocks  Define the problem, give necessary conditions!  Graph-based models (single vs. multiple resources per type)   Resource Allocation Graph Wait-For Graph Prevention  What  Methods for handling deadlocks  can we do to ensure that no deadlock can ever occur? can we detect that the system/some processes is/are in a deadlock state? we detected a deadlock: how to resolve the situation?  Detection  How/when  Recovery from deadlock  If Operating System Principles Syllabus.7 Silberschatz, Galvin and Gagne ©2005 Chapter 8: Main Memory Operating System Principles Syllabus.8 Silberschatz, Galvin and Gagne ©2005 Chapter 9: Virtual Memory Operating System Principles Syllabus.9 Silberschatz, Galvin and Gagne ©2005 Chapter 10: File System Interface Operating System Principles Syllabus.10 Silberschatz, Galvin and Gagne ©2005 Chapter 11: File System Implementation Operating System......

Words: 624 - Pages: 3

Deadlock It

...Deadlock Jack Pressler POS/355 11-25-2013 Liane Monaco Deadlock Deadlock can occur when the permanent blocking of a set of processes compete for the same system resources. A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set. Deadlock is permanent because none of the events are ever triggered. Three conditions must take place for a deadlock to take place. The first one is Mutual exclusion, which is a single process that uses one resource at a time. No process may access a resource unit that is being utilized by another process. Hold and wait is the second condition, it can be described as one process that holds assigned resources while waiting for another assignment. Finally, No preemption occurs when no resource can be forced or removed from a process holding it. These three conditions are necessary for a deadlock to exist. However, a fourth condition is required for an actual deadlock to take place. Circular wait occurs when a closed chain of processes exists, and each process holds one or more resources needed by the next process in the chain. This condition is an immediate result of the first three. Below is a self-explanatory illustration of Deadlock. Deadlock blocks a set of processes that competes for system resources. This can be permanent unless the OS takes action, such as forcing one or more processes to backtrack. Deadlock may involve......

Words: 435 - Pages: 2


...others that are worth looking at. Deadlock Another danger of concurrent programming is deadlock. A race condition is produces incorrect results, where a deadlock results in the deadlocked processes never making any progress. In the simplest form it’s a process waiting for a resource held by a second process that’s waiting for a resource that the first holds. Here’s an example: -4- #define N 100 /* Number of free slots */ semaphore mutex = 1; semaphore empty = N; semaphore full = 0; void producer() { item i; while (1) { i = produce_item(); P(mutex); P(empty); insert_new_item(i); V(mutex); V(full); } } void consumer() { item i; while(1) { P(full); P(mutex); i = get_next_item(); V(mutex); V(empty); consume_item(i); } } When the producer arrives at a full queue, it will block on empty while holding mutex, and the consumer will subsequently block on mutex forever. Graphically, this looks like: Resource 1 W an ts Ha s Process a Process b Resource 2 Processes we hopefully understand. Resources are the other parts of the computer system - hardware and software. For the purposes of deadlock, we’re concerned with resources that require exclusive control: tape drives, CD-ROM burners, locks & semaphores, process table slots, etc. W an ts Ha s -5- 4 Conditions More formally there are 4 conditions for deadlock: • • • • Mutual Exclusion: Resources can only be held by at most one process. A process canniot deadlock on a sharable resource.2 Hold and...

Words: 1511 - Pages: 7

Databse Amnagement System

...considered too restrictive as a measure of correctness for schedules? A concurrency control is said to be serializable if the final result of that schedule is totally same as the final result given by the serial schedule. So in executing transaction it will be allow to access multiple transaction with the DBMS in orders to enhance the efficiency and the maximum usability of the resources. But it should give the same result for particular transaction, otherwise it is useless. So through serializability it will lead to the same final outcome by using the schedules, But it is called serializability sometimes too restrictive as because the in serializability it is used locking mechanisms so using locking mechanism me lead to the occurring deadlocks and abort the transaction. This is the reason for called serializability is sometimes too restrictive. 21. What is locking? What is the relevance of lock in database in database management system? How does a lock work? Locking is the process of defining variable with the data items of the database in order to control the access mechanism with respect to the particular operation, by locking it will be controlled and coordinate the process of access items in the database in a sequence manner. In the locking mechanism, Data items will be given values as lock(x) =1 or unlock(x) =0. When a one transaction need to access data item it will check the status. If it is (x) =1 it indicates that data item is still using by another transaction......

Words: 5571 - Pages: 23

The Deadlock

...ABSTRACT The purpose of this study is to get hold of relevant information with the gathered data from the barangay Punta Prinsesa, Cebu City; to accumulate secondary data and other necessary information about the said barangay and verify the information at hand; to identify the community’s assets, needs, opportunities and threats; to list down and infer the community’s assets, needs, opportunities and threats from the households or residents; to outline the community’s assets, needs, opportunities and threats; to categorize the assets, needs, opportunities and threats given by the respondents; and to congregate and analyze the gathered data. In addressing to the documents needed for our research, we used transect mapping, structured questionnaire data for the interview, thorough study and lines of research to come up with the necessary information as regards to the community’s assets, needs, opportunities and threats. With the conclusion that we have reached, it has been found out that women are more active in participating in such environmental activities. Also, citizens aging from the range of 40-75 years old are more concerned of the surroundings and the environmental involvement occurring in their barangay than the young citizens do. In addition, all of our respondents are aware of the environment as well as the things to be made for the betterment of their place. Overall, they are all willing to participate and volunteer to make an action towards a healthier......

Words: 340 - Pages: 2

Transaction Management Ch 10

...keeps track of all transactions that modify the database. The transaction log data may be used for recovery (ROLLBACK) purposes. Next, explain that concurrency control is the management of concurrent transaction execution. (Therefore, a single-user database does not require concurrency control!) Specifically, explore the concurrency control issues concerning lost updates, uncommitted data, and inconsistent databases. Note that multi-user DBMSs use a process known as a scheduler to enforce concurrency control. Since concurrency control is made possible through the use of locks, examine the various levels and types of locks. Because the use of locks creates a possibility of producing deadlocks, discuss the detection, prevention, and avoidance strategies that enable the system to manage deadlock conditions. Answers to Review Questions 1. Explain the following statement: a transaction is a logical unit of work. A transaction is a logical unit of work that must be entirely completed of aborted; no intermediate states are accepted. In other words, a transaction, composed of several database requests, is treated by the DBMS as a unit of work in which all transaction steps must be fully completed if the transaction is to be accepted by the DBMS. Acceptance of an incomplete transaction will yield an inconsistent database state. To avoid such a state, the DBMS ensures that all of a transaction's database operations are completed before they are committed......

Words: 4230 - Pages: 17

Deadlock Detector and Solver Research Paper

... Deadlock Detector and Solver Abstract Deadlock is one of the most serious and complex problems concerning the reliability of concurrent Java Programs. This paper presents Deadlock Detector and Solver which detects and resolves circular deadlocks of a java program. An agent written in C++ runs parallel to Java Program and monitors the Java Virtual Machine for deadlocks. If the deadlock is detected, the solver agent is used to resolve the deadlock . Introduction The onset of multicore processors forces the programmers to use multiple threads in order to take advantage of hardware parallelism. Java is one of the first languages to make multithreading available to developers. Along with advantages of concurrent systems and multithreading, there are some challenges involved. Java has inter-process communication model which means it has set of methods for exchange of data among multiple threads and processes. It is based on shared data structures and meshes well with hardware architectures in which multiple cores share memory. However Java is susceptible to deadlocks. Deadlock is a condition under which the entire program is halted as each thread in a set attempts to acquire a lock already held by another thread in a set. Java is susceptible to deadlocks because (a) threads exchanges information by sharing variables that they lock with mutex locks and (b) the locking mechanism interacts with other language features, such as aliasing. Consider a simple banking transaction......

Words: 3641 - Pages: 15

Optimal Packet Routing

...dynamically adjusted depending on the network congestion. Adaptive routing uses dynamic load balancing can achieve better throughput and latency when compared to oblivious routing. But with the adaptive the challenges may be faced are balancing the router complexity with capability to adapt. Main Body- In this paper, we will discuss the application aware oblivious routing framework that statically determines the deadlock free routes considering applications communication characteristics Michel et. al [3].As the framework supports a variety of algorithms which can optimize various cost functions like channel load, latency of routes, or the combination. Band width sensitive oblivious routing, with static virtual channel allocation, produces deadlock-free routes gives rough estimates of bandwidth demands of all flows obtained through application program analysis and/or profiling. Using these estimates, an offline algorithm determines routes for the data transfers that maximize satisfaction of flow demand or minimize maximum channel load, while ensuring deadlock freedom. The network is then statically configured prior to runtime as processing elements are loaded with the computation code. This approach can achieve better throughput than traditional oblivious routing algorithms because routes are optimized based on the bandwidth demands. The routers used for these processes are kept simple as the routes are configured statically and they do not change at runtime. Router......

Words: 1064 - Pages: 5


...Resource Allocation Graphs Roger Henriksson Department of Computer Science Lund University The possibility of deadlock is an undesired property (to say the least) of safety-critical real-time systems. Therefore, a method to verify that a system cannot deadlock, or to detect possible deadlock situations, is of tremendous value. One such method is resource allocation graphs. As stated in Operating System Concepts by Peterson and Silberschatz [PS85], the occurrence of deadlock requires among other things that hold-wait situations exist and a circular chain of such hold-waits must exist. A resource allocation graph attempts to graphically illustrate all the hold-wait situations in a system. In this graph it is possible to search for cases of circular hold-wait. In their book, Peterson and Silberschatz [PS85] (Section 8.2.2) introduce a method for drawing resource allocation graphs. However, in their version the resource allocation graph shows all the hold-wait-states that exist at any one given point in time. This is a good tool for illustrating a transient state in the system, but in order to use their version of the graphs for detecting any possible deadlock situation we would have to draw a graph for each and every possible combination of execution state for all threads in the system. Then, each and every one of these graphs would have to be analysed for cycles indicating circular wait. This is clearly unpractical. Instead, we modify the method of drawing......

Words: 1937 - Pages: 8


...1. Deadlock (“deadly embrace”) is a system-wide tangle of resource requests that begins when 2 or more jobs are put on hold. • Each job is waiting for a vital resource to become available. • Needed resources are held by other jobs also waiting to run but can’t because they’re waiting for other unavailable resources. • The jobs come to a standstill. • The deadlock is complete if remainder of system comes to a standstill as well. • The resources can be categorized into physical and logical resources. The physical resources are printer, disk drive, cpu, memory, scanner etc. The logical resources are files. • Deadlock is more serious than indefinite postponement or starvation because it affects more than one job. • Because resources are being tied up, the entire system (not just a few programs) is affected. • Requires outside intervention (e.g., operators or users terminate a job) to resolved the deadlock. 2. Seven Cases of Deadlocks Case 1 Deadlocks on file requests Case 2 Deadlocks in databases Case 3 Deadlocks in dedicated device allocation Case 4 Deadlocks in multiple device allocation Case 5 Deadlocks in spooling Case 7 Deadlocks in disk sharing Case 8 Deadlocks in a network Case 1: Deadlocks on File Requests | |If jobs can request and hold files for duration of......

Words: 3058 - Pages: 13

Existing Product to Go Green - Term Paper - Gdot80

...Server Error in '/' Application. [pic] Transaction (Process ID 750) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction. Description: An unhandled exception occurred during the execution of the current web request. Please review the stack trace for more information about the error and where it originated in the code. Exception Details: System.Data.SqlClient.SqlException: Transaction (Process ID 750) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction. Source Error: |An unhandled exception was generated during the execution of the current web request. Information regarding the origin and | |location of the exception can be identified using the exception stack trace below. | Stack Trace: | | |[SqlException (0x80131904): Transaction (Process ID 750) was deadlocked on lock resources with another process and has been | |chosen as the deadlock victim. Rerun the transaction.] | |System.Data.SqlClient.SqlConnection.OnError(SqlException exception, Boolean breakConnection) +1951450 ......

Words: 294 - Pages: 2