CS 416 Exam 1

Spring 2012

See the solutions (6 per page).

    Part I – 26 Points

  1. 4 points
    UNIX-derived systems execute new programs via a two-step process of fork and execve. Other systems provide a single system call to run a new program. Explain an advantage of using this two-step approach.
  2. 4 points
    1. What is the potential danger in running this code?

      while (1) fork();
    2. What should be done in the kernel to limit this problem?
  3. 4 points

    We need to sum up a huge array of numbers and will use multiple threads to do so. A worker thread is started with a thread ID as a parameter, where threads are numbered 0, 1, ... (numvalues-1). Each of N worker threads sums up every Nth element of the array in parallel into a local variable, sum. At the end, they each add their answer to a running total called total. A separate thread, main, dispatches the workers and computes and prints the final result.

    /* global values */ int total, values[], numvalues, N; sem s= event e= main() { pthread t[N]; int i; for (i=0; i < N; ++i) { pthread_create(&t[i], NULL, worker, i); } printf(“total = %d\n”, total); } worker(int i) { int j, sum=0; for (j=i; j < numvalues; j+=N) { sum += values[j]; } total += sum; }

    Using one semaphore, s, and one event variable e, and without waiting on (joining) threads, define the initial values of s and e and the placement of up(s)/down(s) and advance(e)/await(e, value) operations to ensure that all the summations takes place without race conditions and only when the data is ready.

  4. 4 points
    What is the difference between deadlock and starvation?
  5. 4 points
    If short time slices improve interactive performance, what is the downside?
  6. 4 points
    How does Multilevel Feedback Queue scheduling try to approximate Shortest Remaining Time First (SRTF) scheduling? How does it not have the disadvantage of SRTF?
  7. PART II – 60 points – 3 points each

    For each statement, select the most appropriate answer.

  8. In contrast to the BIOS, EFI (Extensible Firmware Interface):
    (a) Is stored in system firmware instead of on the disk.
    (b) Loads a boot loader from the master boot record (MBR).
    (c) Bypasses the Master Boot Record (MBR) and load a boot loader from the volume boot record (VBR) directly.
    (d) Can load a boot loader from a file system on the disk.
  9. Which of the following is most likely to be a system call?
    (a) The implementation of a while loop in C.
    (b) Parse a token from a string.
    (c) Get the cosine of a number.
    (d) Get the time of day.
  10. The primary use of a Programmable Interval Timer (PIT) is to:
    (a) Measure the elapsed time between two events.
    (b) Put the system to sleep but have it wake up later at a predetermined time.
    (c) Put a process to sleep for a specified interval.
    (d) Make sure that the kernel gets control of the processor periodically.
  11. Which of these statements is true?
    (a) A mode switch precedes a context switch.
    (b) A context switch precedes a mode switch.
    (c) A context switch can occur without a mode switch.
    (d) A mode switch is just a different name for a context switch.
  12. Disk controllers tend to use Direct Memory Access (DMA) over Programmed I/O (PIO) because:
    (a) The CPU does not have to copy the disk data byte by byte.
    (b) Most disks are not programmable.
    (c) Transferring data to or from a disk is performed by the kernel.
    (d) The entire disk appears as memory to an operating system.
  13. The first demonstration of a computer system with a graphical display, keyboard, mouse, networking, shared screen collaboration, and hypertext took place in:
    (a) 1956
    (b) 1968
    (c) 1980
    (d) 1992
  14. Which process state transition is not valid?
    (a) Ready → Running
    (b) Running → Ready
    (c) Running → Blocked
    (d) Blocked → Running
  15. Which process state transition is valid only on a preemptive multitasking system?
    (a) Ready → Running
    (b) Running → Ready
    (c) Running → Blocked
    (d) Blocked → Running
  16. A Thread Control Block (PCB) stores:
    (a) User (owner) ID
    (b) Memory map
    (c) The machine state (registers, program counter)
    (d) Open file descriptors
  17. A race condition is:
    (a) When one process is trying to beat another to execute a region of code.
    (b) When a process cannot make progress because another one is blocking it.
    (c) When the outcome of processes is dependent on the exact order of execution among them.
    (d) A form of locking where processes coordinate for exclusive access to a critical section.
  18. A process scheduler is responsible for moving processes between these states:
    (a) Ready and Blocked
    (b) Running and Blocked
    (c) Ready and Running
    (d) Ready, Running, and Blocked
  19. The wait system call on UNIX systems puts a process to sleep until:
    (a) A semaphore wakes it up.
    (b) The specified elapsed time expires.
    (c) A child process terminates.
    (d) The process is preempted by another process.
  20. Priority inversion occurs when:
    (a) A scheduler repeatedly schedules a low-priority thread over a high-priority one.
    (b) A high-priority thread is blocked, causing the scheduler to run a low-priority thread.
    (c) A scheduler schedules a high-priority thread when it would be better to schedule a low-priority one.
    (d) A high-priority thread wakes up a low-priority thread, causing it to be scheduled.
  21. Every process gets the same share of the CPU with a:
    (a) Round-robin scheduler.
    (b) Shortest remaining time first scheduler.
    (c) Priority scheduler.
    (d) Multilevel feedback queues.
  22. A weighted exponential average is useful in process scheduling for:
    (a) Determining the length of a quantum for the thread.
    (b) Allowing a priority scheduler to assign a priority to the process.
    (c) Estimating the length of the next CPU burst for the thread.
    (d) Ordering processes in the ready queue for a round robin scheduler.
  23. Process aging:
    (a) Increases the priority of a process if it sits in the ready state for a long time.
    (b) Decrease the priority of a process each time the process gets to run.
    (c) Increases the priority of a process as it gets older.
    (d) Decreases the priority of a process as it gets older
  24. Which scheduler does not risk starvation of processes?
    (a) Round-robin scheduler.
    (b) Shortest remaining time first scheduler.
    (c) Priority scheduler.
    (d) Multilevel feedback queues.
  25. Processes A and B are ready to run at the same time. A needs 600 msec of CPU time. B needs 800 msec of CPU time. Both need to finish within one second. Assume that a Least Slack scheduler is used with an infinitesimally small time slice. When do A and B terminate?
    (a) A at 600 msec, B at 1400 msec.
    (b) A at 1400 msec, B at 800 msec.
    (c) A and B at 1400 msec.
    (d) A and B at 1000 msec (1 sec).
  26. Now assume that an Earliest Deadline First scheduler is used. When do A and B terminate?
    (a) A at 600 msec, B at 1400 msec.
    (b) A at 1400 msec, B at 800 msec.
    (c) A and B at 1400 msec.
    (d) A and B at 1000 msec (1 sec).
  27. Process A runs 30 times a second. Each run lasts for 4 msec (a total of 120 msec CPU per second). Process B runs 60 times a second. Each run lasts for 2.5 msec (a total of 150 msec CPU per second). Process C runs 4 times a second. Each run lasts for 45 msec (a total of 180 msec CPU per second). Which is a valid priority assignment using Rata Monotonic assignment where higher numbers correspond with higher priorities?
    (a) A=2, B=1, C=3
    (b) A=2, B=3, C=1
    (c) A=1, B=2, C=3
    (d) A=3, B=2, C=1
  28. PART III – 14 points – 2 points each

    For each statement, specify whether it is true or false by circling the correct choice.

  29. A system call always results in a context switch.
          True        False
  30. On a pre-EFI PC architecture, the BIOS is loaded from the Master Boot Record (MBR), which then loads the Volume Boot Record (VBR)
          True        False
  31. A process executes faster when running in kernel mode than when running in user mode.
          True        False
  32. Hardware support for mutual exclusion, such as test-and-set locks has the advantage of avoiding the need for spin locks.
          True        False
  33. Mailboxes are a form of messaging using indirect addressing.
          True        False
  34. Rendezvous messaging between processes on the same system reduces the amount of message copying needed.
          True        False
  35. Push migration may be used in multiprocessor scheduling with hard CPU affinity.
          True        False