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
Gopher Gallery consists of a shopping mall and a cart ride that covers the 150 acre habitat. There are m visitors and n single-person vehicles. Visitors stroll around the mall at

Q. Explain about Operating System Services? An operating system offers services to programs and to users of those programs. It provided by one environment for execution of

Q. Presume that a system is in an unsafe state. Illustrate that it is possible for the processes to complete their execution without entering a deadlock state. Answer: An unsaf

What is Demand paging? Virtual memory is commonly executed by demand paging. In demand paging, the pager brings only those essential pages into memory instead of swapping in a

Explain the Thread Contextual Data  Threads in Net Ware carry additional context as well. Per-thread, stacks, errno, Net Ware Errno, t_errno and others are available to the ap

What is the main advantage of the layered approach to system design? As in all cases of modular design, designing an operating system in a modular way has several benefits. Th

Question: (a) The actual use and scope groups depend on the mode in which a domain is running. There are two domain modes in which you can run a Windows 2000 domain. List and d

Question 1: a) State the different file attributes and briefly explain the operations that can be performed on each files. b) What is a semaphore? Describe why it is impor

COMBINED ULT/KLT APPROACHES Idea is to merge the best of both approaches Solaris is an illustration of an OS that combines both ULT and KLT  Thread creation complete i

Question: (a) As a System administrator, elaborate on how you can manage computer accounts in Active Directory of Windows Server 2008? (b) Explain the following user p