Transcript Final Review

Operating Systems
Review
Questions



What are two functions of an OS?
What “layer” is above the OS?
What “layer” is below the OS?

Manages all system resources





CPU
Memory
I/O
Files
Objectives:



Security
Efficiency
Convenience
Questions

What causes OS to change?






What is multi-programming?
What is time-sharing?
Or, why aren’t we still running MS-DOS?
What is a process? What is a thread?
What is address space?
What is a file?
Review



What is (average) waiting time?
Explain how SJF,FCFS,RR etc. works
True or False:



FCFS is optimal in terms of avg waiting time
Most processes are CPU bound
The shorter the time quantum, the better

Response time



Estimate by time from job submission to time to first CPU
dispatch
Assume all jobs submitted at same time, in order given
Turnaround time


Time interval from submission of a process until completion
of the process
Assume all jobs submitted at same time
FCFS
P1
P2
20
SJF
P5 P3
4
RR
P3
32
P2
P4
40
56
P4
12
24
P5
60
P1
40
60
P1 P2 P3 P4 P5 P1 P2 P3 P4 P1 P2 P4 P1 P4 P1
4
8
12
16
20
24
28
32
36
40
44
48
52
56
60
6
Response Time Calculations
Job
FCFS
SJF
RR
P1
0
40
0
P2
20
12
4
P3
32
4
8
P4
40
24
12
P5
56
0
16
Average
29.6
16
8
7
Turnaround Time Calculations
Job
FCFS
SJF
RR
P1
20
60
60
P2
32
24
44
P3
40
12
32
P4
56
40
56
P5
60
4
20
Average
41.6
28
42.4
8
Review


What is a “race condition”?
What are 3 properties necessary for a correct
“critical region” solution?



mutual exclusion, progress, bounded waiting
What is Peterson’s Solution?
Why is semaphore better than Peterson’s
solution and TSL?
Review


What is deadlock?
What is the four conditions for deadlock to
happen?
Review of Banker’s Algorithm


P = {P0, P1, …, P4}; R={A(10), B(5), C(7)}
Snapshot at time T0:
Allocation
Max
Available
ABC
ABC
ABC
P0
010
753
332
P1
200
322
P2
302
902
P3
211
222
P4
002
433
Can request for (1,0,2) by P1 be granted?
Can request for (3,3,0) by P4 be granted?
Can request for (0,2,0) by P0 be granted?
Review


What is the Memory Management Unit?
How does it work during a virtual—physical
address translation?
Translate virtual
address to
physical address
1.20
2.4100
3.8300
Review

A paging scheme uses a Translation Looaside Buffer (TLB) A TLB access takes 10 ns
and a main memory access takes 50 ns.
What is the effective access time (in ns) if the
TLB hit ratio is 90% and there is no pagefault?
Multilevel Page Tables
What is the PT1 and
PT2 value for a virtual
address 0x00403004?
Figure 3-13. (a) A 32-bit address with two page table fields.
(b) Two-level page tables.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
?

A computer has 32-bit virtual addresses and
4-KB pages. The program and data together
fit in the lowest page (0-4095) the stack fits in
the highest page. How many entries are
needed in the page table if traditional paging
is used? How many page table entries are
needed for 2-level paging, with 10 bits in
each part?
Review



What is internal fragmentation?
What is external fragmentation?
What is compaction?
True or False



With paging, a process’ logical address
spaces is contiguous
With paging, a process’ physical address
spaces is contiguous
Paging reduces the size of the possible
address space used by a process
Review

Does paging have fragmentation?



No? Then why not?
Yes? Then what kind?
What are the overheads associated with
paging?
Review

True or False:
a)
b)

The logical address space cannot be bigger
than the physical address space
Processes have big address spaces
because they always need them
Demand paging:
a)
b)
c)
Is unrelated to prepaging
Brings logical pages into physical memory
when requested by a process
Increases memory requirements for a
system
Review

Page faults



What is a Page Replacement Algorithm?




What is a page fault?
What does an OS do during a page fault?
What is “Belady’s Anomaly”?
How does the Optimal algorithm work?
How does Enhanced Second Chance work?
What is thrashing?

How do we fix it?
?







A computer has four page frames. The time of loading,
time of last access, and the R and M bits for each page
are as shown below (the times are in clock ticks):
Page Loaded Last Ref. R M
0
126
285
1 0
1
120
265
0 0
2
140
270
0 1
3
110
280
1 1
(a) Which page will NRU replace? (b) Which page will
FIFO replace? (c) Which page will LRU replace? (d)
Which page will second chance replace?
Cause of thrashing
CPU utilization
thrashing increases
Degree of multiprogramming
?

Array A[1024, 1024] of integer, each row is
stored in one page

Program 1
for j := 1 to 1024 do
for i := 1 to 1024 do
A[i,j] := 0;


1024 × 1024 page faults
Program 2
for i := 1 to 1024 do
for j := 1 to 1024 do
A[i,j] := 0;

1024 page faults
First-In-First-Out (FIFO)
1,2,3,4,1,2,5,1,2,3,4,5
3 Frames / Process
1
4 5
2
1
3
2 4
3
9 Page Faults
How man page faults would we have if we had
4 Frames/Process?
?

How long does it take to load a 64KB
program from a disk whose average seek
time and rotation time are 10 msec, and
whose tracks hold 32KB.


For 2KB page size?
For 4KB page size?
The UNIX V7 File System (2)
Figure 4-34. A UNIX i-node.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
I-Node
i-node
Disk blocks

62
77
null
null
null
null
null

How many data blocks are
there?
If you added 3 more data
blocks to the file, what
would happen?
Review

Directories:



Aliases:



In what way is a directory different than a file?
In what way is a directory similar to a file?
Describe a hard-link
Describe a soft-link
Free space management:

If the size of a block is B bytes, then what is the
biggest size of a group in ext2?
The UNIX V7 File System (3)
Figure 4-35. The steps in looking up /usr/ast/mbox.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639