Alternative Themes # 2

Question

Imagine a situation in which there is one king and n is the number of minions presented to him. When the king says “One!”, One of the minions says “Two!”, But only one of them. That is, says only the fastest minion, while others must wait for another king call.

This is my attempt:

using System; using System.Threading; class Program { static bool leaderGO = false; void Leader() { do { lock(this) { //Console.WriteLine("? {0}", leaderGO); if (leaderGO) Monitor.Wait(this); Console.WriteLine("> One!"); Thread.Sleep(200); leaderGO = true; Monitor.Pulse(this); } } while(true); } void Follower (char chant) { do { lock(this) { //Console.WriteLine("! {0}", leaderGO); if (!leaderGO) Monitor.Wait(this); Console.WriteLine("{0} Two!", chant); leaderGO = false; Monitor.Pulse(this); } } while(true); } static void Main() { Console.WriteLine("Go!\n"); Program m = new Program(); Thread king = new Thread(() => m.Leader()); Thread minion1 = new Thread(() => m.Follower('#')); Thread minion2 = new Thread(() => m.Follower('$')); king.Start(); minion1.Start(); minion2.Start(); Console.ReadKey(); king.Abort(); minion1.Abort(); minion2.Abort(); } } 

The expected result will be like this (# and $ representing two different minions):

 > One! # Two! > One! $ Two! > One! $ Two! ... 

The order in which they appear does not matter, it would be random. The problem, however, is that this code produces this instead when compiled:

 > One! # Two! $ Two! > One! # Two! > One! $ Two! # Two! ... 

That is, several minions appear simultaneously. This would cause a storm with even more minions, and the king should not allow such interference.

What will be the possible solution?

---

For future readers, here is the last working code:

 using System; using System.Threading; class Program { static AutoResetEvent leader = new AutoResetEvent(false); static AutoResetEvent follower = new AutoResetEvent(false); void Leader() { do { Console.WriteLine(" One!"); Thread.Sleep(300); follower.Set(); // Leader allows a follower speak leader.WaitOne(); // Leader waits for the follower to finish speaking } while(true); } void Follower (char emblem) { do { follower.WaitOne(); // Follower waits for the leader to allow speaking Console.WriteLine("{0} Two!", emblem); leader.Set(); // Follower finishes speaking } while(true); } static void Main() { Console.WriteLine("Go!\n"); Program m = new Program(); Thread king = new Thread(() => m.Leader()); Thread minion1 = new Thread(() => m.Follower('#')); Thread minion2 = new Thread(() => m.Follower('$')); Thread minion3 = new Thread(() => m.Follower('&')); king.Start(); minion1.Start(); minion2.Start(); minion3.Start(); Console.ReadKey(); king.Abort(); minion1.Abort(); minion2.Abort(); minion3.Abort(); } } 

Answer 1

Try using AutoResetEvent instead of lock / monitor. This allows you to create “gates” through which only one stream can pass at a time.

event.WaitOne() () is called in your Follower () event.WaitOne() (optionally with a timeout). The Leader () function will call event.Set() , which will output one of the waiting threads.

AutoResetEvent (unlike other types of wait descriptors) will automatically "close the gate" once from the waiting threads.

http://msdn.microsoft.com/en-us/library/system.threading.autoresetevent.aspx

Answer 2

You do not block subscribers. So both threads see leaderGo and they respond. Lock the stream before recording, and this should fix it.

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; namespace Threading { class Program { static bool leaderGO = false; static bool followerGo = false; void Leader() { do { lock (this) { //Console.WriteLine("? {0}", leaderGO); if (leaderGO) Monitor.Wait(this); Console.WriteLine("> One!"); Thread.Sleep(200); leaderGO = true; followerGo = true; Monitor.Pulse(this); } } while (true); } void Follower(char chant) { do { lock (this) { //Console.WriteLine("! {0}", leaderGO); if (!leaderGO) Monitor.Wait(this); if(followerGo) { followerGo = false; Console.WriteLine("{0} Two!", chant); leaderGO = false; } Monitor.Pulse(this); } } while (true); } static void Main() { Console.WriteLine("Go!\n"); Program m = new Program(); Thread king = new Thread(() => m.Leader()); Thread minion1 = new Thread(() => m.Follower('#')); Thread minion2 = new Thread(() => m.Follower('$')); king.Start(); minion1.Start(); minion2.Start(); Console.ReadKey(); king.Abort(); minion1.Abort(); minion2.Abort(); } } 

}

Answer 3

What you are experiencing is a race condition. You have two separate threads running on an unlocked resource (leaderGo) that controls their access to the critical section (by printing "Two!").

Placing a mutex lock (as recommended by manman) on leaderGo before printing "Two!" this is the beginning. You will also need to check that trueGo is still true before printing it, as both threads will eventually acquire a lock, but only one of them will get a lock, and leaderGo will be true.

Sort of:

 lock(leaderGo) { if (leaderGo) Console.WriteLine("{0} Two!", chant); leaderGo = false; } 

This ensures that only one follower is able to respond (since it requires blocking). It does not guarantee which thread gets a lock, the frequency with which specific threads get a lock, or anything like that. However, in each pass, each thread gets a lock - all that matters is who it was first.

Answer 4

A few tips:

• NEVER use lock(this) . By locking the object from the inside out, anything that uses your object as the focus of the lock will interfere with your own ability to synchronize codes.
• NEVER use Thread.Abort() . This evil; it kills your running threads by introducing an exception that is unpredictable and therefore difficult or impossible to catch and handle gracefully. Instead, try passing an instance of the class with the boolean property IsCancelled and use !IsCancelled as the condition under which you continue the loop.

The actual problem with your code is that your combination of Monitor and locks causes the lock to be released in the critical section by the thread that receives the lock, if that thread considers that someone else should go first. You have three threads, each of which can receive, then release and wait before intercepting the lock and continuing, as if the condition under which it was waiting was now false.

Possible scenario:

• Follower 1 enters the critical section (lock ()) block for Follower.
• Follower 2 approaches the critical section of Follower and is invited to wait.
• The king approaches the critical section of the Leader, and he is told to wait.
• Follower 1 sees that leaderGO is false and waits, releasing the lock in the critical section.
• The King, despite being the second in a row, “races” into a critical section ahead of Follower 2.
• The king continues (leaderGo is a lie, so King Never Wait () s) calls "One!" and sets the flag before releasing the lock at the end of the critical section.
• Follower 2 now “races” goes to the critical section before follower 1, sees the flag set, and continues, calling “Two!”. and exit from the critical section.
• Follower 1 now receives a turn, again locking the lock in the middle of its critical section. He no longer makes sure that the leader is false; he has already passed the test. Thus, it continues, also calls “Two!”, Sets the flag (to the value that was already) and exits.

There are many possible ways in which these threads can "race" based on how you configured it.

Here is something that might work a little better; it was called a double lock check, and although it is not reliable, it is much better than yours:

 private static readonly object syncObj = new object(); void Leader() { do { if(leaderGo) { Thread.Sleep(200); continue; } lock(syncObj) { //the "double-check"; here it not necessary because there //only one King to set leaderGo to true, //but it doesn't hurt anything. if(leaderGo) continue; //we won't get here unless we have control of //the critical section AND must do something. Console.WriteLine("> One!"); Thread.Sleep(200); leaderGO = true; } } while(true); } void Follower (char chant) { do { if(!leaderGo) { Thread.Yield(); continue; } lock(syncObj) { //this double-check is critical; //if we were waiting on the other follower to release //the lock, they have already shouted out and we must not do so. if (!leaderGO) continue; //we only get here if we have //control of the lock and should shout out Console.WriteLine("{0} Two!", chant); leaderGO = false; } } while(true); } 

EDIT: As mentioned in the comments, this model does not rely on luck, but it is not reliable because .NET for performance can allow multiple leaderGO instances to exist in different thread caches and synchronize them backstage. If .NET is not johnny-on-the-spot with this synchronization, a double check performed by a single thread may see the old, "outdated" state of the flag and move incorrectly when it should exit.

You can fix this in one of two simple ways:

• Place a MemoryBarrier immediately after any leaderGO update and immediately before any leaderGO reading. Memory items or “memory booms” that they can call in other languages ​​basically block each running thread on the memory barrier until all threads are placed in the memory barrier (or blocked in other ways), ensuring that all instructions are executed before execution any instructions before executing any commands.
• Declare leaderGO as volatile . The NET variable cannot be optimized; it is guaranteed to be in one place in memory, which is accessible, albeit inefficient, by any thread that will run this code. Therefore, any update to its value is immediately visible to any other thread.