19 November 1998
Answer all questions.
Time: 1 hour 50 minutes
1. (a) What is the critical-section problem? (b) List three overall strategies in handling deadlocks. (c) What are overlays? (d) What is thrashing? (e) List operations to be performed on directories. (f) List three ways of allocating storage, and give advantages of each.
(a) [3 points] To design an algorithm that allows at most one process into the critical section at a time, without deadlock.
(b) [3 points]
i. Ensure system will never enter a deadlock state.
ii. Allow deadlocks, but devise schemes to recover from them.
iii. Pretend deadlocks don't happen.
(c) [3 points] Segments or sets of routines, A, which are loaded into the same area of memory as other routines, B; A and B are not in memory concurrently, but one erases the other when loaded in.
(d) [3 points] State where the system spends an excessive amount of time on paging, compared to the execution of processes.
(e) [3 points] Search for a file, create a file, delete a file, list a directory, rename a file, traverse the file system.
(f) [6 points]
i. Contiguous allocation. Fastest, if no changes are to be made. Also
easiest for random access files.
ii. Linked allocation. No external fragmentation. File can grow without
complications.
iii. Indexed allocation. Supports direct access without external fragmentation.
2. Suppose processes P0 and P1 share variable V2, processes P1 and P2 share variable V0, and processes P2 and P3 share variable V1. Show how the processes can use semaphores to coordinate access to V0, V1, and V2 so that the critical section problem does not occur.
[6 points]
semaphore s0 = s1 = s2 = 1;
P0 {
...
wait(s2);
access V2
signal(s2);
...
}
P1 {
...
wait(s2);
access V2;
signal(s2);
...
wait(s0);
access V0;
signal(s0);
...
wait(s2);
wait(s0);
access V2;
access V0;
signal(s2);
signal(s0);
}
P2 {
...
wait(s0);
access V0;
signal(s0);
...
wait(s1);
access V1;
signal(s1);
...
wait(s0);
wait(s1);
access V0;
access V1;
signal(s1);
signal(s0);
}
P3 {
...
wait(s1);
access V1;
signal(s1);
...
}
3.(a) Explain what the hardware instruction "swap" does, and
(b) show how it can be used to implement binary semaphores.
(a) [3 points] It indivisibly swaps the contents of two boolean variables, as follows (Fig. 6.8).
procedure Swap (var a, b:boolean); var temp: boolean; begin temp := a; a := b; b := temp; end;(b) [3 points] The following uses Swap() to implement semaphores (Fig. 6.9).
repeat // wait: key := true; repeat Swap(lock, key); until key = false; critical section; // signal: lock := false; remainder section until false;4.Construct a monitor that implements semaphores. This will demonstrate that a monitor can be used any place a semaphore can be used.
[6 points]
monitor semaphore {
private:
int count = 1;
condition hold;
public:
wait() { count--; if (count < 0) hold.wait; };
signal() { count++; hold.signal; };
}
5.[7.2] Is it possible to have a deadlock involving only one
single process? Explain your answer.
[6 points] No. Because a process cannot simultaneously hold and wait for a resource.
6.[7.13] Consider the following snapshot of a system:
Allocation Max Available A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6Answer the following questions using the banker's algorithm. (a) What is the content of the Need matrix? (b) Is the system in a safe state? Explain your answer. (c) If a request from P1 arrives for (0 4 2 0), can the request be granted immediately? Explain your answer.
(a) [4 points] Need = Max - Allocation. Hence:
A B C D P0 0 0 0 0 P1 0 7 5 0 P2 1 0 0 2 P3 0 0 2 0 P4 0 6 4 2(b) [2 points] Yes. [2 points] The sequence P0,P2,P1,P3,P4 satisfies the safety requirement.
(c) [1 point] Yes, [2 points] since (0,4,2,0) <= Available = (1,5,2,0) and (0,4,2,0) <= Max[1] = (1,7,5,0), and [1 points] the new state after the allocation is a safe state:
Allocation Max Need Available A B C D A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 0 0 0 0 1 1 0 0 P1 1 4 2 0 1 7 5 0 0 3 3 0 P2 1 3 5 4 2 3 5 6 1 0 0 2 P3 0 6 3 2 0 6 5 2 0 0 2 0 P4 0 0 1 4 0 6 5 6 0 6 4 2The sequence P0,P2,P1,P3,P4 satisfies the safety requirement.
7.[8.2] Explain the difference between internal and external fragmentation.
[3 points] Internal fragmentation is the area in a region or a page that is not used by the job occupying the region or page. This space is unavailable for use by the system until that job is finished and the page or region is released. [3 points] External fragmentation refers to unused areas between regions or pages allocated to different programs or the same program, which turn out to be too small for subsequent allocations.
8.Suppose a system has a disk with 2 KB disk blocks and the average access time on a block is 20 milliseconds. A process holding 40 KB of memory transitions from running to blocked state due to an I/O request. How long must the process remain blocked to justify swapping out the process? Explain your answer.
[6 points] A 40 KB image requires 40/2 = 20 disk writes to save the image and another 20 disk reads to restore it. Since the average access time is 20 ms, it would take 20 ms x 20 operations = 400 ms to swap the process out once the OS decided to swap it. The process would incur another 400 ms of delay while it is being swapped back in later. Hence, if the process became ready in less than 400 ms + 400 ms = 800 ms after it became blocked, then the process should not have been swapped out.
9.[9.3] A certain computer provides its users with a virtual-memory space of 232 bytes. The computer has 218 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4096 bytes. A user process generates the virtual address 11123456. Explain how the system establishes the corresponding physical location. (Distinguish between software and hardware operations.)
The virtual address in binary form is
0001 0001 0001 0010 0011 0100 0101 0110Since the [2 points] page size is 212, the [2 points] page table size is 220. Therefore [2 points] the low-order 12 bits, 0100 0101 0110, are used as the displacement into the page, while the remaining 20 bits, 0001 0001 0001 0010 0011, are used as the displacement in the page table (a hardware operation). There are 26 pages in physical memory. If the page pointed to by the page table entry thus located is not one of these physical pages, then a page fault occurs, resulting in swapping in the needed page. Most of the actions during paging would be directed by the OS. Once the page is in place, the suspended instruction is restarted.
10. Given an allocation of 3 frames and the following page reference string
0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6(a) how many page faults will the above reference string incur under the optimal algorithm, assuming that the primary memory is initially empty? (b) Same as (b) but using the LRU algorithm. (c) Same as (a) but using the working-set algorithm with a window size of 6. (d) What is the working-set size after the entire string has been processed?
(a) [3 points] The optimal algorithm is to replace the page that will not be used for the longest period of time. 9 faults.
Frame 0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6 --------------------------------------------------------------------- 0 0* 0 0 0 0 0 0 0 1* 1 2* 2 7* 7 0* 0 0 0 0 0 0 1 3* 3 3 3 5* 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 4* 4 4 4 6* 6 6 6 6 6 6 6 6 6 6 6 6 6(b) [3 points] 13 faults.
0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6 ------------------------------------------------------------- 0* 0 0 0 0 0 0 0 0 5* 5 5 7* 7 7 7 7 6* 6 6 6 3* 3 3 3 5* 5 5 1* 1 1 6* 6 6 0* 0 0 0 0 0 0 4* 4 4 4 6* 6 6 2* 2 2 5* 5 5 5 5 5 5 5(c) [3 points] 9 faults.
0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6 ------------------------------------------------------------- 0* 0 0 0 0 0 0 0 0 0 0 0 7* 7 7 7 7 7 3* 3 3 3 3 3 6* 6 6 6 6 6 6 6 6 6 6 6 6 6 4* 4 4 4 4 4 2* 2 2 2 2 2 5* 5 5 5 5 5 5 5 5 5 5 5 5 5 1* 1 1 1 1 1 0* 0 0 0 0 0 0 ------------------------------------------------------------- 1 2 2 3 3 4 4 4 5 4 5 4 5 5 5 5 4 4 3 2 2(d) [1 point] 2 pages.
Note that for (c) above, if there are only three frames in the memory, then we have a situation where we have to combine working sets with the optimal page replacement algorithm, which is a rare practice. The scenario becomes the following, with 9 faults.
0 3 0 4 0 5 0 6 1 5 2 6 7 5 0 0 0 6 6 6 6 ------------------------------------------------------------- 0* 0 0 0 0 0 0 0 1* 1 2* 2 7* 7 0* 0 0 0 0 0 0 3* 3 3 3 5* 5 5 5 5 5 5 5 5 5 5 5 5 5 4* 4 4 4 6* 6 6 6 6 6 6 6 6 6 6 6 6 6 ------------------------------------------------------------- 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 211.[11.6] Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions: (a) How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.) (b) If we are currently at logical block 10 and want to access logical block 4, how many physical blocks must be read from the disk?
Contiguous: Divide the logical address by 512 with X and Y being the resulting quotient and remainder respectively. (a) [2 points] Add X to Z to obtain the physical block number, where Z is the starting block address of the file on disk. Y is the displacement into the block. (b) [1 point] 1.
Linked: Divide the logical address by 511 with X and Y being the resulting quotient and remainder respectively (assume 1 byte is used for the pointer to the next logical block). (a) [2 points] Chase down the linked list from the first block, getting X + 1 blocks. Y is the displacement into the last physical block. (b) [1 point] 4.
Indexed: Divide the logical address by 512 with X and Y being the resulting quotient and remainder respectively. (a) [2 points] Get the index block into memory. Physical block address is contained in the index block at location X. Y is the displacement into the desired physical block. (b) [1 point] 2.
12.Suppose a UNIX disk block will hold 2048 disk addresses. (a) What is the maximum-sized file using only the direct pointers? (b) Single-indirection capability? (c) Double-indirection capability?
Assume that the block size is 4K and an i-node has 12 direct pointers. With 2048 (2K) addresses per block, we have: (a) [3 points] direct: 12 blocks x 4 KB/block = 48 KB (b) [3 points] single-indirection: 48 KB + 2 K x 4 KB = 48 KB + 8 KB (c) [3 points] double-indirection: 48 KB + 8 MB + 2K x (2K x 4KB) = 48 KB + 8 MB + 16 GB.
13.[Bonus] What is the most dangerous single UNIX command line one could issue?
[Maximum 5 points]
rm -rf /
