15-412 Problem Set 2
Handed out: Wednesday, February 16, 2000
Due: Wednesday, February 23, 2000 at the end of class
This document is available at http://www.cs.cmu.edu/~412/homework/homework2
Instructions:
· These problems should be done individually.
· Please write all of your answers on this handout. Attach extra sheets of paper if necessary.
· Write your name on the first page of this handout!
· Please write your solution neatly.
· Some of the answers are numeric. Write down the intermediate steps in reasonable detail. Explain briefly but clearly in words if the steps are not obvious. If you are making assumptions, state them clearly.
· Please staple all pages together using one staple in the upper-left corner of the pages.
· Brevity is appreciated. Verboseness is not rewarded.
Name: ___________________________________
Student
ID: ________________________
I spent ___________ hours on this assignment.
Question
|
Max |
Points |
|
1 |
20 |
|
|
2 |
20 |
|
|
3 |
20 |
|
|
4 |
20 |
|
|
5 |
20 |
|
|
Total |
100 |
|
1. Cake
Production [20 points]
The following recipe describes the production of devil’s food cake.
Devil's Food Cake
2 cups dark brown sugar
1/2 c. butter - melted
5 eggs
3 tsp. cocoa (heaping spoonfuls)
2 c. flour
1 1/2 heaping tsp. soda
1 c. milk
1 tsp vanilla
Mix butter, sugar ,and vanilla, and then cream
thoroughly. Next add eggs
and beat again. Add cocoa. Sift flour and soda
together. Add sifted mixture
and milk alternately to creamed mixture. Bake for 20
minutes in oven
preheated to 375 degrees.
This cake is so delicious that you decide to mass-produce it for sale at the finest restaurants in the city. The pseudo-code below and on the next two pages is designed to mass-produce the cake. Each function is operating in a separate thread. Please complete the pseudo-code to ensure that the prerequisite ingredients are ready before the next step of production continues. Please use only semaphores for synchronization.
The following are the shared data structures and variables:
BuffType SugarContainer
[MAX_SUGAR];
BuffType ButterBuffer
[MAX_BUTTER];
BuffType CocoaBuffer
[MAX_COCOA];
BuffType FlourBuffer
[MAX_FLOWER];
BuffType SodaBuffer [MAX_SODA];
BuffType MilkBuffer [MAX_MILK];
BuffType CollectVanilla
[MAX_MILK];
BuffType CollectEgg [MAX_EGG];
int sugar_index = 0;
int butter_index = 0;
int cocoa_index = 0;
int flour_index = 0;
int soda_index = 0;
int milk_index = 0;
int vanilla_index = 0;
int egg_index = 0;
/*
* Add and initialize additional shared items here
*/
The following functions are the body of the threads that produce the ingredients:
void CollectSugar()
{
SugarContainer[sugar_index++]
= FULL;
}
void CollectButter()
{
ButterContainer[butter_index++]
= FULL;
}
void CollectCocoa()
{
CocoaContainer[cocoa_index++]
= FULL;
}
void CollectFlour()
{
FLourContainer[flour_index++]
= FULL;
}
void CollectSoda()
{
SodaContainer[soda_index++]
= FULL;
}
void CollectMilk()
{
MilkContainer[milk_index++]
= FULL;
}
void CollectVanilla()
{
VanillaContainer[vanilla_index++]
= FULL;
}
void CollectMilk()
{
MilkContainer[milk_index++]
= FULL;
}
void CollectEgg()
{
EggContainer[egg_index++]
= FULL;
}
The following functions is the body of the thread that collects all the ingredients, follows the recipe, and bakes the cakes:
void BakeCake()
{
PreheatOven();
while
(FOREVER)
{
MixButterSugarVanilla();
CreamMix();
AddEggs();
BeatMix();
AddCocoa();
SiftFlourAndSoda();
AddFlourSodaMilk();
CreamMix();
PlaceMixInPan();
Bake();
RemoveCake();
CleanKitchen();
}
}
2. Traffic
Gridlock [20 points]
Consider the intersection of two streets, one running
north-south and the other running east-west, controlled by a traffic signal
light as follows:
·
For eastbound and westbound traffic, the signal light is
flashing yellow, indicating that cars approaching the intersection heading
either east or west may proceed immediately through the intersection unless
another car is already in the intersection traveling north or south.
·
For northbound and southbound traffic, the signal light is
flashing red, indicating that cars approaching the intersection heading either
north or south must stop before entering the intersection, and can only proceed
across the intersection if no cars are currently in the intersection traveling
either east or west.
·
Any number of cars heading east or west may be in the
intersection at the same time, but at most one car heading north and one car
heading south may be in the intersection together, and cars heading north or
south may not be in the intersection at the same time as cars heading east or
west.
A solution to the synchronization needs of the cars, as
described above, could be achieved by implementing the following two
procedures:
·
enter_intersection(direction) : called by a car before entering
the intersection heading in the specified direction (north = 0, east = 1, south
= 2, east = 3).
·
exit_intersection(direction) : called by a car when leaving the
intersection after crossing in the specified direction (0 : : : 3) and arriving
at that side of the intersection.
Using pseudo-code similar to that used in class or in the
textbook, give the following two separate solutions to this problem:
(a) Using a Hoare monitor, with enter_intersection and
exit_intersection as entry procedures of the monitor.
(b) Using a Mesa monitor, with enter_intersection and
exit_intersection as entry procedures.
Your two solutions should allow maximum concurrency between cars crossing the intersection, but (unlike a real traffic intersection) must avoid deadlock and starvation.
3. 1-level
Page Table and Shared memory [20
points]
Consider two processes running on a UNIX-ish system that implements virtual address space but not demand paging. These processes are sharing the code segment as well as 1 small global array. Please complete the diagram on the following page that depicts the physical memory of the system, as well as the virtual memory and page table for each process.
You may locate the items in any legal location in physical memory. Please follow the virtual memory convention used in class (code at the bottom, stack at the top).
Please label the diagram to identify the contents of each
page and frame and draw arrows depicting the relationship between each occupied
virtual page, page table entry, and physical frame.
The system is configured as follows:
Physical Address space: 64KB
Virtual Address space: 32KB
Page Size: 4KB
The processes are configured as follows:
Process 1:
Code (Shared): 5KB
Heap (Shared): 500B
Heap (Private): 6KB
Stack: 8KB
Process 2:
Code (Shared): 5KB
Heap (Shared): 500B
Heap (Private): 2KB
Stack: 7KB
4. 1-level vs.
2-level Page Tables [20 Points] Consider a computer with 64Kbyte of physical memory and a
frame size of 8Kbytes. The virtual
memory has 8 pages. There are two processes (P1 and P2) running from the same
code segments on this computer. P1’s
stack size is 2 Kbytes, its heap size is 16Kbytes, and its code size is
16Kbytes. P2’s stack size is 6Kbytes
and its heap size is 3Kbytes. The code
segment is shareable between the processes. a) Assuming the memory architecture uses a single-level page
table scheme, complete the schematic diagram showing the page tables of the two
processes. Give appropriate values to
the page table entries and draw arrows showing this association. b) Now assume the machine uses a 2-level paging structure,
where the level-1 page table contains 4 entries. Complete the schematic diagram
below. You need to draw the 2-level
paging structure, fill out the page table, and sketch the arrows showing the
association between virtual address and page table, and between page table and
physical memory. c) If P1’s heap size is increased by 4 Kbytes, what does
the page table in b) look like? Mark
your answer on the same diagram above using a different color of ink/marking agent to indicate the change. Consider a computer that uses a single-level paging scheme
with no data cache. The hardware
provides a 32 entry translation lookaside buffer (TLB), a.k.a. translation
buffer. The TLB read access time is 2 ns (nanoseconds). A memory access takes 20ns. a) How long does a memory access take in the case of a TB
hit? A miss? c) What is the effective
memory-access time if we have a TB hit ratio of 80%? Effective memory-access time indicates the
average amount of time a memory access takes.
d) What is the minimal hit ratio that will guarantee the
effective access time of at most 22ns?
5.
Memory Access [20 Points]