Name: Project 2: Synchronization
SKU: 24525
Price: 24.99 USD
Availability: InStock

Description

5/5 – (2 votes)

To submit your project code, submit your GitHub Classroom repository to Gradescope. **Only the following files will be used for grading**:

– `museumsim.c`

– `p2-writeup.md` (the writeup in [GitHub Markdown](https://guides.github.com/features/mastering-markdown/))

—

Project overview

—————-

Imagine that the **CS1550 museum** has been established to showcase old operating systems from all over the history of computing. Imagine also that a number of CS1550 students have volunteered to work as tour guides to answer the questions of the museum visitors and help them run the showcased operating systems.

The museum is hosted in a room that can hold up to 20 visitors and 2 tour guides at a time (with COVID-19 social distancing restrictions in place). In order not to overwhelm the volunteer tour guides, who already have lots of work to do in the CS1550 class, each volunteer guide is limited to supervise at most 10 visitors each day, and is free to leave afterwards. However, being such nice students, if there is more than one guide inside the museum, all guides will wait for each other before leaving, and leave together.

To provide good quality of service to the visitors, it should never be the case that the number of visitors inside the museum exceeds 10 times the number of tour guides who are inside the museum.

The museum has an associated ticket booth. Each morning, a number of tickets is made available based on the number of visitors which will arrive and the number of tour guides that volunteered to show up on that day. Visitors claim the tickets in no particular order. Once there are no more tickets, any arriving visitors are turned away. Once no more visitors will arrive, any remaining guides can leave.

Synchronization

—————

The CS1550 museum involves multiple independently acting entities – namely, the visitors and the tour guides. We will use our synchronization skills to simulate the operation of the CS1550 museum. In particular, you will use locks, condition variables, and/or barriers to simulate the **safe museum tour problem**, whereby visitors and guides are modeled as threads that need to synchronize in such a way that all of the following constraints are met:

– visitors cannot tour the museum without a ticket; if there are no more tickets, the visitor leaves

– visitors cannot tour the museum without a guide; if there is no guide inside the museum, the visitor waits outside; if all guides inside the museum have admitted ten visitors each, the visitor waits outside; otherwise, the visitor proceeds into the musuem

– guides cannot leave until all visitors inside the museum leave

– guides inside the museum must leave together

– _at most_ **two** guides can be in the museum at a time

– each guide serves _at most_ **ten** visitors

To enforce the above conditions, you need to use shared variables between the visitor and guide **threads**. Recall from Project 1 that any time we share data between two or more processes or threads, we run the risk of having race conditions and deadlocks. In race conditions, the shared data could become corrupted. In deadlocks, the threads end up waiting indefinitely on each other. In order to avoid race conditions, we have discussed various mechanisms to ensure that critical regions are guarded.

Your job is to write a multi-threaded program that:

– always satisfies the above constraints

– under no conditions busy waits

– under no conditions causes a deadlock to occur

– under no conditions causes a race condition to occur

A deadlock happens, for example, when a guide and a visitor arrive to an empty museum, and they stay waiting outside forever.

You are not allowed to use busy waiting or timed sleeping to implement this project. This means spinlocks and looping until a memory value changes are **not allowed**, and the use of any sleep call is **not allowed**. Instead, you must use the POSIX threading primitives discussed below and present in the respective document.

POSIX threading API

——————-

The POSIX threading library (`libpthread`) allows implementing multi-threaded applications and synchronization primitives on a wide array of platforms, such as Windows (via `winpthread`), Linux and MacOS. A discussion on how to use its various features follows. You may use any or all of the allowed features depending on how you choose to implement your project, but not all will be required to produce a working implementation.

Please see the [README for POSIX threads](README.libpthread.md) for information on the functions you may use.

Project details

—————

You are to write C code for four functions:

– `museum_init`

– `museum_destroy`

– `visitor`

– `guide`

### Constants

Some of the constants you will use while implementing the program are defined as macros, and will be referenced using these names in the following code.

“`c

#define VISITORS_PER_GUIDE 10

#define GUIDES_ALLOWED_INSIDE 2

“`

### Shared data

Because we need variables to be shared across multiple threads, we must have a safe place to put the synchronization constructs and the variables we will be synchronizing. This safe place is provided for you in a global structure which can be accessed from any thread.

“`c

struct shared_data {

// Add any relevant synchronization constructs and shared state here.

// For example:

// pthread_mutex_t ticket_mutex;

// int tickets;

}

static struct shared_data shared;

“`

### `museum_init` and `museum_destroy`

To set up and tear down the shared variables for your implementation, `museum_init` will be called before any threads are created, and `museum_destroy` will be called after all threads are done executing.

In `museum_init`, you must initialize the synchronization constructs in your shared data section. As an example:

“`c

void museum_init(int num_guides, int num_visitors)

{

pthread_mutex_init(&shared.ticket_mutex, NULL);

shared.tickets = MIN(VISITORS_PER_GUIDE * num_guides, num_visitors);

}

“`

In `museum_destroy`, you will do the reverse, destroying all the synchronization constructs you made, and potentially freeing any memory you have allocated (e.g., using `malloc()`).

“`c

void museum_destroy()

{

pthread_mutex_destroy(&shared.ticket_mutex);

}

“`

### `visitor`

In `visitor`, you will implement the visitor arrival, touring, and leaving sequence.

“`c

void visitor(int id)

{

}

“`

The visitor thread will indicate that it has arrived at the museum as soon as it has started. However, the visitor should leave without touring if there are no tickets remaining.

After acquiring a ticket, the thread must get in line and **block** (i.e., wait) until there is a tour guide available to let the visitor in.

Unlike in a real museum, in the CS1550 museum, visitors who arrive may enter the museum in any order after they arrive, as long as there are no more than `GUIDES_ALLOWED_INSIDE * VISITORS_PER_GUIDE` inside the museum at any given time.

Once the visitor thread has entered the museum, it should indicate that it is touring by calling the `visitor_tours` mentioned below. Once a visitor thread is done touring, it should indicate that it is leaving by calling `visitor_leaves`, and after that, it may do anything else necessary to leave. Each visitor’s departure should **not** depend on any other visitor leaving, or on a tour guide leaving.

Three functions are provided by the driver program to automatically test your code.

“`c

void visitor_arrives(int id);

void visitor_tours(int id);

void visitor_leaves(int id);

“`

You must call these functions in the correct order and at the correct times to receive full credit. The respective functions will print the following messages to the console:

“`

Visitor V arrives at time T.

Visitor V tours the museum at time T.

Visitor V leaves the museum at time T.

“`

To simulate touring, `visitor_tours` will also sleep for a configurable amount of time. The default when debugging is two seconds, but you can adjust this to help you test your implementation.

The driver program will automatically measure the elapsed time for you; you do not need to measure it in your code.

### `guide`

In `guide`, you will implement the tour guide arrival, admitting, and leaving sequence.

“`c

void guide(int id)

{

}

“`

Like the visitor thread, the tour guide thread will indicate that it has arrived as soon as it has started. If there are already `GUIDES_ALLOWED_INSIDE` tour guides inside the museum, it must wait until all guides inside leave before entering.

Once the tour guide is inside the museum, it should indicate that it has entered. Then, it must then begin waiting for and admitting visitors until it has either served a maximum of `VISITORS_PER_GUIDE` visitors, or there are no visitors waiting and no tickets remaining.

After the tour guide has admitted all the visitors it can, it must leave as soon as possible given the following constraints: it must wait for all visitors inside to leave, and for any other tour guide inside to finish before it can leave.

Multiple tour guides inside must indicate they are leaving together before any new tour guides enter. The order in which multiple tour guides leave does not matter. If there are tour guides remaining but no visitors left to serve, the tour guides should enter and then immediately leave.

If another tour guide enters after a guide inside is done but before it leaves, both most wait until the one that entered is done serving visitors.

As with the visitor, four functions are provided by the driver program to automatically test your code.

“`c

void guide_arrives(int id);

void guide_enters(int id);

void guide_admits(int id);

void guide_leaves(int id);

“`

You must call these functions in the correct order and at the correct times to receive full credit. The respective functions will print the following messages to the console:

“`

Guide G arrives at time T.

Guide G admits a visitor at time T.

Guide G leaves the museum at time T.

“`

You should be able to use **one mutex lock** to solve this problem.

Testing your code

—————–

As you implement your project, you are going to want a way to automatically build and debug your code. To do this, run `make debug` from the project directory. If all goes well, your output could be similar to the following:

“`

INFO: Starting run

Guide 0 arrives at time 0.

Guide 0 enters at time 0.

Visitor 0 arrives at time 0.