Www.cs.scranton.edu
The Little Book of Semaphores
Threading Learning Tool
System Design
Glenn Pirozzi
Dr. Bi
10/15/2010
Submitted in partial fulfillment
of the requirements of
CMPS 490 – Computer Project
Abstract
Synchronization is a huge problem that must be addressed in any software application that uses threading, communications, or any parallel connections or computing. Most do not see the practical side to the synchronization problems; they see solutions but never implementations of said solutions. Threading is an easy way to show examples of parallel computing and the power of synchronization and its uses of semaphores. If a person would like to learn the application of synchronization through a programming language they understand; they will be able to once this project is completed. This project will incorporate python examples of the use of semaphores and synchronization from the book The Little Book of Semaphores into an understandable version of Java that will utilize threads to test said examples. Through this rewriting of the python examples; there will be a better understanding for current Computer Science Majors and any subset Majors on the real applications of synchronization solutions.
Table of Contents
Chapter 1 Abstract 1
Chapter 2 Introduction 5
Chapter 3 Main Driver 6
Architectural Design 6
Abstract Specification 6
Single Button 6
Double Button 7
Exit Button 7
Interface Design 7
Single Button 7
Double Button 8
Exit Button 8
Chapter 4 Single Driver 8
Architectural Design 8
Abstract Specification 9
JTextArea 9
JComboBox 9
Run Button 10
Menu Bar 10
Switch 10
Interface Design 10
JTextArea 10
JComboBox 11
Run Button 11
Menu Bar 11
Chapter 5 Double Driver 11
Architectural Design 11
Abstract Specification 12
JTextArea 12
JComboBox 13
Run Button 13
Menu Bar 13
Switch 13
Interface Design 14
JTextArea 14
JComboBox 14
Run Button 14
Menu Bar 14
Chapter 6 Save Driver 14
Architectural Design 14
Abstract Specification 15
Save Button 15
JLabel 16
JTextField 16
Interface Design 16
Save Button 16
JTextField 16
Chapter 7 Cases 17
Architectural design 17
Abstract Specification 17
Algorithm 17
Logging Thread 18
Algorithms Design 18
Signaling 18
Rendezvous 19
Mutex 19
Multiplex 20
Barrier 21
Reusable Barrier 21
Queue 23
Exclusive Queue 23
Producer-Consumer 26
Readers-Writers 27
No-Starve Mutex 28
Dining Philosophers 29
Tanenbaum's Solution 30
Cigarette Smokers 31
The Dining Savages 32
Barbershop 34
Hilzer's Barbershop 35
Santa Claus 37
Building H2O 39
River Crossing 41
Roller Coaster 42
Multi-car Roller Coaster 44
Search-Insert-Delete 46
Unisex Bathroom 47
Modus Hall 48
Sushi Bar 50
Child Care 53
Extended Child Care 53
Room party 55
Senate Bus 58
Alternate Senate Bus Solution 59
Faneuil Hall 60
Dining Hall 63
Chapter 8 User Interface Design 65
Chapter 9 Glossary 66
Chapter 10 Index 67
Introduction
The application, as described in earlier chapters, is based off of the algorithms in the book by Allen B. Downey, “The Little Book of Semaphores.” Almost all algorithms used in the application are taken directly from this book and so will be explained thoroughly throughout this section. A quick synopsis of the system shows a three tier hierarchy for the entire system design. The application starts with the Main Driver. The Main Driver is the launcher for all other features of the application and is crucial to the success of the application. If for any reason the Main Driver fails, the user will not be able to launch any Sub Drivers that make up the bulk of the User Interface. The second tier or the Sub Drivers are the bulk of the User Interface. The Sub Drivers run all features of the application. These features include the options for running Cases, which Cases to run and how output should be presented. There are a few different types of Sub Drivers, those that are visible and those that are invisible. Visible are Sub Drivers that operate a User Interface and will interact directly with the user. Invisible are Sub Drivers that operate without any interface for the user to act directly with the Sub Drivers. Users may know of the existence of invisible Sub Drivers, but can only influence these Sub Drivers indirectly through other Sub Drivers. The last tier is the use cases or Cases. These are the algorithms included in “The Little Book of Semaphores” and are the bulk of the running operations of the application. They allow the user to explore the ideas and functionality of the algorithms and the application supplies a test environment for the algorithms. Each Case class is started from a Sub Driver, where many different features can be changed, such as the way output is handled. With the three tier hierarchy in place, it makes modifications to the application simple, it also makes user content easy to implement.
Main Driver
1 Architectural Design
The Main Driver is the Java class that holds the main method. This class is the main application program that starts the application and for which the user will start any important functions in. The Main Driver window is 200 pixels wide by 350 pixels long. The Main Driver is composed of three buttons currently, with an estimated five buttons by the time that development is complete. Four buttons are currently planned as the Sub Driver buttons with one button being the exit button. The three buttons that are currently there are the Single button, Double button, and Exit button. Each button is 80 pixels wide by 30 pixels long. Currently the Driver uses the default layout, meaning that it uses a uniform "Java" look to it, it is planned that this may change to a windows look, it is not determined if this will be uniform.
[pic][pic]
2 Abstract Specification
1 Single Button
The Single button is an event driven button utilizing the JButton class of the Java Swing environment. This button, when pressed activates an event through the ActionListener where it launches the class SingleDriver.class. The button's title is "Single" with a scroll over text of "Single text area threading case test." This button is situated 50 pixels from the left and 100 pixels from the top.
2 Double Button
The Double button is an event driven JButton class of the Java Swing environment. This button, when pressed activates an event through the ActionListener where it launches the class DoubleDriver.class. The button's title is "Double" with a scroll over text of " Double text area threading case test." This button is situated 50 pixels from the left and 150 pixels from the top.
3 Exit Button
The Exit button is also an event driven JButton class of the Java Swing environment. However when this button is pressed although it does activate an event with the ActionListener class, it does not launch another class. The event instead launches the command "System.exit(0);" This command when given the parameter 0, will kill the process and thus exit the application. This button does not have a scroll over text. The button is situated 50 pixels from the left and 250 from the top.
3 Interface Design
1 Single Button
The Single Button is a standalone button. Although it resembles the other buttons in the group, its button press will not affect the Main Driver other than launching its Sub Driver. Once the Sub Driver is launched the Main Driver will continue on where the button can be pressed again and launch another object of the Sub Driver. This is not another instance as it creates another declaration of the Sub Driver class.
2 Double Button
The Double Button is a standalone button. Even though it also resembles the other buttons in the group, its button press will not affect the Main Driver other than launching its Sub Driver. Once the Double Driver is launched the Main Driver will continue on where the button can be pressed again and launch another object of the Sub Driver. This is not another instance as it creates another declaration of the Sub Driver class.
3 Exit Button
The Exit Button is unlike the first two buttons in that it is not a standalone button. Different from the other two buttons is in its ability to exit out of the Main Driver. This does affect the Main Driver, it also affects the Sub Drivers because if the Main Driver is closed the Sub Drivers are also closed, however the System.exit(0) will close out of the entire application regardless of the fact that in that process the Main Driver is closed.
Single Driver
1 Architectural Design
The Single Driver is the first of two Sub Drivers that are implemented through button presses in the Main Driver. The Single Driver is also the first of three of the Visible Sub Drivers. The Single Driver is a Java class with all of its UI declarations housed in the constructor of the class. The window is 500 pixels wide by 600 pixels long. It consists of a JTextArea with a JScrollPane of 400 pixels wide by 400 pixels long, a JComboBox of 150 pixels wide by 20 pixels long, and a Run button of 80 pixels wide by 30 pixels long. The Single Driver also includes a menu bar with the drop down menu File that consists of Save and Close, all of which are 20 pixels long. What the user cannot see is the switch used to determine the user selection on the combo box as well as the list used to populate the combo box.
[pic][pic]
2 Abstract Specification
1 JTextArea
This houses all output from the Case that is selected by the user. The Text Area is an object that is sent to a Case to be output to. Output is handled by the case leaving the Single Driver ready to handle another user input. It also saves the Single Driver the trouble of needing to accept anything back from the Case. The reason for this is that every case has a different output and trying to determine how to handle this output should be handled independently from the Single Driver. The Text Area starts 40 pixels from the left and 21 pixels from the top.
2 JComboBox
All user selections for Cases are stored inside the Combo Box. The Combo Box is given a String in which to display all available Cases that the user can select. If a selection is selected the Combo Box sets a variable to that corresponding selection for which the switch will use. The Combo Box sits 50 pixels from the left and 450 pixels from the top.
3 Run Button
Run button is an event driven button utilizing the JButton class of the Java Swing environment. This button, when pressed activates an event through the ActionListener where it launches the method run. The button's title is "Run." This button is situated 250 pixels from the left and 450 pixels from the top.
4 Menu Bar
The menu bar is an event driven menu utilizing the JMenuBar class of the Java Swing environment. This menu, when the cursor is placed over it will open up to show two selections. These two selections are Save and Close. The Save and Close are both JMenuItems with Action Listeners that function exactly like the JButtons. Only the Save Menu Item has an "active" Action Listener which when activated will open the SaveDriver.class. The Menu Bar sits 0 pixels from the left and 0 pixels down.
5 Switch
The Switch is located in the run method of the class. It holds a case for each Case that starts at zero. When the method run is accessed it accepts both an integer called "index" and a JTextArea called "a". The Switch then uses the integer index to determine which case is to be accessed thus selecting the correct Case.
3 Interface Design
1 JTextArea
JTextArea creates a JTextArea that will be passed to the Cases. When a JTextArea is passed to a Case that Case is allowed to output to the specific JTextArea. Before the JTextArea is passed to a Case it is passed into the method run in which will be passed into the constructor of each Case.
2 JComboBox
The JComboBox is used to make the selection for the Switch. This is done through the variable Index. The Variable index can be any number from 0 to n - 1 where n is the amount of Cases implemented. The Variable index from the JComboBox is passed to the method run where it will be utilized by the Switch.
3 Run Button
The Run button accesses the method run. It passes to the method run the index and JTextArea. It does not directly affect anything within the Single Driver other than starting the method run.
4 Menu Bar
Is used as access to the Save Driver and as another way to close out the Single Driver. The Save MenuItem is used to access the Save Driver while the Close MenuItem is used to close out of the Single Driver. If the Save Driver is accessed it is sent the JTextArea.
Double Driver
1 Architectural Design
The Double Driver is the last of two Sub Drivers that are implemented through button presses in the Main Driver. The Double Driver is also the second of three of the Visible Sub Drivers. The Double Driver is a Java class with all of its UI declarations housed in the constructor of the class. The window is 500 pixels wide by 600 pixels long. It consists of two JTextArea with a JScrollPane of 200 pixels wide by 400 pixels long, two JComboBox of 150 pixels wide by 20 pixels long, and a Run button of 80 pixels wide by 30 pixels long. The Double Driver also includes a menu bar with the drop down menu File that consists of Save and Close, all of which are 20 pixels long. What the user cannot see is the switch used to determine the user selection on the combo box as well as the list used to populate the combo boxes. The Double Driver also utilizes threads to achieve a concurrent execution of two Cases instead of one. This means that each thread can access the switch, although not at the same time to ensure that synchronization is achieved.
[pic][pic]
2 Abstract Specification
1 JTextArea
This houses all output from the Case that is selected by the user. The Text Area is an object that is sent to a Case to be output to. Output is handled by the case leaving the Single Driver ready to handle another user input. It also saves the Double Driver the trouble of needing to accept anything back from the Case. The reason for this is that every case has a different output and trying to determine how to handle this output should be handled independently from the Double Driver. The first Text Area starts 40 pixels from the left and 21 pixels from the top. The second Text Area starts 250 pixels from the left and 21 pixels from the top.
2 JComboBox
All user selections for Cases are stored inside the Combo Box. The Combo Box is given a String in which to display all available Cases that the user can select. If a selection is selected the Combo Box sets a variable to that corresponding selection for which the switch will use. The first Combo Box sits 50 pixels from the left and 450 pixels from the top. The second Combo Box sits 200 pixels from the left and 450 pixels form the top.
3 Run Button
Run button is an event driven button utilizing the JButton class of the Java Swing environment. This button, when pressed activates an event through the ActionListener where it launches the method run. The button's title is "Run." This button is situated 250 pixels from the left and 450 pixels from the top.
4 Menu Bar
The menu bar is an event driven menu utilizing the JMenuBar class of the Java Swing environment. This menu, when the cursor is placed over it will open up to show two selections. These two selections are Save and Close. The Save and Close are both JMenuItems with Action Listeners that function exactly like the JButtons. Only the Save Menu Item has an "active" Action Listener which when activated will open the SaveDriver.class. The Menu Bar sits 0 pixels from the left and 0 pixels down.
5 Switch
The Switch is located in the run method of the class. It holds a case for each Case that starts at zero. When the method run is accessed it accepts both an integer called "index" and a JTextArea called "a". The Switch then uses the integer index to determine which case is to be accessed thus selecting the correct Case.
3 Interface Design
1 JTextArea
JTextArea creates a JTextArea that will be passed to the Cases. When a JTextArea is passed to a Case that Case is allowed to output to the specific JTextArea. Before the JTextArea is passed to a Case it is passed into the method run in which will be passed into the constructor of each Case.
2 JComboBox
The JComboBox is used to make the selection for the Switch. This is done through the variable Index. The Variable index can be any number from 0 to n - 1 where n is the amount of Cases implemented. The Variable index from the JComboBox is passed to the method run where it will be utilized by the Switch.
3 Run Button
The Run button accesses the method run. It passes to the method run the index and JTextArea. It does not directly affect anything within the Double Driver other than starting the method run.
4 Menu Bar
Is used as access to the Save Driver and as another way to close out the Double Driver. The Save MenuItem is used to access the Save Driver while the Close MenuItem is used to close out of the Double Driver. If the Save Driver is accessed it is sent both JTextAreas.
Save Driver
1 Architectural Design
The Save Driver is accessed from both the Single Driver and the Double Driver. Its purpose is to save the output of the JTextArea to a file specified by the user. The Save Driver just like the other two Visible Drivers is a Java class with all of its UI declarations housed in the constructor of the class. The difference being though that the other classes do not just create the object for the Save Driver and then let the Save Driver handle itself. After the Save Driver is declared and instantiated a method called "savefunction" must be called. The method "savefunction" is overloaded, one with a single passed JTextArea and one with two JTextArea's passed. The window of the Save Driver is 450 pixels wide by 200 pixels long. It consists of three objects. The first is the JButton, "Save", of which is 80 pixels wide by 30 pixels long. The second is a JLabel which includes the words "Enter in file name: ." The third is the JTextField which is 120 pixels wide by 10 pixels long.
[pic][pic]
2 Abstract Specification
1 Save Button
Save button is an event driven button utilizing the JButton class of the Java Swing environment. This button, when pressed activates an event through the ActionListener where it declares and instantiates both a FileWriter and BufferedWriter. Both of these The button's title is "Run." This button is situated 250 pixels from the left and 450 pixels from the top.
2 JLabel
The JLabel is used to denote to the user what the JTextArea is used for. In this case the JLabel includes the String "Enter in file name: ." The label is situated 150 pixels from the left and 20 pixels from the top.
3 JTextField
The JTextField is used to store input from the user denoting the file that the user wants the output of the JTextArea to be placed in. As of now the JTextField does not hold any restrictions against a users input. The user must include their own extension when naming the file they are going to save. The JTextField is situated 300 pixels from the left and 20 pixels from the top.
3 Interface Design
1 Save Button
The Save button interacts with the FileWriter and BufferedWriter. They take the input from the JTextField and apply it to the name of the file they are writing the JTextArea to. The Save button will not at this time close out of the window when done saving, this must be manually done by the user.
2 JTextField
JtextField is used by the FileWriter and BufferedWriter to name the file they are writing to. However the user inputs the file name is how the writers will write it as. This means that the user could conceivably save a file as both a .txt or as a .doc. If the user feels they could save it as a .jpg or .exe if they so choose.
Cases
1 Architectural design
Each Case is a use case based off of an algorithm from "The Little Book of Semaphores." All use cases from the book are in python. They are then translated to Java for use in the application. Each Case is implemented with Semaphore usage, however there are also Cases implemented with Synchronized Methods. The Cases are Java classes with no user interface. They are not Sub Drivers but their own entity. Each Case when created accepts a single variable of a JTextArea for output. Each Case also includes a "Logging Thread" of which will log all the output of the Case.
[pic]
2 Abstract Specification
1 Algorithm
The Algorithm taken from the book "The Little Book of Semaphores" may constitute any classical and or non classical synchronization algorithm. It may also be noted that all the algorithms included with the base application are from "The Little Book of Semaphores" however users may make their own Cases in which use different algorithms from different sources.
2 Logging Thread
The Logging Thread is an extra thread created to handle all output from the Case. Its purpose is to attempt to minimize interruption from output to the JTextArea as well as keep synchronization true for the JTextArea. The way it achieves this is by using the ConcurrentLinkedQueue class. This queue is thread safe and therefore cannot be accessed by more than one thread at a time. As every thread places an output into the queue the thread will take this output and add it to the JTextArea. In between each add to the JTextArea the Logging Thread will sleep for an amount of time before waking up to accept the next output. When a thread ends it will output the String "END." When the Logging Thread receives this String "END" it will increment a counter which will exit the thread when it reaches the same number as threads that were running in the Case. This ensures minimal interruptions from the output.
3 Algorithms Design
1 Signaling
This is the most basic algorithm. It is the idea that one thread sends a signal to another thread to indicate when an event has occurred. This makes it possible to guarantee that a section of code in one thread will run before another thread. This algorithm uses a semaphore named sem with an initial value of 0. Thread A and Thread B have access to it.
Thread A
1 statement a1
2 sem.signal()
Thread B
1 sem.wait()
2 statement b1
2 Rendezvous
This is a generalization of the Signaling algorithm, this makes it so that it can work both ways. The idea behind this is that two threads will meet at a point of execution, and neither will be allowed to proceed until both have arrived. This Algorithm uses two semaphores, aArrived and bArrived both set to zero.
Thread A
1 statement a1
2 aArrived.signal()
3 bArrived.wait()
4 statement a2
Thread B
1 statement b1
2 bArrived.signal()
3 aArrived.wait()
4 statement b2
3 Mutex
This is an algorithm used for mutual exclusion. The mutex will guarantee that only one thread may access the a shared resource at a time. The idea behind this is that only one thread may access the mutex at any time, therefore only one thread may do what it has to do with the shared resource at a time. In this algorithm both threads will used a shared variable count. They will also use the semaphore mutex that is initialized to 1.
Thread A
mutex.wait()
# critical section
count = count + 1
mutex.signal()
Thread B
mutex.wait()
# critical section
count = count + 1
mutex.signal()
4 Multiplex
This is a generalization of the mutex algorithm to allow more than two threads to use the algorithm at once. For this algorithm to work, the semaphore mutex must be set to a value n. This value n is the maximum number of allowed threads. If the value of the semaphore reaches zero the semaphore will block the next thread that tries to access the critical section. When a thread leaves, the value of the semaphore is incremented allowing another thread to enter.
1 multiplex.wait()
2 critical section
3 multiplex.signal()
5 Barrier
Is the generalization of the rendezvous solution to allow multiple threads. This algorithm assumes that there are n threads and that this is stored in a variable n. When the first n - 1 threads arrive they should block until the nth thread arrives, when this happens all threads will be able to proceed. The variables used in this algorithm are n which is the number of threads. A count which is set to 0 which keeps track of how many threads have arrived. The semaphore mutex initialized to 1 and the semaphore barrier initialized to 0.
1 rendezvous
2
3 mutex.wait()
4 count = count + 1
5 mutex.signal()
6
7 if count == n: barrier.signal()
8
9 barrier.wait()
10 barrier.signal()
11
12 critical point
6 Reusable Barrier
A barrier that will lock itself after all the threads have passed through. The algorithm uses the idea of turnstiles to allow access. These are built into semaphores called turnstile which is initialized to 0 and turnstile2 which is initialized to 1. There is also the semaphore mutex initialized to 1.
# rendezvous
2
3 mutex.wait()
4 count += 1
5 if count == n:
6 turnstile2.wait() # lock the second
7 turnstile.signal() # unlock the first
8 mutex.signal()
9
10 turnstile.wait() # first turnstile
11 turnstile.signal()
12
13 # critical point
14
15 mutex.wait()
16 count -= 1
17 if count == 0:
18 turnstile.wait() # lock the first
19 turnstile2.signal() # unlock the second
20 mutex.signal()
21
22 turnstile2.wait() # second turnstile
23 turnstile2.signal()
7 Queue
This algorithm uses semaphores as a queue. For this algorithm it uses the idea that both a leader and a follower need to be present to continue. This is because the value of a semaphore should never be positive in this example of a queue. The reason for this is that it should not be possible to signal unless there is a thread waiting. We should create two semaphores a leaderQueue initialized to 0 and a followerQueue initialized to 0. This algorith goes off of the idea of a ballroom dance in which a leader must be accompanied by a follower, thus the call to dance().
Code for Leaders:
1 followerQueue.signal()
2 leaderQueue.wait()
3 dance()
Code for Followers:
1 leaderQueue.signal()
2 followerQueue.wait()
3 dance()
8 Exclusive Queue
This algorith adds the constraint to Queue that each leader can invoke dance concurrently with only one follower, and vice versa. As Downey states "You got to dance with the one that brought you." This algorithm uses two variables leaders and followers both set to 0. It also includes four semaphores: mutex initialized to 1, leaderQueue initialized to 0, followerQueue initialized to 0, and rendezvous initialized to 0.
Code for Leaders:
1 mutex.wait()
2 if followers > 0:
3 followers--
4 followerQueue.signal()
5 else:
6 leaders++
7 mutex.signal()
8 leaderQueue.wait()
9
10 dance()
11 rendezvous.wait()
12 mutex.signal()
Code for Followers:
1 mutex.wait()
2 if leaders > 0:
3 leaders--
4 leaderQueue.signal()
5 else:
6 followers++
7 mutex.signal()
8 followerQueue.wait()
9
10 dance()
11 rendezvous.signal()
Fifo Queue
This adds the idea that the first thread to arrive at a semaphore should be the first to enter the semaphore and so forth. This solution uses two semaphores: mySem initialized to 0 and mutex initialized to 1. It also uses a queue called queue. There is also a mutex semaphore.
class Fifo:
2 def __init__(self):
3 self.queue = Queue()
4 self.mutex = Semaphore(1)
5
6 def wait():
7 self.mutex.wait()
8 self.queue.add(mySem)
9 self.mutex.signal()
10 mySem.wait()
11
12 def signal():
13 self.mutex.wait()
14 sem = self.queue.remove()
15 self.mutex.signal()
16 sem.signal()
For the more advanced algorithms short summaries will not be given, instead a list of variables and the solutions will be given instead.
9 Producer-Consumer
Variables:
1 mutex = Semaphore(1)
2 items = Semaphore(0)
3 local event
Producer Solution:
1 event = waitForEvent()
2 mutex.wait()
3 buffer.add(event)
4 mutex.signal()
5 items.signal()
Consumer Solution:
1 items.wait()
2 mutex.wait()
3 event = buffer.get()
4 mutex.signal()
5 event.process()
10 Readers-Writers
Variables:
1 int readers = 0
2 mutex = Semaphore(1)
3 roomEmpty = Semaphore(1)
Writers Solution:
1 roomEmpty.wait()
2 critical section for writers
3 roomEmpty.signal()
Readers Solution:
1 mutex.wait()
2 readers += 1
3 if readers == 1:
4 roomEmpty.wait() # first in locks
5 mutex.signal()
6
7 # critical section for readers
8
9 mutex.wait()
10 readers -= 1
11 if readers == 0:
12 roomEmpty.signal() # last out unlocks
13 mutex.signal()
11 No-Starve Mutex
Variables:
1 room1 = room2 = 0
2 mutex = Semaphore(1)
3 t1 = Semaphore(1)
4 t2 = Semaphore(0)
Morris's algorithm:
mutex.wait()
2 room1 += 1
3 mutex.signal()
4
5 t1.wait()
6 room2 += 1
7 mutex.wait()
8 room1 -= 1
9
10 if room1 == 0:
11 mutex.signal()
12 t2.signal()
13 else:
14 mutex.signal()
15 t1.signal()
16
17 t2.wait()
18 room2 -= 1
19
20 # critical section
21
22 if room2 == 0:
23 t1.signal()
24 else:
25 t2.signal()
12 Dining Philosophers
Variables and Definitions :
1 def left(i): return i
2 def right(i): return (i + 1) % 5
1 forks = [Semaphore(1) for i in range(5)]
Solution:
1 def get_forks(i):
2 footman.wait()
3 fork[right(i)].wait()
4 fork[left(i)].wait()
5
6 def put_forks(i):
7 fork[right(i)].signal()
8 fork[left(i)].signal()
9 footman.signal()
13 Tanenbaum's Solution
This solution is for the dining philosophers
Variables:
1 state = [’thinking’] * 5
2 sem = [Semaphore(0) for i in range(5)]
3 mutex = Semaphore(1)
Solution:
1 def get_fork(i):
2 mutex.wait()
3 state[i] = ’hungry’
4 test(i)
5 mutex.signal()
6 sem[i].wait()
7
8 def put_fork(i):
9 mutex.wait()
10 state[i] = ’thinking’
11 test(right(i))
12 test(left(i))
13 mutex.signal()
14
15 def test(i):
16 if state[i] == ’hungry’ and
17 state (left (i)) != ’eating’ and
18 state (right (i)) != ’eating’:
19 state[i] = ’eating’
20 sem[i].signal()
14 Cigarette Smokers
Variables:
1 isTobacco = isPaper = isMatch = False
2 tobaccoSem = Semaphore(0)
3 paperSem = Semaphore(0)
4 matchSem = Semaphore(0)
Pushers Code:
1 tobacco.wait()
2 mutex.wait()
3 if isPaper:
4 isPaper = False
5 matchSem.signal()
6 elif isMatch:
7 isMatch = False
8 paperSem.signal()
9 else:
10 isTobacco = True
11 mutex.signal()
Smoker with Tobacco:
1 tobaccoSem.wait()
2 makeCigarette()
3 agentSem.signal()
4 smoke()
15 The Dining Savages
Variables:
1 servings = 0
2 mutex = Semaphore(1)
3 emptyPot = Semaphore(0)
4 fullPot = Semaphore(0)
Cook Code:
1 while True:
2 emptyPot.wait()
3 putServingsInPot(M)
4 fullPot.signal()
Savage Code:
while True:
2 mutex.wait()
3 if servings == 0:
4 emptyPot.signal()
5 fullPot.wait()
6 servings = M
7 servings -= 1
8 getServingFromPot()
9 mutex.signal()
10
11 eat()
16 Barbershop
Variables:
1 customers = 0
2 mutex = Semaphore(1)
3 customer = Semaphore(0)
4 barber = Semaphore(0)
Customer Code:
1 mutex.wait()
2 if customers == n+1:
3 mutex.signal()
4 balk()
5 customers += 1
6 mutex.signal()
7
8 customer.signal()
9 barber.wait()
10 getHairCut()
11
12 mutex.wait()
13 customers -= 1
14 mutex.signal()
Barber Code:
1 customer.wait()
2 barber.signal()
3 cutHair()
17 Hilzer's Barbershop
Variables:
1 customers = 0
2 mutex = Semaphore(1)
3 standingRoom = Fifo(16)
4 sofa = Fifo(4)
5 chair = Semaphore(3)
6 barber = Semaphore(0)
7 customer = Semaphore(0)
8 cash = Semaphore(0)
9 receipt = Semaphore(0)
Customer Code:
1 mutex.wait()
2 if customers == 20:
3 mutex.signal()
4 exitShop()
5 customers += 1
6 mutex.signal()
7
8 standingRoom.wait()
9 enterShop()
10
11 sofa.wait()
12 sitOnSofa()
13 standingRoom.signal()
14
15 chair.wait()
16 sitInBarberChair()
17 sofa.signal()
18
19 customer.signal()
20 barber.wait()
21 getHairCut()
22
23 pay()
24 cash.signal()
25 receipt.wait()
26
27 mutex.wait()
28 customers -= 1
29 mutex.signal()
30
31 exitShop()
Barber Code:
1 customer.wait()
2 barber.signal()
3 cutHair()
4
5 cash.wait()
6 acceptPayment()
7 receipt.signal()
18 Santa Claus
Variables:
1 elves = 0
2 reindeer = 0
3 santaSem = Semaphore(0)
4 reindeerSem = Semaphore(0)
5 elfTex = Semaphore(1)
6 mutex = Semaphore(1)
Santa Code:
1 santaSem.wait()
2 mutex.wait()
3 if reindeer == 9:
4 prepareSleigh()
5 reindeerSem.signal(9)
6 else if elves == 3:
7 helpElves()
8 mutex.signal()
Reindeer Code:
1 mutex.wait()
2 reindeer += 1
3 if reindeer == 9:
4 santaSem.signal()
5 mutex.signal()
6
7 reindeerSem.wait()
8 getHitched()
Elves Code:
1 elfTex.wait()
2 mutex.wait()
3 elves += 1
4 if elves == 3:
5 santaSem.signal()
6 else
7 elfTex.signal()
8 mutex.signal()
9
10 getHelp()
11
12 mutex.wait()
13 elves -= 1
14 if elves == 0:
15 elfTex.signal()
16 mutex.signal()
19 Building H2O
Variables:
1 mutex = Semaphore(1)
2 oxygen = 0
3 hydrogen = 0
4 barrier = Barrier(3)
5 oxyQueue = Semaphore(0)
6 hydroQueue = Semaphore(0)
Oxygen Code:
1 mutex.wait()
2 oxygen += 1
3 if hydrogen >= 2:
4 hydroQueue.signal(2)
5 hydrogen -= 2
6 oxyQueue.signal()
7 oxygen -= 1
8 else:
9 mutex.signal()
10
11 oxyQueue.wait()
12 bond()
13
14 barrier.wait()
15 mutex.signal()
Hydrogen Code:
1 mutex.wait()
2 hydrogen += 1
3 if hydrogen >= 2 and oxygen >= 1:
4 hydroQueue.signal(2)
5 hydrogen -= 2
6 oxyQueue.signal()
7 oxygen -= 1
8 else:
9 mutex.signal()
10
11 hydroQueue.wait()
12 bond()
13
14 barrier.wait()
20 River Crossing
Variables:
1 barrier = Barrier(4)
2 mutex = Semaphore(1)
3 hackers = 0
4 serfs = 0
5 hackerQueue = Semaphore(0)
6 serfQueue = Semaphore(0)
7 local isCaptain = False
Solution:
1 mutex.wait()
2 hackers += 1
3 if hackers == 4:
4 hackerQueue.signal(4)
5 hackers = 0
6 isCaptain = True
7 elif hackers == 2 and serfs >= 2:
8 hackerQueue.signal(2)
9 serfQueue.signal(2)
10 serfs -= 2
11 hackers = 0
12 isCaptain = True
13 else:
14 mutex.signal() # captain keeps the mutex
15
16 hackerQueue.wait()
17
18 board()
19 barrier.wait()
20
21 if isCaptain:
22 rowBoat()
23 mutex.signal() # captain releases the mutex
21 Roller Coaster
Variables:
1 mutex = Semaphore(1)
2 mutex2 = Semaphore(1)
3 boarders = 0
4 unboarders = 0
5 boardQueue = Semaphore(0)
6 unboardQueue = Semaphore(0)
7 allAboard = Semaphore(0)
8 allAshore = Semaphore(0)
Car Code:
1 load()
2 boardQueue.signal(C)
3 allAboard.wait()
4
5 run()
6
7 unload()
8 unboardQueue.signal(C)
9 allAshore.wait()
Passenger Code:
1 boardQueue.wait()
2 board()
3
4 mutex.wait()
5 boarders += 1
6 if boarders == C:
7 allAboard.signal()
8 boarders = 0
9 mutex.signal()
10
11 unboardQueue.wait()
12 unboard()
13
14 mutex2.wait()
15 unboarders += 1
16 if unboarders == C:
17 allAshore.signal()
18 unboarders = 0
19 mutex2.signal()
22 Multi-car Roller Coaster
Variables and Definitions (some variables carry over from last problem):
1 loadingArea = [Semaphore(0) for i in range(m)]
2 loadingArea[1].signal()
3 unloadingArea = [Semaphore(0) for i in range(m)]
4 unloadingArea[1].signal()
1 def next(i):
2 return (i + 1) % m
Car Code:
1 loadingArea[i].wait()
2 load()
3 boardQueue.signal(C)
4 allAboard.wait()
5 loadingArea[next(i)].signal()
6
7 run()
8
9 unloadingArea[i].wait()
10 unload()
11 unboardQueue.signal(C)
12 allAshore.wait()
13 unloadingArea[next(i)].signal()
Passenger Code:
1 boardQueue.wait()
2 board()
3
4 mutex.wait()
5 boarders += 1
6 if boarders == C:
7 allAboard.signal()
8 boarders = 0
9 mutex.signal()
10
11 unboardQueue.wait()
12 unboard()
23 Search-Insert-Delete
Variables:
1 insertMutex = Semaphore(1)
2 noSearcher = Semaphore(1)
3 noInserter = Semaphore(1)
4 searchSwitch = Lightswitch()
5 insertSwitch = Lightswitch()
Searcher Code:
1 searchSwitch.wait(noSearcher)
2 # critical section
3 searchSwitch.signal(noSearcher)
Inserter Code:
1 insertSwitch.wait(noInserter)
2 insertMutex.wait()
3 # critical section
4 insertMutex.signal()
5 insertSwitch.signal(noInserter)
Deleter Code:
1 noSearcher.wait()
2 noInserter.wait()
3 # critical section
4 noInserter.signal()
5 noSearcher.signal()
24 Unisex Bathroom
Variables:
1 empty = Semaphore(1)
2 maleSwitch = Lightswitch()
3 femaleSwitch = Lightswitch()
4 maleMultiplex = Semaphore(3)
5 femaleMultiplex = Semaphore(3)
Female Code:
1 femaleSwitch.lock(empty)
2 femaleMultiplex.wait()
3 # bathroom code here
4 femaleMultiplex.signal()
5 female Switch.unlock(empty)
Male Code:
1 maleSwitch.lock(empty)
2 maleMultiplex.wait()
3 # bathroom code here
4 maleMultiplex.signal()
5 male Switch.unlock(empty)
25 Modus Hall
Variables:
1 heathens = 0
2 prudes = 0
3 status = ’neutral’
4 mutex = Semaphore(1)
5 heathenTurn = Semaphore(1)
6 prudeTurn = Semaphore(1)
7 heathenQueue = Semaphore(0)
8 prudeQueue = Semaphore(0)
Solution:
1 heathenTurn.wait()
2 heathenTurn.signal()
3
4 mutex.wait()
5 heathens++
6
7 if status == ’neutral’:
8 status = ’heathens rule’
9 mutex.signal()
10 elif status == ’prudes rule’:
11 if heathens > prudes:
12 status = ’transition to heathens’
13 prudeTurn.wait()
14 mutex.signal()
15 heathenQueue.wait()
16 elif status == ’transition to heathens’:
17 mutex.signal()
18 heathenQueue.wait()
19 else
20 mutex.signal()
21
22 # cross the field
23
24 mutex.wait()
25 heathens--
26
27 if heathens == 0:
28 if status == ’transition to prudes’:
29 prudeTurn.signal()
30 if prudes:
31 prudeQueue.signal(prudes)
32 status = ’prudes rule’
33 else:
34 status = ’neutral’
35
36 if status == ’heathens rule’:
37 if prudes > heathens:
38 status = ’transition to prudes’
39 heathenTurn.wait()
40
41 mutex.signal()
26 Sushi Bar
Variables:
1 eating = waiting = 0
2 mutex = Semaphore(1)
3 block = Semaphore(0)
4 must_wait = False
Solution #1:
1 mutex.wait()
2 if must_wait:
3 waiting += 1
4 mutex.signal()
5 block.wait()
6 else:
7 eating += 1
8 must_wait = (eating == 5)
9 mutex.signal()
10
11 # eat sushi
12
13 mutex.wait()
14 eating -= 1
15 if eating == 0:
16 n = min(5, waiting)
17 waiting -= n
18 eating += n
19 must_wait = (eating == 5)
20 block.signal(n)
21 mutex.signal()
Solution #2:
1 mutex.wait()
2 if must_wait:
3 waiting += 1
4 mutex.signal()
5 block.wait() # when we resume, we have the mutex
6 waiting -= 1
7
8 eating += 1
9 must_wait = (eating == 5)
10 if waiting and not must_wait:
11 block.signal() # and pass the mutex
12 else:
13 mutex.signal()
14
15 # eat sushi
16
17 mutex.wait()
18 eating -= 1
19 if eating == 0: must_wait = False
20
21 if waiting and not must_wait:
22 block.signal() # and pass the mutex
23 else:
24 mutex.signal()
27
28
29 Child Care
Variables:
1 multiplex = Semaphore(0)
2 mutex = Semaphore(1)
Solution:
1 multiplex.signal(3)
2
3 # critical section
4
5 mutex.wait()
6 multiplex.wait()
7 multiplex.wait()
8 multiplex.wait()
9 mutex.signal()
30 Extended Child Care
Variables:
1 children = adults = waiting = leaving = 0
2 mutex = Semaphore(1)
3 childQueue = Semaphore(0)
4 adultQueue = Semaphore(0)
Child Code:
1 mutex.wait()
2 if children < 3 * adults:
3 children++
4 mutex.signal()
5 else:
6 waiting++
7 mutex.signal()
8 childQueue.wait()
9
10 # critical section
11
12 mutex.wait()
13 children--
14 if leaving and children = 50
8
9 if students >= 50:
10 dean = ’in the room’
11 breakup()
12 turn.wait() # lock the turnstile
13 mutex.signal()
14 clear.wait() # and get mutex from the student.
15 turn.signal() # unlock the turnstile
16
17 else: # students must be 0
18 search()
19
20 dean = ’not here’
21 mutex.signal()
Student Code:
1 mutex.wait()
2 if dean == ’in the room’:
3 mutex.signal()
4 turn.wait()
5 turn.signal()
6 mutex.wait()
7
8 students += 1
9
10 if students == 50 and dean == ’waiting’:
11 lieIn.signal() # and pass mutex to the dean
12 else:
13 mutex.signal()
14
15 party()
16
17 mutex.wait()
18 students -= 1
19
20 if students == 0 and dean == ’waiting’:
21 lieIn.signal() # and pass mutex to the dean
22 elif students == 0 and dean == ’in the room’:
23 clear.signal() # and pass mutex to the dean
24 else:
25 mutex.signal()
32 Senate Bus
Variables:
1 riders = 0
2 mutex = Semaphore(1)
3 multiplex = Semaphore(50)
4 bus = Semaphore(0)
5 allAboard = Semaphore(0)
Bus Code:
1 mutex.wait()
2 if riders > 0:
3 bus.signal() # and pass the mutex
4 allAboard.wait() # and get the mutex back
5 mutex.signal()
6
7 depart()
Riders Code:
1 multiplex.wait()
2 mutex.wait()
3 riders += 1
4 mutex.signal()
5
6 bus.wait() # and get the mutex
7 multiplex.signal()
8
9 boardBus()
10
11 riders -= 1
12 if riders == 0:
13 allAboard.signal()
14 else:
15 bus.signal() # and pass the mutex
33 Alternate Senate Bus Solution
Variables:
1 waiting = 0
2 mutex = new Semaphore(1)
3 bus = new Semaphore(0)
4 boarded = new Semaphore(0)
Bus Code:
1 mutex.wait()
2 n = min(waiting, 50)
3 for i in range(n):
4 bus.signal()
5 boarded.wait()
6
7 waiting = max(waiting-50, 0)
8 mutex.signal()
9
10 depart()
Riders Code:
1 mutex.wait()
2 waiting += 1
3 mutex.signal()
4
5 bus.wait()
6 board()
7 boarded.signal()
34 Faneuil Hall
Variables:
1 noJudge = Semaphore(1)
2 entered = 0
3 checked = 0
4 mutex = Semaphore(1)
5 confirmed = Semaphore(0)
Immigrant Code:
1 noJudge.wait()
2 enter()
3 entered++
4 noJudge.signal()
5
6 mutex.wait()
7 checkIn()
8 checked++
9
10 if judge = 1 and entered == checked:
11 allSignedIn.signal() # and pass the mutex
12 else:
13 mutex.signal()
14
15 sitDown()
16 confirmed.wait()
17
18 swear()
19 getCertificate()
20
21 noJudge.wait()
22 leave()
23 noJudge.signal()
Judge Code:
noJudge.wait()
2 mutex.wait()
3
4 enter()
5 judge = 1
6
7 if entered > checked:
8 mutex.signal()
9 allSignedIn.wait() # and get the mutex back.
10
11 confirm()
12 confirmed.signal(checked)
13 entered = checked = 0
14
15 leave()
16 judge = 0
17
18 mutex.signal()
19 noJudge.signal()
Spectator Code:
1 noJudge.wait()
2 enter()
3 noJudge.signal()
4
5 spectate()
6
7 leave()
35 Dining Hall
Variables:
1 eating = 0
2 readyToLeave = 0
3 mutex = Semaphore(1)
4 okToLeave = Semaphore(0)
Solution:
1 getFood()
2
3 mutex.wait()
4 eating++
5 if eating == 2 and readyToLeave == 1:
6 okToLeave.signal()
7 readyToLeave--
8 mutex.signal()
9
10 dine()
11
12 mutex.wait()
13 eating--
14 readyToLeave++
15
16 if eating == 1 and readyToLeave == 1:
17 mutex.signal()
18 okToLeave.wait()
19 elif eating == 0 and readyToLeave == 2:
20 okToLeave.signal()
21 readyToLeave -= 2
22 mutex.signal()
23 else:
24 readyToLeave--
25 mutex.signal()
26
27 leave()
User Interface Design
The idea behind the user interface is an interface that is easy and intuitive to use. As seen in this document the user interface is built of Drivers including the Main Driver and Sub Drivers. The formatting that is being applied to the user interface is the generic formatting. It will be Microsoft Windows formatting once everything is completed. There will not be a thorough examination of the user interface as that has already been covered. Instead this final statement will be about the idea of flexability in an interface. Right now a new design mechanic is being developed for this appliction. It will be housed in the DynamicDriver. This Sub Driver will be an invisible driver that will allow users to input their own Sub Drivers and Cases. Depending on what Sub Drivers or Cases a user adds will change the way the user interface looks. The only conventions that will remain the same are the sizes of the buttons on the Main Driver. Any user created Sub Driver may have its own formatting conventions. The only thing that must stay the same is that each Case that a user creates can only accept one parameter, which is a JTextArea.
Glossary
Driver - Parts of the application that run all the features and execute other drivers and cases
Main driver - Driver that starts all the sub drivers
Sub driver - Drivers that include outputs and features used for running cases
Case - Coded examples of semaphore and thread usage that are able to execute
Semaphore- The classic method for restricting access to shared resources (e.g. storage) in a multi-processing environment. ()
Index
Case, 66
Cases, 3, 5, 9, 10, 11, 12, 13, 14, 17, 18, 65
Double Driver, 2, 8, 11, 12, 14, 15
drivers, 66
Logging Thread, 3, 17, 18
Main driver, 66
Main Driver, 2, 5, 6, 7, 8, 11, 65
Save Driver, 3, 11, 14, 15
Semaphore, 66
Single Driver, 2, 8, 9, 11, 12, 15
Sub driver, 66
Sub Drivers, 5, 8, 11, 17, 65
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- https www municipalonlinepayments
- cs ny employee benefits nyship
- 7 cs of communication ppt
- cs ny gov employee benefits
- 7 cs of effective communication
- the 7 cs of communication
- cs phd salary
- seven cs of communication
- project ideas for cs students
- oxford cs philosophy
- the 7 cs of communication definitions
- freud and cs lewis