COMP3230B: Principles of Operating Systems 2019
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
The University of Hong Kong 1 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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. you may check to learn more about complexity of making it possible.
Your job in this assignment is to
process of Tesla electric car and
you can with limited resources.
There are some videos in the reference section the simplicity of the design and the
write a program to simulate the production make the production process as efficient as
The University of Hong Kong
Department of Computer Science
Academic Year 2019-2020 Semester 1
2
COMP3230B: Principles of Operating Systems 2019
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
The University of Hong Kong 3 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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:
The University of Hong Kong 4 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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_
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.
The University of Hong Kong 5 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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):
The University of Hong Kong 6 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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).
The University of Hong Kong 7 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
The production time of 4 cars decreased as the number of worker threads increased.
The University of Hong Kong 8 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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.
The University of Hong Kong 9 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
Marking scheme:
1. Deadlock free implementation: 30 marks (20 bonus marks included);
Your total mark = 30 × ∑𝑁 𝑇𝑖 𝑚𝑖𝑛, where 𝑇 is your runtime of the ith
𝑖=1 𝑇𝑖 𝑖
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:
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
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.
The University of Hong Kong 10 Department of Computer Science
Academic Year 2019-2020 Semester 1
COMP3230B: Principles of Operating Systems 2019
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:
Unix Nohup: Run a Command or Shell-Script Even after You Logout
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-shell-
prompt.html
10.vim + tmux – OMG!Code (1:17:20)
The University of Hong Kong 11 Department of Computer Science
Academic Year 2019-2020 Semester 1