A program simulating people entering and exiting an elevator, used to practice using threads and semaphores
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.md
design.pdf
project2.cpp

README.md

#CS4348-Semaphores and Threads A project designed to obtain deeper, practical understanding of the concepts of multithreading, including deadlock and semaphores, using a metaphor of people entering and exiting an elevator. This particular project uses UNIX pthreads.

##How to Run This program was designed to be run in a UNIX environment. As such, ensure that project2.cpp is located in the proper UNIX directory when attempting to compile.

To compile and run this program, navigate to the UNIX directory which contains the project2.cpp file, then type the following command:

gcc -pthread -o "name" project2.cpp

Where "name" is any executable name you want, no quotes.

Then, to run, simply write in the same directory

./"name"

##General Procedure For this project, there is an ten story building containing a single elevator, which can hold 7 people. Upon initialization, 49 people enter the building, each having a specific floor that they want to go to. People don't want to go to multiple floors: they go to a single floor and then stay there for the duration of the simulation. All people want to go to a floor other than the ground floor.

The elevator, as well as all 49 people, are seperate threads. The key of the project is to set up a series of semaphores such that people only enter and exit the elevator at the proper times (that is, when it's on their floor, has room, and is going to a floor they want to go to), and that the elevator only moves at the proper times (that is, when all of its business on a floor is done).

This design, as it turns out, can be done with 11 semaphores.

Enter is a semaphore that defines how many people may enter the elevator on the ground floor.Every person will wait() on Enter when they enter the building (that is, upon initialization), and the elevator will signal() Enter 7 times every time that it returns to the ground floor to let 7 people on. Initial value = 0

9 semaphores called Floor2, Floor3, Floor4... Floor10 define when people are able to get out on the elevator onto the corresponding floor. They’re kept in an array, allowing for easy access (since they can be referred to by array index). Every person will wait() on the Floor semaphore corresponding to the floor they want to go to when they come in, and whenever the elevator goes to a floor, it will signal() that floor’s semaphore as many times as there are people on the elevator that want to go to that floor. Initial values = 0

LoadUnload is a semaphore that keeps the elevator on a single floor, with the doors open, while people enter or exit the elevator. The elevator calls wait() on it for every person it expects to move in/out of the elevator on this floor, and then that many people call signal() on it to indicate to the elevator that they are on the side of the doors they want. When the elevator finally gets unblocked, everyone’s where they want to be and the elevator can move. Initial value = 0

##Semaphores In Action When the program formally begins, after all semaphores and process threads begin, the elevator is empty on the ground floor, and all 49 people on the ground floor wait() on Enter, indicating that they are going to wait until the elevator tells them to move. The elevator then calls signal() on Enter seven times, allowing seven people to get on the elevator. The elevator meanwhile calls wait() on LoadUnload seven times, which seven people, once on the elevator, will signal(), indicating the elevator is free to move.

When those people get on the elevator, they wait() on the Floor semaphore corresponding to their destination floor. Using a series of counters, the elevator knows how many people want to go to each floor, so it will go to every floor that a passenger wants to go to, in ascending order (minimum 1 floor, maximum 7).

When the elevator reaches a floor that at least one passanger wants to get off on, it stops there and opens its doors, calling signal() on that Floor's semaphore equal to the number of passengers on the elevator that want to go there, and wait() an equal number of times on LoadUnload. Every time a passenger gets off (due to the Floor semaphore being signalled), they will signal() LoadUnload, until everyone that wants to get off gets off, and the elevator is free to progress to the next floor.

When the elevator finishes with all of its passengers, it returns to the bottom floor, grabs seven new passengers, and repeats the cycle. When every passenger has made it to their floor of choice, the simulation ends.

##Credit This program was written entirely by Michael Burdick for Greg Ozbirn's CS 4348 Operating Systems class, using Visual Studio 2010