The purpose of this lab is to introduce you to some typical problems of synchronisation and how they can be solved with semaphores. You will be shown how to use System V style semaphores supplied by UNIX as well as writing a partial semaphore implementation yourself. The context of this lab is largely in problems of interprocess communication, and you will be shown how to use System V style shared memory for that.
This lab sheet contains a lot of explanation. As such, it is much longer than it needs to be to just give instructions. Part of the reason for all this explanation is in case some classes do this exercise before the relevant material has been covered in lectures.
The lab is divided into sections, and these sections do not always build on each other. You are required to keep your solution from every section so your demonstrator can mark it.
You must complete this lab to pass it.
In many parts of the lab you will be writing large amounts of test data to files. You should remove these files when you are finished so that they do not take up valuable disk space.
In the previous lab you were shown how to create a pipe with the pipe() function, and you saw that this function returns file descriptors so that the pipe can be treated as a file. Something similar can be set up manually in the user environment with the mkfifo command (there is also a function with the same name which does the same thing, but it is easier to use the command for this section). This command, given a filename, creates something that looks like a file with that name, but is in fact a pipe, and this is indicated by a `p' at the beginning of the file mode (`d' is for directories, `-' is a normal file). Writes to the pipe send data into it, at the back of the queue, and reads from it take data off the front.
Create a pipe. In one window, redirect the output of cat into it, and in another window, redirect the input of cat to come from it. The first cat is a `producer' for the pipe, and will be reading from standard input, so type something in that window. Once you press return, you should see that line appear in the second window, where the other cat is acting as a `consumer' , taking things from the pipe. Type a few lines, and then end the input with ^D, which causes EOF. Both instances of cat should exit, since the EOF condition is transmitted through the pipe. Make sure you are able to do all of this, since the rest of the lab depends on you understanding it.
To really `stress test' the pipe, repeat the previous redirections, except redirect the input of the producer to come from a large binary file, such as the executable for emacs, and redirect the output of the consumer to go to a file. After some time both programs should complete, having transmitted the file through the pipe. Verify that the transmission was successful by comparing the new file with the original using cmp.
It is worth noting that the correct tool for the job of redirecting data like this is the command dd, but cat is traditionally used.
The pipe can be removed as a normal file would be.
The simplest way for two processes to communicate is with shared memory. This is some region in memory that they both can access, so one process can give data to another by leaving it in that region for the other to `pick up'. The problem with shared memory is that it violates the basic memory protection of UNIX, and indeed many other operating systems, so it must be created and used in a very controlled manner.
For this part of the lab, you will write three separate programs. The first program allocates some shared memory, and gives the addresses of it. The other two will be the producer and consumer, and will need to be given the addresses output by the allocator. The aim is to have your programs behave the same way as the producer and consumer with the pipe in the first section.
When allocating shared memory, it is important to note that it remains allocated even after the program has terminated. In other words, it is persistent, and you should run the allocator as little as possible. At any time, you may check what shared memory you have allocated with the command ipcs. This command will also display allocated semaphores and queues, but you don't need to worry about these yet.
You should periodically clean up the shared memory you have
allocated using the command ipcrm. A fast way to remove every
bit of shared memory you have priviledges for is
ipcs -m | awk
'{print $2}' | xargs -n1 ipcrm -m
Keep in mind, however, that
this will remove as much as possible, including shared memory
allocated by programs you didn't write. Although it is uncommon for
programs to use shared memory, it is possible you may have run a few.
When using ipcs you may also see shared memory for other users, including root since the X server sometimes uses it.
To allocate your own shared memory, use shmget(). Indicate the memory segment is new instead of giving a key, and request memory for an array of 15 ints. You should also specify permissions that allow you to read and write the memory, but nobody else. These permissions are given using chmod style numbers.
You need to print out the identifier returned by shmget() so that you can use it with other programs. After you've written and run the allocator once, take note of this identifier, find the memory in the output of ipcs and check its permissions. Once you are happy with the memory you have allocated, you are ready to write the producer and consumer.
The first thing the producer needs to do is connect to the shared memory that has been allocated. This is called attaching, and is done with shmat(). It needs the identifier output by the allocator, but you cannot give this on standard input. Remember the aim is to have these programs behave the same way as in the first section, so we will be using standard input to send data to the producer. Consequently, you should give the identifier on the command line for your program, as the first argument.
When the memory is successfully attached, you will have a pointer to it. Program your producer to input some characters and write it to the shared memory. You need to do this in a loop which reads in one character at a time and writes it out to each element in the array, which is working as a buffer between the producer and consumer. Once input ends with an EOF, store the EOF in the buffer also. This is possible because it's an array of ints instead of chars, and the EOF can then be used to mark the end of input for the consumer.
After storing the data in the buffer, the producer can exit.
The consumer needs to begin by attaching to the shared memory too, so copy this part of the program from your producer. Next, read the characters from the buffer and print them out, also doing this one character at a time. The consumer should exit when it reaches the EOF element.
Run the producer and enter some characters, pressing return and then ^D to end the input. Make sure you enter fewer than 15 characters so that the buffer is not exceeded. Then run the consumer. Repeat this a couple of times to make sure everything is working.
Now try running your producer in one window and, before entering any characters, running your consumer in another, just like was done in the first section. The consumer should print out some characters and then exit, without waiting for you to type anything into the producer. This is, of course not the correct behaviour.
The consumer needs to be made to wait until there are characters to be consumed, and the easiest way to do this is to create a counter, also in shared memory, that keeps track of the number of unconsumed characters.
Modify your allocator to reserve space for this counter. You may like to reserve the space in addition to the buffer so that the allocator reserves both if you have to stop work on the lab and come back to it later, but be aware that you will end up with two buffers if you run the new allocator immediately. You should remove the old buffer before doing so.
In both the producer and consumer, add code to attach to this counter, which is in a separate place in memory and will need to be given as a second argument.
In the producer, before entering the loop, initialise the shared counter to 0, since there are no characters to begin with. Then inside the loop, every time a character is written to the buffer, increment the counter. Do not use the counter as the buffer index. You should already have a variable for this purpose, and you need to keep it separate.
The consumer needs to wait every time it tries to get a character from the buffer if there is nothing to get, and so the code for this wait will be the very first thing in the main loop. The easiest way to make the wait happen is with a loop that does nothing except check the value of the shared counter. Such a loop is called a `spinlock', because the process `spins' in the loop while waiting, and is a type of busy waiting because the loop uses CPU time to execute.
Write this loop so that it exits when the counter indicates there is something in the buffer. Immediately following the loop, decrement the counter since the rest of the main loop is going to consume one character. Once again, you should be keeping the buffer index apart from the counter.
Repeat what failed before. Run the producer and, before typing anything, run the consumer. The consumer should wait this time. Type two characters and press return. The consumer should print them out. Type two more and press return. They should then be printed out.
The next problem is that with each character you type, the producer and consumer move further along the buffer, and will eventually run off the end of it. To see this, send a large file into the producer. It will quickly run off the end and cause an error. The consumer should do the same when you run it after having run and got the error from the producer. To fix this the buffer needs to be `reused'. That is, when either the producer or the consumer reach the end, they need to go back to the beginning.
Program this behaviour any way you choose, although incrementing the array index modulo the buffer size is the usual way. Then test it by sending a large file into the producer again. Although you shouldn't get the same error now it is unlikely you will have time to run the consumer before the producer terminates. This means there will be an EOF sitting in the buffer and you will be unable to test the consumer for the buffer overrun problem.
To prevent the producer's EOF and
test the consumer, do
cat testfile - | ./your_producer
This
will prevent the producer finishing by having it wait for keyboard input
after writing the testfile into the buffer, and allow you to run the
consumer to make sure that it's not running off the end of the buffer either.
Type a single line into the producer which is longer than 15 characters. It is likely that something strange will happen to the consumer, although it's possible to be lucky. You should keep trying until you observe a failure.
What has happened is that the producer filled the buffer and, without waiting for the consumer, overwrote some unconsumed characters. The solution is to create a second shared counter, this time to represent the amount of space left in the buffer.
(It is possible to do this section without a second counter, but that makes a later section very difficult.)
Change your allocator again to make space for a second counter. You can do this by either a separate piece of shared memory, or making the counter you already have into an array of two counters. The advantage of the latter approach is that it saves you a third command line argument for the producer and consumer. If you prefer the other method, don't forget to add code in the producer and consumer to attach to this new piece.
In the producer, before the main loop, initialise this new counter to the size of the buffer. At the start of the main loop, add a `do nothing' loop that waits on this counter until there's space in the buffer. Immediately following the loop, decrement the counter for the space that's about to be used.
In the consumer, at the end of the main loop after a character has been consumed, increment the new counter to indicate some space has been made available.
The producer and consumer should be somewhat symmetrical now, with the producer waiting for space at the start and the consumer waiting for characters. At the end of the producer it should indicate an extra character, whereas the consumer will indicate extra space.
Test this final version by typing in one very long line of characters. The consumer should output it correctly. Nevertheless, the worst problem remains and there is a chance it may not manage the whole line (although it should manage most). There is an even greater chance that subsequent lines will not work.
Now that your producer and consumer are mostly working, conduct the stress test from the first section with them, and compare the resulting file with the original using cmp again. It is likely they will be different (an EOF doesn't count), but if not, reduce the size of the buffer and repeat the test until you see a problem. As well as a difference in data, the file sizes might be different.
The problem affecting your programs now is known as the mutual update problem, and concerns the shared counters. An increment or decrement on these counters involve a load of the current value, an arithmetic operation, and then a store of the new value, and if both the producer and the consumer attempt this on the same counter at the same `time' (the instructions really take turns), then the counter value becomes corrupted. Specifically, both processes can load the same value for the counter, alter it, and then write it back. One of those alterations will be lost, overwritten by the other, when instead that other process should have waited until the new value of the counter was available, and loaded that.
The solution is to make operations on a counter `atomic', i.e. when one process is in the middle of modifying the counter, it cannot be interrupted. This is done by making operations on a counter mutually exclusive for the two programs - only one of them will be able to use a counter at a time. This is exactly the same idea as locking a file for writing. Having two programs write to a file at the same time would also cause problems of mutual update.
The mutual exclusion will be implmented using semaphores - one for each counter. This works because the semaphore operations provided by the operating system are themselves atomic, and no process is allowed to interrupt them. Since the interface to System V semaphores is more involved than the traditional wait() and signal() calls (which don't exist in System V), the first step will be to implement those traditional functions using the functions provided by the operating system.
You should write these functions in a separate .c file so that the producer and consumer programs can both use them.
Just like shmget() is used for shared memory, semget() is used for semaphores, and is used nearly the same way. The only difference is that instead of giving the size of the memory, you give the number of semaphores you want to allocate. For this lab we need two semaphores, but it is easier to allocate them separately, so call semget() twice, requesting one semaphore both times.
Modify your allocator to allocate these semaphores in addition to the buffer and counters. Don't forget to clean up what you've already allocated before running your allocator again. Semaphores are removed using ipcrm also.
The semaphores are binary semaphores as they will only need two values for mutexing: `locked' and `unlocked'. These values will be 0 and 1 respectively, and so both semaphores need to be initialised to 1. The way to do this is with the semctl() function, which needs the semaphore identifier and the number of the semaphore to be operated on. Since we only allocated one semaphore per identifier, this number will always be 0.
The producer has contained the initialisation code for everything else, so put the two semctl() calls in there also. This means that the producer will always need to be run before the consumer, but this is adequate for the lab.
The function wait() traditionally doesn't return anything, and has
one argument which is the semaphore to be waited for. We will use the
identifier to indicate this, so the function looks like
void
wait(int);
To implement the wait you will need to use the function semop(). This requires the semaphore identifier, an array of semaphore operations to be performed, and the size of the array. We are only doing one operation, so allocate an array of one struct to hold it. The struct contains the number of the semaphore to be operated on (0 again), the operation, and some flags. For a wait, the operation is to decrement the semaphore so that it becomes 0 (locked). No flags are needed.
The signal() is identical to wait() except it increments the semaphore so that it becmoes 1 (unlocked).
Pick which semaphore will protect which counter, and in both the producer and consumer use a wait() just before changing the counter and a signal() immediately after changing it. There needs to be as few lines as possible within the wait()/signal() pair to prevent deadlock, which is where the two processes are stuck waiting for each other, so make sure they only guard code that is involved with changing the counter.
Repeat the stress test and the file comparison. It should work perfectly now, no matter how small you make the buffer. A larger buffer will work faster, however, and you may wish to try this.
As mentioned above, the mutex semaphores are binary semaphores since they only have two values. In general, however, semaphores can take on any value from 0 and up (some semaphores can even go negative). These are called counting semaphores, and binary semaphores are just a special case of them.
Counting semaphores can be implemented using binary semaphores, and what you've already done in this lab is very close to that. The shared counters can be interpreted as the counting semaphores, and the spinlock immediately followed by the decrement does the waiting and decrementing required by a counting semaphore wait(). The increment on its own is a signal(). The only problem is if two processes tried to wait on the same semaphore at the same time; they could both get through the spinlock and both decrement the counter, when only one of them should have. An additional mutex solves this problem, and is discussed in most textbooks.
If you consider the counters, when protected, to be counting semaphores, and remember that OS-provided semaphore operations are atomic and so have their own protection, you should realise that, using real counting semaphores instead of the shared counters, we can get rid of the mutex semaphores.
Do exactly this by changing the initialisation of the two semaphores so they behave like the counters, and call your wait() function when you need to decrement a counter and signal() when you need to increment it. The two semaphore functions you wrote do not need to be changed. Since the two mutex semaphores have essentially replaced the counters now, remove the counters and their spinlocks. Once this is done, you should test the result again.
Any use of a semaphore can (and should) be viewed as a means of keeping track of the number of available instances of a resource. In the case of our counting semaphores there are two types of resources used by the producer and consumer: space in the buffer and characters in the buffer. The producer decrements the amount of space, but will wait until space is available if it has to. This is why the wait operation does the decrement. The producer also increments the character count, and will signal the presence of a new character in case the consumer was waiting for one. This is why signal does the increment.
Even the binary semaphores we used can be seen as counting a resource; that resource is the number of processes that can modify the counter at any one time. When we initialise the semaphore to 1, we are saying only one process at a time can do this, which is the idea of mutual exclusion. When a process waits for this resource, it will decrement that counter so that 0 processes can modify the counter during that time. When the processes finishes, it signals to indicate that 1 process may now modify the counter.
Although this completely explains the semaphore itself, there is more to a semaphore implementation. Firstly, multiple processes may end up waiting, and to ensure bounded waiting for each of them they are usually queued. Using a spinlock for all of them means that the next one through would be chosen randomly, and one of them might wait for a long time. Secondly, when operating systems provide the semaphores there is the option of doing a non-busy wait. Since the operating system is in charge of process scheduling it can force a process to wait by just not executing it. This saves the time that would be wasted by a busy wait like a spinlock.
Even considering all of this, it is not always easy to tell what the `resources' are, particular when the problem is only a matter of timing.
A traditional text animation to show a program is still progressing is the spinning wheel, which is achieved by the characters |, /, -, \ being repeatedly output, overwriting each other.
Write a program that displays this spinning wheel, using an infinite loop. To overwrite the characters you should use carriage return (`\r') instead of newline after each character, which will return the cursor to the beginning of the same line instead of going to the next line. Also, to make sure that the character is really being output when it's printed, do fflush(stdout) after every character.
To make the animation slow enough for the naked eye, put delay loops in between each character output. These loops do nothing, much like the spinlocks before, but loop a specified number of times and are usually for loops. You might need to use a long int to make the number large enough to slow the animation.
Create a copy of your program, but without the delay loops. The aim of this exercise is to synchronise this undelayed wheel with the delayed one so that they appear to display the same character at the same time. Since you will be using a semaphore, you will need to allocate it appropriately using a separate allocator program.
To begin with, create a semaphore that the undelayed wheel can wait for each time through the loop. The delayed one will need to signal it. The wheels should now be synchronised once every cycle, although the undelayed wheel will probably look like the same character all the time. Next, instead of putting the delay loops back in, make it wait for each character of the delayed wheel. You will not need more than one semaphore to make the wheels spin together since if the signalling wheel gets ahead, the waiting wheel will soon catch up.
As mentioned earlier, the update of a counter is broken up into a load, a change, and a store. If two processes engage in this three step process at the same time, one of the changes will be overwritten. This can be hard, if not impossible, to see while it is happening, and the aim of this section is to cause the problem to happen deliberately, and slowly.
Write two programs that share a counter. Have one program do the three steps, printing out the value of the counter after each step, but write it so that it waits for the user to press return after each step. That way the progress is controlled. Write the second program to also do the steps and print out values, but instead of waiting for return make it wait for a semaphore that is signalled in the first, just like you had in the spinning wheels exercise.
You should be able to clearly demonstrate a corruption of the counter when both programs try to update it.