Homework 3 Solutions

22C:116, Fall 1997

1. Write out an algorithm using the Alpha's Load Locked and Store Condtional instructions that will perform an atomic operation equivalent to the atomic Exchange Memory and Register operations of classical architectures.

   	exchange( m, r )
              repeat
   	      LOAD_LOCKED        load_temp,m
   	      store_temp = r
   	      STORE_CONDITIONAL  store_temp,m
   	   until store_temp = reset -- indicating success
   	   r = load_temp
   

   Then: Build on what you just did by outlining the entire code for the lock() and unlock() primitives given in Lectures 4 and 5, using the Alpha instructions instead of an exchange instruction.

   	lock( lk )
              repeat
   	      LOAD_LOCKED        load_temp,lk
   	      store_temp = 1
   	      STORE_CONDITIONAL  store_temp,lk
   	   until (store_temp = reset) and (load_temp = 0)
   
   	unlock( lk )
   	   store_temp = 0
   	   STORE                 store_temp,lk
   

2. Assuming that semaphores are used for all mutual exclusion and syncronization, how many semaphores are required by this system, total, what is each used for, and what is the maximum and minimum value of the count in each?
   • Free list management: 2 (1 mutex, 1 counts free buffers)
   • For each queue: 2 (1 mutex, 1 counts data buffers)
   For 3 FIFO queues, this translates to 8 semaphores. All mutex semaphores have maximum value 1. All of the counting semaphores have a maximum of 10 because there are 10 buffers and all 10 may be in the same list or queue.

3. Consider a heap that runs from addresses 100 to 1000 (decimal). How many free blocks will this heap be divided into by the binary buddy system, as documented in lecture 6, prior to any allocation or after the final deallocation and merger of free blocks.

     992-999 --   8
     960-991 --  32
     896-959 --  64
     768-895 -- 128
     512-767 -- 256
     256-512 -- 256
     128-255 -- 128
     112-127 --  16
     104-111 --   8
     100-103 --   4
   
   Write reasonably detailed pseudocode for the allocate and deallocate
   (or malloc() and free()) operations on a boundary-tag heap with lazy
   merger of free blocks.
   
   In the following, we assume that freelist is a pointer to a distinguished
   free block that is never merged with other free blocks and never allocated
   (size zero with status set to not free would do this!)  We also assume that
   the free list is circularly linked.
   
   Each block in the heap has a successor and a predecessor link to its neighbors,
   and each free block has a nextfree link to the next free block.  The state
   field of each block may indicate either free or allocated.
       malloc(s)
           t = freelist
   	repeat
               p = t
               t = t.nextfree
   	    if t.successor.state = free then
   		merge(t,t.successor)
   	    endif
   	    if t.predecessor.state = free then
   		merge(t.predecessor,t)
   		t = t.predecessor -- problematic!
   	    endif
   	    if size(t) > s+minsplit then
   		split(t,s)
   	    endif
   	    if size(t) > s then
   		p.nextfree = t.nextfree
   		t.state = allocated
   		return t
   	    endif
   	until t = freelist
   	-- we've tried all free blocks and none fit!
   	failure
   
       free(n)
   	n.nextfree = freelist.nextfree
   	freelist.nextfree = n
   
       merge(a,b)
   	-- assert a and b are consecutive blocks in memory
   	-- snip b out of list of blocks
   	a.successor = b.successor
   	b.sucessor.predecessor = a