※ [本文转录自 NTU-Exam 看板 #1KZKdhap ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
标题: [试题] 101下 郭大维 作业系统 期末考+解答
时间: Sun Dec 14 16:27:20 2014
课程名称︰作业系统
课程性质︰必修
课程教师︰郭大维
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰
考试时限（分钟）：150
试题 :
Operating Systems
Final Exam
Spring 2013
The exam is 150 minutes long. The total score is 108pts. Please read the
questions carefully.
1. Terminologies (21pts).
a. Deadlock
Ans: A set of process is in a deadlock state when every process in the
set is waiting for an event that can be caused by only another
process in the set.
b. Segmentation
Ans: Segmentation is a memory management scheme that supports the user
view of memory.
c. Working Set (Hint: Thrashing and Frame Allocation)
Ans: The working set is an approximation of a program's locality.
d. Optimal Algorithm for Page Replacement (OPT)
Ans: Replace the page that will not be used for the longest period of
time.
e. Hard Link (Hint: Acyclic-Graph Directory
Ans: A hard link of a file name let its directory entry point to the
i-node that describes the file's contents.
f. Network-Attached Storage (NAS)
Ans: Clients access NAS via a remote procedure call interface such as
NFS (for UNIX) or CIFS (for Windows) where NAS has a file system
running on it.
g. Raw Disk
Ans: A partition as a large sequential array of logical blocks.
2. Please provide one advantage and one disadvantage of a deadlock avoidance
algorithm (such as the Banker's Algorithm), compared to a deadlock
prevention algorithm (such as the one without "Hold-and-Wait"). (6pts)
Ans: Advantage: Better resource utilization and/or better system
throughput/performance.
Dsadvantage: Processes must claim maximum usages of each resource.
3. Given the following snapshot of the system: Please determine whether the
current state is safe. (5pts)
┌─┬──────┬───────┬──────┐
│ │ Allocation │Maximum Needs │ Available │
│ │ A B C D │ A B C D │ A B C D │
├─┼──────┼───────┼──────┤
│P0│ 1 1 2 1 │ 3 1 2 1 │ 0 1 1 0 │
├─┼──────┼───────┼──────┤
│P1│ 2 1 1 0 │ 2 0 1 1 │ │
├─┼──────┼───────┼──────┤
│P2│ 1 1 0 1 │ 2 2 2 1 │ │
├─┼──────┼───────┼──────┤
│P3│ 0 0 1 1 │ 0 1 1 1 │ │
└─┴──────┴───────┴──────┘
Ans: Yes, it is safe bcause there is one sequence is < P3, P1, P2, P0 >.
4. Please answer these questions for memory management. (l6pts)
a. Consider the excution of a program by the Overlays method. Is the
binding time at the compiling time, loading time, or execution time?
(5pts)
b. Most mid-term schedulers usually use paging in normal situations,
instead of swapping. Please explain why "swapping" is not used by most
mid-term schedulers until the number of available free pages falls under
a safe threshold for some time. (5pts)
c. Please provide two reasons why kernel memory allocation is separated
from user-mode memory allocation, e.g., paging. (6pts)
Ans: (a) Compiling time.
(b) It is because swapping has a lot of cost in swapping in/out
processes. That is why it is not used until it is urgent.
(c) 1. The kernel might request memory of various sizes, that are
often less than a page in size.
2. Certain hardware devices interact directly with physical
memory, and the accesses memory must be in physically
contiguous pages.
5. The effective access time is equal to (1 - p) * ma + p * pft, where p is
the probability of a page fault, ma is memory access time for paging, and
pft is the page fault time. Please explain the help of each of these
methods in reducing the effective access time, with respect to the above
formula (e.g., help on either p, ma, pft, or any 2 or 3 of them):
(1) A LRU page replacement algorithm,
(2) a good frame allocation algorithm,
(3) Page Buffering with a pool of free frames,
(4) Pre-paging,
(5) a big TLB,
(6) Inverted Page Table.
You must provide explanation to receive any credit. (24pts)
Ans: (1) p
(2) p
(3) pft
(4) pft and/or p with proper explanation
(5) ma
(6) p because more memory space is saved that is originally used for
page tables.
6. Given a computer system with a 32-bit virtua1 address and 4 bytes per page
entry, let the physical address be of 24 bits, and the system is only
word-addressable, and every word is of 4 bytes. Assume that every page is
of 2KB. Please answer the following questions: (l5pts).
a. What is the maximum number of pages per process? (5pts)
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, and multi-level page tables are
all in the main memory. 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)
Ans: a. 2^23 pages.
b. 3 levels.
c. EMAT = (1 - 0.99) * 410 + 0.99 * 110, unit = ns
7. What is the maximum number of pages needed for the following instruction:
MVC x, y, 4 (4pts)
Ans: 6 pages.
8. Given the following reference string, which reference causes a page fault
under the Enhanced Second-Chance algorithm. Suppose that we have 4
available frames with Pages 0, 2, 5, and 3 as shown in the following graph,
only the reference bit of Page 3 is 0 (others are 1), and the selection
pointer starts at Page 2. Please also show us which page is replaced when
a page replacement occurs? Let all pages be "not dirty" originally, and
every following reference be write (and every dirty bit is not cleared once
it is set in this case). (8pts)
5 0 1 4 2 4 3 3
Ans: init│ 5 0 1 4 2 4 3 3
──┼────────────
0 │ 0 0 0 0 0 0 3 3
│
2 │ 2 2 2 4 4 4 4 4
│
5 │ 5 5 5 5 2 2 2 2
│
3 │ 3 3 1 1 1 1 1 1
换 换 换 换
3 2 5 0
9. Please explain why he execution of lseek() causes no I/O. (4pts)
Ans: only modification of the file offset pointer in the system open file
table.
10. Compared to the Shortest-seek-time-first (SSTF) Algorithm, give me one
advantage of the Scan (or Elevator) Algorithm? (5pts)
Ans: There is no starvation.