Thread: "Dressing Room Problem" Code Review

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

    "Dressing Room Problem" Code Review

    So here is my latest project. It is pretty complex what with all the synchronization. Hopefully I've commented it enough for you to get the gist out of it works.
    I'm sure there are probably tons of little small problems. Feel free to point them out.
    Possibly there are bugs as well, so again feel free to point out how you would have done it.

    The code is below. I'm also attaching the files if someone finds that more convenient.

    Semaphore class:
    Code:
    #ifndef SEMAPHORE_20120219_1214
    #define SEMAPHORE_20120219_1214
    
    #include <boost/thread/condition_variable.hpp>
    #include <boost/thread/mutex.hpp>    
    
    class XSemaphore
    {
    	//The current semaphore count.
    	unsigned int m_count;
    
    	//mutex_ protects count_.
    	//Any code that reads or writes the count_ data must hold a lock on
    	//the mutex.
    	mutable boost::mutex m_mutex;
    
    	//Code that increments count_ must notify the condition variable.
    	boost::condition_variable m_condition;
    
    public:
    	explicit XSemaphore(unsigned int initial_count)
    	{
    		m_count = initial_count;
    	}
    
    	unsigned int get_count() const
    	{
    		//The "lock" object locks the mutex when it's constructed,
    		//and unlocks it when it's destroyed.
    		boost::unique_lock<boost::mutex> lock(m_mutex);
    		return m_count;
    	}
    
    	void up() //called "release" in Java
    	{
    		boost::unique_lock<boost::mutex> lock(m_mutex);
    		if (m_count == 1) // WORKAROUND
    			return;
    
    		++m_count;
    
    		//Wake up any waiting threads. 
    		//Always do this, even if count_ wasn't 0 on entry. 
    		//Otherwise, we might not wake up enough waiting threads if we 
    		//get a number of signal() calls in a row.
    		m_condition.notify_one(); 
    	}
    
    	void down() //called "acquire" in Java
    	{
    		boost::unique_lock<boost::mutex> lock(m_mutex);
    		while (m_count == 0)
    			m_condition.wait(lock);
    		--m_count;
    	}
    };
    
    class XSemaphoreLock
    {
    public:
    	XSemaphoreLock(XSemaphore& semaphore): m_semaphore(semaphore) { m_semaphore.down(); /*assert(m_semaphore.get_count() == 0);*/ }
    	~XSemaphoreLock() { m_semaphore.up(); /*assert(m_semaphore.get_count() == 1);*/ }
    
    protected:
    	XSemaphore& m_semaphore;
    };
    
    #endif
    Event class:
    Code:
    #include <tbb/atomic.h>
    #include "semaphore.hpp"
    
    class XEvent
    {
    public:
    	XEvent(bool initial_state): m_semaphore(initial_state ? 1 : 0), m_threadsafety(1)
    	{
    		if (!initial_state)
    			m_flag = false;
    		else
    			m_flag = true;
    	}
    
    	void wait()
    	{
    		m_threadsafety.down();
    
    		while (!m_flag)
    		{
    			m_threadsafety.up();
    			m_semaphore.down();
    			m_threadsafety.down();
    			m_semaphore.up();
    		}
    		
    		m_threadsafety.up();
    	}
    
    	bool get_status()
    	{
    		XSemaphoreLock lock(m_threadsafety);
    		return m_flag;
    	}
    
    	void signal()
    	{
    		XSemaphoreLock lock(m_threadsafety);
    		if (m_flag)
    			return;
    		m_flag = true;
    		m_semaphore.up();
    	}
    
    	void clear()
    	{
    		XSemaphoreLock lock(m_threadsafety);
    		if (!m_flag)
    			return;
    		m_flag = false;
    		m_semaphore.down();
    	}
    
    protected:
    	bool m_flag;
    	XSemaphore m_semaphore;
    	XSemaphore m_threadsafety;
    };
    synced_out class:
    Code:
    #include "semaphore.hpp"
    #include <string>
    
    class synced_out
    {
    protected:
    	std::string m_output;
    	static XSemaphore m_OutputMutex;	// Protects output to screen
    
    public:
    	template<typename T> synced_out(const T& output): m_output(boost::lexical_cast<std::string>(output)) {}
    	template<typename T> synced_out& operator << (const T& output) { m_output += boost::lexical_cast<std::string>(output); return *this; }
    	friend std::ostream& operator << (std::ostream& lhs, const synced_out& rhs)
    	{
    		XSemaphoreLock lock(synced_out::m_OutputMutex);
    		lhs << rhs.m_output;
    		return lhs;
    	}
    };
    Main program:
    Code:
    // Changing Room Problem.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include <boost/thread.hpp>
    #include <boost/date_time.hpp>
    #include <tbb/atomic.h>
    #include "semaphore.hpp"
    #include <boost/bind.hpp>
    #include <boost/lexical_cast.hpp>
    #include "Event.hpp"
    #include "synced_out.hpp"
    #include <vector>
    #include <cstdlib>
    #include <ctime>
    #include <random>
    #include <map>
    #include <utility>
    
    template<typename T>
    struct XAtomicContainer
    {
    	XAtomicContainer(): m_semaphore(1) {}
    	XSemaphore m_semaphore;
    	T container;
    };
    
    void Timer();
    
    XEvent g_NoMalesChanging(true), g_NoFemalesChanging(true);			// No males or females in the dressing room. We need mutual exclusion.
    XEvent g_OKToChangeFemales(true), g_OKToChangeMales(true);			// We sometimes need to block to ensure some new gender doesn't start changing (see XTimer)
    
    tbb::atomic<unsigned int> g_NumFemalesChanging, g_NumMalesChanging; // Keeps track of number females/males currently dressing. We need to keep track of the last one leaving the dressing room.
    tbb::atomic<unsigned int> g_NumFemalesWaiting,  g_NumMalesWaiting;	// Keeps track of number females/males currently waiting to dress. We need to keep track of the first one to wait.
    
    XSemaphore g_TurnLock(1);											// Protects g_FemaleTurn and g_MaleTurn
    
    struct XThreadData
    {
    	XThreadData() {}
    	XThreadData(boost::thread* thread, bool changing, float DetectionThreshold, int hp): Thread(thread) 
    	{
    		Changing = changing; 
    		this->DetectionThreshold = DetectionThreshold;
    		Hp = hp;
    	}
    	boost::thread* Thread;
    	tbb::atomic<bool> Changing;
    	tbb::atomic<float> DetectionThreshold; // How good females are at spotting males and how good males are at avoiding detection.
    	tbb::atomic<float> ChaseThreshold; // How likely females are at chasing males out of the dressing room
    	tbb::atomic<int> Hp;
    };
    
    XAtomicContainer<std::vector<XThreadData>> g_ThreadData;
    
    #define NO_INTERRUPTS { boost::this_thread::disable_interruption no_interrupts;
    #define NO_INTERRUPTS_END }
    
    template<typename T>
    class XAtomicInit
    {
    public:
    	XAtomicInit(tbb::atomic<T>& var, const T& value) { var = value; }
    	XAtomicInit(tbb::atomic<T>& var, T&& value) { var = value; }
    };
    
    
    // Starts up a timer to ensure one gender does not keep hugging the dressing room to themselves.
    // If the timer expires and the same gender is occupying the room as before, it will kick them out of there.
    class XTimer
    {
    protected:
    	boost::thread m_TimerThread;
    
    	void Timer(bool FemaleIsChanging)
    	{
    		try
    		{
    			XEvent* OKToChange;
    			if (FemaleIsChanging)
    			{
    				OKToChange = &g_OKToChangeFemales;
    			}
    			else
    			{
    				OKToChange = &g_OKToChangeMales;
    			}
    
    			try
    			{
    				boost::this_thread::sleep(boost::posix_time::time_duration(0, 0, 3));
    				OKToChange->clear();
    				boost::this_thread::sleep(boost::posix_time::time_duration(0, 0, 3));
    
    				for (auto it = g_ThreadData.container.begin(), end = g_ThreadData.container.end(); it != end; ++it)
    				{
    					if (it->Changing)
    						it->Thread->interrupt();
    				}
    
    				// SHOULD PROBABLY WAIT UNTIL ALL M/F THREADS HAVE ACTUALLY MANAGED TO STOP.
    			}
    			catch (const boost::thread_interrupted&)
    			{
    				// The gender currently changing finished in time. Do nothing.
    			}
    
    			//NO_INTERRUPTS
    			//OKToChange->signal();
    			//NO_INTERRUPTS_END
    		}
    		catch (const boost::thread_interrupted&)
    		{
    			assert(false); // Thread interrupted at wrong location
    		}
    	}
    
    public:
    	XTimer(bool FemaleIsChanging)
    	{
    		static XSemaphore lock(1);
    		XSemaphoreLock scoped_lock(lock);
    		m_TimerThread = boost::thread(&XTimer::Timer, this, FemaleIsChanging);
    	}
    
    	~XTimer()
    	{
    		m_TimerThread.interrupt();
    		m_TimerThread.join();
    	}
    };
    
    int synced_rand(int min, int max)
    {
    	static XSemaphore lock(1);
    	XSemaphoreLock scoped_lock(lock);
    	static std::mt19937 randomizer((unsigned long)std::time(nullptr));
    	int rnd;
    	do
    		rnd = randomizer();
    	while (!(rnd >= min && rnd <= max));
    	return rnd;
    }
    
    static tbb::atomic<int> g_id;
    
    void EnterDressingRoom(bool IsFemale, int id, int thread_id)
    {
    	try
    	{
    		std::string WordCapitalMaleFemale /* contains "Male" or "Female" */, WordOppositeMaleFemale /* contains "female" or "male" */, WordHeShe; /* contains "he" or "she" */
    		XEvent* GenderEvent;								// Signals when there are no more of the current gender changing
    		XEvent* OppositeEvent;								// Signals when there are no more of the OPPOSITE gender changing
    		tbb::atomic<unsigned int>* GenderChangingCount;		// Counts the number of the current gender changing. Used to know when the first of the gender enters and leaves the dressing room.
    		tbb::atomic<unsigned int>* GenderWaitingCount;		// Counts the number of the current gender changing. Used to know when the first of the gender enters and leaves the dressing room.
    		XEvent* GenderOKToChange;
    		XEvent* OppositeOKToChange;
    
    		if (IsFemale)
    		{
    			WordCapitalMaleFemale = "Female";
    			WordOppositeMaleFemale = "males";
    			WordHeShe = "she";
    			GenderEvent = &g_NoFemalesChanging;
    			OppositeEvent = &g_NoMalesChanging;
    			GenderChangingCount = &g_NumFemalesChanging;
    			GenderWaitingCount = &g_NumFemalesWaiting;
    			GenderOKToChange = &g_OKToChangeFemales;
    			OppositeOKToChange = &g_OKToChangeMales;
    		}
    		else if (!IsFemale/*IsMale*/)
    		{
    			WordCapitalMaleFemale = "Male";
    			WordOppositeMaleFemale = "females";
    			WordHeShe = "he";
    			GenderEvent = &g_NoMalesChanging;
    			OppositeEvent = &g_NoFemalesChanging;
    			GenderChangingCount = &g_NumMalesChanging;
    			GenderWaitingCount = &g_NumMalesWaiting;
    			GenderOKToChange = &g_OKToChangeMales;
    			OppositeOKToChange = &g_OKToChangeFemales;
    		}
    
    		for (;;)
    		{
    			NO_INTERRUPTS								// We must disallow interrupts to happen here. It can leave the function in an inconsistent state.
    			std::cout << (synced_out(WordCapitalMaleFemale) << " #" << id << " is trying to change!\n");
    			g_TurnLock.down();							// Make sure to use mutual exclusion here
    			
    			while (OppositeEvent->get_status() == 0 ||
    				GenderOKToChange->get_status() == 0)	// If opposite gender is changing, wait
    			{
    				g_TurnLock.up();
    				GenderOKToChange->wait();
    				g_TurnLock.down();
    				//std::cout << (synced_out(WordCapitalMaleFemale) << " #" << id << " was unable to change because there are " << WordOppositeMaleFemale << " in the dressing room!\n");
    		
    				// Give timer thread OK to start. This is to ensure that we do not wait forever. If one gender takes too long to change, and there is a queue with the opposite gender, then we must clear
    				// the currently changing ender so the other gender can start changing.
    				if (++*GenderWaitingCount == 1)
    				{
    					XTimer timer(!IsFemale);			// Constructor expects the gender who is currently changing
    					g_TurnLock.up();					// We MUST release the lock to allow other threads to process here.
    					OppositeEvent->wait();				// Wait until opposite gender has stopped changing
    				}
    				else
    				{
    					g_TurnLock.up();					// We MUST release the lock to allow other threads to process here.
    					OppositeEvent->wait();				// Wait until opposite gender has stopped changing
    				}
    
    				--*GenderWaitingCount;
    				g_TurnLock.down();						// We aren't finished yet, so grab the lock to allow for mututal exclusion.
    			}
    			
    			if (++(*GenderChangingCount) == 1)			// Increase the count of current number of individuals in dressing room. We need to keep track of the last one leaving.
    			{
    				OppositeOKToChange->signal();
    				GenderEvent->clear();					// Clear the signal that the current gender isn't changing (they will change now!)
    			}
    			
    			g_TurnLock.up();							// All finished. Release mututal exclusion lock.
    		
    			g_ThreadData.container[thread_id].Changing = true;
    			std::cout << (synced_out(WordCapitalMaleFemale) << " #" << id << " is now changing!\n");
    			NO_INTERRUPTS_END
    
    			// Simulate the dressing
    			try
    			{
    				int changing_time = synced_rand(1000, 10000);
    				while (changing_time > 0)
    				{
    					boost::this_thread::sleep( boost::posix_time::millisec(changing_time > 2000 ? 2000 : changing_time) );
    					std::cout << (synced_out(WordCapitalMaleFemale) << " #" << id << " is still changing!\n");
    					changing_time -= 2000;
    				}
    
    				std::cout << (synced_out(WordCapitalMaleFemale) << " #" << id << " has finished changing and is now leaving the dressing room!\n");
    			}
    			catch(const boost::thread_interrupted&)
    			{
    				std::cout << (synced_out(WordCapitalMaleFemale) << " #" << id << " was kicked out of the dressing room because " << WordHeShe << " was taking too long time!\n");
    			}
    
    			NO_INTERRUPTS							// Again, we must disable interrupts because it can leave the function in an inconsistent state.
    			g_ThreadData.container[thread_id].Changing = false;
    			if (--(*GenderChangingCount) == 0)
    				GenderEvent->signal();				// Signal that none of the current gender changing is now changing
    
    			int sleep = synced_rand(0, 10000);
    			boost::this_thread::sleep(boost::posix_time::millisec(sleep));
    			NO_INTERRUPTS_END
    		}
    	}
    	catch (const boost::thread_interrupted&)
    	{
    		assert(false); // Thread interrupted at wrong location
    	}
    }
    
    int main()
    {
    	g_NumFemalesChanging = g_NumMalesChanging = 0;
    	g_NumFemalesWaiting  = g_NumMalesWaiting  = 0;
    	g_id = 0;
    
    	std::srand((unsigned int)std::time(nullptr));
    
    	boost::thread_group threads;
    	for (int i = 1, thread_id = 0; i <= 10; i++)
    	{
    		auto * Thread = threads.create_thread(boost::bind(&EnterDressingRoom, true, i, thread_id++));
    		g_ThreadData.container.push_back(XThreadData(Thread, false, 10.0f, 10000));
    		boost::this_thread::sleep(boost::posix_time::time_duration(0, 0, 0, 500));
    		
    		Thread = threads.create_thread(boost::bind(&EnterDressingRoom, false, i, thread_id++));
    		g_ThreadData.container.push_back(XThreadData(Thread, false, 10.0f, 10000));
    		boost::this_thread::sleep(boost::posix_time::time_duration(0, 0, 0, 500));
    	}
    	threads.join_all();
    	return 0;
    }
    Attached Files Attached Files
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    What is the "problem statement" for the "dressing room problem"? Requirements etc...

    It's looks like a variation of the "unisex bathroom problem", but I'd rather have the problem stated instead of inferring it from the code

    gg

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Codeplug View Post
    It's looks like a variation of the "unisex bathroom problem", but I'd rather have the problem stated instead of inferring it from the code
    You can call it that, except change "bathroom" to "dressing room" (sounds better, if you ask me!).
    Only requirements are to use semaphores and ensure fairness.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> ... and ensure fairness.
    I assume that just means that no one is allowed to wait forever.

    Your solution seems a bit atypical, in that is kicks people out of the room, as apposed to ensuring every waiter eventually gets a turn (regardless of how long others are taking).

    Also, there's usually an upper bound on how many people can be in the room at any given time. I don't think I see anything like that, but I've only scanned the code briefly.

    gg

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The solution is actually supposed to be two-fold, though I have not tested that intensely... First it stops more people from being admitted into the room. The second takes care of the problem makers.

    Since there was no requirement on an upper bound, I have not implemented such a thing.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. An interesting code about "struct" in "union"
    By meili100 in forum C++ Programming
    Replies: 3
    Last Post: 04-08-2008, 04:37 AM
  2. Replies: 2
    Last Post: 03-13-2008, 11:34 AM
  3. Replies: 3
    Last Post: 04-30-2003, 03:17 PM
  4. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 08:25 AM
  5. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 07:59 AM