Final Exam Part 2 Flashcards Preview

Operating Systems > Final Exam Part 2 > Flashcards

Flashcards in Final Exam Part 2 Deck (61):
1

The two things you need for any replacement algorithm:

1. main memory size (ex. 4 frames)
2. sequence of pages that a running program request

2

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

the higher the hit rate, the lower the response time

3

FIFO/FCFS (Replacement algorithm)

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

4

The best replacement policy is _____

OPT (Optimum Policy)

5

OPT (Replacement algorithm)

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

6

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

False. how would you predict the future

7

LRU (Replacement algorithm)

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

8

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

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

9

MRU (Replacement algorithm)

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

10

Where is MRU implemented?

lower level cache, like storage cache

11

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

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

12

NUR (Replacement algorithm)

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

13

what is the relationship between NUR and LRU

NUR is a LRU approximation

14

Goal of OS replacement schemes

1. lower page faults
2. ensures that the CPU is utilized

15

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

True

16

thrashing

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

17

solution to thrashing

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

18

Working Set Model

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

19

Most OS use:

working set model and some version of NUR replacement policy

20

requirement for working set model

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

21

disk access time =

seek time + rotational latency + transfer time

22

seek time =

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

23

rotational latency =

time for the correct sector to arrive under the head

24

transfer time =

time to transfer data to/from the disk

25

the performance metric for disk scheduling is based upon

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

26

FIFO (Disk Scheduling Policy)

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

27

SSTF (Disk Scheduling Policy)

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

28

Disadvantages of FIFO and SSTF

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

29

SCAN (Disk Scheduling Policy)

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

30

CSCAN (Disk Scheduling Policy)

service requests while disk head is always moving in one direction

31

LOOK (Disk Scheduling Policy)

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

32

CLOOK (Disk Scheduling Policy)

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

33

RAID stands for

Redundant Array of Indepenant (Inexpensive) Disks

34

Benefits of RAID

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

35

RAID 0

no redundancy; data are written across all the disks (stripe units)

S1 S2 S3 S4
S5 S6 S7 S8

36

RAID 1

mirroring; every disk has a copy, no striping

D1 D1' D2 D2'

37

RAID 1 read/write

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

38

RAID 10

combines striping of RAID 0 and mirroring of RAID 1

S1 S1' S2 S2'
S3 S3' S4 S4'

39

RAID 10 disadvantage

capacity is 1/2 the disk space

40

RAID 5

parity blocks are used to rebuild corrupt blocks

S1 S2 S3 P1
S4 S5 P2 S6
S7 P3 S8 S9

41

How are parity blocks saved

Cascading XORs

42

disk address

cylinder/track #, sector #

43

maps LA -> PA

disk controller

44

keeps track of LAs

OS

45

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

fragmented

46

performance will __________ if the file is fragmented

decrease

47

What is a file?

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

48

all programs had automatic access to 3 devices:

1. stdin
2. stdout
3. stderr

49

file metadata

inode

50

files identified by:

inode #

51

information stored by inode:

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

52

file system layout on the disk:

boot block, super blocks, inode list, data blocks

53

boot block

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

54

super blocks

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

55

inode list

same sized inodes

56

indexed block file allocation scheme

inode -> index block -> data block

OR

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

57

What is a directory?

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

58

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

True

59

cwd

current working directory

60

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

5 disk accesses

61

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

1 disk access