Return to the Homework Index

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.



5. Memory Access [20 Points]

 

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?