CS-350 - Fundamentals of Computing Systems
Homework Assignment #7
Due on November 14, 2020 at 11:59 pm
Prof. Renato Mancuso
Renato Mancuso
1
CS-350 - Fundamentals of Computing Systems::Homework Assignment #7 Problem 1
Problem 1
You have entered the CubeSat Developer’s Workshop (it’s real thing! See here: https://www.cubesat.org/)
and you are progressing towards the design of your very own cube satellite. In terms of hardware, you are
trying to settle on how many cores your main processor needs to handle all the software workload. The
deployed software components need to collect data from the onboard sensors and to keep the satellite on the
right orbit and 3D orientation.
You have computed that at the very minimum, you need three periodic components. These are (1) “star
tracking” to identify the 3D pose of the satellite using the position of the visible stars in the field of view.
Star tracking needs to be done every 19 ms, with each instance taking up to 4.5 ms processor time; (2)
“orbit correction” to be done every 22 ms and that requires a worst-case computation time of 4.5 ms; and
(3) ground-station radio link handling which takes up to 3 ms of CPU time and requires to be performed
every 9 ms.
Now on to the workbench to figure out the following:
a) Can you conclude that you should be able to get away with a single-core CPU and RM scheduling?
Motivate your answer and show your work.
b) To achieve better bandwidth on the radio link, it would be best to add an on-board atomic clock and
the appropriate atomic time sampling task. Atomic clock sampling needs to be done every 6 ms but it
takes only 1 ms to complete in the worst case. Can you still use RM and a single-core CPU? Motivate
your answer and show your work.
c) You just got off the phone with your other friends at the CubeSat workshop. They want to create
a mesh network where satellites can exchange information among themselves and relay messages to
collaboratively increase their visibility from the ground. To perform inter-satellite communication, a
new task with a WCET of 4 ms and a period of 15 ms needs to be added to all the ones considered so
far. Can you still use RM and a single-core CPU? Motivate your answer and show your work.
d) To ensure future upgradability and be able to comfortably schedule all the necessary workload, you are
now considering using a processor with two identical CPUs. Use RM-FF to produce a task-to-CPU
assignment for the considered tasks in taken in the following order: (1) star tracking, orbit correction,
ground-station communication, atomic clock sampling, and inter-satellite communication.
e) Would it be possible to schedule the system using Global EDF? If necessary, draw the resulting schedule
up to time 44 ms.
f) Having studied Global EDF, how would Global RM work? Provide a brief description of its policy and
draw the schedule produced by Global RM on the considered system up to time 44 ms.
2
CS-350 - Fundamentals of Computing Systems::Homework Assignment #7 Problem 2
Problem 2
Consider the code for 2-party mutual exclusion between two processes, namely Process i and Process j,
reported in Listing 1. Here, mutual exclusion is performed so that only one process at a time can issue a
print line() command. The code of Process j is identical, except for all the occurrences of “i” having
been replaced with “j” and vice-versa. The flag array is shared among all the processes, and so is the
variable turn. Always assume an in-order CPU.
Listing 1: 2-party mutual exclusion.
1 Process i:
2 Repeat:
3
4 /* REMAINDERSECTION */
5
6 flag[i] = true;
7
8 print line("Process i: Entering CS");
9
10 while (flag[j]) {
11 if (turn == j) {
12 flag[i] = false;
13 while (turn == j);
14 flag[i] = true;
15 }
16 }
17
18 /* CRITICAL SECTION−− BEGIN */
19 ...
20 print line("Process i: Inside CS");
21 ...
22 /* CRITICAL SECTION−−END */
23
24 turn = j;
25 flag[i] = false;
26
27 /* REMAINDERSECTION */
28
29 Forever
Answer the following questions.
a) What is the value to which we should initialize the items in the flag array for the algorithm to
guarantee 2-party mutual exclusion?
b) Explain the implications of initializing turn to j if only Process i will attempt to acquire the resource?
c) Can the following output be produced by the code? Motivate your answer.
Process i: Entering CS
Process i: Inside CS
Process j: Entering CS
Process i: Entering CS
Process j: Inside CS
Process j: Entering CS
Process j: Inside CS
Process j: Entering CS
Process j: Inside CS
...
d) Your colleague has modified this code to perform an optimization. He has inserted a break command
between line 12 and line 13. Is this going to be a problem? If you believe that there is a problem,
produce a sample of execution interleaving that illustrates the problem.
Problem 2 continued on next page. . . 3
CS-350 - Fundamentals of Computing Systems::Homework Assignment #7 Problem 2 (continued)
e) Change the code to leverage semaphores instead of the software-based approach currently employed in
the code. Specify how you are going to initialize any semaphore you decide to use.
4
CS-350 - Fundamentals of Computing Systems::Homework Assignment #7 Problem 3
Problem 3
You and your roomates are studying for CS-350 and decide that you are going to work as long as you can
munch on some pizza. A standard pizza has 8 slices 1. The behavior that you and your roomies have is the
following. If pizza is available, you first grab a plate, which are in limited number (less than 8). You then
go ahead and grab a slice of pizza. You then study for CS-350 and eat the pizza slice. After eating the slice,
you wash and put back the plate as a courtesy to your roomies. After that, you simply start over and keep
doing the same steps forever. If no plates or no pizza slices are available, then you block and do nothing at
all.
a) Write a pseudo-code for a generic “roomie” process that only uses semaphores to perform synchro-
nization. Collectively, the processes should follow the behavior described above. For this part, assume
that the pizza slices are never replenished.
b) Assume for a second that you and your roomies are fancy people. That means you will categorically
refuse to eat pizza unless you have a fork and a knife at hand. There are exactly 3 knives and 5 forks
in the apartment. So it is important that you synchronize with your roomies to acquire a fork and
a knife before attempting to grab a slice; you are also supposed to wash and put back the silverware
once done eating your slice. Modify the code you wrote above to handle acquisition/release of forks
and knives making sure that the roomies do not end up stuck forever while pizza is still available.
c) Modify/augment the code written in the previous step to handle replenishment of pizza slices. Specif-
ically, handle the case in which right before grabbing the last slice of pizza, a roomie detects that all
the pizza is gone and orders a new pizza from the nearest MamaJane pizzeria. After ordering, the
mindful roomie goes on with the same protocol as before. It is crucial, however, that it is never the
case that more than one roomie orders a pizza at the same time. Moreover, the code for the MamaJane
employee process should be provided. The MamaJane employee does nothing until a pizza is ordered,
then cooks and delivers the pizza in an endless cycle.
1As defined by the Special Committee on Pizza Standardization which met in Naples, Italy in 1925.
5
CS-350 - Fundamentals of Computing Systems::Homework Assignment #7 Problem 4
Problem 4
Code: In this problem you will write a function to navigate a complex multi-level structure that has an
emerging structure that is progressively revealed as the different hashes are cracked.
a) The code you have written in the previous assignments should have provided you with a basic unit,
namely the Dispatcher, capable of creating a work queue and distributing the work to a set of worker
threads. In this problem, we will further extend the code to introduce a super-entity responsible for
coordinating the macro-phases of the processing flow. Because in the end the goal is to find a treasure,
we call the coordinating super-entity the Pirate.
Let us first review the processing problem at hand and then define the operating scope of the Pirate
entity. The file provided in input is still a list of hashes. Just like in the previous homework assignment,
the list contains hashes that can be immediately cracked and result in some non-negative integer
number. Other hashes are impossible to crack. And other yet are crackable with a compound hint.
The idea is that the compound hint can be constructed from the integer values of the hashes that were
immediately crackable.
Specifically, as you crack those hashes that have a simple answer, your code will produce a sequence
of integers. Consider the sorted list of integers L = {A,B,C,D, . . .} such that A > B > C > D . . ..
Then, a compound hint has the form: “α; k;β” where α and β are some integers in L and such that
α < β. Note that α and β are not necessarily contiguous in L. Finally, k is any integer between α and
β but different from them. Moreover, no two compound hints share the same α or β. So if a compound
hint was of the form “α; k;β” (for some k), then there cannot exist any compound hint with the form
“α; k′;β” or “β; k′; γ” or “α; k′; γ” or “γ; k′;α” or “γ; k′;β”.
Let’s make an example. Suppose we have the following input file content:
202cb962ac59075b964b07152d234b70
d81f9c1be2e08964bf9f24b15f0e4900
03f206ba972ab43c585255d26826c4b3
37cba5957ccb647a5fb310923ac8794a
You will notice that the first and second hash can be reversed as “123” and “345”, respectively. While
the third and fourth hash appear to be initially uncrackable. We can then construct any compound
hint that follows the format “123; k; 345” and where k ∈ {124, . . . , 344}. We then discover that the
fourth hash can be cracked with the compound hint “123;234;345”. The output produced by the code
should then be2:
123
345
123;234;345
03f206ba972ab43c585255d26826c4b3
Write a Java class Pirate.java that defines a method called findTresure(...) that internally uses
the dispatcher to initially split the hashes in input to the worker threads. There are no restrictions
on the exact arguments and return value of this method, so use whatever you deem more appropriate.
The job of findTresure(...) is to coordinate the processing steps. After organizing the first run, it
collects the result from the worker threads (cracked hashes and timed out hashes) and organizes a new
run. In the second run, it will consider each pair of numbers α, β in the resulting L list and use the
worker threads to check if any timed-out hashes can be cracked with a compound hint constructed
using α and β.
2The order of the lines in the output is not important.
Problem 4 continued on next page. . . 6
CS-350 - Fundamentals of Computing Systems::Homework Assignment #7 Problem 4 (continued)
Apart from implementing the findTreasure(...) method, the class should also include a public
static void main(String [] args) function. The main(...) function should accept 3 parameters
from the calling environment. The path to the file is passed as the first parameter by the calling
environment. The format of this file is the same as in the previous assignments. The second parameter
passed to your code is the number of available CPUs. The third parameter encodes the length of the
timeout for (currently) uncrackable hashes expressed in milliseconds.
It is responsibility of the main(...) function to internally invoke the implemented findTreasure(...)
method only once and make sure that the desired result is printed in output.
Submission Instructions: in order to submit this homework, please follow the instructions below for
exercises and code.
The solutions for Problem 1-3 should be provided in PDF format, placed inside a single PDF file named
hw7.pdf and submitted via Gradescope. Follow the instructions on the class syllabus if you have not received
an invitation to join the Gradescope page for this class. You can perform a partial submission before the
deadline, and a second late submission before the late submission deadline.
The solution for Problem 4 should be provided in the form of Java source code. To submit your code,
place all the .java files inside a compressed folder named hw7.zip. Make sure they compile and run cor-
rectly according to the provided instructions. The first round of grading will be done by running your code.
Use CodeBuddy to submit the entire hw7.zip archive at https://cs-people.bu.edu/rmancuso/courses/
cs350-fa20/scores.php?hw=hw7. You can submit your homework multiple times until the deadline. Only
your most recently updated version will be graded. You will be given instructions on Piazza on how to
interpret the feedback on the correctness of your code before the deadline.
7

欢迎咨询51作业君