• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Assignment 5
• Assignment 6
• Assignment 7

Assignment 1 (due 9/13)

• Problem 1.9 A computer consists of a CPU and an I/O device D connected to main memory M via a shared bus with a data bus width of one word. The CPU can execute a maximum of 10⁶ instructions per second. An average instruction requires five machine cycles, three of which use the memory bus. A memory read or write operation uses one machine cycle. Suppose that the CPU is continuously executing "background" programs that use 95% of its instruction execution rate but not any I/O instructions. Assume that one processor cycle equals one bus cycle. Now suppose that very large blocks of data are to be transferred between M and D.
  1. If programmed I/O is used and each one-word I/O transfer requires the CPU to execute two instructions, estimate the maximum I/O data transfer rate, in words per second, possible through D.
  2. Estimate the same rate if DMA transfer is used.

• Problem 2.4 What is the purpose of system calls, and how do system calls relate to the operating system and to the concept of dual-mode (kernel mode and user mode) operation?

• Problem 3.5 Table 3.13 shows the process states for the VAX/VMS operating system.
  1. Can you provide a justification for the existence of so many distinct wait states?
  2. Why do the following states not have resident and swapped-out versions: page fault wait, collided page wait, common event wait, free page wait, and resource wait?
  3. Draw the state transition diagram and indicate the actions or occurrence that causes each transition.

• Problem 3.7 The VMS scheme discussed in the preceding problem is often referred to as a ring protection structure, as illustrated in Figure 3.18. Indeed, the simple kernel/user scheme, as described in Section 3.3, is a two-ring structure. [SILB04] points out a problem with this approach: The main disadvantage of the ring (hierarchical) structure is that it does not allow us to enforce the need-to-know principle. In particular, if an object must be accessible in domain D_j but not accessible in domain D_i, then we must have j < i. But this means that every segment accessible in D_i is also accessible in D_j.
  1. Explain clearly what the problem is that is referred to in the preceding quote.
  2. Success a way that a ring-structured operating system can deal with this problem

• Problem 3.9 In a number of early computers, an interrupt caused the register values to be stored in fixed locations associated with the given interrupt signal. Under what circumstances is this a practical technique? Explain why it is inconvenient in general.

Assignment 2 (due 9/20)

• Problem 4.2 In the discussion of ULTs versus KLTs, it was pointed out that a disadvantage of ULTs is that when a ULT executes a system call, not only is that thread blocked, but also all of the threads within the process are blocked. Why is that so?

• Problem 4.4 Consider an environment in which there is a one-to-one mapping between user-level threads and kernel-level threads that allows one or more threads within a process to issue blocking system calls while other threads continue to run. Explain why this model can make multithreaded programs run faster than single-threaded counterparts on a uniprocessor machine.

• Problem 4.7 A multiprocessor with eight processors has 20 attached tape drives. There are a large number of jobs submitted to the system that each require a maximum of four tape drives to complete execution. Assume that each job starts running with only three tape drives for a long period before requiring the fourth tape drive for a short period toward the end of its operation. Also assume an endless supply of such jobs.
1. Assume the scheduler in the OS will not start a job unless there are four tape drives available. When a job is started, four drives are assigned immediately and are not released until the job finishes. What is the maximum number of jobs that can be in progress at once? What are the maximum and minimum number of tape drives that may be left idle as a result of this policy?
2. Suggest an alternative policy to improve tape drive utilization and at the same time avoid system deadlock. What is the maximum number of jobs that can be in progress at once? What are the bounds on the number of idling tape drives?
   
• Problem 4.8 In the description of Solaris ULT states, it was stated that a ULT may yield to another thread of the same priority. Isn't is possible that there will be a runnable thread of higher priority and that therefore the yield function should result in yielding to a thread of the same or higher priority?

Assignment 3 (due 9/29)

• Problem 5.2 Consider a concurrent program with two processes, p and q, defined as follows. A, B, C, D, and E are arbitrary atomic (indivisible) statements. Assume that the main program (not shown) does a parbegin of the two processs.

  void p() {    A;    B;    C; }

  void q() {    D;    E; }

  Show all the possible interleavings of the execution of the preceeding two processes (show this by giving execution "traces" in terms of the atomic statements).

• Problem 5.6 Another software approach to mutual exclusion is Lamport's bakery algorithm, so called because it is based on the practice in bakeries and other shops in which every customer receives a numbered ticket on arrival, allowing each to be served in turn. The algorithm is as follows:

  boolean choosing[n];
  int number[n];
  while (true)
  {
       choosing[i] = true;
       number[i] = 1 = getmax( number[], n );
       choosing[i] = false;
       for (int j=0; j < n; j++ )
       {
            while (choosing[j])
            { };
            while ((number[j]!=0) &&(number[j],j)<(number[i],i))
            { };
       }
       /* critical section*/;
       number[i] = 0;
       /* remainder */;
  }
  

  The arrays choosing and number are initialized to false and 0 respectively. The ith element of each array may be read and written by process i but only read by other processes. The notation (a,b) < (c,d) is defined as (a < c) or (a = c and b < d)
  • Describe the algorithm in words
  • Show that this algorithm avoids deadlock
  • Show that it enforces mutual exclusion

• Problem 5.11 The following problem was once used on an exam:
  Jurassic Park consists of a dinosaur museum and a park for safari riding. There are m passengers and n single-passenger cars. Passengers wander around the museum for a while, then line up to take a ride in a safari car. When a car is available, it loads the one passenger it can hold and rides around the park for a random amount of time. If the n cars are all out riding passengers around, then a passenger who wants to ride waits; if a car is ready to load but there are no waiting passengers, then the car waits. Use semaphores to synchronize the m passenger processes and the n car processes.
  The following skeleton code was found on a scrap of paper on the floor of the exam room. Grade it for correctness. Ignore syntax and missing variable declarations. Remember that P and V correspond to semWait and semSignal.

  resource Jurassic_Park()
    sem car_avail:=0, car_taken:=0, car_filled:=0, passenger_released:=0
    process passenger(i:=1 to num_passengers )
      do true -> nap( int(1000*wander_time)))
        P(car_avail); V(car_taken); P(car_filled)
        P(passenger_released)
      od
    end passenger
    process car(j:=1 to num_cars)
      do true -> V(car_avail); P(car_taken); V(car_filled)
        nap( int(1000*ride_time)))
        V(passenger_released)
      od
    end car
  end Jurassic_Park
  

• Problem 5.13 Consider the solution to the infinite-buffer producer/consumer problem defined in Figure 5.10. Suppose we have the (common) case in which the producer and consumer are running at roughly the same speed. The scenario could be: Producer: append; semSignal; produce; ... append; semSignal; produce; ...
  Consumer: consume; ...; take; semWait; consume, ...; take; semWait; ...
  The producer always manager to append a new element to the buffer and signal during the consumption of the previous element by the consumer. The producer is always appending to an empty buffer and the consumer is always taking the sole item in the buffer. Although the consumer never blocks on a semaphore, a large number of calls to the semaphore mechanism is made, creating considerable overhead.

  Construct a new program that will be more efficient under these circumstances. Hints: Allow n to have the value -1, which is to mean that not only is the buffer empty but that the consumer has detected this fact and is going to block until the producer supplies fresh data. The solution does not require the use of the local variable m found in Figure 5.10.

• Problem 5.17 Show that message passing and semaphores have equivalent functionality by:
  • Implementing message-passing using semaphores. Hint: Make use of a shared buffer area to hold mailboxes, each one consisting of an array of message slots.
  • Implementing a semaphore using message-passing. Hint: Introduce a separate synchronization process.

Assignment 4 (due 10/20)

• Problem 7.6 The dynamic partitioning scheme is being used, and the following is the memory configuration at a given point in time:

  

  The shaded areas are allocated blocks; the white areas are free blocks. The next three memory requests are for 40M, 20M, and 10M. Indicate the starting address for each of the three blocks using the following placement algorithms:

  • First-Fit
  • Best-Fit
  • Next-Fit. Assume the most recently added block is at the beginning of memory
  • Worst-Fit

• Problem 7.12 Consider a simple paging system with the following parameters: 2³² bytes of physical memory; page size of 2¹⁰ bytes; 2¹⁶ bytes of logical address space.
  • How many bits are in a logical address?
  • How many bytes in a frame?
  • How many bits in the physical address specify the frame?
  • How many entries in the page table?
  • How many bits in each page table entry? Assume each page table entry includes a valid/invalid bit.

• Problem 7.14 Consider a simple segmentation system that has the following segment table:

  Starting Address	Length (bytes)
  660	248
  1752	422
  222	198
  996	604

  For each of the following logical addresses, determine the physical address or indicate if a segment fault occurs:

  • 0, 198
  • 2, 156
  • 1, 530
  • 3, 444
  • 0, 222

• Problem 8.1 Suppose the page table for the process currently executing on the processor looks like the following. All numbers are decimal, everything is numbered starting from zero, and all addresses are memory byte addresses. The page size is 1024 bytes.

  Virtual Page number	Valid bit	Reference bit	Modify bit	Page frame number
  0	1	1	0	4
  1	1	1	1	7
  2	0	0	0	-
  3	1	0	0	2
  4	0	0	0	-
  5	1	0	1	0

  • Describe exactly how, in general, a virtual address generated by the CPU is translated into a physical main memory address
  • What physical address, if any, would each of the following virtual addresses correspond to? (Do not try to handle any page faults, if any).
    • 1052
    • 2221
    • 5499

• Problem 8.6 A process contains eight virtual pages on disk and is assigned a fixed allocation of four page frames in main memory. The following page trace occurs:

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

  • Show the successive pages residing in the four frames using the LRU replacement policy. Compute the hit ratio in main memory. Assume the frames are initially empty.
  • Repeat part (a) for the FIFO replacement policy
  • Compare the two hit ratios and comment on the effectiveness of using FIFO to approximate LRU with respect to this particular trace.
  Note: In computing the hit ratio, ignore the page faults that occur while the system is filling memory.

• Problem 8.15 Consider the following sequence of page references (each element in the sequence represents a page number):
  1 2 3 4 5 2 1 3 3 2 3 4 5 4 5 1 1 3 2 5

  Define the mean working set size after the kth reference as and define the missing page probability after the kth reference as , where F( t, Δ ) = 1 if a page fault occurs at virtual time t and 0 otherwise.

  • Draw a diagram similar to that of Figure 8.19 for the reference sequence just defined for the values Δ = 1, 2, 3, 4, 5, 6.
  • Plot s₂₀(Δ) as a function of Δ.
  • Plot m₂₀(Δ) as a function of Δ.

Assignment 5 (due 10/29)

• Problem 9.3 Prove that, among nonpreemptive scheduling algorithms, SPN provides the minimum average waiting time for a batch of jobs that arrive at the same time. Assume that the scheduler must always execute a task if one is available.

• Problem 9.6 In the bottom example in Figure 9.5, process A runs for 2 time units before control is passed to process B. Another plausible scenario would be that A runs for 3 time units before control is passed to process B. What policy differences in the feedback scheduling algorithm would account for the two different scenarios?

• Problem 9.9 Define residence time T_r as the average total time a process spends waiting and being served. Show that for FIFO, with mean service time T_s we have T_r = T_s / ( 1 = ρ), where ρ is utilization.

• Problem 9.14 Which type of process is generally favored by a multilevel feedback queueing scheduler - a process-bound process or an I/O-bound process? Briefly explain why.

• Problem 9.16 Five batch jobs, A through E, arrive at a computer center at essentially the same time. They have an estimated running time of 15, 9, 3, 6, and 12 minutes, respectively. Their (externally defined) priorities are 6, 3, 7, 9, and 4 respectively, with a lower value corresponding to a higher priority. For each of the following scheduling algorithms, determine the turnaround time for each process and the average turnaround for all jobs. Ignore process switching overhead. Explain how you arrived at your answers. In the last three cases, assume that only one job at a time runs until it finishes and that all jobs are completely processor bound.
  • round robin with a time quantum of 1 minute
  • priority scheduling
  • FCFS (run in order 15, 9, 3, 6, and 12)
  • shortest job first

Assignment 6 (due 11/10)

Create a program that will allow the user to input the execution time and period for up to ten periodic real-time tasks. Then your program should determine if they can be successfully scheduled using Rate Monotonic Scheduling. Note since we are starting all tasks at time 0, you need only check until every task has finished its first period. You should output a message indicating that the tasks can be scheduled successfully, or the first task that fails to meet its deadline.

Note: Rate Monotonic Scheduling is a preemptive algorithm!

Example 1 (successful)   P1 P2 P3 Ci (time) 20 40 100 Ti (rate) 100 150 350		Example 2 (successful)   P1 P2 P3 P4 Ci (time) 5 20 20 40 Ti (rate) 25 50 100 200
Example 3 (P4 misses its first deadline)   P1 P2 P3 P4 Ci (time) 10 30 35 55 Ti (rate) 60 120 140 200		Example 4 (P4 misses its first deadline)   P1 P2 P3 P4 Ci (time) 18 24 80 70 Ti (rate) 100 150 250 300
Example 5 (successful)   P1 P2 P3 P4 P5 P6 Ci (time) 10 18 22 25 35 50 Ti (rate) 100 120 150 200 250 300		Example 6 (P6 misses its first deadline)   P1 P2 P3 P4 P5 P6 Ci (time) 273 310 348 389 435 491 Ti (rate) 2245 2518 2828 3176 3565 4000
Example 7 (successful)   P1 P2 P3 P4 P5 P6 Ci (time) 20 40 50 60 45 40 Ti (rate) 100 150 350 400 450 800		Example 8 (P5 misses its first deadline)   P1 P2 P3 P4 P5 P6 Ci (time) 20 40 50 70 45 20 Ti (rate) 100 150 350 400 450 800

Assignment 7 (due 12/8)

• Problem 13.5 The previous version of the TFTP specification, RFC 783, included the following statement:
  All packets other than those used for termination are acknowledged individually unless a timeout occurs.

  The new specification revises this to say

  All packets other than duplicate ACKs and those used for termination are acknowledged individually unless a timeout occurs.

  The change was made to fix a problem referred to as the "Sorcerer's Apprentice." Deduce and explain the problem.

• Problem 14.1 Let α be the percentage of program code that can be executed simultaneously by n computers in a cluster, each computer using a different set of parameters or initial conditions. Assume that the remaining code must be executed sequentially by a single processor. Each processor has an execution rate of x MIPS.
  1. Derive an expression for the effective MIPS rate when using the system for exclusive execution of this program, in terms of n, α, and x.
  2. If n = 16 and x = 4 MIPS, determine the value of α that will yield a system performance of 40 MIPS.

• Problem 15.2 For Figure 15.9, it is claimed that all four processes assign an ordering of { a, q } to the two messages, even though q arrives before a at P₃. Work through the algorithm to demonstrate the truth of the claim.

• Problem 15.6 For the token-passing mutual exclusion algorithm, prove that it
  1. guarantees mutual exclusion
  2. avoids deadlock
  3. is fair

• Problem 16.1 Assume that passwords are selected from four-character combinations of 26 alphabetic characters. Assume that an adversary is ale to attempt passwords at a rate of one per second.
  1. Assuming no feedback to the adversary until each attempt has been completed, what is the expected time to discover the correct password?
  2. Assuming feedback to the adversary flagging an error as each incorrect character is entered, what is the expected time to discover the correct password?

• Problem 16.10 The necessity of the "no read up" rule for a multilevel secure system is fairly obvious. What is the importance of the "no write down" rule?