COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
1
Assignment 2: Tesla Factory Production Line Control System
Table of Contents
Objectives................................................................................................................................................2
Prerequisite.............................................................................................................................................2
Background Story.....................................................................................................................................2
System overview......................................................................................................................................3
Implementation details............................................................................................................................4
Control of resources...........................................................................................................................................................4
Job assignment...................................................................................................................................................................4
Manufacture process.........................................................................................................................................................5
Questions (85 marks + 20 bonus marks)....................................................................................................6
Q1 Complete the single threaded version (20 marks)........................................................................................................6
Q2 Implement a naïve multithreaded program (35 marks) ..............................................................................................7
Q2.1 Implement Thread-safe queue (10 marks)...........................................................................................................7
Q2.2 Multithreaded production(15 marks)...................................................................................................................7
Q3 Make it stable, make it run fast (50 marks, 20 bonus marks included) .......................................................................9
General requirements (15 marks)........................................................................................................... 10
Reference .............................................................................................................................................. 11
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
2
Objectives
In this assignment, you need to write a multithreaded program in C with pthreads
simulating the production process of Tesla electric cars. Upon the completion of
this assignment, you should be able to: • Use pthread library to write multithreaded program
• Use semaphores to handle thread synchronization
• Use semaphores to limit the resource usage
• Solve producer and consumer problem
Prerequisites
Before you start to work on this assignment, you should know the concepts of
thread, semaphore, as well as deadlock. A review of lecture notes and workshop 3
slides is highly recommended, or you will have trouble dealing with this
assignment. You are also required to be able to code in C (as the course
requirement states).
Background Story
Tesla Motors is the leading company of electric cars and is also the first
company who made electric cars so popular around the world. Tesla not only put a
lot of high technologies in their cars but also how they manufacture electric
cars. Tesla factory almost automated the whole production process by using a lot
of smart trainable robot workers. There are some videos in the reference section
you may check to learn more about the simplicity of the design and the
complexity of making it possible.
Your job in this assignment is to write a program to simulate the production
process of Tesla electric car and make the production process as efficient as
you can with limited resources.
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
3
System overview
To simplify the process of manufacturing Tesla electric cars, 7 car parts need
to be built before the final assembly of a car. These parts are skeleton,
engine, chassis, body, window, battery. The relationship among these parts can
be found in the graph below:
Those parts which no arrow is pointing at depend on their own raw materials. We
just assume that they are ready by default. The production rule is: 1 skeleton,
1 engine, and 1 chassis make 1 car body; 7 windows, 1 body, 4 tires, and 1
battery pack make 1 car. 17 parts required for making 1 car.
You will be given 9 source code files of this system as shown below:
File name Function
definitions.h Defines system variables like production time. You are
not allowed to change those variables
main.h and main.c The main program, initiate factory status, manage and
schedule workers, report results
worker.h and worker.c Contains the worker(thread) functions
job.h and job.c Contains the manufacturing functions
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
4
Implementation details
You need to also read the source code to fully understand the program. Only
pivotal parts are introduced here.
Control of resources
Control of resources including number of robot workers, number of storage space
in the factory as well as each car parts is implemented with counting semaphore.
Initial values of sem_worker and sem_space are predefined while the initial
value for each car parts is set to 0. The initiation process is done by the
function initSem().
main.c:
Job assignment
Job is assigned to each robot worker(thread) via predefined struct work_pack.
Each work pack contains worker ID, a reference to the job queue, and the
resource package (semaphore package, struct resource_pack). You can find the
above structures in work.h:
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
5
Manufacture process
Since this is only a simulation of Tesla factory production line, there’s no
need to implement how these car parts are built or how a car is assembled.
Instead those functions just sleep a certain amount of time for each production
job. You can find these build functions in job.c. Time lengths are defined in
file definitions.h which you are not supposed to change. If a car part needs
some other parts as its raw material like the car body, the worker must
wait(sem_wait) for the completion of building those parts. After a part of the
car is built, the worker needs to put it in the storage space(sem_post to
sem_space) and notify its own semaphore(sem_post to sem_) that one
piece has been made. Note that each part no matter what type it is will take
only one unit of storage space and the final product electric car won’t take any
factory storage space as the car will be sent out.
Example of making car body in job.c:
Get and make an item:
definitions.h: you may change DEBUG to 1 to debug. The program will print
more information to help you debug. Don’t forget to change DEBUG to 0
before you make your final submission. Or you can just use gdb instead.
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
6
Questions (85 marks + 20 bonus marks)
Q1 Complete the single threaded version (20 marks)
The code you download is an incomplete program of the production line control
system. What you need to do is to complete the single threaded version and get
familiar with the program.
Your tasks are:
1. Copy the queue.c and queue.h from your first tutorial exercise to directory q1.
2. In file job.c, you should complete 2 functions: makeBattery and makeCar. Functions
for making other parts have been implemented. You may refer to those functions and
have an idea of how they work before you implement these 2 functions.
3. Then you need to add lines to main.c to complete the rest of the program so that
all parts will be made sequentially. There are 2 phases: Task scheduling and
production. You need to finish both parts. To make it simple for this question,
only one car will be made. (15 marks for coding)
4. After you finish your code, you can compile your code by typing in command make in
your Linux console (makefile has been provided). If there’s no error, you can run
your program by executing ./tesla_factory.out.
5. Include a screenshot of your program. Please add a line in main.c to print out
your name and your university ID at the beginning of your program. (5 marks for
screenshot)
Since we only consider the situation that uses one robot worker to make one car
with sufficient space, these corresponding parameters will be hard-coded in the
main function.
Here’s a sample screenshot of the output of question 1 (debug mode off):
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
7
Q2 Implement a naïve multithreaded program (35 marks)
Q2.1 Implement Thread-safe queue (10 marks)
Copy your queue.c from the first tutorial exercise to directory q2_queue. Modify
the code and make your queue thread safe with semaphore. There are some sample
test cases provided in main.c for you to check if your queue is thread safe.
Test enqueue
N threads will be created, and each thread will enqueue number ‘1’ to the
queue. When all threads are done with enqueuing, sum up all the elements
in the queue. If it’s thread safe, all threads can successfully enqueue
and the value of sum should be equal to the number of thread N.
Test dequeue (front/rear)
First enqueue N elements in the queue. Then launch N threads and each will
dequeue once from the queue. If the queue is empty after being dequeued N
times, then the dequeue function is thread safe.
You can also design other test cases to check thread safety of other functions.
Q2.2 Multithreaded production(15 marks)
Now you have some basic ideas about how the program works. Copy the completed
code from q1 to q2 and your thread-safe queue from q2_queue to q2. You will make
it a simple multithreaded program that multiple workers will work simultaneously
to speed up the production process. Your program in Q2 should be able to produce
more than one car with multiple threads and see speed-up from multithreading. We
assume that the storage space is always sufficient for now.
In main.c number of cars to be made, number of storage space and the number of
workers are passed to the main function as parameters for the ease of testing
later.
Now you need to calculate the total number of different car parts for producing
num_cars cars. Then enqueue them (as jobID) to the queue and launch num_workers
threads to start the production. Each worker thread should be able to dequeue a
jobID from the job queue and do the job accordingly until there’s no job
left.(20 marks)
You need to include a screenshot of your testing your code with different
parameters by executing run.sh (5 marks). Sample output is shown below (debug
mode disabled), you should see speedup as the number of threads increases (up to
the limit when the number of jobs equals the number of threads).
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
8
The production time of 4 cars decreased as the number of worker threads
increased.
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
9
Q3 Make it stable, make it run fast (50 marks, 20 bonus marks included)
In Q2, there’s no limitation on the storage space. If we take storage space into
consideration, we may encounter deadlock. Say we have 2 workers and only 1 unit
of storage space. Here’s an example of deadlock:
1. Worker 1 gets jobID=0, and requests 1 unit of storage space and make a skeleton.
2. Worker 2 gets jobID=1 and wants to build an engine. Worker 2 requests 1 unit of
storage space but failed, because it’s been taken to store the skeleton. Worker 2
stops and waits for space…
3. Worker 1 gets jobID=2 building a chassis. Worker 1 requests 1 unit of storage
space but failed either. Worker 1 stops production and waits for space…
4. Both worker 1 and worker2 are waiting for a free space infinitely… Deadlock
appears.
Copy your code from q2 to q3 and tackle this deadlock problem. There are some
sample test cases in q3/run.sh. You can also run more test cases by your own
making sure that deadlock won’t appear in any cases.
Hints:
a. Deadlock detection: you don’t know whether you will encounter deadlock or not
ahead. But once your program detects that certain threads runs for
unreasonable amount of time, you know that deadlock happens. Then you figure
out a way to break the deadlock so that the production process can move on.
sem_trywait() or sem_timedwait() may be useful here.
b. Deadlock prevention: once the production goal is set, you know the number of
each part to achieve the goal. You also know how many unit of space you have.
Your program can analyse these data and execute in a way that is always
deadlock free.
c. Feel free to use more semaphores and queues if necessary.
Requirements:
1. You must use your own implementation of thread-safe queue in Q3.
2. Your program should accept any numbers of workers to produce different number of
cars. You should test your program with many combinations of input parameters
(number of cars, number of spaces, number of workers) and make sure your program
is deadlock free and bug free. Your program should be able to handle deadlock
when given small number of storage space and worker threads.
3. Run your program multiple times with different numbers of threads and collect
their running time, then draw a graph to show the scalability of your program.
You may fix the number of cars and show the relationship between the number of
threads and production time. Put the graph into your report. You should explain
the results and analyse the efficiency of your program. (10 marks for the
analysis)
4. Clearly introduce your deadlock handling algorithm in your report and proof that
it’s deadlock free. (10 marks for explanation and proof).
A set of randomly generated test cases including extreme ones for testing
deadlock will be used to mark all submissions from the whole class.
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
10
Marking scheme:
1. Deadlock free implementation: 30 marks (20 bonus marks included);
Your total mark = 30 × ∑ 𝑇𝑖 𝑚𝑖𝑛
𝑇𝑖
𝑁𝑖=1 , where 𝑇𝑖 is your runtime of the ith
test case, 𝑇𝑖 𝑚𝑖𝑛 is the minimum time among all your classmates.
2. Deadlock handling algorithm explanation and proof in report (requirement
4): 10 marks;
3. If any deadlock case is found with your program, you get 0 mark for
implementation and explanation from above two. Your performance won’t be
recorded either
Deadlock judgement: sequentially producing car parts one by one to make a
car costs about 40s (as Q1 tested). So if your program fails to finish
producing N cars within N*60 seconds, it’ll be considered as a deadlock
situation.
4. Scalability analysis (requirement 3): 10 marks;
General requirements (15 marks)
1. Put your answer source code of question 1 in directory named q1, source code of
question 2 in q2, and question 3 in q3; name your report as follows:
ID>_.pdf. Say your university ID is 6666688899 and your name is Ying-Chun
Leung, so your report name is 6666688899_YingChunLeung.pdf (First name first).
Then put q1, q2, q2_queue, q3 and your report in a directory named
ID>_
_submission, then zip it to a zip file
ID>__submission.zip (5 marks).
Submission folder structure(sample):
2. Code quality: use meaningful variable names and function names, add necessary
comments if possible to help others read your code (5 marks).
3. Report quality: we don’t expect a long report. Express your idea briefly and
logically by any means (graphs, charts, tables, etc.). Good structure, no obvious
mistakes (5 marks).
Make sure that your code for each question can be compiled and run without
problem on workbench, or you will get 0 mark for that question no matter how
well you explain your idea in the report. If your program can’t run, we can’t
tell if your statements are true or not.
If you create more worker threads than num_workers, 0 mark will be given for
that entire question.
Reminder: Start working on your assignment ASAP. You are recommended to write
code and debug your program on workbench directly.
If you want to keep your program running even if you terminate your ssh session
on your local machine, here are two recommended command in Linux you can learn
by yourself: nohup and tmux. There are many tutorials on Google and YouTube.
COMP3230B: Principles of Operating Systems 2019
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
11
Before you use nohup, make sure you know how to check your job (cmd: job) and
kill your program (cmd: kill).
Google, Stack Overflow and GitHub are good places to help solve your problems.
Try to find out solutions by yourself before you bring them to the teaching
stuff.
Some questions are not allowed to asked:
1. Ask for answers to compare with your own code or check your answer with TA
before you submit it
2. Ask if your idea/algorithm work or not. You have an idea, you should find ways
to proof/disproof it.
3. Questions related to programme in C. This is not a programming course, you
should have known C before taking this course(course prerequisite). If you
don’t know how to program in C, there are self-learning materials on Moodle,
tons of great tutorials on YouTube…
4. Debug your program. Try to debug your program with printf or gdb by yourself.
Reference
1. How the Tesla Model S is Made | Tesla Motors Part 1 (4:54)
2. How Tesla Builds Electric Cars | Tesla Motors Part 2 (3:25)
3. Electric Car Quality Tests | Tesla Motors Part 3 (1:49)
4. National Geographic: Tesla Motors Documentary (50:05)
5. A Gentle Introduction to tmux: https://hackernoon.com/a-gentle-introduction-to-tmux-
8d784c404340
6. tmux shortcuts & cheatsheet: https://gist.github.com/MohamedAlaa/2961058
7. Unix Nohup: Run a Command or Shell-Script Even after You Logout:
http://linux.101hacks.com/unix/nohup-command/
8. nohup(1) - Linux man page: https://linux.die.net/man/1/nohup
9. nohup Execute Commands After You Exit From a Shell Prompt:
https://www.cyberciti.biz/tips/nohup-execute-commands-after-you-exit-from-a-shellprompt.html
10. vim + tmux - OMG!Code (1:17:20)
- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp
联系我们 - QQ: 99515681 微信：codinghelp
程序辅导网！