COMP3230 Principles of Operating System
Assignment 2
Tesla Factory Production Line
Details of assignment 2 please refer to the source code and assignment 2 document
Department of Computer Science, HKU 1
Objectives
• Use Pthread library to write multithreaded program • Use semaphores to handle thread synchronization
• Use semaphores to limit resource usage
• Learn parallel programming
• Solve deadlock problem
Department of Computer Science, HKU
2
Prerequisites
• Program in C (prerequisite of this course) • Review Tutorial 1
• Self-learning materials on Moodle
• C Library: https://youtu.be/JbHmin2Wtmc
• Tutorial3&4
• MultithreadprogrammingwithPthread • Thread synchronization with Semaphore
Department of Computer Science, HKU 3
System Overview
• Simplified manufacturing process
• 7 car parts need to be built for making a car • 1 skeleton
• 1engine
• 1chassis
• 1carbody
• 7windows
• 1body
• 4 tires
• 1batterypack
Skeleton 1 Engine 1 1
Chassis 1
Window Body Tire Battery Pack
7
1
1
4
1
Car
Department of Computer Science, HKU
4
Dependency Relationship
• Consumes skeleton, engine, and chassis àRelease or “produce” storage space.
• Produce bodyàconsumes space
Produce partsàconsume storage space
• Consumes body, battery, tires, and windows. àRelease or “produce” storage space
• Produce caràDoesn’t consume space
Department of Computer Science, HKU 5
These semaphores are not directly accessible to you. However, the value of semaphores will be changed as you call functions defined in production.h.
Inside libTeslaFactory.a
• Resource tracking
Department of Computer Science, HKU 6
Inside libTeslaFactory.a
• makeXXX():
Department of Computer Science, HKU 7
sem_wait() is used for makeXXX() sem_trywait() is used for tryMakeXXX()
Inside libTeslaFactory.a
Department of Computer Science, HKU 8
Inside libTeslaFactory.a
makeBody() will call _requestSpace() here.
Once the production process starts, it will run until the end. If some parts are missing, tryMakeBody() will keep trying until all parts are acquired.
Department of Computer Science, HKU 9
Inside libTeslaFactory.a
makeCar() won’t request space
Department of Computer Science, HKU 10
Q1. Complete the simple multithreaded version
Job IDs are continuous numbers. Here we can use a for loop to enqueue Job IDs to the queue. You can also manually type “SKELETON”, “ENGINE”, … if you find it is clearer.
Department of Computer Science, HKU 11
Q1. Complete the simple multithreaded version
Create num_typeB robots for type B robots and num_typeC robots for type C robots. One pthread represents one rotbot.
Don’t forget to join all robot threads.
Department of Computer Science, HKU 12
Q2 Implement a deadlock free multithreaded program
• Strategy 1: Deadlock prevention
• The production process is executed in a way that we can be sure there won’t
be any deadlock.
• E.g.: The hungry philosopher example in T4àthose philosophers produce an agreement to ensure there is no deadlock.
• Hintforthisstrategy:Youcaneitherhaveacleverschedulertoarrangethe order of jobs so that there’s no deadlock or your robots are smart enough to pick jobs to ensure the whole production process is deadlock free.
Department of Computer Science, HKU 13
Q2 Implement a deadlock free multithreaded program
• Strategy 2: Deadlock detection
• We don’t know if there will be a deadlock situation, but we can detect one.
• E.g.: If one robot has been waiting for a space for unreasonable amount of time, we can say that there is a deadlock. Then you may need to rearrange the jobs so that the deadlock can be broken.
• Hint for this strategy: If you only want your robot wait for certain seconds, you can use those timedTryMakeXXX() functions. Be noted, you should determine a reasonable amount of waiting time. If you wait too long, deadlock detection will degrade the performance of production.
Department of Computer Science, HKU 14
Hint
• Code provided in Q1 is simply an example.
• You can use more queues and semaphores to help you solve deadlock problem and improve the performance.
15
Common Parallel Programming Technique
• Master-slave model
E.g.: T3 Exercise 1. Each working thread doesn’t care about the total range. They just calculate the numbers they are assigned to.
Master thread(usually the thread which executes main() function) arranges/coordinate the jobs. It is responsible for keep tracking the progress. It may need to dynamically adjust the job arrangement in read time in case something goes wrong.
Department of Computer Science, HKU 16
Working threads don’t need to ”think” or consider the whole picture of the process. Just do the job it is asked to do.
Common Parallel Programming Technique
• Autonomous thread model
• No centralized command system
• Each working thread can work by their own • All working threads share the same goal
• Each working thread must be wise
• Each working thread knows what to do to
contribute the most to the goal.
Put the result into the result pool
Pick the best suitable task
Department of Computer Science, HKU
17
Common Parallel Programming Technique
• Hybrid model
You may combine Master-slave model and autonomous thread model together.
For example, some autonomous working threads can serve as a “team leader” while other working threads just do what the leader tell them to do.
Working Thread
Team leader
Working Thread
Team A
Team B
…
• If the decision-making process is time consuming or needs to compete to access certain resources, hybrid model may reduce the decision-making overhead while keeping certain level of autonomy.
Working Thread Working Thread
Team leader
…
Department of Computer Science, HKU 18
Common Parallel Programming Technique
• Work stealing
• Assume each working threads has a job queue.
• If one working thread has completed all jobs in its job queue, this thread can “steal” jobs from other threads.
• Purpose: keep all working threads busy to maximize performance.
Working Thread 1
Working Thread 2
Working Thread 3
…
Example
• Thread 1 has finished all its jobs in job queue 1.
• Thread 1 checks job queues of other threads
• Thread 1 steals jobs from other threads by dequeuing
other threads’ job queue and enqueue jobs to its own job queue.
• What kind of jobs should thread 1 steal so that the overall performance can be improved?
• How many jobs should thread 1 steal before it starts to work again?
3 2 7 1 5
Job queue 1
Job queue 2
Job queue 3
19
5 6 1 2
See if there’s any job worth stealing.