CS354 Fall 1999

Final Exam

Name:


1. What are the differences between a thread and a process. (3 pts)
 
 
 
 
 

2. What is the difference between deadlock and starvation. (3 pts)
 
 
 
 
 

3. Describe the advantages of demand paging compared to process swap and segment swap. (3 pts)
 
 
 
 
 
 

4. What is the page-table register for and when it is updated? (3 pts)
 
 
 
 
 

5. What is the advantage of using multi-level page tables? (3 pts)
 
 
 
 

6. Why does the page-size have to be a power of two? (3 pts)
 
 
 
 

7. List the different page-bits in the page-table entry. (3 pts)
 
 
 
 

8. List the different types of page-faults. (3 pts)
 
 
 
 

9. List the steps to process a page-fault. (3 pts)
 
 
 
 

10. Explain how copy-on-write works when fork() is called. (3 pts)
 
 
 
 

11. Explain the advantages and disadvantages of first-fit and best-fit in memory allocation. (3 pts)
 
 
 
 
 

12. Why does the malloc library is necessary? (3 pts)
 
 
 
 
 

13. What is memory fragmentation? (3 pts)
 
 
 
 

14. What are the problems with explicit memory management and describe them. (3 pts)
 
 
 
 

15. What is the function of the "count" field in the i-node? (3 pts)
 
 
 
 

16. What are the differences between a hard-link and a soft link. (3 pts)
 
 
 
 

17. Why does the UNIX file system use direct, single, double, and triple indirections? (3 pts)
 
 
 
 

18. Assume that a computer has only three physical pages. The following diagrams show two sequences of referenced pages. Write down in the empty slots the pages that are loaded in physical memory at each page reference. Also, also write down the number of hits and misses. Use the LRU page replacing policy in both cases. (8 pts)
 
 

Page Referenced: 1 2 3 4 1 2 3 4
Phys Page 1                
Phys Page 2                
Phys Page 3                

# of hits =
# of misses =
 
 

Page Referenced  1 2 1 2 3 4 3 4
Phys Page 1                
Phys Page 2                
Phys Page 3                

# of hits =
# of misses =

19. Assume the following 2-level page table. Translate the VM address 0x00801B4B to its corresponding physical address. Assume a page size of 4KB and that the first 10 bits of the VM address index the level 1 page table, the next 10 bits index the second level and the bits left are the page offset, similar to what was discussed in class. Assume a 32-bit word size. (8 pts)

VM Address 0x00801B4B is _______________ in Physical Memory
 

Level 1
0 0x38000
1 0x36000
2 0x32000
Level 2
At 0x38000 0 0x42000
1 0x50000
2 0x70000

 
Level 2
At 0x32000 0 0x56000
1 0x58000
2 0x72000

 
Level 2
At 0x36000 0  0x5a000
1 0x5c000
2 0x62000

 
 

20. What is the problem in the following code? Reimplement the transfer function to fix this problem. Assume that multiple threads call the transfer() procedure simultaneously. (8 pts)
 
 

 

void
transfer( int source, int destination, int amount )
{
mutex_lock( &mutex[ source ] );
mutex_lock( &mutex[ detination ] );
balance[ source ] - = amount;
balance[ destination ] + = amount;
mutex_unlock( &mutex[ source ] );
mutex_unlock( &mutex[ detination ] );
}

void
fixed_transfer( int source, int destination, int amount )
{

 
 
 
 
 
 
 
 
 
 
}

21. Complete the following code to implement the bounded buffer problem using condition variables.(8 pts)
 


int n = 5;
int buffer[ n ] ;
int count = 0;
 
 

void 
writeBuffer( int v ) 
{
 
 
 

buffer[ tail ] = v;
tail = (tail + 1 ) % n;

 

}

int
readBuffer()
{
 
 

int tmp = buffer[ head ];
head = (head + 1 ) % n;
 
 

return tmp;

}

 

22. Implement the semaphore operations using condition variables. Implement the operations for a single semaphore.(8 pts)
 
 

//Define variables here
 
 

void
sema_init( int count )
{
 
 

}

void
sema_wait()
{
 
 
 
 
 
 

}

void
sema_signal()
{
 
 
 
 
 
 
 

}
 

23. The following code implements the read/write lock using condition variables. In which circumstances this read/write lock can suffer from starvation?(8 pts)
 
 
 
 
 
 
 

void readlock(){
mutex_lock( &mutex );
while( writers > 0 ) {
cond_wait ( &condrw, &mutexrw );
}
readers++;
mutex_unlock ( &mutexrw ); 
}

void readUnlock()
{

mutex_lock( &mutexrw );
readers--;
cond_broadcast( &condrw ); 
mutex_unlock( &mutexrw );
} 

void writelock()
{

mutex_lock( &mutexrw );
while( readers > 0 || writers > 0 ) {
cond_wait( &condrw, &mutexrw);
}
writer++;
mutex_unlock( &mutexrw );
}                    

void write_Unlock()
{

mutex_lock( &mutexrw );
writers--;
cond_bradcast( &condrw );
mutex_unlock( &mutexrw );
}