Project 2 Air Traffic Control with Pthreads solution

Description

Notes: The project must be done individually. You may discuss the problems with other teams and post questions to the OS discussion forum but the submitted work must be your own work. This assignment is worth 20% of your total grade.

Corresponding TAs: Muhammad Aditya Sasongko

Description

In this project, you will get more familiar with the concepts of scheduling, synchronisa-tion, multi-threading and deadlock prevention in operating systems by using POSIX threads (pthreads) API.

Air Tra c Controller

Air tra c control (ATC) is a service to prevent collisions of planes during take-o or land-ing. ATC provides information for pilots during landing or take-o . In this project, you will implement a simulator that simulates multiple independently acting planes in air tra c by modelling their take-o and landing, where the air tra c is controlled by the ATC tower. Your job is to implement the collision and deadlock-free simulator.

Figure 1: Air tra c directed by the control tower

COMP 304 ( Spring 2020): Project 2

Part I Air Tra c Control with Pthreads DESCRIPTION

Part I

(50 points) Here is how planes use the runway. When a plane needs to land or depart, it will contact with the tower and notify the tower that it is ready to land/depart. The tower will acknowledge the plane about its position (e.g. 3rd place to land). The tower contacts (signals/wakes up) the plane that is in the rst position to land/depart and asks it to get ready to land/depart. Here are more detailed rules for the simulation environment.

The simulation should use real-time. Get the current time of the day, run the simulation until current time + simulation time.

There is a single runway that is used both for take-o and landing.

There is only one plane on the runway at any time, otherwise collision is assumed to occur.

After a plane takes o or lands, it can head to any direction and has no consequence on the simulation.

Each plane takes 2t secs to land or take-o (sleep the thread for 2t secs).

Arriving or departing planes have to notify the tower and ask for permission to use the runway.

A plane arrives to the airport with probability p at every t secs and noti es the tower that it is ready to land.

A plane becomes ready to take o with probability 1-p at every t secs and noti es the tower that it is ready to take-o .

It is not allowed for a plane to land without the acknowledgement of the tower (a plane cannot acquire a lock from another plane to land/depart).

For fuel e ciency, the control tower favors the landing planes and lets the waiting planes in the air to land until no more planes is waiting to land. The tower will let only one plane to take o and start favouring the landing planes again.

At time zero, there is one plane waiting to take o and one plane waiting to land.

Use a command line argument -s to indicate the total simulation time (e.g. -s 200) and -p for probability.

In real life, t is usually in the order of minutes but assume t is 1 sec for the purpose of the computer simulation.

Part II

(30 points) Part I may cause starvation to the planes waiting on the ground. In this section, we will add a maximum wait-time and counter for the planes on the ground to avoid this situation. The control tower favors the landing planes and lets the waiting planes in the air to land until one of following conditions hold

COMP 304 ( Spring 2020): Project 2

Part III Air Tra c Control with Pthreads KEEPING LOGS

(a) No more planes is waiting to land,

(b) 5 planes or more on the ground are lined up to take o .

Note that this solution now causes starvation to the planes in the air. Suggest and implement a solution to avoid starvation of waiting planes in the air. Brie y explain why starvation for landing planes occurs and how you solve it in your report.

Part III

(10 points)

Now, we will add an emergency landing for a plane. Assume that every 40t a newly arriving plane has to land because of an emergency (e.g. due to the malfunctioning engine, lack of fuel or a passenger having a health problem). Give this plane immediate access to the runway under the control of the tower.

Keeping Logs

(10 points)

You are required to keep a log for the planes and for the tower, which will help you debug and test your code. The planes.log should keep the plane no (ID), its status (landing (L) or departing (D) or emergency (E)), the request time to use the runway, the runway time (end of runway usage), turnaround time (runway time – request time). Use even IDs to indicate landing, odd IDs for the departing planes.

PlaneID	Status	Request Time	Runway Time	Turnaround Time
1	D	0	2	2
2	L	0	4	4

Output the snapshot of the waiting planes on the ground and in the air with their IDs in every second starting from n^th secs to the terminal, where n is also a command line argu-ment. The numbers indicates the plane IDs waiting in the queue at time n on the ground and in the air. Feel free to come up with a better representation or GUI.

At 20 sec ground: 16, 18, 20

At 20 sec air

: 23, 25

COMP 304 ( Spring 2020): Project 2

Air Tra c Control with Pthreads DELIVERABLES

Implementation

You may want to keep a queue for landing planes and another queue for departing planes, add planes to queues at the appropriate times. C++ STL queues may help your implementation of the data structure.

You can use random number generator to generate planes at the speci ed probability. For easy debugging, add a command line argument for a seed and feed the seed to the random number generator. (Very important for debugging).

You should represent each plane as a thread. The air control tower should have its own separate thread.

Start simple. For example simulate rst landing planes only. Add complexity as you are sure the current implementation works (no deadlock, no accident).

To sleep pthreads, please use the code that we provided on blackboard. Do not use sleep() system call.

For Pthread semaphores, mutexes and condition variables, also refer to the pthread tutorial online: https://computing.llnl.gov/tutorials/pthreads/

Revisit the condition variable example we covered in the class.

Deliverables

You are required to submit the followings packed in a zip le (named your-username(s).zip)

to blackboard :

.c or .cpp source le that implements the simulation. Please comment your implemen-tation.

sample log les for 60 sec simulation for p=0.5.

any supplementary les for your implementation (e.g. Make le)

a README (report) le describing your implementation, particularly which parts of your code work. Since we cannot hold a demo with everyone, document your report properly.

Finally you may perform a demo if requested by the TA if there are issues with your implementation.

GOOD LUCK.

Student Name: Page 4 of 4