os

os

Citation preview

CSC 369H1 F OPERATING SYSTEMS UNIVERSITY OF TORONTO FALL 2003 Midterm Test NO AIDS ALLOWED Please PRINT in answering the following requests for information: Family Name: _________________________________ Given Names: _________________________________ Student Number: |_ _ _| |_ _ _| |_ _ _| Login (@cdf): ____________________ Notes to students: 1. This test lasts for 50 minutes and consists of 50 marks. Budget your time accordingly. 2. This test has 7 pages and 5 questions; Check that you have all pages before starting. 3. Write in pen. No pencils. 4. Write your answers on this “question and answer” paper, in the spaces provided. Be concise. In general, the amount of space provided is an upper bound on the “size” of answer that is expected. If necessary, use space where available and provide explicit pointers. 5. In general, state your assumptions and show your intermediate work, where appropriate. 6. Do not go beyond here until instructed to do so. Write your student number at the top of each succeeding page once you get going.

Question Marks 1 2 3 4 5 Total

../continued

CSC 369H1 F, Fall 2003, Midterm

1. [10 marks, 2 each] True/False

2

Student Number: |_ _ _| |_ _ _| |_ _ _|

Circle “T” if the statement is always true. Otherwise circle “F”. a) In paging systems, external fragmentation cannot occur.

T

b) Race conditions cannot occur on a uniprocessor.

F

c) SJF can be implemented as a priority algorithm, where the priority is determined by the arrival time of the job.

F

d) A process in the Ready state can only transition to Running or Exit states.

T

e) The two-phase locking protocol guarantees that concurrent transactions are deadlock-free.

F

../continued

CSC 369H1 F, Fall 2003, Midterm

3

Student Number: |_ _ _| |_ _ _| |_ _ _|

2. [9 marks; 3 each] Define the following terms in the context of this course: (a) Starvation: A condition in which a process is blocked indefinitely because another process is always given preference. May occur because of priority scheduling, or unfair synchronization algorithms.

(b) Page Frame A fixed-size block of physical memory used in paging systems to hold parts of a process’s address space. Frames are identical; any frame can be used to hold any page for any process.

(c) Turnaround Time The difference between the time at which a process arrives, and the time at which it completes.

____________________

../continued

CSC 369H1 F, Fall 2003, Midterm

3. [10 marks; 2 each]

4

Student Number: |_ _ _| |_ _ _| |_ _ _|

Measurements of a certain system have shown that the average process runs for a time T before blocking on I/O. A process context switch requires a time S, which is effectively wasted (overhead). The performance measure of interest is CPU efficiency, defined as the ratio of useful CPU time over total CPU time. For round-robin (RR) scheduling with a quantum of length Q, give a formula for CPU efficiency in each of the following cases (be as specific as possible, give a range if appropriate): a) Q = ∞ No involuntary context switches will occur. Each process will pay 1 context switch per CPU burst. Useful = T, Total = T + S Efficiency = T / (T + S) b) Q > T As long as the quantum Q is larger than T, then no involuntary context switches will occur. Same as (a). Efficiency = T/(T+S) c) S < Q < T Average process will have T/Q context switches per CPU burst, each with a cost S. Useful time is still T, Total is T + S*T/Q. Efficiency = T/(T+ST/Q) = 1/(1 + S/Q) Since S < Q, S/Q is < 1 and efficiency falls in the range (0.5, 1) or 50-100% d) Q = S Starting with the equation from C, the efficiency is now exactly 0.5

e) Q nearly 0 (or tending to 0) Again use the equation from C, but as Q approaches zero, S/