CS563 Assignment 3: Programming with Message Passing
Instructor: Xinghui Zhao Due: 11:59pm, February 9, 2020
1 Overview
The purpose of this assignment is to give you some practice on programming using message passing. You will write pseudo code using the message passing syntax discussed in Lectures 4 and 5 to solve a problem.
2 Roller Coster
There are n passenger trying to ride on one roller coaster car. The passengers repeatedly wait to take rides in the car, which can hold C passengers (C ă n). However, the car can go around the tracks only when it is full. After finishes a ride, each passenger wanders around the amusement park before returning to the roller coaster for another ride. Due to safety reasons, the car only operates T times and then it will be shut off for maintenance before it can go back to business.
In a nutshell, when the system is running, the following requirements must be satisfied:
• The car always rides with exactly C passengers;
• No passengers will jump off the car while the car is running;
• No passengers will jump on the car while the car is running;
• No passengers will request another ride before they can get off the car.
Programming Help
3 Message Passing
Suppose the car and each passenger are represented by processes, you can use message passing to solve this problem. The syntax covered in Lectures 4 and 5 is as follows:
• Channels: chan(id1: type 1; …; idN: type N)
• Asynchronous send: send name(expr1, …, exprN)
• Blocking receive: receive name(var1, …, varN)
• Synchronous send: synch send name(expr1, …, exprN)
4 Your Tasks
You need to do the following:
What to Hand In
Develop code for the passenger and car processes. Use message passing for communication.
No shared variable is allowed.
Generalize your answer to employ m car processes (m ą 1). Since there is only one track, cars cannot pass each other, i.e., they must finish going around the track in the order in which they started. Again, a car can go around the tracks only when it is full.
Write a report to explain your algorithm, and what communication pattern you used in your code. Analyze the communication complexity (in terms of number of messages being sent) of your algorithm.
Is it possible to use a different communication pattern to solve this problem? If so, what is the communication complexity for that algorithm?
Submit the following:
1. Pseudo code. 2. Your report.
CS Help, Email: tutorcs@163.com
6 Grading Scheme
This assignment will be graded out of 100. For your information, the grading scheme is shown in the following table.
Percentage
One car system 40% M car system 40% Analysis 20%
Computer Science Tutoring