stau.space
Threads and Scheduling
1# **Assignment 02: Threads and Scheduling**
2
3University of Puerto Rico at Rio Piedras
4Department of Computer Science
5CCOM4017: Operating Systems
6
7## **Introduction**
8
9In this project the student will simulate a **Shortest Job First** scheduling
10algorithm for a distributed system that consists of one embedded device and a
11central computer cluster.
12
13The student will assume that we have one embedded device that generates
14computational problems that are too heavy to be performed in their hardware,
15either because the device's battery will drain, they do not have enough memory,
16nor computational resources to perform them in a timely manner.
17
18We will simulate a computer cluster that will have a head node that receives
19requests for computing time from the embedded device, will put the jobs in a
20queue of processes, and then two different compute nodes will “execute”
21them.
22
23## **Objectives**
24
25* Practice threads implementations
26* Practice inter process communication using sockets (TCP) and a shared buffer
27* Identify critical regions
28* Implementation of mutual exclusion and semaphores
29
30**REMARK:** Your assignment MUST only use the primitive Locks and Semaphores
31objects. The queue must also be implemented by the student using a regular
32python list. **NO other synchronization, or synchronized object library may be
33used in this assignment.** The use of these libraries will immediately
34invalidate the assignment, and it will not be graded.
35
36## **Prerequisites**
37
38* Python:
39 * [www.python.org](http://www.python.org/)
40* Python threads:
41 * [https://docs.python.org/3/library/threading.html](https://docs.python.org/3/library/threading.html)
42 * [https://pymotw.com/3/threading/](https://pymotw.com/3/threading/) (good
43 tutorial with examples)
44* Python sockets (**TCP**):
45 * [https://docs.python.org/3/library/socket.html](https://docs.python.org/3/library/socket.html)
46* Threaded sockets (**You are NOT allowed to use this one for this assignment**)
47 * [https://docs.python.org/3/library/socketserver.html](https://docs.python.org/3/library/socketserver.html)
48
49## **Instructions**
50
51### **The embedded device:**
52
53The embedded device will consist of **one process (not threads)** that will:
54
551. Get the processes running in the computer where the simulation is running.
562. For each process obtained in step 1, send a different message to the cluster
57head node, with a random number that will simulate the time it takes for the
58process to complete.
59 * sleep a **random** **short** (1 to 5 seconds) random period of time
60 between sends.
61
62For instance if the embedded device gets the processes: top, ls, and cut, then
63the embedded device will send to the head node the messages:
64
65* `top:3`
66* `ls:1`
67* `cut:5`
68
69where 3, 1, and 5 are random numbers generated to simulate the time it took to
70execute each process. Note that in this example the syntax is
71`Process Name:cpu time`.
72
73Example of how to run the embedded device:
74
75```sh
76python edevice.py <server address> <server port>
77```
78
79where `<server address>` is the IP address of the cluster, and `<server port>`
80is the port number of the cluster.
81
82**Remark**: Your implementation of the edevice MUST be a process. You MUST use
83big port numbers less than 65,000
84
85### **The cluster:**
86
87The cluster will consist of three threads:
881. One thread that will simulate the head node:
89 * Receives the messages generated by the embedded device and
90 * puts the "processes" in the **Shortest Job First** Scheduler queue,
912. and two threads to
92 * extract the processes from the queue and "execute" them.
93
94The first thread will act as a **producer to the scheduler** by:
95
961. Listening to the embedded device messages.
972. Extract the time and process name out of the message and store them in a
98 shared queue.
99
100The other two threads will act as **consumers** by:
101
1021. Picking a message from the shared queue.
1032. Keeping a table of the processes attended by each consumer and the total
104 time consumed by each process.
1053. Sleep the time extracted from the message picked from the queue.
106
107For instance, let's assume the producer thread receives messages `top:3`,
108`ls:1`, `cut:5`, and puts them in the queue, and that the consumer 1 extracts
109`top:3`, and consumer 2 extracts `ls:1`, `cut:5`.
110
111Consumer 1 must have a list:
112```python
113[("top",3)] # total = 3
114```
115and consumer 2 must have a list:
116```python
117[("ls",1), ("cut", 5)] # total = 6
118```
119
120Example of how to run the cluster:
121
122```sh
123python cluster.py <server port>
124```
125
126**Note:** The consumers must not poll for messages in the shared queue
127(repeatedly ask for messages in the queue). The thread **MUST** block
128(Semaphores) until there is a message in the queue.
129
130Example output of the cluster:
131
132Consumer 1 consumed 3 seconds of CPU time
133Consumer 2 consumed 6 seconds of CPU time
134
135### **Other notes**
136
137Make every configuration variable a global variable. Example:
138
1391. Range of sleep times
1402. Range of process CPU time
141
142## **Rubric**
143
1441. Programs that do not run (can’t be tested) will automatically obtain 0
145 points.
1462. Documentation of the code and the README (10 pts)
1473. Use of an unsynchronized Data Structure for the messages (5 pts)
148 1. **Remember that the use of a synchronized data structure will invalidate
149 your project**.
1504. Implementation of Semaphores for blocking and not polling or busy waiting
151 (10 pts)
1525. Implementation of Mutexes to protect the critical regions. (Only the
153 critical regions) (10 pts)
1546. Use of the sleep libraries (5 pts)
1557. Implementation of TCP sockets for message communication(10 pts)
1568. Working implementation of the cluster server (35 pts)
1579. Working implementation of the embedded device. (15 pts)
158
159## **Deliverables**
160
161* The source code of the programs (well documented)
162* A README file with:
163 * Good description of the program
164 * How to use your program, how to execute the processes.
165 * Any additional reference used to perform the project and the names of
166 students who helped perform the project.
167 * Verbal collaborations are allowed, however any form of code sharing is
168 not allowed.
169
170## **Bonus**
171
172Implement the embedded devices (edevice.py) such that it sends the jobs to the
173compute server and waits for a response of the compute server instead of just
174randomly sleep to send the next job.