Little Book of Semaphores: Threading Learning Tool

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

2


Little Book of Semaphores: Threading Learning Tool

Chapter 1 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

Chapter 2 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.

Chapter 3 Main Driver

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.

Abstract Specification

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.

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.

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.

Interface Design

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.

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.

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.

Chapter 4 Single Driver

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.

Abstract Specification

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.

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.

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.

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.

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.

Interface Design

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.

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.

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.

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.

Chapter 5 Double Driver

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.