What would happen if Avis tried to rent a car to two persons at a time or if Amtrak sold one train seat to two people in one trip? Disasters!!! Do you think they never happen? Why not?! In the old days, when every thing was done manually, these incidents wouldn't happen. Nowadays, we usually use computers to buy a train seat or rent a car. Assume two people are simultaneously trying on line ticket purchasing from Amtrak. The system shows one seat available. Does the system sell the seat to both of them? How does the system avoid doing so?

Now, assume Alice is trying to deposit some money while her husband, Bob, is withdrawing some amount, both approaching different ATMs at the same time. Alice and Bob are using "one shareable resource" that is the bank database "simultaneously". Will their bank account balance be messed up? Let's take a closer look. A deposit or withdrawal is not done in a unitary fashion in computers. We, as human beings, may think a deposit is just one single atomic function, but it is not! A bank ATM implements a request (deposit/withdrawal) in the following way: download balance from the bank database, add deposit (or subtract withdrawal) amount, upload result to the bank database. If all three steps of one request take place before or after all three steps of the others request, the final balance will be correct. Assume Alice is making a $200 deposit while Bob is trying to make $200 withdrawal and the current balance is $50. Suppose Alice's request is processed first. Current balance of $50 is downloaded, $200 is added, and new balance of $250 is uploaded to the bank database. Right after this, Bob's request is handled. Current balance of $250 is downloaded, $200 is subtracted, and new balance of $50 is uploaded. This is correct. Now, if Bob's request is processed first, the result will be different. Current balance of $50 is downloaded. This amount is less than $200. Therefore he fails to withdraw the money. Then Alice's request is handled and as a result the new balance is $250. This is correct, too. Well, the answers are both predictable and correct. There is a "race" over using the bank database (a shared resource for both ATMs), but this is not an unwanted "race". In other words, the result depends on which request is processed first, but both results are correct.

Now suppose an account balance is $500. Alice is making $200 deposit while Bob making $200 withdrawal simultaneously (step 1). There is again a "race" over using the bank database. The correct result after implementing both requests must be $500. What would happen if the steps of two requests interleaved in time? To reply to Alice's request, balance ($500) is downloaded (step 2), then $200 is added to it (step 3). But before uploading this amount to the bank ATM, system starts handling Bob's request. Current Balance ($500) is downloaded (step 4).

Then $200 is subtracted from it (step 5). Then the system goes back to Alice's request again to upload the result that is $700 (step 6). Going back to Bob's request, then, the result ($300) is uploaded to the bank ATM (step 7). The final balance is $300 (step 8)!

What a loss! This problem is called "exclusive use". You don't want this to happen to you, do you? A different scenario may happen, too. Suppose the system first takes the first two steps of implementing Bob's request (downloading $500 and subtracting $200 from it) and then goes on with taking the first two steps of implementing Alice's request (downloading $500 and adding $200 to it). Then it goes back to Bob's request and takes the last step that is uploading $300. After all, it takes the last step of implementing Alice's requests and uploads $700. This is the new balance. Well, now you don't mind it but the bank doesn't like it! The results are neither correct nor predictable. We need to avoid such a "race".

Solution I. Mutual Exclusion: A Great Idea!

Well, we know that if all the steps of implementing a request (that is to use a sharable resource) follow each other without any external interruption, the result will be as desired. The problem arises when the steps of replying two or more requests interleave each other. The parts of programs that use a shared resource (e.g. bank database) are called "critical sections". Therefore, when one process is in "critical section", other's entrance to "critical section" at the same time will result in incorrect data. This is what to be avoided. In fact, if no more than one process were allowed to be in critical section at a time, no problem would happen. This is the great idea that can take care of the problem. This great idea is called "mutual exclusion".

Solution II. Using Semaphores: A Great Idea!

First Story:

For their research papers, students of a class have to use an old book of which there is only one copy in the small library of the class. They all have to "share" this book and borrow it one at a time. They don't have any electronic database to find out if the book has been checked out. They come up with some set of "rules" for checking out the book so that one person can borrow it at a time and inform others that the book is not available. They decide to signal each other by some symbol (the word, "flag") on a sheet of paper. When the book hasn't been checked out, "flag = 0" is on the sheet. When one wants to check out the book, s/he checks what is on the sheet (i.e. what is "flag" equal to?). If "flag = 0" is on it, s/he erases "flag = 0" and changes the message into "flag = 1" and then checks out the book. Then, one willing to check out the book, finding "flag = 1" should wait. He has to keep going to the library and checking "flag". He may do this several times before being able to actually check the book out. We can call this "busy waiting". When the first person checks the book back in, changes the message into "flag = 0". This lets next person (finding "flag=0") check out the book, following the same rules. With this rule, checking and changing the message is done as two indivisible parts of an action. One person holding the sheet checking the message does not let any body else does so at the same time.

How these students manage borrowing the book resembles with how "mutual exclusion" is achieved using "TEST AND LOCK" (TSL) instruction in a computer. Processes trying to use a shared resource keep checking the "flag" (do busy waiting) to see if it is clear and if they can set it then and enter their critical section. They do this through TSL instruction. TSL is indivisible, only one process can pass it at a time. It does not let any other process check or set "flag" while another one has been already doing so.

Well, this was a solution, but not a very good one! A major problem with this kind of solution was "busy waiting". Each process might have to keep checking the flag and therefore use computer's resources for a long time without doing anything productive. It was not efficient. It was very hard to manage "mutual exclusion" while making sure all processes get the chance to get into the critical section and no process is waiting to enter the critical section while the shared resource is free. Therefore, computer scientists wanted a better solution, a "great idea"! In 1956, E. W. Dijkstra found it. His "great idea" was to use a new variable type, called "semaphore". To see how this idea works, look at the other way the students of our story found to manage borrowing the book.

Second Story:

The students realized it was just a waste of time to keep checking the flag to see if the book was available. So they came up with a better idea! They assigned a librarian who would make a list of people trying to borrow the book on first come first served basis (a queue). There is also a flag. When it is 1, it means the book is available. The first person coming, finding flag =1, checks out the book as the librarian's list is empty, and sets the flag to 0. The second (third and so on) person trying to borrow the book, finds out the book is not available (as flag = 0), so his name goes into the librarian's list. As soon as the book is checked in, flag is set to 1 again, and the librarian calls the first person in the list to borrow the book. The person comes upon the librarian's call, the book is checked out and the flag is set to 0. This process goes on until the queue is empty. This method works even when there is more than one copy of the book in the library. In the case of two or more books, the flag is initially equal to the number of books. Everyone finding it nonzero checks a copy of the book out and decrements the value of the flag. When the flag is 0, there are no more books available and people's names go into the librarian's queue. As soon as one book is checked in, the flag is incremented, and first person in the queue gets the librarian's call to come and check out the book.

In the same way "semaphores" carry out mutual exclusion. Processes are sent to "sleep" when the shared resource is not available the same way people sent back home when the book is not available. Then the operating system gives the process a "wake up" call when the resource becomes available the same way the librarian calls the person to go to the library and check out the book. Incrementing and decrementing the semaphore is also done in a similar manner. A semaphore is an integer variable that, apart from initialization, is accessed only through two standard operations: WAIT and SIGNAL. The WAIT operation checks the value of the semaphore to see whether or not it is greater than 0. If it is, the process can go to the critical section after the value is decremented; if it is not, the process is put to sleep (in a waiting list). The SIGNAL operation increments the value of the semaphore. If one or more process were sleeping on that semaphore, unable to complete an earlier WAIT operation, one of them is chosen and allowed to complete its WAIT. These two operations must be executed indivisibly. Checking the value of semaphore, changing it, and possibly going to sleep (in the WAIT operation) or waking up a process (in SIGNAL operation) is all done as a single atomic action. This way just one process at a time is allowed to go to the critical section. When a process come out of the critical section, the value of semaphore is changed so a process that is asleep is awakened.

Next section: Arbitration