Synchronization, Operating System

As we already know, threadsmust ensure consistency; otherwise, race conditions (non-deterministic results) might happen. Now consider the "too much milk problem": two people share the same fridge and must guaran tee that there's always milk, but not too much milk. How can we solve it? First, we consider some important concepts and their de?nitions:

 Mutex: prevents things from operating on the same data at the same time;

 Critical section: a piece of code that only one thread can execute at a time;

 Lock: a mechanism for mutual exclusion; the program locks on entering a critical section, accesses the shared data, and then unlocks. Also, a program waits if it tries to enter a locked section.

 Invariant: something that must always be true when not holding the lock. For the above mentioned problem, we want to ensure some correctness properties. First, we want to guarantee that only one person buys milk when it is need (this is the safety property, aka "noth-ing bad happens"). Also, wewant to ensure that someone does buymilkwhen needed (the progress property, aka "something good eventually happens"). Nowconsider thatwe can use the following atomic operations when writing the code for the problem:

 "leave a note" (equivalent to a lock)

 "remove a note" (equivalent to an unlock)


"don't buy milk if there's a note" (equivalent to a wait)

An atomic operation is an unbreakable operation. Once it has started, no other thread or process can interrupt it until it has ?nished. Our ?rst try could be to use the following code on both threads:

if (no milk && no note) {
leave note;
buy milk;
remove note;
}
Unfortunately, this doesn't work because both threads could simultaneously verify that there's no note and no milk, and then both would simultaneously leave a note, and buy more milk. The problem in this case is that we end up with too much milk (safety property not met).

Now consider our solution #2:

Thread A:
leave note "A";
if (no note "B")
if (no milk)
buy milk;
remove note "A";
Thread B:
leave note "B";
if (no note "A");
if (no milk)
buy milk;
remove note "B";

The problemnowis that if both threads leave notes at the same time, neitherwill ever do anything. Then, we end up with no milk at all, which means that the progress property not met. Now, let's consider an approach that does work:

Thread A
leave note A
while (note B)
do nothing
if (no milk)
buy milk
remove note A
Thread B
leave note B;
if (no note A)
if (no milk)
buy milk;
remove note B;

This approach, unlike the two examples considered on the previous class, does work. However, it is complicated: it is not quick-and-easy to convince yourself that these two sections of code always produce the desired behavior.

Posted Date: 3/12/2013 5:10:39 AM | Location : United States







Related Discussions:- Synchronization, Assignment Help, Ask Question on Synchronization, Get Answer, Expert's Help, Synchronization Discussions

Write discussion on Synchronization
Your posts are moderated
Related Questions
Define approaches that require knowledge of the system state?  Answer: Deadlock detection, Deadlock prevention, Deadlock Avoidance.

whta is an operating system ? what sorts services are provided by an operating system ?

Concept of Reentrancy   It is a useful, memory-saving method for multiprogrammed timesharing machines. A Reentrant method is one in which multiple clients can share a singl


A UNIX file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contains 10 direct entries, and one single, double, and triple indirect entry

Swapping : Whole process is moved from the swap machine to the main memory for execution. Process size must be equal or less than to the used main memory. It is easier to exe

What are the methods for handling deadlocks ? The technique for handling the deadlocks are: We are able to use protocol to prevent or avoid the deadlock, make sure tha

For the first assignment you are required to construct a logic circuit onto a copper clad circuit board (vero board). This construction will require the use of planning the positio

Explain about threading issues? The fork and exec system calls In a multithreaded program of few UNIX systems have chosen to have two versions of fork, one that duplicates e

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4 Provide two programm