Thursday, April 24, 2014

UPCASTING AND DOWNCASTING in C++

UPCASTING
Upcasting is converting a derived-class reference or pointer to a base-class. In other words, upcasting allows us to treat a derived type as though it were its base type. It is always allowed for public inheritance, without an explicit type cast. This is a result of the is-a relationship between the base and derived classes.
Here is the code dealing with shapes. We created Shape class, and derived CircleSquare, and Triangle classes from the Shapeclass. Then, we made a member function that talks to the base class:
void play(Shape& s) 
{
   s.draw();
   s.move();
   s.shrink();
   ....
}
The function speaks to any Shape, so it is independent of the specific type of object that it's drawing, moving, and shrinking. If in some other part of the program we use the play( ) function like below:
Circle c;
Triangle t;
Square sq;
play(c);
play(t);
play(sq);
Let's check what's happening here. A Triangle is being passed into a function that is expecting a Shape. Since a Triangle is aShape, it can be treated as one by play(). That is, any message that play() can send to a Shape a Triangle can accept.
Upcasting allows us to treat a derived type as though it were its base type. That's how we decouple ourselves from knowing about the exact type we are dealing with.
Note that it doesn't say "If you're a Triangle, do this, if you're a Circle, do that, and so on." If we write that kind of code, which checks for all the possible types of a Shape, it will soon become a messy code, and we need to change it every time we add a new kind of Shape. Here, however, we just say "You're a Shape, I know you can move(), draw(), and shrink( ) yourself, do it, and take care of the details correctly."
The compiler and runtime linker handle the details. If a member function is virtual, then when we send a message to an object, the object will do the right thing, even when upcasting is involved.
Note that the most important aspect of inheritance is not that it provides member functions for the new class, however. It's therelationship expressed between the new class and the base class. This relationship can be summarized by saying, "The new class is a type of the existing class."
class Parent {
public:
 void sleep() {}
};

class Child: public Parent {
public:
 void gotoSchool(){}
};

int main( ) 
{ 
 Parent parent;
 Child child;

 // upcast - implicit type cast allowed
 Parent *pParent = &child; 

 // downcast - explicit type case required 
 Child *pChild =  (Child *) &parent;

 pParent -> sleep();
 pChild -> gotoSchool();
  
 return 0; 
}
Child object is a Parent object in that it inherits all the data members and member functions of a Parent object. So, anything that we can do a Parent object, we can do to a Child object. Therefore, a function designed to handle a Parent pointer (reference) can perform the same acts on a Child object without any problems. The same idea applies if we pass a pointer to an object as a function argument. Upcasting is transitive: if we derive a Child class from Parent, then Parent pointer (reference) can refer to aParent or a Child object.
Upcasting can cause object slicing when a derived class object is passed by value as a base class object, as in foo(Base derived_obj).



DOWNCASTING
The opposite process, converting a base-class pointer (reference) to a derived-class pointer (reference) is called downcasting. Downcasting is not allowed without an explicit type cast. The reason for this restriction is that the is-a relationship is not, in most of the cases, symmetric. A derived class could add new data members, and the class member functions that used these data members wouldn't apply to the base class.
As in the example, we derived Child class from a Parent class, adding a member function, gotoSchool() for getting the size information. It wouldn't make sense to apply the gotoSchool() method to a Parent object. However, if implicit downcasting were allowed, we could accidentally assign the address of a Parent object to a pointer-to-Child
Child *pChild =  &parent; // actually this won't compile
    // error: cannot convert from 'Parent *' to 'Child *'
and use the pointer to invoke the gotoSchool() method as in the following line.
pChild -> gotoSchool();
Because a Parent isn't a Child (a Parent need not have a gotoSchool() method), the downcasting in the above line can lead to anunsafe operation.
C++ provides a special explicit cast called dynamic_cast that performs this conversion. Downcasting is the opposite of the basic object-oriented rule, which states objects of a derived class, can always be assigned to variables of a base class.
One more thing about the upcasting:
Because implicit upcasting makes it possible for a base-class pointer (reference) to refer to a base-class object or a derived-class object, there is the need for dynamic binding. That's why we have virtual member functions.
  • Pointer (Reference) type: known at compile time.
  • Object type: not known until run time.
DYNAMIC CASTING
The dynamic_cast operator answers the question of whether we can safely assign the address of an object to a pointer of a particular type.
Here is a similar example to the previous one.
#include <string>

class Parent {
public:
 void sleep() {
 }
};

class Child: public Parent {
private:
 std::string classes[10];
public:
 void gotoSchool(){}
};

int main( ) 
{ 
 Parent *pParent = new Parent;
 Parent *pChild = new Child;
  
 Child *p1 = (Child *) pParent; // #1
 Parent *p2 = (Child *) pChild; // #2
 return 0; 
}
Let look at the lines where we do type cast.
Child *p1 = (Child *) pParent; // #1
Parent *p2 = (Child *) pChild; // #2
Which of the type cast is safe?
The only one guaranteed to be safe is the ones in which the pointer is the same type as the object or else a base type for the object.
Type cast #1 is not safe because it assigns the address of a base-class object (Parent) to a derived class (Child) pointer. So, the code would expect the base-class object to have derived class properties such as gotoSchool() method, and that is false. Also,Child object, for example, has a member classes that a Parent object is lacking.
Type case #2, however, is safe because it assigns the address of a derived-class object to a base-class pointer. In other words, public derivation promises that a Child object is also a Parent object.
The question of whether a type conversion is safe is more useful than the question of what kind of object is pointed to. The usual reason for wanting to know the type is so that we can know if it's safe to invoke a particular method.
Here is the syntax of dynamic_cast.
Child *p = dynamic_cast<Child *>(pParent)
This code is asking whether the pointer pParent can be type cast safely to the type Child *.
  • It returns the address of the object, if it can.
  • It returns 0, otherwise.
How do we use the dynamic_cast?
void f(Parent* p) {
  Child *ptr = dynamic_cast<Child*>(p);
  if(ptr) { 
  // we can safely use ptr
 } 
}
In the code, if (ptr) is of the type Child or else derived directly or indirectly from the type Child, the dynamic_cast converts the pointer p to a pointer of type Child. Otherwise, the expression evaluates to 0, the null pointer.
In other words, we want to check if we can use the passed in pointer p before we do some operation on a child class object even though it's a pointer to base class.
"The need for dynamic_cast generally arises because we want perform derived class operation on a derived class object, but we have only a pointer-or reference-to-base." -Scott Meyers

Thursday, April 10, 2014

Virtual Memory Exercise

Problem 1. Consider a virtual memory system that uses a single-level page map to translate virtual addresses into physical addresses. Each of the questions below asks you to consider what happens when one of the design parameters of the original system is changed.
  1. If the physical memory size (in bytes) is doubled, how does the number of bits in each entry of the page table change?
    increases by 1 bit. Assuming the page size remains the same, there are now twice as many physical pages, so the physical page number needs to expand by 1 bit.
  1. If the physical memory size (in bytes) is doubled, how does the number of entries in the page map change?
    no change. The number of entries in the page table is determined by the size of the virtual address and the size of a page -- it's not affected by the size of physical memory.
  1. If the virtual memory size (in bytes) is doubled, how does the number of bits in each entry of the page table change?
    no change. The number of bits in a page table entry is determined by the number of control bits (usually 2: dirty and resident) and the number of physical pages -- the size of each entry is not affected by the size of virtual memory.
  1. If the virtual memory size (in bytes) is doubled, how does the number of entries in the page map change?
    the number of entries doubles. Assuming the page size remains the same, there are now twice as many virtual pages and so there needs to be twice as many entries in the page map.
  1. If the page size (in bytes) is doubled, how does the number of bits in each entry of the page table change?
    each entry is one bit smaller. Doubling the page size while maintaining the size of physical memory means there are half as many physical pages as before. So the size of the physical page number field decreases by one bit.
  1. If the page size (in bytes) is doubled, how does the number of entries in the page map change?
    there are half as many entries. Doubling the page size while maintaining the size of virtual memory means there are half as many virtual pages as before. So the number of page table entries is also cut in half.
  1. The following table shows the first 8 entries in the page map. Recall that the valid bit is 1 if the page is resident in physical memory and 0 if the page is on disk or hasn't been allocated.
    Virtual pageValid bitPhysical page
    007
    119
    203
    312
    415
    505
    604
    711
    If there are 1024 (210) bytes per page, what is the physical address corresponding to the decimal virtual address 3956?
    3956 = 0xF74. So the virtual page number is 3 with a page offset of 0x374. Looking up page table entry for virtual page 3, we see that the page is resident in memory (valid bit = 1) and lives in physical page 2. So the corresponding physical address is (2<<10)+0x374 = 0xB74 = 2932.


Problem 2. A particular 32-bit microprocessor includes support for paged virtual memory addressing with 212 byte pages. The mapping of virtual to physical addresses requires two translation steps:
  1. The most significant 10 bits of the virtual address (the Dir field) are multiplied by 4 and appended to the 20 most significant bits of the dirbase (directory base) register to get the address in main memory of a page directory entry. Each entry in the page directory is a 32-bit record composed of a 20-bit PTBL field and various control bits (Present, Dirty, Read-only, etc.).
  2. The bits of the Page field (virtual address bits 21 to 12) are multiplied by 4 and appended to the PTBL field to form the page-table address. This page table address references a 32-bit page table entry. Each page table entry is composed of a 20-bit physical page number (PPN) and a series of control bits.
All page-table entries and the page directory are stored in main memory. The results of these translations are cached in a 4-way set-associative translation look-aside buffer (TLB) with a total of 64 entries, and a LRU replacement strategy is used on TLB misses.

  1. Given a computer system with 227 bytes of physical memory that uses the virtual-to-physical address translation scheme described, how many pages of physical memory are there?
    215 = 227/212 = the size of physical memory divided by the size of each page.
  1. How many memory pages does the Page Directory occupy?
    We are told that the Page Directory index is 10 bits, implying 210 = 1024 entries. Each entry occupies 4 bytes, so the total size of the of the Page Directory is 4*210 = 212 bytes, or exactly one page.
  1. What is the approximate maximum size for a process's working set that still achieves a 100% TLB hit rate?
    The TLB has 64 entries, so to achieve 100% hit rate in the TLB we can access only 64 different pages as part of our working set. 64 pages = 64*212 = 218 bytes.
  1. Which virtual address bits would most likely be used to select which set to access in the TLB cache?
    We would like adjacent virtual pages to be able to mapped by the TLB, so we'd like them to occupy different sets in the cache. This is achieved by using the low-order 4 bits of the virtual page number as the TLB index, i.e., bits 12 through 15 of the address. Remember that the TLB is 4-way associative, so each subcache has 64/4 = 16 entries.
  1. How large must the tag field of the TLB be?
    The tag field should contain all the bits of the virtual page number not used to form the index, i.e., bits 16 through 31, a total of 16 bits.
  1. A control bit, C, in each page table entry determines if memory references to that page are cacheable. In order to support this feature, which of the following statements concerning the interaction between virtual-to-physical address translations and caching must be true?
    1. The cache tags must contain physical addresses
    2. Each memory access requires a virtual-address translation to take place in parallel with the cache access
    3. The status of the cacheable bit, C, needs only to be considered on a cache miss
    4. Page table entries with their dirty bit set should clear their cacheable bit
    5. All of the above
    C. We only need to worry if a page is cacheable if we're considering bringing some of its entries into the cache, and we only do this if the access can't be satisfied from current contents of the cache.


Problem 3. Consider two possible page-replacement strategies: LRU (the least recently used page is replaced) and FIFO (the page that has been in the memory longest is replaced). The merit of a page-replacement strategy is judged by its hit ratio.
Assume that, after space has been reserved for the page table, the interrupt service routines, and the operating-system kernel, there is only sufficient room left in the main memory for four user-program pages. Assume also that initially virtual pages 1, 2, 3, and 4 of the user program are brought into physical memory in that order.
  1. For each of the two strategies, what pages will be in the memory at the end of the following sequence of virtual page accesses? Read the sequence from left to right: (6, 3, 2, 8, 4).
    LRU:
      start: 1 2 3 4
      access 6: replace 1 => 2 3 4 6
      access 3: reorder list => 2 4 6 3
      access 2: reorder list => 4 6 3 2
      access 8: replace 4 => 6 3 2 8
      access 4: replace 6 => 3 2 8 4
    FIFO:
      start: 1 2 3 4
      access 6: replace 1 => 2 3 4 6
      access 3: no change => 2 3 4 6
      access 2: no change => 2 3 4 6
      access 8: replace 2 => 3 4 6 8
      access 4: no change => 3 4 6 8
  1. Which (if either) replacement strategy will work best when the machine accesses pages in the following (stack) order: (3, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 7, 6, ...)?
    LRU misses on pages 3 & 7 => 2/8 miss rate.FIFO doesn't work well on stack accesses => 5/8 miss rate.
  1. Which (if either) replacement strategy will work best when the machine accesses pages in the following (repeated sequence) order: (3, 4, 5, 6, 7, 3, 4, 5, 6, 7, ...).
    Both strategies have a 100% miss rate in the steady state.
  1. Which (if either) replacement strategy will work best when the machine accesses pages in a randomly selected order, such as (3, 4, 2, 8, 7, 2, 5, 6, 3, 4, 8, ...).
    Neither FIFO nor LRU is guaranteed to be the better strategy in dealing with random accesses since there is no locality to the reference stream.


Problem 4. A paged memory with a one-level page table has the following parameters: The pages are 2P bytes long; virtual addresses are V bits long, organized as follows:
virtual page numberoffset in page
The page-table starts at physical address PTBL; and each page-table entry is a 4-byte longword, so that, given a virtual address, the relevant page-table entry can be found at PTBL + (page number)*4. Answer the following in terms of the parameters P and V:
  1. How many bits long is the "offset in page" field?
    It takes log2(2P) = P address bits to select a single byte from a page with 2P bytes.
  1. How many bits long is the "virtual page number" field?
    Since there a P bits in the offset field, the remaining V-P bits are part of the virtual page number.
  1. How many entries does the page table have, and what is the highest address occupied by a page-table entry?
    Since the virtual page number field has V-P bits, there are 2V-P virtual pages and each has its own entry in the page table. Each entry is 4 bytes longs, so the highest address occupied by a page table entry is PTBL + 4*(2(V-P)-1).
  1. How many pages long is the page table?
    There are 2P/4 page table entries per page and 2V-P pages, so the page table is 2V-P/2P-2 = 2V-2P+2 pages long.
  1. What is the smallest value of P such that the page table fits into one page?
    Using the formula from the previous question, to make the page table fit in one page, we want V-2P+2 = 0. Solving for P we get P = V/2 + 1.
  1. What relationships, if any, must hold between P, V, and the size of physical memory?
    Suppose physical memory contained 2M bytes. Then
    • The physical page number must fit in 30 bits since we reserve 2 bits of the 32-bits page table entry for the dirty and resident control bits. So 30 >= M - P.
    • It useful to have room in memory for at least one page other than those occupied by the page map. So M > V-P+2.


Problem 5.
  1. If virtual addresses are V bits long, physical addresses are A bits long, the page size is 2P bytes, and a one-level page table is used, give an expression for the size of the page table.
    There are 2V-P pages and the page table entry for each page contains a physical page number (A-P bits), a dirty bit (1 bit) and a resident bit (1 bit). So the page table occupies 2V-P(A-P+2) bits.


Problem 6. Adverbs Unlimited has recently added a new product, the VIRTUALLY to the product line introduced in an earlier tutorial problem. The VIRTUALLY has a 210-byte, two-way set-associative cache, 220 bytes of physical memory, 16-bit virtual addresses, and a 26-entry page map. The VIRTUALLY will be used to support multiuser time-sharing. The page map holds the address translation for a single (current) process and must be reloaded (by the kernel) at each process switch. The cache is located between the page map and main memory.
  1. What is the page size?
    page size in bytes = size of virtual address divided by number of entries in the page map = 216/26 = 210 bytes per page.
  1. Which virtual address lines are used to form the index to the page map?
    The virtual page number is used as the index to the page map. The virtual page number includes all virtual address bits that aren't part of the page offset. Since there 210 bytes per page, the page offset requires 10 bits, i.e., address bits 0 through 9. The remaining six bits (bits 10 through 15) form the virtual page number.
  1. Can the cache and page-map be read simultaneously? Explain in a single sentence.
    Yes since the virtual page number (bits 10 through 15) doesn't overlap with the cache index/block index (bits 0 through 8 remembering that the cache is 2-way set associative).
  1. Under what circumstances, if any, must the cache be invalidated (that is, its entries marked as invalid)?
    Since the cache is located after the page map, it caches physical addresses. So it must be invalidated when there is a page replacement due to a page fault, since this operation changes the contents of physical memory.


Problem 7.
  1. Program A consists of 1000 consecutive ADD instructions, while program B consists of a loop that executes a single ADD instruction 1000 times. You run both programs on a certain machine and find that program B consistently executes faster. Give two plausible explanations.
    Explanation #1: one would expect the loop to achieve a higher hit rate in the cache since it involves many fewer instruction words.Explanation #2: the loop, occupying many fewer instruction words, should all fit onto a single page. The 1000 instructions might span several pages and hence their execution may involve some page faults.
  1. If a TLB is implemented as a set-associative cache, how would you recommend determining the TLB slots examined when mapping the virtual address VA[31:0]? Why?
    We should use the low-order bits of the virtual page number as the index into the TLB so that adjacent pages can be mapped by the TLB without collisions.

Friday, April 4, 2014

Cache Memory Assignments


Problem 1.

The diagram above illustrates a blocked, direct-mapped cache for a computer that uses 32-bit data words and 32-bit byte addresses.
  1. What is the maximum number words of data from main memory that can be stored in the cache at any one time?
    Maximum number of data words from main memory = (16 lines)(4 words/line) = 64 words
  1. How many bits of the address are used to select which line of the cache is accessed?
    With 16 cache lines, 4 bits of the address are required to select which line of the cache is accessed.
  1. How many bits wide is the tag field?
    Bits in the tag field = (32 address bits) - (4 bits to select line) - (4 bits to select word/byte) = 24 bits
  1. Briefly explain the purpose of the one-bit V field associated with each cache line.
    The tag and data fields of the cache will always have value in them, so the V bit is used to denote whether these value are consistent (valid) with what is in memory. Typically the V bit for each line in the cache is set to "0" when the machine is reset or the cache is flushed.
  1. Assume that memory location 0x2045C was present in the cache. Using the row and column labels from the figure, in what cache location(s) could we find the data from that memory location? What would the value(s) of the tag field(s) have to be for the cache row(s) in which the data appears?
    The cache uses ADDR[7:4] to determine where data from a particular address will be stored in the cache. Thus, location 0x0002045C will be stored in line 5 of cache. The tag field should contain the upper 24 bits of the address, i.e., 0x000204. Note that the bottom 4 bits of the address (0xC) determine which word and byte of the cache line is being referenced.
  1. Can data from locations 0x12368 and 0x322FF8 be present in the cache at the same time? What about data from locations 0x2536038 and 0x1034? Explain.
    Location 0x12368 will be stored in line 6 of the cache. Location 0x322F68 will be stored in line F of the cache. Since the lines differ, both locations can be cached at the same time. However, locations 0x2536038 and 0x1034 both would be stored in line 3 of cache, so they both could not be present in the cache at the same time.
  1. When an access causes a cache miss, how many words need to be fetched from memory to fill the appropriate cache location(s) and satisfy the request?
    There are 4 words in each line of the cache and since we only have one valid bit for the whole line, all 4 words have to have valid values. So to fill a cache line on a cache miss all 4 words would have to be fetched from main memory.


Problem 2. Cache multiple choice:
  1. If a cache access requires one clock cycle and handling cache misses stalls the processor for an additional five cycles, which of the following cache hit rates comes closest to achieving an average memory access of 2 cycles?

    (A) 75%
    (B) 80%
    (C) 83%
    (D) 86%
    (E) 98%
    2 cycle average access = (1 cycle for cache) + (1 - hit rate)(5 cycles stall)
    => hit rate = 80%
  1. LRU is an effective cache replacement strategy primarily because programs

    (A) exhibit locality of reference
    (B) usually have small working sets
    (C) read data much more frequently than write data
    (D) can generate addresses that collide in the cache
    (A). Locality implies that the probability of accessing a location decreases as the time since the last access increases. By choosing to replace locations that haven't been used for the longest time, the least-recently-used replacement strategy should, in theory, be replacing locations that have the lowest probability of being accessed in the future.
  1. If increasing the associativity of a cache improves performance it is primarily because programs

    (A) exhibit locality of reference
    (B) usually have small working sets
    (C) read data much more frequently than write data
    (D) can generate addresses that collide in the cache
    (D). Increasing cache associativity means that there are more cache locations in which a given memory word can reside, so replacements due to cache collisions (multiple addresses mapping to the same cache location) should be reduced.
  1. If increasing the block size of a cache improves performance it is primarily because programs

    (A) exhibit locality of reference
    (B) usually have small working sets
    (C) read data much more frequently than write data
    (D) can generate addresses that collide in the cache
    (A). Increased block size means that more words are fetched when filling a cache line after a miss on a particular location. If this leads to increased performance, then the nearby words in the block must have been accessed by the program later on, ie, the program is exhibiting locality.
  1. A fully-associative cache using an LRU replacement policy always has a better hit rate than a direct-mapped cache with the same total data capacity.

    (A) true
    (B) false
    False. Suppose both caches contain N words and consider a program that repeatedly accesses locations 0 through N (a total of N+1 words). The direct-mapped cache will map locations 0 and N into the same cache line and words 1 through N-1 into separate cache lines. So in the steady state, the program will miss twice (on locations 0 and N) each time through the loop.Now the fully-associative case: when the program first accesses word N, the FA cache will replace word 0 (the least-recently-used location). The next access is to location 0 and the FA cache will replace word 1, etc. So the FA cache is always choosing the replace the word the program is about to access, leading to a 0% hit rate!
  1. Consider the following program:
    integer A[1000];
    for i = 1 to 1000
      for j = 1 to 1000
        A[i] = A[i] + 1
    
    When the above program is compiled with all compiler optimizations turned off and run on a processor with a 1K byte direct-mapped write-back data cache with 4-word cache blocks, what is the approximate data cache miss rate? (Assume integers are one word long and a word is 4 bytes.)

    (A) 0.0125%
    (B) 0.05%
    (C) 0.1%
    (D) 5%
    (E) 12.5%
    (A). Considering only the data accesses, the program performs 1,000,000 reads and 1,000,000 writes. Since the cache has 4-word blocks, each miss brings 4 words of the array into the cache. So accesses to the next 3 array locations won't cause a miss. Since the cache is write-back, writes happen directly into the cache without causing any memory accesses until the word is replaced. So altogether there are 250 misses (caused by a read of A[0], A[4], A[8], ...), for a miss rate of 250/2,000,000 = 0.0125%
  1. In a non-pipelined single-cycle-per-instruction processor with an instruction cache, the average instruction cache miss rate is 5%. It takes 8 clock cycles to fetch a cache line from the main memory. Disregarding data cache misses, what is the approximate average CPI (cycles per instruction)?

    (A) 0.45
    (B) 0.714
    (C) 1.4
    (D) 1.8
    (E) 2.22
    (C). CPI = (1 inst-per-cycle) + (0.05)(8 cycles/miss) = 1.4
  1. Consider an 8-line one-word-block direct-mapped cache initialized to all zeroes where the following sequence of word addresses are accessed:1, 4, 5, 20, 9, 19, 4, 5, 6, and 9.
    Which of the following tables reflect the final tag bits of the cache?
    First map the addresses to cache line numbers and tags where
      line number = address mod 8
      tag = floor(address / 8)
    address:   1   4   5  20   9  19   4   5   6   9
    line #:    1   4   5   4   1   3   4   5   6   1
    tag:       0   0   0   2   1   2   0   0   0   1
    
    So, figure (E) represents the final tag bits of the cache.
  1. Consider the following partitioning of a CPU's 32-bit address output which is fed to a direct-mapped write-back cache:
    What is the memory requirement for data, tag and status bits of the cache?

    (A) 8 K bits
    (B) 42 K bits
    (C) 392 K bits
    (D) 1,160 K bits
    (E) 3,200 K bits
    The tag is 15 bits, cache index is 13 bits, and byte offset 4 bits (ie, 16 bytes/block). So there are 213= 8192 cache lines. Each cache line requires
     15 tag bits
      1 valid bit
      1 dirty bit (since this is a write-back cache)
    128 data bits (16 bytes/cache line)
    ===
    145 bits per cache line
    
    Total storage required = 8192*145 bits = 1,160K bits.


Problem 3. A student has miswired the address lines going to the memory of an unpipelined BETA. The wires in question carry a 30-bit word address to the memory subsystem, and the hapless student has in fact reversed the order of all 30 address bits. Much to his surprise, the machine continues to work perfectly.
  1. Explain why the miswiring doesn't affect the operation of the machine.
    Since the Beta reverses the order of the 30 bit address in the same manner for each memory access, the Beta will use the same reversed address to access a particular memory location for both stores and loads. Thus, the operation of the machine will not be affected.
  1. The student now replaces the memory in his miswired BETA with a supposedly higher performance unit that contains both a fast direct mapped cache and the same memory as before. The reversed wiring still exists between the BETA and this new unit. To his surprise, the new unit does not significantly improve the performance of his machine. In desperation, the student then fixes the reversal of his address lines and the machine's performance improves tremendously. Explain why this happens.
    Caches take advantage of locality of reference by reading in an entire block of related data at one time, thereby reducing main memory accesses. By reversing the order of the 30 bit address, locality of the memory addresses is disrupted. The low-order bits that would normally place related data close to one another are instead the high-order bits and related data is more spread out through the main memory. This reduction in locality reduces cache performance significantly. When the student fixes the address line reversal problem, locality of the memory is restored, and the cache can perform as intended.


Problem 4. For this problem, assume that you have a processor with a cache connected to main memory via a bus. A successful cache access by the processor (a hit) takes 1 cycle. After an unsuccessful cache access (a miss), an entire cache block must be fetched from main memory over the bus. The fetch is not initiated until the cycle following the miss. A bus transaction consists of one cycle to send the address to memory, four cycles of idle time for main-memory access, and then one cycle to transfer each word in the block from main memory to the cache. Assume that the processor continues execution only after the last word of the block has arrived. In other words, if the block size is B words (at 32 bits/word), a cache miss will cost 1 + 1 + 4 + B cycles. The following table gives the average cache miss rates of a 1 Mbyte cache for various block sizes:
  1. Write an expression for the average memory access time for a 1-Mbyte cache and a B-word block size (in terms of the miss ratio m and B).
    Average access time = (1-m)(1 cycle) + (m)(6 + B cycles) = 1 + (m)(5+B) cycles
  1. What block size yields the best average memory access time?
  1. If bus contention adds three cycles to the main-memory access time, which block size yields the best average memory access time?
  1. If bus width is quadrupled to 128 bits, reducing the time spent in the transfer portion of a bus transaction to 25% of its previous value, what is the optimal block size? Assume that a minimum one transfer cycle is needed and don't include the contention cycles introduced in part (C).


Problem 5. The following four cache designs C1 through C4, are proposed for the Beta. All use LRU replacement where applicable (e.g. within each set of a set associative cache).
  1. Which cache would you expect to take the most chip area (hence cost) ?
    Cache C4 would most likely take up the most chip area because it is fully associative, thereby requiring a comparator for each cache line, and because it has the most data word capacity.
  1. Which cache is likely to perform worst in a benchmark involving repeated cycling through an array of 6K integers ? Explain.
    C2 would likely have the worst performance on a benchmark involving repeated cycling through an array of 6K integers since it is the only cache listed with less than 6K data word capacity.
  1. It is observed that one of the caches performs very poorly in a particular benchmark which repeatedly copies one 1000-word array to another. Moving one of the arrays seems to cure the problem. Which cache is most likely to exhibit this behavior ? Explain.
    We are told that one of the caches performs poorly in a particular benchmark which repeatedly copies one 1000-word array to another and that if one of the arrays is moved, the problem seems to be cured. This behavior is most likely exhibited by cache C3 because it is a direct mapped cache which only has one location to put any particular address. If the lower bits (used to choose the cache line) for the addresses of the array overlap, poor performance could be observed. Moving the array so that the lower bits of the array addresses don't overlap could solve this problem.
  1. Recall that we say cache A dominates cache B if for every input pattern, A caches every location cached by B. Identify every pair (A, B) of caches from the above list where A dominates B. Explain your reasoning.
    So long as we are not using a random replacement strategy, it is always possible to come up with a benchmark that will make a particular type of cache have a miss on every data access. Thus, we cannot say that one particular type of cache always dominates another type of cache. However, we can compare two caches of the same type. Both C4 and C1 are fully associative caches with the same replacement strategy. We can say that C4 dominates C1 since C4 has a greater data word capacity.


Problem 6. The data-sheet for a particular byte-addressable 32-bit microprocessor reads as follows:
The CPU produces a 32-bit virtual address for both data and instruction fetches. There are two caches: one is used when fetching instructions; the other is used for data accesses. Both caches are virtually addressed. The instruction cache is two-way set-associative with a total of 212 bytes of data storage, with 32-byte blocks. The data cache is two-way set-associative with a total of 213 bytes of data storage, with 32-byte blocks
  1. How many bits long is the tag field in each line of the instruction cache?
    There are 32 = 25 bytes per block. The cache has 212 total bytes and is 2-way set associative, so each set has 211 bytes and thus 211/25 = 26 cache lines. So the address is partitioned by the cache as follows:
      [4:0] = 5 address bits for selecting byte/word within a block
      [10:5] = 6 address bits for selecting the cache line
      [31:11] = 21 address bit of tag field
  1. How many address bits are used to choose which line is accessed in the data cache?
    There are 32 = 25 bytes per block. The cache has 213 total bytes and is 2-way set associative, so each set has 212 bytes and thus 212/25 = 27 cache lines. So the address is partitioned by the cache as follows:
      [4:0] = 5 address bits for selecting byte/word within a block
      [11:5] = 7 address bits for selecting the cache line
      [31:12] = 20 address bit of tag field
  1. Which of the following instruction addresses would never collide in the instruction cache with an instruction stored at location 0x0ACE6004?

    (A) 0x0BAD6004    (D) 0x0ACE6838
    (B) 0x0C81C81C    (E) 0xFACE6004
    (C) 0x00000004    (F) 0x0CEDE008
    Collisions happen when instruction addresses map to the same cache line. Referring to the answer for (A), address bits [10:5] are used to determine the cache line, so location 0x0ACE6004 is mapped to cache line 0.Only (D) 0x0ACE6838 maps to a different cache line and hence could never collide in the instruction cache with location 0x0ACE6004.
  1. What is the number of instructions in the largest instruction loop that could be executed with a 100% instruction cache hit rate during all but the first time through the loop?
    The instruction cache hold 212 bytes or 210 = 1024 instructions. So if the loop had 1024 instructions it would just fit into the cache.


Problem 7. The following questions ask you to evaluate alternative cache designs using patterns of memory references taken from running programs. Each of the caches under consideration has a total capacity of 8 (4-byte) words, with one word stored in each cache line. The cache designs under consideration are:
    DM: a direct-mapped cache.S2: a 2-way set-associative cache with a least-recently-used replacement policy.
    FA: a fully-associative cache with a least-recently-used replacement policy.
The questions below present a sequence of addresses for memory reads. You should assume the sequences repeat from the start whenever you see "...". Keep in mind that byte addressing is used; addresses of consecutive words in memory differ by 4. Each question asks which cache(s) give the best hit rate for the sequence. Answer by considering the steady-state hit rate, i.e., the percentage of memory references that hit in the cache after the sequence has been repeated many times.
  1. Which cache(s) have the best hit rate for the sequence 0, 16, 4, 36, ...
    DM: locations 4 and 36 collide, so each iteration has 2 hits, 2 misses.S2: 100% hit rate. 0 and 16 map to the same cache line, as do 4 and 36, but since the cache is 2-way associative they don't collide.FA: 100% hit rate. The cache is only half filled by this loop.
  1. Which cache(s) have the best hit rate for the sequence 0, 4, 8, 12, 16, 20, 24, 28, 32, ...
    DM: locations 0 and 32 collide, so each iteration has 7 hits, 2 misses.S2: locations 0, 16 and 32 all map to the same cache line. The LRU replacement strategy replaces 0 when accessing 32, 16 when accesing 0, 32 when accessing 16, etc., so each iteration has 6 hits, 3 misses.FA: has 0% hit rate in the steady state since the LRU replacement strategy throws out each location just before it's accessed by the loop!
  1. Which cache(s) have the best hit rate for the sequence 0, 4, 8, 12, 16, 20, 24, 28, 32, 28, 24, 20, 16, 12, 8, 4, ...
    All caches perform the same -- locations 0 and 32 trade places in the caches, so each iteration has 14 hits and 2 misses.
  1. Which cache(s) have the best hit rate for the sequence 0, 4, 8, 12, 32, 36, 40, 44, 16, ..
    DM: 32 collides with 0, 36 with 4, 40 with 8, 44 with 12, so each itreation has only 1 hit and 8 misses.S2: locations 0, 16 and 32 trade places in the cache, so each iteration has 6 hits and 3 misses.FA: 0 hits since LRU throws out each location just before it's accessed by the loop.
  1. Assume that a cache access takes 1 cycle and a memory access takes 4 cycles. If a memory access is initiated only after the cache has missed, what is the maximum miss rate we can tolerate before use of the cache actually slows down accesses?
    If accesses always go to memory, it takes 4 cycles per access. Using the cache the average number of cycles per access is
      1 + (miss rate)*4
    So if the miss rate is larger than 75% the average number of cycles per access is more than 4.


Problem 8. Ben Bitdiddle has been exploring various cache designs for use with the Beta processor. He is considering only caches with one word (4 bytes) per line. He is interested in the following cache designs:
    C1: 2-way set associative, LRU replacement, 256 total data words (128 sets of 2 words each).C2: 2-way set associative, random replacement, 256 total data words (128 sets of 2 words each).
    C3: 2-way set associative, LRU replacement, 512 total data words (256 sets of 2 words each).
    C4: 4-way set associative, LRU replacement, 512 total data words (128 sets of 4 words each).
    C5: Fully associative, LRU replacement, 512 total data words.
In order to help her analysis, Ben is trying to identify cases where one cache dominates another in terms of cache hits. Ben considers that cache A dominates cache B if, given identical strings of memory references, every memory reference that gives a cache hit using B is also a hit using A. Thus if A dominates B, A will give at least as high a hit rate as B for every program.
In each of the following pairs of caches, deduce whether the first dominates the second:
  1. C1 dominates C2
    False. C1 has a 0% hit rate for 0, 256, 512, 0, 256, 512, ..., but C2 might do slightly better because it chooses the replacement set at random.
  1. C2 dominates C1
    No. C1 has a 100% hit rate for 0, 256, 0, 256, ..., but C2 might have an occasional miss.
  1. C3 dominates C1
    Yes. C3 differs only in having a higher capacity than C1.
  1. C3 dominates C2
    No. As we saw in (A) there are programs where LRU gets 0% hit rate and random may do slightly better, independently of the sizes of the caches.
  1. C4 dominates C3
    No. C4 has 0% hit rate on 0, 128, 256, 384, 512, 0, ... since all accesses map to the same cache line and LRU throws out the location just about to be accessed. In C3, 128 and 384 map to a different cache line than 0, 256 and 512, so manages a 40% hit rate in the steady state.
  1. C4 dominates C2
    No, for the same reason as (A) and (D).
  1. C5 dominates C1
    No. Consider the following access pattern: 0, accesses to 512 uncached locations whose addresses don't map to cache line 0 for cache C1, 0, ...C5 will replace location 0 on the 513th access and hence miss when 0 is accessed in the following cycle. C1 will have location 0 still in the cache when it's accessed again by the loop.
  1. Averaged over a wide range of typical application programs, which of the above caches would you expect to yield the highest hit rate?
    In general larger caches are better and fully associative caches are better than set associative caches, so C5 should have the highest hit rate.


Problem 9. Adverbs Unlimited is considering a computer system based loosely on the Beta. Five designs have been proposed, each of them similar to the Beta except for a cache between the 32-bit processor data bus and the main-memory subsystem. Like the Beta, each machine deals with 32-bit main-memory addresses, for a total address space of 232 bytes. The machines' caches differ only in the parameters of associativity, size, and writeback. The block size for each cache 1 word (4 bytes).
ModelAssociativityTotal data size (bytes)Write-
DEFINATELYfour-way216back
CERTAINLYdirect-mapped216back
HOPEFULLY4-way210through
PERHAPS2-way210back
DOUBTFULLYdirect-mapped210back
  1. How many bits are required for the tag portion of each cache line for each of the architectures? How bits of comparitor are needed? How many bits of SRAM altogether (including tag fields, valid and dirty bits).
    DEFINIATELY: 216/4-way = 214 bytes/subcache
    => 212 cache lines/subcache => 32 - 14 = 18 tag bits
    => 18 * 4 = 76 bits of comparator
    => total SRAM bits = 4*(8*214 data bits + 212*(18 tag + 1 valid + 1 dirty))CERTAINLY: 216/1-way = 216 bytes/subcache
    => 214 cache lines => 32 - 16 = 16 tag bits
    => 16 bits of comparator
    => total SRAM bits = 8*216 data bits + 214*(16 tag + 1 valid + 1 dirty)
    HOPEFULLY: 210/4-way = 28 bytes/subcache
    => 26 cache lines/subcach => 32 - 8 = 24 tag bits
    => 24 * 4 = 96 bits of comparator
    => total SRAM bits = 4*(8*28 data bits + 26*(24 tag + 1 valid))
    PERHAPS: 210/2-way = 29 bytes/subcache
    => 27 cache lines/subcach => 32 - 9 = 23 tag bits
    => 23 * 2 = 46 bits of comparator
    => total SRAM bits = 2*(8*29 data bits + 27*(23 tag + 1 valid + 1 dirty))
    DOUBTFULLY: 210/1-way = 210 bytes/subcache
    => 28 cache lines => 32 - 10 = 22 tag bits
    => 22 bits of comparator
    => total SRAM bits = 8*210 data bits + 28*(22 tag + 1 valid + 1 dirty)
  1. Address lines from the CPU are designated A31, ..., A1, A0, where A0 is the low-order address bit. Which of these CPU address lines are used as address inputs to the SRAMs of the cache in the PERHAPS model?
    PERHAPS is a 2-way set-associative cache with a total of 210 bytes, so each direct-mapped subcache contains 29 bytes. With a block size of 1 word (4 bytes), address bits [8:2] would be used as the index into the 32-bit-wide SRAM.
  1. Suppose that address lines A2 and A9 were inadvertently interchanged in the cable between the DOUBTFULLY CPU and its cache. Which, if any, of the following statements best describes the effect(s) of this change, assuming that other hardware and software remain unmodified?
    1. The machine would no longer work.
    2. The machine would continue to work as before.
    3. The machine would continue to work, but at a reduced performance level.
    4. The machine would continue to work, at an improved performance level.
    (B). Address bits A2 through A9 are used as the cache index, interchanging them has no effect other than to change where in SRAM each cache line is stored, i.e., all the same locations are cached, they just happen to be stored in different cache SRAM locations than one might have expected.


Problem 10. You are designing a controller for a tiny cache that is fully associative but has only three words in it. The cache has an LRU replacement policy. A reference record module (RRM) monitors references to the cache and always outputs the binary value 1, 2, or 3 on two output signals to indicate the least recently used cache entry. The RRM has two signal inputs, which can encode the number 0 (meaning no cache reference is occurring) or 1, 2, or 3 (indicating a reference to the corresponding word in the cache).
  1. What hit ratio will this cache achieve if faced with a repeating string of references to the following addresses: 100, 200, 104, 204, 200?
    Here's what happens:
    access 100: miss; cache contains 100, ---, ---
    access 200: miss; cache contains 200, 100, ---
    access 104: miss; cache contains 104, 200, 100
    access 204: miss; cache contains 204, 104, 200
    access 200: hit;  cache contains 200, 204, 104
    access 100: miss; cache contains 100, 200, 204
    access 200: hit;  cache contains 200, 100, 204
    access 104: miss; cache contains 104, 200, 100
    access 204: miss; cache contains 204, 104, 200
    access 200: hit;  cache contains 200, 204, 104
    ...
    
    So in the steady state, location 200 stays in the cache and all other locations get replaced. So the hit rate is 2/5 or 40%.
  1. The RRM can be implemented as a finite-state machine. How many states does the RRM need to have? Why?
    There are 3! = 6 ways to list the three locations in order of use. Thus RRM needs 6 states, one state for each possible order.
  1. How many state bits does the RRM need to have?
    We can encode six states using 3 state bits.
  1. Draw a state-transition diagram for the RRM.
  1. Consider building an RRM for a 15-word fully associative cache. Write a mathematical expression for the number of bits in the ROM required in a ROM-and-register implementation of this RRM. (You need not calculate the numerical answer.)
    There are 15! possible states, so we would need ceiling(log2(15!)) = 41 state bits. So the ROM would have 241 locations of 41 bits each, for a total of approximately 90 trillion bits.
  1. Is it feasible to build the 15-word RRM above using a ROM and register in today's technology? Explain why or why not.
    90 trillion bits is a bit much even for today's technology. In a .18u technology, a single transistor pulldown in a ROM might require (.2u x .5u) = .1u2, so our ROM would require about 9 square meters of silicon!

Thursday, March 27, 2014

Semaphores Practice

Problem 1. The following is a set of three interacting processes that can access two shared semaphores:
semaphore U = 3;
semaphore V = 0;

[Process 1]     [Process 2]    [Process 3]

L1:wait(U)      L2:wait(V)     L3:wait(V)
   type("C")       type("A")      type("D")
   signal(V)       type("B")      goto L3
   goto L1         signal(V)
                   goto L2
Within each process the statements are executed sequentially, but statements from different processes can be interleaved in any order that's consistent with the constraints imposed by the semaphores. When answering the questions below assume that once execution begins, the processes will be allowed to run until all 3 processes are stuck in a wait() statement, at which point execution is halted.
  1. Discussed in section Assuming execution is eventually halted, how many C's are printed when the set of processes runs?
    Exactly 3. Each time Process 1 executes the "wait(U)" statement, the value of semaphore U is decremented by 1. Since there are no "signal(U)" statements, the loop in Process 1 will execute only 3 times (ie, the initial value of U) and then stall the fourth time "wait(U)" is executed.
  1. Discussed in section Assuming execution is eventually halted, how many D's are printed when this set of processes runs?
    Exactly 3. Process 1 will execute its loop three times (see the answer to the previous question), incrementing "signal(V)" each time through the loop. This will permit "wait(V)" to complete three times. For every "wait(V)" Process 2 executes, it also executes a "signal(V)" so there is no net change in the value of semaphore V caused by Process 2. Process 3 does decrement the value of semaphore V, typing out "D" each time it does so. So Process 3 will eventually loop as many times as Process 1.
  1. Discussed in section What is the smallest number of A's that might be printed when this set of processes runs?
    0. If Process 3 is scheduled immediately after Process 1 executes "signal(V)", then Process 2 might continue being stalled at its "wait(V)" statement and hence never execute its "type" statements.
  1. Discussed in section Is CABABDDCABCABD a possible output sequence when this set of processes runs?
    No. Here are the events implied by the sequence above:
    start: U=3 V=0
    type C: U=2 V=1
    type A: U=2 V=0
    type B: U=2 V=1
    type A: U=2 V=0
    type B: U=2 V=1
    type D: U=2 V=0
    type D: oops, impossible since V=0
    
  1. Discussed in section Is CABACDBCABDD a possible output sequence when this set of processes runs?
    Yes:
    start: U=3 V=0
    type C: U=2 V=1
    type A: U=2 V=0
    type B: U=2 V=1
    type A: U=2 V=0
    type C: U=1 V=1
    type D: U=1 V=0
    type B: U=1 V=1
    type C: U=0 V=2
    type A: U=0 V=1
    type B: U=0 V=2
    type D: U=0 V=1
    type D: U=0 V=0
    
  1. Discussed in section Is it possible for execution to be halted with either U or V having a non-zero value?
    No. If U has a non-zero value, Process 1 will be able to run. If V has a non-zero value, Process 3 will be able to run.


Problem 2. The following pair of processes share a common variable X:
Process A         Process B
    int Y;             int Z;
A1: Y = X*2;      B1:  Z = X+1;
A2: X = Y;        B2:  X = Z;
X is set to 5 before either process begins execution. As usual, statements within a process are executed sequentially, but statements in process A may execute in any order with respect to statements in process B.
  1. Discussed in section How many different values of X are possible after both processes finish executing?
    There are four possible values for X. Here are the possible ways in which statements from A and B can be interleaved.
    A1 A2 B1 B2: X = 11
    A1 B1 A2 B2: X = 6
    A1 B1 B2 A2: X = 10
    B1 A1 B2 A2: X = 10
    B1 A1 A2 B2: X = 6
    B1 B2 A1 A2: X = 12
    
  1. Discussed in section Suppose the programs are modified as follows to use a shared binary semaphore S:
    Process A        Process B
        int Y;           int Z;
        wait(S);         wait(S);
    A1: Y = X*2;     B1: Z = X+1;
    A2: X = Y;       B2: X = Z;
        signal(S);       signal(S);
    
    S is set to 1 before either process begins execution and, as before, X is set to 5.
    Now, how many different values of X are possible after both processes finish executing?
    The semaphore S ensures that, once begun, the statements from either process execute without interrupts. So now the possible ways in which statements from A and B can be interleaved are:
    A1 A2 B1 B2: X = 11
    B1 B2 A1 A2: X = 12
    
  1. Discussed in section Finally, suppose the programs are modified as follows to use a shared binary semaphore T:
    Process A         Process B
        int Y;            int Z;
    A1: Y = X*2;      B1: wait(T);
    A2: X = Y;        B2: Z = X+1;
        signal(T);        X = Z;
    
    T is set to 0 before either process begins execution and, as before, X is set to 5.
    Now, how many different values of X are possible after both processes finish executing?
    The semaphore T ensures that all the statements from A finish execution before B begins. So now there is only one way in which statements from A and B can be interleaved:
    A1 A2 B1 B2: X = 11
    


Problem 3. The following pair of processes share a common set of variables: "counter", "tempA" and "tempB":
Process A                            Process B
...                                  ...
A1: tempA = counter + 1;             B1: tempB = counter + 2;
A2: counter = tempA;                 B2: counter = tempB;
...                                  ...
The variable "counter" initially has the value 10 before either process begins to execute.
  1. Discussed in section What different values of "counter" are possible when both processes have finished executing? Give an order of execution of statements from processes A and B that would yield each of the values you give. For example, execution order A1, A2, B1, B2 would yield the value 13.
    There are three possible values for X. Here are the possible ways in which statements from A and B can be interleaved.
    A1 A2 B1 B2: X = 13
    A1 B1 A2 B2: X = 12
    A1 B1 B2 A2: X = 11
    B1 A1 B2 A2: X = 11
    B1 A1 A2 B2: X = 12
    B1 B2 A1 A2: X = 13
    
  1. Discussed in section Modify the above programs for processes A and B by adding appropriate signal and wait operations on the binary semaphore "sync" such that the only possible final value of "counter" is 13. Indicate what should be the initial value of the semaphore "sync".
    We need to ensure that A and B run uniterrupted, but it doesn't matter which runs first.
    semaphore sync = 1;
    
    Process A                            Process B
        wait(sync);                          wait(sync);
    A1: tempA = counter + 1;             B1: tempB = counter + 2;
    A2: counter = tempA;                 B2: counter = tempB;
        signal(sync);                        signal(sync);
    
  1. Discussed in section Draw a precedence graph that describes all the possible orderings of executions of statements A1, A2, B1 and B2 that yield the a final value of 11 for "counter".
       A1     B1
         \  /
          B2
          |
          A2
    
  1. Discussed in section Modify the original programs for processes A and B by adding binary semaphores and signal and wait operations to guarantee that the final result of executing the two processes will be "counter" = 11. Give the initial values for every semaphore you introduce. Try to put the minimum number of constraints on the ordering of statements. In other words, don't just pick one ordering that will yield 11 and enforce that one by means of semaphores; instead, enforce only the essential precedence constraints marked in your solution to question 3.
    semaphore s1 = 0;
    semaphore s2 = 0;
    
    Process A                            Process B
    A1: tempA = counter + 1;             B1: tempB = counter + 2;
        signal(s1);                          wait(s1);
        wait(s2);                        B2: counter = tempB;
    A2: counter = tempA;                     signal(s2);
    


Problem 4. The figure below shows two processes that must cooperate in computing N2 by taking the sum of the first N odd integers.
  Process P  Process Q
  N = 5;
  Sqr = 0;
 loopP: loopQ:

  if (N==0)  Sqr = Sqr + 2*N + 1;
    goto endP;
  N = N - 1;  goto loopQ;
  goto loopP;
 endP:
  print(Sqr);
  1. Add appropriate semaphore declarations and signal and wait statements to these programs so that the proper value of Sqr (i.e., 25) will be printed out. Indicate the initial value of every semaphore you add. Insert the semaphore operations so as to preserve the maximum degree of concurrency between the two processes; do not put any nonessential constraints on the ordering of operations. Hint: Two semaphores suffice for a simple and elegant solution.
    Looking at the code for process Q, we see that we want it to execute with N = 4, 3, 2, 1, and 0. So we want the decrement of N to happen before the first execution of Q. We can use two semaphores to control the production and consumption of "N values" by the two loops. To achieve maximum concurrency, we'll signal the availability of a new N value as soon as it's ready and then do as much as possible (i.e., branch back to the beginning of the loop and check the end condition) before waiting for the value to be consumed:
      Semaphore P = 1;  // P gets first shot at execution
      Semaphore Q = 0;  // Q has to wait for first N value
      int N, Sqr;
    
      Process P  Process Q
      N = 5;
      Sqr = 0;
     loopP: loopQ:
      if (N==0)  wait(Q);
        goto endP;  Sqr = Sqr + 2*N + 1;
      wait(P);                signal(P);
      N = N - 1;  goto loopQ;
      signal(Q);
      goto loopP;
     endP:
      wait(P);  // wait for last Q iteration!
      print(Sqr);
    
    Optionally, you could also split Sqr = Sqr + 2*N + 1 into Sqr = Sqr + 1 and Sqr = Sqr + 2*N to slightly improve concurrency.


Problem 5. A computer has three commonly used resources designated A, B and C. Up to three processes designated X, Y and Z run on the computer and each makes periodic use of two of the three resources.
  • Process X acquires A, then B, uses both and then releases both.
  • Process Y acquires B, then C, uses both and then releases both.
  • Process Z acquires C, then A, uses both and then releases both.
  1. If two of these processes are running simultaneously on the machine, can a deadlock occur? If so, describe the deadlock scenario.
    No deadlock is possible since one of the two processes will always be able to run to completion.
  1. Describe a scenario in which deadlock occurs if all three processes are running simultaneously on the machine.
    All three processes make their first acquisition then hang waiting for a resource that will never become available.
  1. Modify the algorithm for acquiring resources so that deadlock cannot occur with three processes running.
    If we change Z to acquire A then C, no deadlock can occur.


Problem 6. The following is a question about dining computer scientists. There are 6 computer scientists seated at a circular table. There are 3 knives at the table and 3 forks. The knives and forks are placed alternately between the computer scientists. A large bowl of food is placed at the center of the table. The computer scientists are quite hungry, but require both a fork and a knife to eat.
Consider the following policies for eating and indicate for each policy if it can result in deadlock.
    • Attempt to grab the fork that sits between you and your neighbor until you are successful.
    • Attempt to grab the knife that sits between you and your neighbor until you are successful.
    • Eat
    • Return the fork.
    • Return the knife.
    No deadlock is possible since the number of available forks limits the number of knives that can be acquired, i.e., if you have a fork, a knife is guaranteed to be available.
    • Attempt to grab any fork on the table until you are successful (if there are many forks grab the closest one).
    • Attempt to grab any knife on the table until you are succesful (if there are many forks grab the closest one).
    • Eat
    • Return the knife.
    • Return the fork.
    No deadlock is possible for the same reason as above.
    • Flip a coin to decide if you are going to first try for a fork or a knife.
    • Attempt to grab your choice until you are successful (if there are many of that utensil grab the closest one).
    • Attempt to grab the other type of utensil until you are successful (if there are many of that utensil grab the closest one).
    • Eat
    • Return the knife.
    • Return the fork.
    Deadlock is possible since now it is possible all the philosophers to acquire a utensil and then stall indefinately waiting for the other utensil to appear.


Problem 7. Gerbitrail is a manufacturer of modular gerbil cages. A Gerbitrail cage is assembled using a catalog of modules, including gerbil "rooms" of various sizes and shapes as well as sections of tubing whose diameter neatly accommodates a single gerbil. A typical cage contains several intercon- nected rooms, and may house a community of gerbils:

The Gerbitrail cages are immensely successful, except for one tragic flaw: the dreaded GERBILOCK. Gerbilock is a situation that arises when multiple gerbils enter a tube going in opposite directions, meeting within the tube as shown below:

Since each gerbil is determined to move forward and there is insufficient room to pass, both gerbils remain gerbilocked forever.
There is, however, hope on the horizon. Gerbitrail has developed little mechanical ggates that can be placed at the ends of each tube, and which can both sense and lock out gerbil crossings. All ggates are controlled by a single computer. Each ggate X has two routines, X_Enter and X_Leave, which are called when a gerbil tries to enter or leave respectively the tube via that ggate; the gerbil is not allowed to procede (ie, to enter or leave) until the Enter or Leave call returns. Gerbitrail engi- neers speculate that these routines can solve Gerbilock using semaphores.
They perform the following experiment:

where each of the ggates A and B are controlled by the following code:
semaphore S=???;        /* Shared semaphore. */

A_Enter()              /* Handle gerbil entering tube via A */
{ wait(S); }
A_Leave()              /* Handle gerbil leaving tube via A */
{ signal(S); }
B_Enter()              /* Handle gerbil entering tube via B */
{ wait(S); }
B_Leave()              /* Handle gerbil leaving tube via B */
{ signal(S); }
  1. What is the proper initial value of the semaphore S?
    S = 1 since one gerbil is allowed in the tube.
  1. An argument among the Gerbitrail technical staff develops about how the above solution should be extended to more complex cages with multiple tubes. The question under debate is whether separate semaphores should be allocated to each ggate, to each tube, or whether a single semaphore should be shared for all gates. Help resolve the argument. For each proposal, indicate OK if it works, SLOW if it works but becomes burdensome in complex cages, and BAD if it doesn't prevent gerbilock.Single semaphore shared among all ggates: OK -- SLOW -- BAD
    Semaphore for each tube: OK -- SLOW -- BAD
    Semaphore for each ggate: OK -- SLOW -- BAD
    Single semaphore shared among all ggates: SLOW
    Semaphore for each tube: OK
    Semaphore for each ggate: BAD
  1. Gerbitrail management decides to invest heavily in the revolutionary technology which promises to wipe out the gerbilock threat forever. They hire noted computer expert Nickles Worth to evaluate their ggate approach and suggest improvements. Nickles looks at the simple demonstration above, involving only 2 gerbils and a single tube, and immediately objects. "You are enforcing non-essential constraints on the behavior of these two gerbils", he exclaims.What non-essential constraint is imposed by the ggate solution involving only 2 gerbils and one tube? Give a specific scenario.
    Since only 1 gerbil is allowed in the tube at a time, both gerbils can't go through the tube simultaneously in the same direction even though that would work out okay.
  1. Nickles proposes that a new synchronization mechanism, the gerbiphore, be defined to handle the management of Gerbitrail tubes. His proposal involves the implementation of a gerbiphore as a C data structure, and the allocation of a single gerbiphore to each tube in a Gerbitrail cage configuration.Nickles's proposed implementation is:
    semaphore mutex=1;
    
    struct gerbiphore {          /* definition of "gerbiphore" structure*/
     int dir;                    /* Direction: 0 means unspecified. */
     int count;                  /* Number of Gerbils in tube */
    } A, B, ...;                 /* one gerbiphore for each tube */
    
    int Fwd=1, Bkwd=2;           /* Direction codes for tube travel */
    
    /* genter(g, dir) called with gerbiphore pointer g and direction dir
       whenever a gerbil wants to enter the tube attached to g
       in direction dir */
    
    genter(struct gerbiphore *g, int dir) {
     loop:
       wait(mutex);
       if (g->dir == 0)
         g->dir = dir;    /* If g->dir unassigned, grab it! */
       if (g->dir == dir) {
         g->count = 1 + g->count;   /* One more gerbil in tube. */
         *********;                 /* MISSING LINE! */
         return;
       }
       signal(mutex);
       goto loop;
    }
    
    /* gleave(g, dir) is called whenever a gerbil leaves the tube
       attached to gerbiphore g in direction dir. */
    
    gleave(struct gerbiphore *g, int dir) {
       wait(mutex);
       g->count = g->count - 1;
       if (g->count == 0) g->dir = 0;
       signal(mutex);
    }
    
    Unfortunately a blotch of red wine obscures one line of Nickles's code. The team of stain analysts hired to decode the blotch eventually respond with a sizable bill and the report that "it appears to be Ch. Petrus, 1981". Again, your services are needed.
    What belongs in place of ********* at the line commented "MISSING LINE"?
    signal(mutex). We have to release the mutual exclusion lock before returning from genter.
  1. Ben Bitdiddle has been moonlighting at Gerbitrail Research Laboratories, home of the worlds largest gerbil population. Ben's duties include computer related research and shoveling. He is anxious to impress his boss with his research skills, in the hopes that demonstrating such talent will allow him to spend less of his time with a shovel.Ben observes that the GRL Gerbitrail cage, housing millions of gerbils and involving tens of millions of tubes, is a little sluggish despite its use of Nickles Worth's fancy gerbiphore implementation. Ben studies the problem, and finds that each gerbil spends a surprisingly large amount of time in genter and gleave calls, despite the fact that tubes are infrequently used due to their large number. Ben suspects some inefficiency in the code. Ben focuses on the gleave code, and collects statistics about which line of code in the gleave definition is taking the most CPU time.
    Which line of the (4-line) gleave body do you expect to be the most time consuming?
    wait(mutex) since that may hang while waiting for other instances of genter or gleave to complete.
  1. Identify a class of inessential precedence constraints whose imposition by Nickles's code causes the performance bottleneck observed by Ben.
    The mutex semaphore implements a global lock, so you can't manipulate more than one 1 semaphore at a time.
  1. Briefly sketch a change to Nickles's code which mitigates the performance bottleneck.
    If we use a separate mutex for each gerbifore than the mutual exclusion each mutex provides will only apply to operations on that gerbifore.
  1. Encouraged by his success (due to your help), Ben decides to try more aggressive performance improvements. He edits the code to gleave, eliminating entirely the calls to wait and signal on the mutex semaphore. He then tries the new code on a 2-gerbil, 1-tube cage.Will Ben's change work on a 2-gerbil, 1-tube cage? Choose the best answer.

    1. It still works fine. Nice work, Ben!
    2. Gerbilock may be caused by two nearly simultaneous genter calls.
    3. Gerbilock may be caused by two nearly simultaneous gleave calls.
    4. Gerbilock may be caused by nearly simultaneous gleave and genter calls, followed by another genter call.
    5. Gerbilock can't happen, although the system may fail in other ways.
    D.


Problem 8. Similar Software is a software startup whose 24 employees include you and 23 lawyers. Your job is to finish the initial product: the Unicks timesharing system for a single-processor Beta system. Unicks is very similar to the OS code we've seen in lecture, and to a popular workstation OS. To avoid legal entanglements, it incorporates a distinguishing feature: an inter-process communication mechanism call the tube.
A tube provides a flow-controlled communication channel among processes. The system supports at most 100 different tubes, each identified by a unique integer between 0 and 99. The system primitives for communicating via tubes are the Beta SVCs WTube, which writes the nonzero integer in R1 to the tube whose number is in R0, and RTube, which reads a nonzero datum from the tube whose number is passed in R0. Note that tubes can only be used to pass nonzero integers between processes.
The Unicks handlers for WTube and RTube are shown below:
int Tubes[100]; /* max of 100 tubes */

WTube_handler() {
  int TubeNumber = User.R0; /* which tube to write */
  int Datum = User.R1; /* the data to write */

  if (Tubes[TubeNumber] != 0) { /* wait until Tube is empty */
    User.XP = User.XP - 4;
    return;
  } else { 
    Tubes[TubeNumber] = Datum; /* tube empty, fill it up! */
  }
}

RTube_handler() {
  int TubeNumber = User.R0; /* which tube to read */

  if (Tubes[TubeNumber] == 0) { /* wait until there's data */
    User.XP = User.XP - 4;
    return;
  } else {
    User.R1 = Tubes[TubeNumber]; /* read the datum */
    Tubes[TubeNumber] = 0; /* mark the tube as empty */
  }
}
The handlers run as part of the Unicks kernel and will not be interrupted, i.e., handling of interrupts is postponed until the current process returns to user mode. Note that the initial values in the Tubes array are zero, and keep in mind that only nonzero data is to be written to (and read from) each tube.
  1. Let Wi be the ith write on a tube, and Rj be the jth read. What precedence constraint(s) does the above implementation enforce between completion of the Wi and Rj?
    The code requires that the With write must precede the Rith read, that the Rith read must precede the Wi+1th write. All other precedence relationships can be derived from these.
  1. You observe that a process that waits once will waste the remainder of its quantum looping. Suggest a one-line improvement to each of the handlers which will waste less time synchronizing the communication processes.
    Each handler could call the scheduler before returning on a read/write fail.
  1. Assume, for the remaining questions, that your improvement HAS NOT been implemented; the original code, as shown, in being used.Since tubes are advertised as a general mechanism for communication among a set of Unix processes, it is important that they work reliably when several processes attempt to read and/or write the simultaneously. S. Quire, the ex-lawyer CEO, has been unable to figure out just what the semantics of tubes are under these circumstances. He finally asks you for help.
    Describe what will happen if a process writes an empty tube while multiple processes are waiting to read it. How many processes will read the new value?
    Since RTube_handler() is not interruptible, exactly one process will get the new value.
  1. Describe what will happen if multiple processes write different values to a tube at about the same time that another process is doing successive reads from that tube. Will each value be read once? Will at least one value be read, but some may be lost? Will garbage (values other than those written) be read?
    Since WTube_handler() is not interruptible, no values will be lost. Each value will be read correctly.
  1. S. Quire suggests that the interrupt hardware be modified so that timer interupts (which mark the end of the quantum for the currently running process) are allowed to happen in both user and kernel mode. How would this modification change your answer to parts (C) and (D)?
    If the handlers are interruptible, multiple processes may read the same value or garbage (zero). Multiple processes may write over other values before they are read, but will not be read twice if there is only a single reader.
  1. Customers have observed that Unicks seems to favor certain processes under some circumstances. In particular, when one process writes data to a tube while processes A, B, and C are waiting to read it, it is typically the case that the amount of data read by A, B, and C will be dramatically different.Briefly explain the cause for this phenomenon.
    If process D writes data and the scheduler calls A, B, C, and D round-robin (in that order), process A has the best chance of having its Rtube call succeed since it runs right after process D has finished calling Wtube.
  1. Sketch, in a sentence or two, a plausible strategy for treating the processes more equitably.
    If processes have numbers, each tube could remember the last process that read it. When a process writes to the tube again, it could reorder scheduling so that the waiting process with the next higher process number is called next. Another approach would be to use a randomized scheduler, but this creates the possibility that some processes will not be run for a long period of time.
  1. Nickles Worth, a consultant to Similar Software, claims that tubes can be used to implement mutual exclusion-that is, to guarantee that at most one process is executing code within a critical section at all times. He offers an example template:
    int TubeNumber = 37; /* tube to be used for mutual exclusion */
    
    WTube(TubeNumber,1); /* one-time-only initialization */
    
    while () { /* loop with critical section */
       
        /* LOCK ACCESS */
       
       <critical section>
       
        /* UNLOCK ACCESS */
       
    }
    
    where the regions marked LOCK ACCESS and UNLOCK ACCESS use the tube TubeNumber to ensure exclusive access to the code marked <critical section>. These two regions may contain the forms datum=RTube(TubeNumber) and Wtube(TubeNumber,datum) as a C interface to the tube SVCs.Fill in the LOCK and UNLOCK code above.
    LOCK: datum=RTube(TubeNumber)
    UNLOCK: Wtube(TubeNumber,datum)