Computer Science 284

Introduction to Operating Systems

FOR THE PURPOSE OF THIS EXAM, A 'SIGNAL' MEANS A cond_signal AND AN 'INTERRUPT' MEANS A UNIX/KERNEL TYPE signal.

  1. What is an atomic operation?
  2. What is a spin-lock?
  3. What is an alternative to spin-locking?
  4. Explain under what circumstances a spin lock might be more efficient than the alternative.
  5. Explain under what circumstances a spin lock might be less efficient than the alternative.
  6. Under Solaris 2 running on a uniprocessor, threads waiting for a lock always sleep rather than spin.     Why is this true (and reasonable)?
  7. Why is it always important to associate a 'mutex lock' variable with a 'condition' variable?
  8. From the point of view of the calling thread, what actions occur from the time that a condition_wait() is called until the calling thread is allowed to resume execution?
  9. What is the "lost wake-up" with respect to condition signals?
  10. Explain what programming 'logic error' could allow a "lost wake-up" to occur.
  11. What is a likely result of a  "lost wake-up" having occurred?
  12. List a sequence of events that might result in a lost wake-up' if it were not programmed correctly.  Number the events 1..N and be explicit as to where/when the signal 'gets lost'.
  13. What does it mean that "condition signals do not pend"?
  14. What is the difference between starvation and deadlock?
  15. Define Deadlock.
  16. What are the necessary conditions for a deadlock to exist.
  17. What is a critical section i.e. what makes a section 'critical'?
  18. What is the difference between a mutex_t and a sema_t?
  19. What is the difference between mutex_lock and mutex_trylock?
  20. Explain the behavior of:     sema_wait()     sema_post()     sema_init()     sema_trywait()
  21. Under what conditions must a sema_t be initialized?
  22. What are the 3 possible dispositions that a process may specify with respect to an interrupt?
  23. True False Different threads within a process may specify different dispositions for a specific interrupt
  24. An interrupt will pend unless a process specifies _______________________.
  25. Using signal(...), show the program parts necessary to cause a process to print a message the 1st time that the keyboard operator presses ^C (and further ^Cs would exit the program).  For the same program, show/describe what has to be changed to get the message N times and then exit on the (N+1)th time? (assume that N is hard coded).
  26. What is a sigset_t?  How is a variable of this type set/modified?  In what ways can a variable of this type be used after it has been assigned an appropriate value(s)?
  27. Using sigaction(...), show how you would block the delivery of SIGINT within a thread.
  28. What functions are used from within a process to send an interrupt to a process?
  29. What is the "very largest" program that could execute on a machine with a 24-bit location counter?
  30. The address contained in a page table entry <PTE> are (physical | logical).
  31. List at least 3 flags that are contained in a PTE.
  32. Define hit-ratio in a memory management context.

  33. Given the figure presented in class, (or use the figure on page 351) you will be given some (enough) of the following to allow you to calculate values for the remainder.  You are to assume that page tables and segment table(s) 'fit' into one frame

Description

Answer
s number of bits in the segment number portion of the virtual address  
d number of bits in the displacement portion of the virtual address  
p number of bits in the page number portion of the virtual address  
f number of bits in the frame number portion of the physical address  
frame size (bytes)  
segment table entry size (bytes)  
page table entry size (bytes)  
max physical address  
max virtual address  
max segment size  
max number of entries in segment table  
max number of entries in page table  
  1. Describe the behavior of a "2-handed clock" algorithm. Describe the differences between a global allocation scheme and the working-set model for allocation.
  2. Why would the page-in mechanism immediately mark a newly loaded page as 'dirty'?
  3. When reading from a pipe, what causes the kernel to send EOF to the reader?
  4. Why can parent/child processes communicate via unnamed pipes but 2 unrelated processes can not?
  5. If your program contains a race condition, what does that mean?
  6. How can the code segment     if( i < y ) cout << foobar(i,y) be made to behave as if it were atomic?  Answer the question by recoding the segment.
  7. What interrupt is created when a desired frame is not currently resident in RAM?
  8. How does the hardware 'know' that a desired frame is not currently resident in RAM?
  9. How does the kernel 'know' where on disk the desired information is for a non-resident frame?
  10. What precisely does it mean if the 'dirty bit' is set for a frame?
  11. What is 'good' vs. 'bad' program locality?
  12. Comparing global allocation vs. working set allocation, which would be more adversely affect by a program with 'bad' locality? and WHY would that be true?
  13. Unix uses a global page allocation scheme.  Describe  NT's scheme.
  14. What is the important different between NT  threads and Solaris user threads?  An NT thread is most like ___________ in Solaris.
  15. Explain when/how internal fragmentation may occur.
  16. Explain when/how external fragmentation may occur.
  17. What is the function of a linker?
  18. Describe what demand paging means.
  19. You will be given a 'claim matrix', an 'allocation matrix' and a 'resource vector' for a set of processes. You will then be given a resource request from one of the processes. Should the request be granted? and if yes, give a <safe sequence>.
Claim Matrix
R1 R2 R3
P1 3 2 2
P2 6 1 3
P3 3 1 4
P4 4 2 2


Allocation Matrix
R1 R2 R3
P1 1 0 0
P2 5 1 1
P3 2 1 1
P4 0 0 2


Resource Vector
R1 R2 R3
9 3 6

Process P(i) requests N units of resource R(j). Is this a 'safe' request? Give a <safe sequence>.