CS-350 – Fundamentals of Computing Systems
Homework Assignment #7
You have entered the CubeSat Developer’s Workshop (it’s real thing!)
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.
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.
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
a) Write a pseudo-code for a generic “roomie” process that only uses semaphores to perform synchronization. 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. Specifically, 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
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx