課程名稱︰作業系統
課程性質︰必修
課程教師︰簡立峰
開課系所︰資管系
考試時間︰93下
試題 :
Mid Term, Operating Systems, NTUIM
2005/4/27
1. Explain the concept of the following terms in short (20%)
(a) Long-term scheduler and short-term scheduler
(b) Logical address and physical address
(c) Swapping
(d) TLBs
(e) External fragmentation and internal fragmentation
(f) Multiprogramming and multiprocessing
(g) Buddy system
(h) Working-set model
(i) Belady’s anomaly
(j) LRU algorithm
2. Draw the diagram of process state (as in Section 3.1.2). (5%)
3. Paging and Calculation of Effective Access Time. (10%)
(a) What is “Paging”?
(b) Calculation of effective access time
Like that described in Section 8.4.2, assume:
Associative Lookup (time to search for TLB) = ε (time unit)
Memory cycle time (time to access memory) is 10 microsecond
Hit ratio = α
Please calculate Effective Access Time (EAT) of a paging system for this case?
4. Consider a demand-paging system with the following time-measured utilizations: (10%)
Paging disk 95%
CPU utilization 18%
Other I/O devices 8%
For each of the following, say whether it will (or is likely to) improve CPU utilization.
Explain your answers.
(a) Decrease the degree of multiprogramming
(b) Increase the page size
(c) Install a faster CPU
(d) Install a bigger paging disk
5. Please explain the “thrashing” phenomenon, and describe how to solve this problem. (5%)
6. The most appropriate scheduling algorithm for an operating system can depend on the
type of workloads expected to run on it. For each of the following two workloads, give the
name of the most appropriate scheduling algorithm for such a workload, from among the
following algorithms: first-come-first-served (FCFS), non-preemptive shortest-job-first
(SJF), round-robin (RR), preemptive priority (PP), multilevel feedback queue (MFQ). For
each system, write a sentence explaining why your choice of algorithm is the most
appropriate. (10%)
(a) An air-traffic control workstation which runs multiple processes for tracking planes,
in which some processes must temporarily gain exclusive access to the CPU in
response to critical conditions (e.g. ensuring two planes do not collide with one
another).
(b) A shared system on which multiple users perform interactive activities such as
reading mail and browsing the web.
2
7. Consider the following set of processes with CPU burst times given in milliseconds: (10%)
Process Burst Time Arrival Time
P1 8 0
P2 2 1
P3 3 3
P4 4 4
P5 1 6
Draw the Gantt chart and computer the average waiting time for each of the following
scheduling algorithms:
(a) FCFS scheduling.
(b) Preemptive SJF scheduling.
8. The following processes arrive for execution at the times indicated. Each process will run
the listed amount of time. (10%)
Process Arrival time Burst time
P1 0.0 8
P2 0.6 4
P3 1.0 1
(a) Suppose the non-preemptive shortest job first (SJF) scheduling algorithm is used,
what is the average turnaround time?
(b) What is the average turnaround time for these processes with the FCFS scheduling
algorithm?
9. Consider the following page reference string: (10%)
1 2 1 3 4 1 5 4 1 5 2 2 3 6 4 1
(a) How many page faults would this reference string produce under the FIFO
replacement scheme with 4 frames? Show your work.
(b) How many page faults would this reference string produce under the LRU
replacement scheme with 4 frames? Show your work.
10. Suppose we have a 40-bit virtual address separated into an x-bit virtual page number and
(40-x)-bit page offset. Using the basic single page table scheme, what is the maximum
number of entries in the page table and what is the size of each page (in bytes)? (5%)
11. Multiple choice:
(a) The scheduler that brings processes into memory and swaps them out on disk as
needed is referred to as: (3%)
(1) Short-term scheduler
(2) Long-term scheduler
(3) Medium-term scheduler
(4) None of the above
(b) Optimal page replacement: (2%)
(1) Is usually the best choice in practice
(2) Is a good idea, but you can never really know what is optimal
(3) Is useful as a basis for comparing other algorithms
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.161.13.221