Midterm Examination #2 COP 4610 - Operating Systems & Concurrent Programming

This is a closed-book examination. You are not allowed to use any notes, other references, or a caculator, during the exam. You are You will have 75 minutes to answer all the questions. Answer on this paper. Write as much of your answer as will fit in the space provided. If your answer does not fit entirely in the space below the question, use the blank paper provided to you to complete your answer. If you believe a question is ambiguous or a multiple-choice question has other than one correct answer, please write a note on the paper, explaining what you think is wrong with the question. The exam will be graded on a scale where 100 pts earns a grade of 'A' (4.0), but it is possible to achieve a score of up to 130. You will probably find some questions are easier for you than others. Therefore, it is important to budget your time. Do not miss the chance to answer some easier questions later in the exam by puzzling too long over one of the earlier questions. Remember to write your name on the exam, and on every page if you remove the staple. On short answer questions that require computation or reasoning, you may receive some credit for an incorrect answer if you show your intermediate results and they are partially correct.

The median score as 89.5 and the average was 86.75. The maximum achieved was 117 and the minimum was 31. The standard deviation was 18.36.

I. True/False: 20 questions, at one point each.

Answer each question by marking a "T" or "F" inside the parentheses on the left side of the statement.

  1. ( F ) External fragmentation may occur with the fixed partitioning model of process memory management.
  2. ( F ) Internal fragmentation may occur with the simple segmentation model of process memory management.
  3. ( T ) Memory compaction takes time proportional to the size of the memory.
  4. ( F ) Memory compaction is done whenever a region of memory is allocated.
  5. ( T ) Memory compaction requires that the hardware support dynamic relocation.
  6. ( T ) Paging provides a mechanism for dynamic relocation.
  7. ( F ) The buddy system eliminates the need for a list of free storage blocks.
  8. ( F ) With the buddy system there is no need to store the size of a block in the block header, because the size of the block can be computed from the block's address.
  9. ( F ) Most systems lock all page tables into main memory.
  10. ( T ) When the working set of a process grows the page fault frequency will go up.

    The objective of the question was to test your knowledge of the principle behind the Page Fault Frequency (PFF) algorithm for managing the resident set size, which uses a sustained increase in the page fault frequency as an indicator that the resident set needs to grow. However, the PFF is a page replacement scheme with local scope. During the in-class review of this question, some students expressed the belief that the page fault frequency need not go up when the working set grows, so long as the page replacement scheme has variable allocation and global scope, and the system has plenty of free page frames. That is at least partly true, if you assume variable allocation and global scope, and the question would have been less ambiguous if it had specified local scope. However, any change in the size of the working set size is likely to be accompanied by a change in the working set membership. If the page replacement scheme is successful, the OS will eventually swap pages to match changes in the working set with changes in the resident set, but the OS is not prescient, so there will be a bit of a lag. During the lag, the page fault rate will go up temporarily. Therefore, I believe the best answer to the question is still "T".

  11. ( F ) Thrashing is unlikely to occur so long as the mean time between page faults does not exceed the mean time required to process a page fault.

    This is reversed. Thrashing is likely to occur if the mean time between page faults is less than or equal to ("does not exceed") the mean time required to process a page fault.

  12. ( T ) One way to avoid thrashing is to adjust the multiprogramming level of the system to keep the utilization of the paging device at 50%.

    The objective of this question was to test your understanding of the principle behind the "50% criterion", which Stallings says "attempts to keep utilization of the paging device at approximately 50%". The question would have been better if it had said "at or below" 50%.

    .
  13. ( F ) Load control is concerned with determining which page to load next into memory when there is a page fault.
  14. ( F ) The multiprogramming level of a system is the number of CPUs in the system.
  15. ( T ) In Unix, the sbrk() system call is used to increase the size of the data segment.

    At least one student had a print-out of an early version of a sample examination question with a typo, showing the answer to this as "F". When I checked the web pages after the exam, the answer showed up as "T". I don't remember for certain, but I guess it was one of those typos that I caught during class and corrected later, but not before some people had printed out copies. For this reason, the question is thrown out of the exam.

  16. ( F ) Given an interactive SMP system with assuming round robin (RR) scheduling, the average response time will be shorter if we assign each user to a unique CPU at login time (one ready queue per processor) than if we allow the processes of all users to compete dynamically for the processors (shared ready queue).
  17. ( F ) The difference in average throughput between RR and FCFS scheduling policies becomes greater as the number of processors goes up.
  18. ( F ) In a real-time system, the operating system may (is likely to) sacrifice scheduling predictability in order to achieve higher average throughput.
  19. ( T ) In a real-time system, fairness in processor scheduling is considered less important than satisfying the timing constraints of processes.
  20. ( ) Demand paging is a placement policy.

II. Multiple choice: 20 questions, at two points each.

Answer each question by marking an "X" over the dot to the left of the best answer.

  1. Shifting the contents of the regions of memory allocated to processes, so that all the free memory forms one contiguous region is called
  2. With an absolute loader, the time at which the absolute address of the entry point of a subprogram is bound is
  3. Combining of multiple object modules into a load module is done by a
  4. With the Buddy System, the address of the buddy of the block of size 256 bytes with byte address 0111001011011100 would be
  5. Which of the following is not true of paging?
  6. An algorithm that chooses which of the free regions of memory should be allocated to satisfy a given request is called a
  7. In a multiprogramming system with dynamic partitioning, the algorithm that chooses which process to swap out of main memory to make room for a new process is called a
  8. Which of the following functions is not served by a base register and a bounds register?
  9. Which of the following is true of the Buddy System?
  10. Which of the following is true of the first-fit algorithm, as applied to the allocation of memory to processes in a non-virtual memory OS with dynamic partitioning?
  11. Which if the following is not one of the motivations for implementing virtual memory?
  12. Which of the following is not one of the advantages of segmentation?
  13. Given a fixed number of TLB entries, using a larger page size has the effect of

    The TLB has nothing to do with page faults. Using a larger page size will mean the TLB covers a wider range of virtual addresses, decreaseing the TLB miss rate.

  14. If it were necessary to have a page table entry for every page of virtual memory, multi-level page tables would take more memory than single-level page tables. Why is this not a problem?

    Note that paging the page table (putting it on secondary storage) does not solve the problem with single-level page tables and large virtual address spaces. For example, with a 64-bit address and 4Kbyte pages, one would need at least 253 bytes to hold a complete page table. There is no disk drive made that would hold that much.

  15. The function implemented by the TLB is called
  16. What is the reason for having multi-level page tables?

    There was a similar quiz question where the answer was to reduce the amount of real memory occupied by page tables. The answer here is also correct, and better. Using multi-level page tables primarily reduces the need for large contiguous ranges of virtual memory to hold page tables. Generally that also will mean the page table occupies more real memory. However, one might quibble that since the page table itself can be paged, only the portion that is used needs to be kept in real memory, and so using multi-level page tables may not reduced real memory usage.

  17. Which of the following takes the least amount of time to handle?
  18. Which of the following signals is generated by Unix when a process attempts to reference an operand in memory at a virtual address that is not aligned properly for the size of the operand?
  19. Which of the following signals is generated by Unix when a process attempts to reference an operand in memory at a virtual address that is not mapped?
  20. The term "aging" is sometimes used for the policy of promoting a process to a higher-priority queue (in a feedback queue scheduling scheme) after it spends a certain amount of time waiting for service in its current queue. The purpose of this policy is to

III. Short answer: 20 questions, at two points each.

Answer each question by writing in one word in each blank space.

  1. Given a paged memory system with page size 2048, the page number of logical address 4100 is page number = 2052 % 2048 = 2. (Assume pages and page frames are numbered starting from zero, in this and all other questions.)
  2. Given a paged memory system with page size 2048, if logical address 4100 maps to page frame 1 the physical address would be offset = 4100 % 2048 = 4, physical address = 1 * 2048 + 4 = 2052.
  3. For a machine with 32-bit logical addresses and 4096-byte pages, the size of the offset part of a logical address is 4096 = 212, so offset is 12 bits bits.
  4. In a paged memory system with 32-bit logical addresses, page size of 2048 bytes, and page table entry size of two bytes, if single-level paging were used, a page table for the entire virtual address space of a process would occupy 2048 = 211, so offset is 11 bits, and we need 232 / 211 = 221 page table entries, at two bytes each, so the total space for the page table is 222 bytes.
  5. A(n) inverted page table is a form of hashing scheme in which the hash table entries point to descriptors each containing a triple (page #, frame #, link to next item in the hash chain).
  6. The condition where the system spends most of its time swapping data between main memory and secondary storage, to the extent that most of the CPU time is wasted waiting for the swapping device, is called thrashing.
  7. The expectation that a program will access again in the future memory locations that have been accessed recently in the past is called temporal locality.
  8. The expectation that a program will access in the future memory locations close to the locations that it accessed recently in the past is called spatial locality.
  9. The abbreviation TLB stands for translation lookaside buffer.
  10. Consider the page table below, where numbers are in decimal and everything is numbered starting from zero, all addresses are memory byte addresses, and the page size is 1024 bytes.
    virtual page numbervalid bitpage frame number
    015
    10-
    214
    311
    40-
    50-
    613
    712
    Which physical address, if any, would the virtual address 2066 correspond to? (If a page fault would occur, just write "page fault".) page is 2066 / 1024 = 2, offset = 2066 % 1024 = 18, page frame is 4, physical address is 4096 + 18 = 4114
  11. Consider the same page table as above. Which physical address, if any, would the virtual address 3100 correspond to? (If a page fault would occur, just write "page fault".) page is 3100 / 1024 = 3, offset is 3100 % 1024 = 28, page frame is 1, physical address is 1024 + 28 = 1052
  12. Consider the same page table as above. Which physical address, if any, would the virtual address 4097 correspond to? (If a page fault would occur, just write "page fault".) page is 4097 / 1024 = 4, which is not valid, so there is a page fault
  13. Consider the page frame table below, where numbers are in decimal and everything is numbered starting from zero.
    page frame numbervirtual page numbertime loadedtime referencedR bitM bit
    06 5022010
    1210010001
    23 9013000
    3021021011
    Suppose a page fault to virtual page 4 has occurred. Which page frame will have its contents replaced if the FIFO algorithm is used?
    frame 0 has the earliest time loaded
  14. In the same situation as for the question above, which page frame will have its contents replaced if the LRU algorithm is used?
    frame 1 has the earliest time referenced
  15. In the same situation as for the question above, which page frame will have its contents replaced if the version of the Clock algorithm that uses only the (R) bit is used?
    the scan visits frames 3, 0, 1, and finds frame 1 has R = 0
  16. In the same situation as for the question above, which page frame will have its contents replaced if the version of the Clock algorithm that uses both the use (R) and modify (M) bits is used?
    the scan visits frames 3, 0, 1, and 2, and finds frame 2 has (R, M) = (0, 0)
  17. In the same situation as for the question above, and assuming the page reference string 4, 6, 3, 3, 4, 4, 2, 5, 0, 5, 2, which page frame will have its contents replaced by the optimal algorithm?
    the last referenced page among those in memory is 0, which is in frame 3
  18. The set of pages a process has referenced in the last t virtual time units is called the
    working set with parameter t.
  19. The set of pages a process has in main memory is called the resident set of the process.
  20. The preemptive scheduling algorithm that minimizes average response time is
    shortest remaining process. Also acceptable were synonyms, such as "shortest remaining processing time first". Not correct, but allowed to slide, were "shortest process next", "shortest processing time first", etc. The latter are described in your text as nonpreemptive policies, but some references also use those names for preemptive policies. A wrong answer would be "shortest response time", since you don't know the response time until you have scheduled the job.

IV. Other questions -- 6 questions, at five points each.

  1. Consider the following program. 
    #include <stdio.h>
int main (int argc, const char *argv[]) {
  char a[5 * sizeof(int)] = {1, 2, 3, 4, 5};
  printf ("%d %d %d %d %d\n",
	   (int) a, *a, (int)(a + 4), *(a + 4), *((int *) ((char *) a + 4)));
  return 0;
}
    Describe the five output values. If a value consists of a small integer, give the exact integer value. If the value consists of a memory address you are not expected to give the exact address; just describe it in words. If the value is garbage, just state that it is garbage. If the expression would cause a segmentation fault or other exception, just say so.
    1. (int) a address of a[0]
    2. *a 1
    3. (int)(a + 4) address of a[4]
    4. *(a + 4) 5
    5. *((int *)((char *) a + 4)) "garbage", or 5 on a 32-bit LSB-first machine

    The objective of this question was to test whether you understand the relationship between arrays and pointers and between characters and integers, and the effects of pointer type conversions.

    The value for part (e) is fairly predicable. The actual output from this program on linprog is: 

    -1073743280 1 -1073743276 5 5
    The last value 5 happens because the four bytes stored starting at a[4] are 5, 0, 0, and 0, and the program was run on an Intel Pentium machine, which stores integers in a format with the least significant bit first. On a 32-bit machine that stores the most significant bit first, the value would be 0x05000000.

  2. Explain why the LRU page replacement algorithm is not used in practice.

    The overhead of keeping track of the last reference time for each page frame is too high. To keep it in memory, we would first need to solve the problem of "recursion" for the page reference that writes the timestamp into memory. If that is solved, we still have doubled the number of memory cycles, unless we have special hardware support in the MMU. If the MMU could keep the reference time along with the other information in the TLB, we would only need to write the timestamp to memory when there is a TLB fault, but that is still very costly, since it about doubles the size of the memory and logic needed in the TLB (timestamps are as big as adddresses), and still requires a double memory reference for every TLB miss.

  3. Little's Law states that N = lambda * W, where N is the average number of jobs in the system, lambda is the average arrival rate of jobs, and W is the average time a job spends in the system. Apply Little's Law to solve the following problem, showing the steps by which you arrive at the answer.

    Suppose that, during the morning rush hour, an average of 100 vehicles back up waiting to get through the traffic light at Thomasville Road and 7th Avenue, the traffic light cycle takes 5 minutes, and each cycle allows and average of 20 vehicles to pass through. What is the average number of minutes a vehicle spends waiting?

    N = 100 vehicles; lambda = 20 vehicles / 50 minutes; W = N / lambda = 100 vehicles / (20 vehicles / 5 minutes) = 100 / 4 = 25 minutes.

  4. Draw the shape of the curve you will get if you plot the average response time of a job against the average processor utilization, for an M/M/1 queueing system with average response time 10 milliseconds. Plot the processor utilization on the X axis and the response time in milliseconds on the Y axis. Obviously, you are not expected to provide an exact plot, but you are expected to be able to show the exact response time for a utilization of zero (1 pt), the behavior of the curve for utilization 1 (1 pt), and the general shape of the curve (3 pt).

    The critical features in the figure are:

    • The curve starts low on the left, at some nonzero value less than 10. The average response time at utilization zero should be equal to the average service time, which must be less than 10 and greater than zero.
    • The curve is asymptotic to a vertical line at utilization 1, since as the utilizaiton approaches 1 the queue length grows without bound.
    • The curve starts out nearly flat and then bends upward.

  5. Consider the following execution profile of a set of periodic real time tasks:
    taskworst-case execution time (ms)period (ms)
    A20100
    B30120
    C100200
    1. What is the total CPU utilization? (1pt) 95% = 20/100 + 30/120 + 100/200 = 20% + 25% + 50% (2 significant digits is close enough)
    2. Show the schedule that would be produced by Rate Monotonic Scheduling (RMS), assuming all the tasks are initially released at the same time, by marking in the letter of the task that is executing for each of the 10 ms boxes in the Gantt chart below. (2 pt)
      0100200
      AABBBCCCCC AABBBCCCCC AACCBBBCCC

      The most frequent errors here were: (1) not recognizing that the tasks are periodic; (2) not computing the release times correctly, especially for task B.
    3. Show the schedule that would be produced by Earliest Deadline First Scheduling (EDF), under the same assumptions. In addition, assume that the deadline for completion of each task is the next arrival time of the same task. (2 pt)
      4. 0100200
      AABBBCCCCC CCCCCAABBB AACCBBBCCC

      There are some acceptable variations on the correct answer for this part, depending on how you treated jobs with equal deadlines. My solution assumes service order among jobs with equal deadliens is FIFO, and ties among jobs with equal arrival time and deadline are broken by alphabetical order.
  6. Suppose a region of 30 words (Yes, that is ridiculously small, but this is just an exam question.) of storage is managed using boundary tags and an implicit free list, where memory is allocated only in whole blocks, and a boundary tag is represented by an integer whose absolute value gives the block size and whose sign indicates whether the block is free. Show the values of the boundary tags at each of the following points in the execution of the system, assuming the operations in the five parts are performed in order, with no other operations intervening. Assume a first-fit placement algorithm is applied and that coalescing of adjacent free regions is always performed at the earliest possible moment. For parts (b) through 3), you only need to show the values that are different from the preceding part.

    There are four acceptable answers for this question, depending on whether you:

    • used negative sizes for allocated blocks, or for deallocated blocks
    • recorded the user size (excluding tags), or the total size (including tags)

    Common errors included:

    • not including the right tags
    • not allocating enough space to hold the tags without reducing the user space
    • nesting blocks (multiple levels of tags)
    • allocating when the question said to free, or vice versa/li>
    1. Initially, when the entire region is free.
      28                                                           28
    2. After blocks of size 3, 5, 4, and 6 (the sizes of the user space) have been allocated, in that order.
      -3       -3-5            -5-4        -4-6              -62    2
    3. After the block of size 4 has been freed.
                               4        4                         
    4. After the block of size 5 has been freed.
                11                       11                         
    5. After a block of size 6 has been allocated.
                -6             -63      3                         
T. P. Baker