12/10/2020 OS practice final exam answers
OS practice final exam answers
These answers are quite brief. I would expect at least some of your answers to be somewhat longer.
Question 1
Copyright By PowCoder代写 加微信 powcoder
The time required for the heads to get to the correct cylinder.
Since we went from 51 to 50, we are going down. For circular scan we only access data in one direction. So we go to 20, then to the top and start accessing going down again. This gives 20, 250, 220, 190, 60.
For SSTF the closest to 50 is 60, then 20 is closest to 60, etc. This gives 60, 20, 190, 220, 250.
Only one bus transaction per block. CPU available during transfer.
Reading last block.
DOS: Traverse the linked list (FAT), which requires 2048 accesses. Read the block. Unix: Read i-node, double indirect block, indirect block, and block.
Adding block to the front.
DOS: Write block. Set a few pointers (linked list insertion) in the FAT.
Unix: Write block. Rewrite all the pointers to blocks (not the blocks themselves). This requires reading and writing the inode, the single indirect block pointed to by the inode, the double indirect block, and all existing single indirect blocks pointed to by the double indirect block.
The answer given for 1D was brief. Here is a longer version as
requested by a student.
Assume the inode contains pointers to D direct blocks, D small.
To be specific let’s assume D=10.
The single indirect block is size 512 Bytes and pointers are
4 Bytes. So the single indirect block contains pointers to 512/4=128
direct blocks. Similarly the double indirect blocks contains pointers
to (up to) 128 single indirect blocks (each of which contains
pointers to (up to) 128 direct blocks).
We want to read block 2048. We need block 2048-10=2038 *after*
the 10 direct blocks pointed to from the inode. The single indirect
gives 128 blocks so we need block 2038-128=1910.
1910/128 = 14 with a remainder of 118.
So the first 10 blocks come from the inode.
file:///home/gottlieb/courses/os202/exams/final/practice/practice-final-ans.html 1/4
12/10/2020 OS practice final exam answers
The next 128 blocks come from the single indirect.
The next 128*14 come from the first 14 singles pointed to by the double.
The last 118 come from the 15th single pointed to by the double.
So to read the last block we
* Read the double pointed to by the inode
* Read the 15th single pointed to by the double
* Read the (118)th block pointed to by the single just read.
To write a block at the front we need to
* Write the block
* Shift all pointers down one
* Have the first pointer in the inode point to the new block
To shift all pointers down one
* Shift down one 128-D pointers in the 15th single pointed to by the double.
* Copy the last pointer in the 14th single to the first pointer in the 15th.
* Shift down one the first 127 pointers in the 14th single
* Copy the last pointer in the 13th to the first pointer in the 14th
* Copy the last pointer in the 1st to the first pointer in the 2nd.
* Shift down one the first 127 pointers in the 1st single
* Copy the Dth pointer from the inode to the first pointer in the 1st single
* Shift down one the first D-1 pointers in the inode
Problem 2 2A
P1 requests 3 R2; granted
P2 requests 3 R1; granted
P1 requests 1 R1
P2 requests 1 R2
file:///home/gottlieb/courses/os202/exams/final/practice/practice-final-ans.html 2/4
12/10/2020 OS practice final exam answers
Assume each process has a claim (not a request) for 3 units of each resource. The Banker defers the request “P2 requests 3 R1”.
The resulting state would not have been safe. There would be no ordering of the processes for which termination could be assured.
It is safer to run X and Y together since they request resources in the same order, which eliminates the circular wait condition needed for deadlock.
Problem 3 3A
Create and Terminate.
PSJF (or SJF)
There are two classes of processes: Producers and Consumers. They share a bounded buffer. Producers produce items and insert them into the buffer. Consumers remove items and consume them. Producers must be blocked from inserting into a full buffer and Consumers must be blocked from removing from an empty buffer.
file:///home/gottlieb/courses/os202/exams/final/practice/practice-final-ans.html 3/4
12/10/2020 OS practice final exam answers
Problem 4 4A
A page is a fixed sized piece of virtual memory. A page frame is a fixed size piece of physical memory. The size of a page frame is the same as the size of a page.
64,000,000 / 4000 = 16000 pages. So there are 16000 PTEs and the
page table is 16000 * 4Bytes = 64,000 bytes.
54321/4000 = 13 and 54321 mod 4000 = 2321; so 13 is the page number and 2321 is the offset.
A memory reference occurs to access PTE#13 (13 words from the beginning of the page table). If the PTE indicates that the page is resident, the PTE also contains the frame number (f#). The second and final memory reference is to memory location 4000f#+2321. These two memory references must occur.
If the page is not resident, and there is a free frame f# available, then (1) an I/O is scheduled to read page 13 into frame f# (2) this process is blocked waiting for the I/O (3) after the I/O completes, PTE13 is updated to indicate that the page is resident in frame f#, and (4) the second required memory reference (4000f#+2321) is made.
If the page is not resident, and there is no free frame, one must be produced. A victim page is chosen and if dirty it is written to disk (again, this involves blocking for I/O). The victim PTE is updated to indicate that the page is not resident. Now we have a free frame and proceed as above.
6 1 2 73 7 216 3
F F F F F H H H F F <--- This line is the answer 6 6 6 61 1 137 2
1 1 12 2 372 1 2 27 3 721 6 73 7 216 3
file:///home/gottlieb/courses/os202/exams/final/practice/practice-final-ans.html 4/4
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com