final

CS354 Spring 2000

Final Exam

Name:

Part 1. Answer True/False (T/F) (1 point each)

____1. The threads in a process share the same stack.
____2. The page-table register is part of the CPU.
____3. During starvation, threads will never be able to proceed.
____4. In segment-swap entire processes are swapped in and out from disk.
____5. Multi-level page tables save more space that single-level page tables.
____6. The page-table register is updated every time there is a context switch from one thread to another.
____7. Page sizes are always a power of two.
____8. In demand paging a virtual address is divided into page number and page offset.
____9. There is one page table for each thread in a process.
____10. A physical page that is replaced is always written back to the backing store.
____11. Having multiple threads increases the reliability of a program compared to having multiple processes.
____12. ELF is an executable format used on Windows.
____13. truss is a UNIX command to show the number of users in the system.
____14. The text section of a program is memory mapped readable and executable.
____15. System calls and interrupts run in user mode.
____16. Most of the processes in a computer are in ready state.
____17. The first step in an interrupt rpoutine is to save the registers of the processes.
____18. The last step in an interrupt routine is to retry the offending instruction.
____19. There is at most one running process in the computer.
____20. Most of the CPU time is spent in user mode.
____21. A program in user mode is able to call functions and modify memory.
____22. Shared libraries run in user mode.
____23. A small time quantum will cause a program to take more time.
____24. The arguments of a system call are checked in user space.
____25. In preemptive scheduling a process takes higher priority until completion.
____26. A program that runs with preemptive scheduling runs faster than one in non-preemptive scheduling.
____27. Most of the processes' CPU bursts are completed before the time quantum expires.
____28. There is only one page-table register in every computer.
____29. Programs that run with FCFS have a higher response time than SJF.
____30. The file descriptors of a process are closed when the process calls fork().
____31.
____32.
____33.
____34.
____35.
____36.
____37.
____38.
____39.
____40. The write() function is a system call but printf() is not.
____41. A pipe that is used to communicate a parent and a child process could be created by the child.
____42. Threads in the same process share the same memory.
____43. A section of code that is guarded by mutex_lock()/mutex_unlock() can be executed by only one thread at a time.
____44. The process table contains a set of registers and program counters for each user and kernel level thread in a process.
____45. pthread_create() by default creates user-level threads.
____46. Disabling interrupts is faster than using spinlocks in programs that run in user space in uniprocessor systems.
____47. A mutex is equivalent to a semaphore that is initialized with a counter of 0.
____48. In the bounded buffer problem solution using semaphores, the writeBuffer() procedure waits on a semaphore that is initialized to the number of buffers available.
____49. mmap() for a shared memory section returns the same address for each caller process.
____50.cond_wait() unlocks the mutex lock that is passed as a parameter.

51. Write the steps for servicing a page-fault. (5 pts.)

52. Explain how copy-on-write works and how fork() benefits from this technique. (5 pts.)

53. The following three threads have access to five databases. Each database has its own mutex lock. Give an example of how these three threads can enter into a deadlock and explain how this can be prevented.( 5 pts.)

thread1()
{
    while (1) {
      mutex_lock( &mutex_db5);
      mutex_lock( &mutex_db2);
      mutex_lock( &mutex_db3);

// Access db5, db2, db3

      mutex_unlock( &mutex_db5);
      mutex_unlock( &mutex_db2);
      mutex_unlock( &mutex_db3);
    }
}

thread2()
{
    while (1) {
      mutex_lock( &mutex_db4);
      mutex_lock( &mutex_db1);

// Access db4, db1

      mutex_unlock( &mutex_db4);
      mutex_unlock( &mutex_db1);
    }
}

thread3()
{
    while (1) {
      mutex_lock( &mutex_db1);
      mutex_lock( &mutex_db2);
      mutex_lock( &mutex_db5);

// Access db1, db2, db5

      mutex_unlock( &mutex_db1);
      mutex_unlock( &mutex_db2);
      mutex_unlock( &mutex_db5);
    }
}

How this deadlock can be prevented?

54. Assume the following 2-level page table. Translate the VM address 0x00C02E4B 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. The third column in the level 2 page tables are physical page addresses.(5 pts)

VM Address 0x00C02E4B is _______________ in Physical Memory

Level 1
0	0x38000
1	0x36000
2	0x32000
3	0x40000

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

Level 2
At 0x40000	0	0x89000
	1	0x82000
	2	0x86000

55. 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. Don't forget to answer the questions that are there at the end of the diagram.(5 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	3	3	2	1	1	2
Phys Page 1
Phys Page 2
Phys Page 3

# of hits =
# of misses =

What can you learn from these two diagrams? Why demand paging works in most computer systems?

56. Write the code for the insert() and lookup(). insert() inserts the integer i to the head of the list, lookup() returns 1 if i exists in the list or 0 otherwise. Add the necessary code to make the code thread safe. (5 pts)

struct ListEntry {
int _value;
struct ListEntry * _next;
};

class List {
ListEntry * _head;
// Other fields go here

public:
List();
void insert( int i );
int lookup( int i );
};

List::List()
{

}

void List::insert( int i )
{

}

int List::lookup( int i )
{

}

57. Write the code for RPCClient::call() from project 2. Try to be as precise as possible. (5 pts.)

int
RPCClient::call( char * rpcName, RPCArgument argument, RPCResult result )
{

}

58. Complete the class ReadWriteLock that implements read/write locks. Add the fields that are necessary. IMPORTANT: Use semaphores.(5 pts.)

class ReadWriteLock {
/* Add other fields here */

public:
ReadWriteLock();
readLock();
writeLock();
readUnlock();
writeUnlock();
};

ReadWriteLock::ReadWriteLock()
{

}

ReadWriteLock::readLock()
{

}

ReadWriteLock::writeLock()
{

}

ReadWriteLock::readUnlock()
{

}

ReadWriteLock::writeUnlock()
{

}

59.Complete the following procedures. sendBroadcast() sends a message to N threads that will call receiveBroadcast(). sendBroadcast() will block until the N threads have called receiveBroadcast(). receiveBroadcast() will block until a thread has called sendBroadcast() and the variable theMessage has a valid value. IMPORTANT: Use condition variables instead of semaphores. (5 pts.)

const int N = 5;
int theMessage;

void sendBroadcast( int msg )
{

theMessage = msg;

}

int receiveBroadcast()
{

int tmp = theMessage;

return tmp;
}

      main()
      {
          // Initialization goes here

}

60. Complete the following procedure that prints the environment variables of a process. (5 pts)

void printEnvironmentVars()
{

}