Final Exam Part 2

Question 1

The two things you need for any replacement algorithm:

Answer 1

1. main memory size (ex. 4 frames)

2. sequence of pages that a running program request

Question 2

Reason why the performance metric for replacement algorithims is based on the hit rate:

Answer 2

the higher the hit rate, the lower the response time

Question 3

FIFO/FCFS (Replacement algorithm)

Answer 3

First In First Out/First Come First Serve; The order in which the page request occur is the order in which they are executed.

Question 4

The best replacement policy is _____

Answer 4

OPT (Optimum Policy)

Question 5

OPT (Replacement algorithm)

Answer 5

Optimum Policy; look into the future and remove the policy that is not used in the near future

Question 6

OPT makes sense to use in real life (T or F)

Answer 6

False. how would you predict the future

Question 7

LRU (Replacement algorithm)

Answer 7

Least Recently Used; the page that was used the least recently is replaced

Question 8

LRU is never implemented in real life systems (T or F)

Answer 8

False. some version of LRU is implemented in all file system caches

Question 9

MRU (Replacement algorithm)

Answer 9

Most Recently Used; the page that was used the most recently is replaced

Question 10

Where is MRU implemented?

Answer 10

lower level cache, like storage cache

Question 11

Why is LRU never implemented as a memory page replacement policy?

Answer 11

The OS has to be called on every page hit to rearrange the replacement queue

Question 12

NUR (Replacement algorithm)

Answer 12

Not Used Recently; has a reference bit and a pointer. The reference bit is set to 1 every time a page is reference and the pointer points to the next frame to be replaced

Question 13

what is the relationship between NUR and LRU

Answer 13

NUR is a LRU approximation

Question 14

Goal of OS replacement schemes

Answer 14

1. lower page faults

2. ensures that the CPU is utilized

Question 15

When CPU utilization is low, the OS loads more programs into MM to keep CPU busy

Answer 15

True

Question 16

thrashing

Answer 16

when a program spends more time page faulting than executing; indicated too few pages in MM

Question 17

solution to thrashing

Answer 17

ensure that every program in MM has the minimum # of pages; Working Set Model

Question 18

Working Set Model

Answer 18

working set of a program: set of pages of his program that must be in MM while the program is executing; implies that the pages in the working set cannot be in the replacement queue

Question 19

Most OS use:

Answer 19

working set model and some version of NUR replacement policy

Question 20

requirement for working set model

Answer 20

working set + replacement queue must be less than or equal to the number of MM frames

Question 21

disk access time =

Answer 21

seek time + rotational latency + transfer time

Question 22

seek time =

Answer 22

time for the read/write head to move to the correct cylinder

Question 23

rotational latency =

Answer 23

time for the correct sector to arrive under the head

Question 24

transfer time =

Answer 24

time to transfer data to/from the disk

Question 25

the performance metric for disk scheduling is based upon

Answer 25

1. minimize response time 2. minimize seek time 3. minimize distance moved by the disk head

Question 26

FIFO (Disk Scheduling Policy)

Answer 26

First Come First Serve; the order in which requests are made are the order in which they are served

Question 27

SSTF (Disk Scheduling Policy)

Answer 27

Shortest Seek Time First; the next request to be served is determined by how far it has to seek to get the the next request

Question 28

Disadvantages of FIFO and SSTF

Answer 28

1. wear-and-tear due to back and forth movement of the disk head 2. could lead to starvation

Question 29

SCAN (Disk Scheduling Policy)

Answer 29

serves the first request and then moves to the closest end, processing rquests along the way, then serves requests as it moves to the next end

Question 30

CSCAN (Disk Scheduling Policy)

Answer 30

service requests while disk head is always moving in one direction

Question 31

LOOK (Disk Scheduling Policy)

Answer 31

equivalent to SCAN where the disk head does not go all the way to the end tracks unless there are requests on those tracks

Question 32

CLOOK (Disk Scheduling Policy)

Answer 32

equivalent to CSCAN where the disk head does not go all the way to the end tracks unless there are requests on those tracks

Question 33

RAID stands for

Answer 33

Redundant Array of Indepenant (Inexpensive) Disks

Question 34

Benefits of RAID

Answer 34

1. multiple disks that are treated a 1 unit by the OS 2. disks crash: more disks mean higher failure rate; but redundancy is included to ensure that failure of a disk does not result in data loss 3. improve performance by parallelism: data distributed across all disks, so queue length at each disk is smaller

Question 35

RAID 0

Answer 35

no redundancy; data are written across all the disks (stripe units) S1 S2 S3 S4 S5 S6 S7 S8

Question 36

RAID 1

Answer 36

mirroring; every disk has a copy, no striping D1 D1' D2 D2'

Question 37

RAID 1 read/write

Answer 37

write: has to write to 2 disks read: can read from either disk (faster)

Question 38

RAID 10

Answer 38

combines striping of RAID 0 and mirroring of RAID 1 S1 S1' S2 S2' S3 S3' S4 S4'

Question 39

RAID 10 disadvantage

Answer 39

capacity is 1/2 the disk space

Question 40

RAID 5

Answer 40

parity blocks are used to rebuild corrupt blocks S1 S2 S3 P1 S4 S5 P2 S6 S7 P3 S8 S9

Question 41

How are parity blocks saved

Answer 41

Cascading XORs

Question 42

disk address

Answer 42

cylinder/track #, sector #

Question 43

maps LA -> PA

Answer 43

disk controller

Question 44

keeps track of LAs

Answer 44

OS

Question 45

your file is _______ if contiguous blocks of your file are not stored contiguously on disk

Answer 45

fragmented

Question 46

performance will __________ if the file is fragmented

Answer 46

decrease

Question 47

What is a file?

Answer 47

User viewpoint: a sequence of bytes OS viewpoint: a sequence of file blocks Disk viewpoint: does not see files

Question 48

all programs had automatic access to 3 devices:

Answer 48

1. stdin 2. stdout 3. stderr

Question 49

file metadata

Answer 49

inode

Question 50

files identified by:

Answer 50

inode #

Question 51

information stored by inode:

Answer 51

1. owner 2. protection settings 3. times: creation time, modification time, last access time 4. size of file 5. location of disk where the file's data blocks are stored 6. open count: # of open copies 7. link count: # of links to this file

Question 52

file system layout on the disk:

Answer 52

boot block, super blocks, inode list, data blocks

Question 53

boot block

Answer 53

boostrap code which points to where the OS is stored on disk

Question 54

super blocks

Answer 54

layout of the file system is stored here: # of blocks, start of inode list, # of nodes, start of data blocks, list of free blocks

Question 55

inode list

Answer 55

same sized inodes

Question 56

indexed block file allocation scheme

Answer 56

inode -> index block -> data block OR inode -> index block -> index block -> data block

Question 57

What is a directory?

Answer 57

a special file that shows the correspondence between file name and inode number

Question 58

. and .. inode numbers are he same in the root directory (T or F)

Answer 58

True

Question 59

cwd

Answer 59

current working directory

Question 60

cwd = u1 open("/usr/u1/file1", O_RDWR) How many disk accesses?

Answer 60

5 disk accesses

Question 61

cwd = U1 open("file1", O_RDWR) How many disk accesses?

Answer 61

1 disk access