David E. Goldschmidt, Ph.D.

exams

Our two exam dates are scheduled as follows:

• Midterm Exam: Tuesday 3/3 (DCC 318)
• Final Exam: Monday 5/4 3-6pm (Ricketts 203)

FINAL EXAM:
 OPEN BOOK, OPEN NOTES; NO COMPUTERS, ETC.
 CALCULATORS OKAY (NO CHEATING!)

 Comprehensive coverage:
  Chapters 1-10, 12, Appendix A

  (also Midterm Exam)

  Synchronization, Semaphores (binary/counting)
  Interprocess Communication (IPC)
    Shared memory, atomicity, message passing
    Sockets
    Serializing sockets in Java
    Marshalling parameters
  Networks, OSI Reference Model
  Starvation, Deadlock
  Memory Management
    Relocatable code, Dynamic Loading/Linking
    Swapping
    Contiguous/Noncontiguous memory allocation
    Allocation algorithms
    Fragmentation (external vs. internal)
    Address translation
      Translation Lookaside buffer (TLB)
    Effective Memory-Access Time (EMAT)
    Paging
    Segmentation
    Virtual Memory
      Demand paging, pre-paging
      Page faults, Thrashing
      Page Replacement Algorithms
  Principle of Locality!
  File Management
    Files, Filesystems
    Disk Space Allocation (Contiguous/Clustered)
    FAT, Unix inodes, Multilevel Indexing
  I/O System
    Disk access time (seek time + rotational lat.)
    Buffering, Caching
    Disk I/O Scheduling Algorithms

Sample Exam Questions

1. In your own words, describe the importance of interrupts in a modern operating system.
2. In your own words, describe the differences between kernel mode and user mode. In particular, what is executed in kernel mode? And why is the use of kernel mode beneficial?
3. In your own words, describe how a system call works. In particular, how are parameters passed to the invoked system call?
4. How are new processes created in an operating system? How are new threads created?
5. What is the exact output of the following C code snippet?

   int main()
   {
     int x = 5;
     pid_t pid = fork();
     printf("FORKING....\n");
   
     if ( pid == 0 ) {
       printf("CHILD: Hello.\n");
       x *= 5;
       printf("CHILD: %d\n", x);
     }
     else {
       wait(NULL);
       printf("PARENT: Child completed.\n");
       x *= 5;
       printf("PARENT: %d\n", x);
     }
   }
   

6. Given the table of processes below, calculate the individual and average turnaround and wait times for both the non-preemptive FCFS and SJF scheduling algorithms. Recalculate using a preemptive SJF scheduling algorithm. Draw a chart showing the order in which processes use the CPU (called a Gantt chart).

    Process   Arrival time   CPU burst time
   -----------------------------------------
      P1          0 ms           10 ms
      P2          7 ms           17 ms
      P3          6 ms            9 ms
      P4         11 ms            4 ms
   

7. In your own words, describe the problems that occur without proper process synchronization. How can such problems be overcome?
8. Given atomic wait() and signal() operations shown below for semaphore S, explain why such operations must be atomic to ensure process synchronization. Further, what is busy waiting and why is it detrimental?

wait(S)
{
  while ( S <= 0 )
    /** no-op **/ ;

  S--;
} 

signal(S)
{
  S++;
}

9. Using atomic wait() and signal() operations shown above, write pseudocode for the producer-consumer problem in which a producer process writes elements to a shared buffer of size n, and a single consumer process reads elements from this same shared buffer. Use a binary semaphore.
10. Revise your solution to the above problem by using a counting semaphore to support multiple consumer processes.
11. In your own words, describe the differences between asynchronous and synchronous communication in an operating system. What are the advantages and disadvantages of each?
12. In your own words, describe the following commonly used client-server communication techniques: remote procedure calls, remote method invocation, and sockets. In particular, what is a socket and what protocols are used to communicate using sockets?
13. In your own words, describe the process of marshalling parameters. Why is it necessary in modern operating systems?
14. In your own words, describe deadlock and starvation in relation to process synchronization. What's necessary for deadlock to occur? Also describe ways to avoid deadlock and starvation.
15. In your own words, describe the differences between logical memory and physical memory. What is relocatable code and why is it important to memory management?
16. In your own words, describe contiguous allocation and the corresponding first-fit and best-fit algorithms. What advantages does a next-fit algorithm provide? Further, describe internal fragmentation and external fragmentation.
17. In a noncontiguous memory allocation scheme, a logical address is represented using 28 bits. Of these bits, the high-order 12 bits represent the page number; the remaining bits represent the page offset. What is the total logical memory space (i.e. how many bytes are logically addressed)? How many pages are there? What is the page size? How would logical memory address 2,345,678 map to physical memory (i.e. what is the resulting page number and page offset)? If a process requires 88,555,222 bytes of memory, how many pages will it require (and how many bytes are wasted due to internal fragmentation)? Given an average process size of 32MB, how many pages will the average process require? What is the average degree of multiprogramming?
18. Consider a paging system with the page table stored entirely in memory. Without using a translation look-aside buffer (TLB), if a memory reference takes 100 nanoseconds, how long does a paged memory reference take?
19. In your own words, describe what a translation look-aside buffer (TLB) is and how it's beneficial to operating system performance. Next, consider a paging system with the page table stored entirely in memory. A memory reference takes 150 nanoseconds. Using a TLB with an access time of 30 nanoseconds, if a TLB miss occurs, how long does a paged memory reference take? Further, if the TLB hit ratio is 85%, what is the effective memory-access time?
20. What is virtual memory and how is it beneficial to modern operating systems? Consider a virtual memory system in which a single memory reference requires 100 nanoseconds and the average page-fault service time is 4 milliseconds. Given page-fault rate p, what is the formula for the effective memory access time? How does performance deteriorate when page faults occur at a rate of 1 every 10,000,000 memory accesses? How does performance deteriorate when page faults occur at a rate of 1 every 1000 memory accesses?
21. Given a physical memory consisting of only three frames, both initially empty, how many page faults occur given the page-reference string shown below and the following replacement algorithms: (a) Least-Recently Used (LRU); (b) First-In-First-Out (FIFO); and (c) Optimal (OPT).

    1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
    

    If memory access time is 100 nanoseconds and page-fault service time is 5 milliseconds, what is the total memory access time for each of the above page replacement algorithms? Of the three page replacement algorithms considered here, which one is the best? And which one is impossible to implement exactly?
22. Given the following snippet of Java caching code, what is the exact output?

      public static void main(String[] args)
      {
        int[] x = new int[100];
        int[] r = new int[100];
    
        boolean done = false;
    
        while ( done == false )
        {
          int q = 47895;
          int index = q % 100;
    
          if ( x[ index ] == q )
          {
            System.out.println( "==> " + r[ index ] + " (cache hit!)" );
            done = true;
          }
          else
          {
            int result = q / 100;   // integer division
            System.out.println( "==> " + result );
            x[ index ] = q;
            r[ index ] = result;
          }
        }
      }
    

23. Describe what a virtual machine is (e.g. Java). What are advantages and disadvantages to using a virtual machine?
24. What is a process context switch and why is it a necessary part of an operating system? What is a disk context switch and what is its significance? How do these two types of context switches compare?
25. Consider a disk I/O scheduling problem in which the disk arm begins at track number 50. Given the track reference string below (i.e. the queue of track numbers that need to be accessed), write the actual order in which tracks are accessed for each of these scheduling algorithms: (a) FCFS; (b) C-SCAN; (c) SSTF; and (d) LOOK. For each case, what is the total number of arm movements?