※ [本文转录自 NTU-Exam 看板 #1LgXXQkA ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
标题: [试题] 103下 郭大维 作业系统 期末考+解答
时间: Sat Jul 18 17:11:51 2015
课程名称︰作业系统
课程性质︰必修
课程教师：郭大维
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2015.06.24
考试时限（分钟）︰
试题 :
Operating Systems
Final Exam
Spring 2015
The exam is 150 minutes long. The total score is 102pts. Please read the
questions carefully.
1. Terminologies (18pts).
a. Starvation
Ans: A process wait infinitely without receiving its requested resource!
b. TLB Reach (Hint: Translation Look-aside Buffers is TLB)
Ans: The address space that is covered by the TLB.
c. Paged Segmentation (Hint: IA-32 Segmentation)
Ans: Divide segments further into pages. That is, having Paging for each
segment.
d. Slab Allocation (Hint: Kernel Memory Allocation)
Ans: The memory is partitioned into slabs, that are physically contiguous
pages and contain objects. A cache is of one or more slabs. When an
object is requested, it is allocated from a slab.
e. Working Set
Ans: The working set is an approximation of locality.
f. Soft Link
Ans: It is implemented as a file that contains a pathname.
2. There are 4 necessary conditions for deadlocks. Which necessary condition is
to fail if we request every process to acquire all of its needed resources
before it starts execution? Which necessary condition is to fail if every
resource in a system is sharable at any time?
(Hint: Deadlock Prevention) (8pts)
Ans: (a) Hold and Wait
(b) Mutual Exclusion.
3. Given the following snapshot of the system: Please determine whether the
system is safe? If it is safe, you must show me one safe sequence. If not,
show me that there is no safe sequence. (5pts)
┌─┬──────┬──────┬──────┐
│ │ Allocation │ Max │ Available │
│ │ A B C D │ A B C D │ A B C D │
├─┼──────┼──────┼──────┤
│P0│ 1 2 0 1 │ 2 2 1 2 │ 0 1 1 1 │
├─┼──────┼──────┼──────┤
│P1│ 1 0 0 2 │ 2 0 1 2 │ │
├─┼──────┼──────┼──────┤
│P2│ 2 1 0 1 │ 2 2 1 2 │ │
├─┼──────┼──────┼──────┤
│P3│ 2 0 1 1 │ 3 1 1 1 │ │
└─┴──────┴──────┴──────┘
Ans: Yes, there is a sequence <P2, P0, P1, P3>.
4. Address binding time could be at the compile time, loading time, or
execution time. What is the address binding time for "Paging"? Will there
be any external fragment for "Paging"? You must provide explanation to
receive any points. (8pts)
Ans: (a) execution time.
(b) No external fragment because every process is partitioned into a
number of pages to fit in frames of the physical memory.
5. Given the following reference string, which reference causes a page fault
under the FIFO algorithm. Please also show us which page is replaced when a
page replacement occurs? Suppose that we have 3 available frames, which are
empty initially. (5pts)
1 2 3 2 1 5 0 2 3 0 1 4 5
Ans:
┌────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│Reference String│１│２│３│２│１│５│０│２│３│０│１│４│５│
└────────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
┌────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ Frame #1 │１│１│１│ │ │５│５│５│３│ │３│３│５│
├────────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│ Frame #2 │ │２│２│ │ │２│０│０│０│ │１│１│１│
├────────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
│ Frame #3 │ │ │３│ │ │３│３│２│２│ │２│４│４│
└────────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
┌────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ Page │ │ │ │ │ │１│２│３│５│ │０│２│３│
│ Replacement │ │ │ │ │ │↓│↓│↓│↓│ │↓│↓│↓│
│ │ │ │ │ │ │５│０│２│３│ │１│４│５│
└────────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
6. Please answer these questions for memory management. You must provide
explanation to receive any credits. (20pts)
a. Please compare "Paging" and "Segmentation" in terms of address
translation. Please also give me one advantage and one disadvantage of
Segmentation, compared to Paging. (10pts)
b. What is the motivation in having an Inverted Page Table? (5pts)
c. What is the minimum number of frames to execute an instruction
ADD (A), (B), (C)? Note (X) is an indirect address. (5pts)
Ans: (a) Paging: Page # + Offset; Segmentation: Segment # + Offset. For
Address Translation, Segmentation must compare the offset with
the segment size, and add the segment base address and the offset
for the physical address, where Paging just replace the Page #
with the Frame #. Segmentation Advantage: Logic unit per segment,
disadvantage: external fragmentation
(B) A page table tends to be big and does not correspond to the # of
pages residing in the physical memory. We just keep one inverted
page table for all processes in the system.
(C) 7 frames
7. The performance of Demand Paging could be improved by reducing the page
fault probability or the page fault service time. Does Page Buffering helps
in reducing the page fault probability or the page fault service time? Do
we reduce the page fault probability or the page fault service time if the
system gives more frames to a process? You must provide explanation to
receive any credits. (10pts)
Ans: (a) the page fault service time because the system keeps a pool of
free frames to page in needed pages asap.
(b) the page fault probability because a reasonable page replacement
algorithm will have less page faults.
8. The Second-Chance Algorithm is an LRU approximation algorithm. Please
explain why the Second-Chance Algorithm could select the LRU page? (Or
explain why recently or actively used pages will not be selected for page
replacement.) (8pts)
Ans: Actively used pages will often have their reference bits set by MMU so
that the Second-Chance Algorithm will always skip them in victim page
selection.
9. Please use Table of Open Files (per Process) and the System Open File Table
to explain when a parent process and a child process can access the same
file with the same file offset pointer. (5pts)
Ans: It is because the Table of Open Files of the child process is copied
from its parent process such that each corresponding entries points to
the same one in the System Open File Table.
10. Given an x86-64 computer system with a 48-bit virtual address, let the
system be only byte-addressable. Assume that every page is of 2KB with
8 bytes per page entry in the page table. Suppose that the frame number
needs 7 bytes to store. Please answer the following questions: (21pts).
a. What would be the maximum number of pages owned by a process? What is
the number of frames owned by a process? (6pts)
b. Suppose that we have multi-level paging. How many levels do we have in
multi-level paging? (5pts)
c. Suppose that TLB is adopted for paging, where the above multi-level
paging is used. Let the memory access time and TLB access time be 100ns
and 10ns, respectively. When the TLB hit ratio is 99%, what is the
effective memory access time? (5pts)
d. Suppose that demand paging is adopted. Let p be the probability of a
page fault, and ma be set as 110ns for the memory access time. pft is
the page fault time. When pft is 10ms, what is the probability of a
page fault so that the effective access time will not be over 120ns.
Note that 1ms = 10^(-3)s, 1ns = 10^(-9)s. (5pts)
Ans: a. 2^37 pages; 2^37 frames
b. 5 levels
c. EMAT = (1 - 0.01) * 610 + 0.01 * 110, unit=ns.
d. Solve p for 120 >= (1 - p) * 110 + p * pft