semaphore
jbwyatt.com
jbwyatt.com
.. critical sections
Process synchronization: ======================= Used resource must be locked from other processes until released A mistake could cause a deadlock Critical Section: ================= A part of a program that must complete execution before other processes can have access to the resources being used Processes within a critical region can’t be interleaved without threatening integrity of the operation
// FLAG to coordinate access while (flag set); // busy wait set flag - problem here?? CS clear Flag TEST and SET ============== An indivisible machine instruction executed in a single machine cycle to see if the key is available and, if it is, sets it to unavailable The actual key is a single bit that can contain a 0 (free) or a 1 (busy) A process P1 tests the condition code using TS instruction before entering a critical region If no other process in this region, then P1 is allowed to proceed and condition code is changed from 0 to 1 When P1 exits, code is reset to 0, allows other to enter
Modification of test-and-set designed to remove busy waiting Two new mutually exclusive operations, WAIT and SIGNAL WAIT is activated when process encounters a busy condition code (sem_wait) SIGNAL is activated when a process exits critical region and the condition code is set to “free” (sem_post) Semaphore: ========== Nonnegative integer variable used as flag and signals when a resource is free Two operations to operate the semaphore P (proberen means to test) P(s): If s > 0 then s: = s – 1 (sem_wait) (test, fetch, decrement, and store sequence) V (verhogen means to increment) V(s): s: = s + 1 (sem_post) (fetch, increment, and store sequence)
.. unix semaphores
( ref: h30097.www3.hp.com/docs/base_doc/DOCUMENTATION) Semaphores are used to control access to shared resources by processes. There are named and unnamed semaphores. Named semaphores provide access to a resource between multiple processes. Unnamed semaphores provide multiple accesses to a resource within a single process or between related processes. Resource is LOCKED if semaphore is ZERO. ======================================= The semaphore lock operation checks to see if the resource is available or is locked by another process. If the semaphore's value is a positive number, the lock is made, the semaphore value is decremented, and the process continues execution. If the semaphore's value is zero or a negative number, the process requesting the lock waits (is blocked) until another process unlocks the resource. Several processes may be blocked waiting for a resource to become available. The semaphore unlock operation increments the semaphore value to indicate that the resource is not locked. A waiting process, if there is one, is unblocked and it accesses the resource. Each semaphore keeps count of the number of processes waiting for access. Semaphores are global entities and are not associated with any particular process. In this sense, semaphores have no owners making it impossible to track semaphore ownership for any purpose, for example, error recovery.
Operations: ========== sem_close Deallocates the specified named semaphore sem_destroy Destroys an unnamed semaphore sem_init Initializes an unnamed semaphore sem_open Opens/creates a named semaphore for use by a process sem_post Unlocks a locked semaphore sem_unlink Removes a specified named semaphore sem_wait Performs a semaphore lock on a semaphore
Creating ======== The following example creates a semaphore named /tmp/mysem with a value of 3: . sem_t *mysemp; // name of semaphore int oflag = O_CREAT; // create if not there, else associate mode_t mode = S_IRUSR | S_IWUSR; const char semname[] = "/xyz" // must start with slash for processes to share mysemp = sem_open(semname, oflag, mode, 1); if (mysemp == -1) cout << "sem_open failed ";
Locking and Releasing ===================== // WAIT FOR ACCESS wait to enter CS if (sem_wait(semlockp) == -1) { cout << "wait failed named semaphore " << argv[1]; return 1; } //////////////////////////////////// C R I T I C A L S E C T I O N (file access) //////////////////////////////////// // RELEASE SEMAPHORE if (sem_post(semlockp) == -1) { cout << "Failed to release semlock\n"; return 1; } Closing - deallocates the semaphore ======= sem_close(semlockp); see jupiter|/export/home/wyatt/private/355/SemaphoreCorrect$ pico simple.cpp
.. code: controlling screen output **
Your code needs to:
1. get semaphore ( id = sem_open(name) )
2. wait for flag allowing access ( sem_wait(id) )
ENTER CS
...
COMPLETE CS
3. restore flag allowing others to access ( sem_post(id) )
4. close process association with semaphore ( sem_close(id) )
5. deallocate system sempahore ( sem_unlink (name) ) ** IMPORTANT
jupiter|/export/home/wyatt/private/355/SemaphoreCorrect$ cat simplest.cpp
#include <sys/wait.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <semaphore.h>
#include <fcntl.h>
#include <errno.h>
#include <fstream>
#include <iostream>
using namespace std;
//====================================
//
// NOTE: must use CC xx.cpp -l posix4
//
//====================================
int main (int argc, char *argv[])
{
// create if doesn't exist - don't use O_EXCL - fails if already created
int oflag = (O_CREAT);
// creator to open sem R/W, others open in R/W
mode_t mode = (S_IRUSR | S_IWUSR | S_IWOTH | S_IROTH);
unsigned int value = 1; // initial value - let procs in
sem_t *semlockp; // semaphore ID from system
int i, returnPid, fr, kids, reps;
ofstream out; // new file stream OUT
// GET ARGS - check for valid number of command-line arguments
if (argc != 4){
cerr << "Usage: " << argv[0]
<< " semaphorename(starts with / ex:/jw) repetitons(int) #kids\n";
return 1;
}
// GET REPETITIONS (how many chars to write) and # KIDS
reps = atoi(argv[2]);
kids = atoi(argv[3]);
// OPEN FILE - kids will have this also when forked
// out.open("out.txt",fstream::app); // append
out.open("out.txt"); // no append - start anew
// CREATE and GET SEM - kids will get this also when forked
semlockp = sem_open(argv[1], oflag, mode, value);
if (semlockp < 0) {
cerr << "\nFailed to create named semaphore " << argv[1];
return 1;
}
// CREATE KIDS - fork in loop (fan) - parent stays in loop
for (i=0; i<kids; i++) {
fr = fork();
if (fr == 0) // kids break here
break;
}
// WAIT FOR ACCESS wait to enter CS
if (sem_wait(semlockp) == -1){
cerr << "\nwait failed named semaphore " << argv[1];
return 1;
}
// *** C S START !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
out << endl << endl;
for (int ii=0; ii<reps; ii++)
out << i;
out << endl << endl;
cout << endl << endl;
for (int ii=0; ii<reps; ii++)
cout << i;
cout << endl << endl;
// *** C S STOP !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// RELEASE SEMAPHORE
if (sem_post(semlockp) == -1){
cerr << "Failed to release semlock\n";
return 1;
}
// get rid of semaphore
sem_close(semlockp); // deallocates
sem_unlink(argv[1]); // removes from the system
// close out file
out.close();
return 0; /// back to OS
}
.. sample screen output
wyatt/private/355/Semaphore$ make
CC -l posix4 simplest.cpp
jupiter|/export/home/wyatt/private/355/SemaphoreCorrect$ a.out /jw 60 9
000000000000000000000000000000000000000000000000000000000000
111111111111111111111111111111111111111111111111111111111111
222222222222222222222222222222222222222222222222222222222222
333333333333333333333333333333333333333333333333333333333333
555555555555555555555555555555555555555555555555555555555555
444444444444444444444444444444444444444444444444444444444444
999999999999999999999999999999999999999999999999999999999999
666666666666666666666666666666666666666666666666666666666666
888888888888888888888888888888888888888888888888888888888888
jupiter|/export/home/wyatt/private/355/SemaphoreCorrect$
777777777777777777777777777777777777777777777777777777777777
(this shell prompt is sometimes in middle of output - WHY?)
** NOTE 1:
tried this with 9 children each doing 25,000 outputs to a file
without interruption
**NOTE 2:
be careful on names of semaphores.
if someoe "BREAKS" a semaphore name (fails to close/unlink it), it may
NOT work right and you think your code is broken, but it is just
the d**g semaphore.
1. use different name
2. unlinking semaphore with old name will fix the old semaphore
(3 hours later...)
.. code: controlling file access (simpler sem_open())
This code has allowed 25000 lines of output using a shared file
with one file pointer shared via fork by 10 children processses and
the parent. There were no interruptions in the output file.
The semaphore (like the file open) is also shared by all processes
by being done BEFORE any fork() occurs.
Both the file.open() and the sem_open() ocur in the parent process prior
to creating any child processes.
================================================================
CODE: - NOTE: must use CC xx.cpp -l posix4 (semaphore ops)
================================================================
// don't use O_EXCL - fails if already created
int oflag = O_CREAT;
// creator to open sem R/W, others open in R/W
mode_t mode = (S_IRUSR | S_IWUSR | S_IWOTH | S_IROTH);
unsigned int value = 1;
sem_t *semlockp;
// GET SEM *BEFORE* FORK - share among kids
semlockp = sem_open(argv[1], oflag, mode, value);
if (semlockp == (void *)-1) {
perror("Failed to create named semaphore");
return 1;
}
// OPEN FILE *BEFORE* FORK - share among kids
// - leave open throughout...
...
// WAIT to enter CS
while (sem_wait(semlockp) == -1)
if (errno != EINTR) {
perror("Failed to lock semlock");
return 1;
}
////////////////////////////////////
C R I T I C A L S E C T I O N
(file access)
////////////////////////////////////
// RELEASE semaphore and exit CS
if (sem_post(semlockp) == -1) {
perror("Failed to unlock semlock");
return 1;
}
.. sample file output
jupiter|/export/home/wyatt/private/355/SemaphorePeace$forkSem.cpp
Well-behaved output - every process using semaphore and parent always goes first (grabs semaphore BEFORE forking: PpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPpPp 00000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000 33333333333333333333333333333333333333333333333333333333333333333333333333 33333333333333333333333333333333333333333333333333333333333333333333333333 11111111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111 44444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444444444444444444444444 22222222222222222222222222222222222222222222222222222222222222222222222222 22222222222222222222222222222222222222222222222222222222222222222222222222 55555555555555555555555555555555555555555555555555555555555555555555555555 55555555555555555555555555555555555555555555555555555555555555555555555555 99999999999999999999999999999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999999999999999999999999999 66666666666666666666666666666666666666666666666666666666666666666666666666 66666666666666666666666666666666666666666666666666666666666666666666666666 88888888888888888888888888888888888888888888888888888888888888888888888888 88888888888888888888888888888888888888888888888888888888888888888888888888 77777777777777777777777777777777777777777777777777777777777777777777777777 77777777777777777777777777777777777777777777777777777777777777777777777777
If i take the semaphore OFF the parent (Pp), this is what happens: If i take the semaphore OFF the parent (Pp), this is what happens: (note: parent does heavy computations after each Pp pair that is output) PpPpPpPpPpPpP88888888888888888888888888888888888888888888888888888888888888888888888888888888 66666666666666666666666666666666666666666666666666666666666666666666666666666666 99999999999999999999999999999999999999999999999999999999999999999999999999999999 pPpPpPpPpPpPpP33333333333333333333333333333333333333333333333333333333333333333333333333333333 22222222222222222222222222222222222222222222222222222222222222222222222222222222 44444444444444444444444444444444444444444444444444444444444444444444444444444444 555555555555555555555555555555555555555555555555555555555555555pP55555555555555555 9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9. pPpP77777777777777777777777777777777777777777777777777777777777777777777777777777777 pPpPpPpPpP8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8. pPpPpPpPpPpPpP5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5. pPpP6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6. pPpPpP1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1. pP7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7. pPpP0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0. pP3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3. pPpPp 4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4.4. 2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.