How to IMPLEMENT a Mutex in C++ ?
-
This looks like a school project, but it's not. Having used mutexes and semaphores a zillion times, "finally the time has arrived to write my own implementation for use in an embedded system without OS." :-( I did some research on the matter and I found Peterson's Algorithm (for 2 processes, threads or whatever) and Lamport's bakery algorithm (for N processes, threads or whatever). ;) There is no need to reinvent "hot water" again, an existing algorithm will do just fine. For info, Peterson's Algorithm: int flag[2] = { FALSE, FALSE } // flag[i] indicates that Pi wants to // enter its critical section. int turn = 0; // turn indicates which process has // priority in entering its critical // section. // mutexbegin: flag[i] = TRUE; turn = 1 - i; while (flag[1 - i] && turn == 1 - i) ; // mutexend: flag[i] = FALSE; Now Lamport's Bakery algorithm. Assumptions: NPROCS is the number of processes. max(int *array) returns the maximum value in array. Each process has a unique ID, so ties on the number chosen are broken by comparing IDs. Replace i with the appropriate process ID. // Global initialization: int choosing[NPROCS] = { FALSE }; int number[NPROCS] = { 0 }; // mutexbegin: choosing[i] = TRUE; number[i] = max(number) + 1; choosing[i] = FALSE; for (j = 0; j < NPROCS; ++j) { while (choosing[j]) ; while (number[j] != 0 && (number[j] < number[i] || number[j] == number[i] && j < i) ) ; } // mutexend: number[i] = 0; THE QUESTION: in the line number[i] = max(number) + 1; we see the function 'max'. How do I interprete this? I thought it meant the maximum of all the numbers in number[], but that does not seam to work. Also, any suggestions on writing a bool CPP_Mutex::TryEnter(unsigned int PNumber) function ? Any input or pointers greatly appreciated! :cool: NOTE: I know this class produces what is called a "spinning lock", but that's OK. I tested it with a dual processor machine with the following code: #define NPROCS 2 #undef Max #define Max(A,B) ((A)<(B)?(B):(A)) // Implementation of LAMPORTS Bakery Algorithm class CPP_Mutex { public: CPP_Mutex() { memset(m_nChoosing, 0, sizeof(int)*NPROCS); memset(m_nNumber, 0, sizeof(int)*NPROCS); } ~CPP_Mutex() { } void Enter(unsigned int PNumber) { m_nChoosing[PNumber] =
-
This looks like a school project, but it's not. Having used mutexes and semaphores a zillion times, "finally the time has arrived to write my own implementation for use in an embedded system without OS." :-( I did some research on the matter and I found Peterson's Algorithm (for 2 processes, threads or whatever) and Lamport's bakery algorithm (for N processes, threads or whatever). ;) There is no need to reinvent "hot water" again, an existing algorithm will do just fine. For info, Peterson's Algorithm: int flag[2] = { FALSE, FALSE } // flag[i] indicates that Pi wants to // enter its critical section. int turn = 0; // turn indicates which process has // priority in entering its critical // section. // mutexbegin: flag[i] = TRUE; turn = 1 - i; while (flag[1 - i] && turn == 1 - i) ; // mutexend: flag[i] = FALSE; Now Lamport's Bakery algorithm. Assumptions: NPROCS is the number of processes. max(int *array) returns the maximum value in array. Each process has a unique ID, so ties on the number chosen are broken by comparing IDs. Replace i with the appropriate process ID. // Global initialization: int choosing[NPROCS] = { FALSE }; int number[NPROCS] = { 0 }; // mutexbegin: choosing[i] = TRUE; number[i] = max(number) + 1; choosing[i] = FALSE; for (j = 0; j < NPROCS; ++j) { while (choosing[j]) ; while (number[j] != 0 && (number[j] < number[i] || number[j] == number[i] && j < i) ) ; } // mutexend: number[i] = 0; THE QUESTION: in the line number[i] = max(number) + 1; we see the function 'max'. How do I interprete this? I thought it meant the maximum of all the numbers in number[], but that does not seam to work. Also, any suggestions on writing a bool CPP_Mutex::TryEnter(unsigned int PNumber) function ? Any input or pointers greatly appreciated! :cool: NOTE: I know this class produces what is called a "spinning lock", but that's OK. I tested it with a dual processor machine with the following code: #define NPROCS 2 #undef Max #define Max(A,B) ((A)<(B)?(B):(A)) // Implementation of LAMPORTS Bakery Algorithm class CPP_Mutex { public: CPP_Mutex() { memset(m_nChoosing, 0, sizeof(int)*NPROCS); memset(m_nNumber, 0, sizeof(int)*NPROCS); } ~CPP_Mutex() { } void Enter(unsigned int PNumber) { m_nChoosing[PNumber] =
Out of curiosity, how are you getting multiple threads if you don't have an OS? Also, if this is an x86 processor, you can use the SMP correct incrementers in x86 assembler. These are instructions which guarantee that they will execute fully before allowing access. IIRC they are instructions such as XADD or something similar.
-
Out of curiosity, how are you getting multiple threads if you don't have an OS? Also, if this is an x86 processor, you can use the SMP correct incrementers in x86 assembler. These are instructions which guarantee that they will execute fully before allowing access. IIRC they are instructions such as XADD or something similar.
A Problem with the previously mentioned algorithms is that they assume "atomic" read and write operations. I also found this solution which is, like you say is dependent on "undividable" processor instructions. // ALGORITHM //////////// // wait(s) // { set s = 0 and if old value of s was 0 then // repeat // 'wait' // until set s = 0 and old value of s was 1 } // signal(s) // { s = 1; Tell OS if appropriate } Concerning, "how are you getting multiple threads if you don't have an OS?". From my perspective (WinNT/W2K backend programmer, now engaged in building software for a NO-OS device), the device we are building has two "tasks" ("Threads"). It has a slow main loop (task 1) which can be 'interrupted' ("pre-empted") by the driver level (task 2..N). The idea is to have the driver level handle the Hardware dependent stuff, e.g. detect if a keypad button that was pressed, and put it in an event queue for the slow main loop to process. If my main loop can get interrupted at any time, I need some protection (locking) on the queue, otherwise it will get corrupted. (if it is locked by the main loop, I could put the event in a temporary queue and put it in the real queue some time later (ASAP of course) ) The standard way of avoiding corruption is: mutex_begin() { disable_interrupts(); } mutex_end() { enable_interrupts(); } Which of course could lead to "event loss". The algorithm above (based on TestAndSet) is an improvement over this, but it needs to be supported by processor instructions. Since I am not a whizz kid in assembler (let's be honest, I never had to use it before so I never did), I am gratefull for any pointers or assembler crash courses that anyone can give me about these undividable SMP safe (i386) instructions I could use to implement a Test And Set function. // MSDN example int power2( int num, int power ) { __asm { mov eax, num ; Get first argument mov ecx, power ; Get second argument shl eax, cl ; EAX = EAX * ( 2 to the power of CL ) } /* Return with result in EAX */ } // my would-be function that sets a value (nValue) on the target address (pTargetAddress) and returns the previous value (that was found in pTargetAddress) int testandset(int* pTargetAddress, int nValue) { __asm ... // help ! } Best regards, Gert.
-
A Problem with the previously mentioned algorithms is that they assume "atomic" read and write operations. I also found this solution which is, like you say is dependent on "undividable" processor instructions. // ALGORITHM //////////// // wait(s) // { set s = 0 and if old value of s was 0 then // repeat // 'wait' // until set s = 0 and old value of s was 1 } // signal(s) // { s = 1; Tell OS if appropriate } Concerning, "how are you getting multiple threads if you don't have an OS?". From my perspective (WinNT/W2K backend programmer, now engaged in building software for a NO-OS device), the device we are building has two "tasks" ("Threads"). It has a slow main loop (task 1) which can be 'interrupted' ("pre-empted") by the driver level (task 2..N). The idea is to have the driver level handle the Hardware dependent stuff, e.g. detect if a keypad button that was pressed, and put it in an event queue for the slow main loop to process. If my main loop can get interrupted at any time, I need some protection (locking) on the queue, otherwise it will get corrupted. (if it is locked by the main loop, I could put the event in a temporary queue and put it in the real queue some time later (ASAP of course) ) The standard way of avoiding corruption is: mutex_begin() { disable_interrupts(); } mutex_end() { enable_interrupts(); } Which of course could lead to "event loss". The algorithm above (based on TestAndSet) is an improvement over this, but it needs to be supported by processor instructions. Since I am not a whizz kid in assembler (let's be honest, I never had to use it before so I never did), I am gratefull for any pointers or assembler crash courses that anyone can give me about these undividable SMP safe (i386) instructions I could use to implement a Test And Set function. // MSDN example int power2( int num, int power ) { __asm { mov eax, num ; Get first argument mov ecx, power ; Get second argument shl eax, cl ; EAX = EAX * ( 2 to the power of CL ) } /* Return with result in EAX */ } // my would-be function that sets a value (nValue) on the target address (pTargetAddress) and returns the previous value (that was found in pTargetAddress) int testandset(int* pTargetAddress, int nValue) { __asm ... // help ! } Best regards, Gert.