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.

Google Online Preview   Download