os hw final review

hw 5-10

Which style of monitor directly transfers the control from the thread invoking signal() to the waken thread? 

A. Hoare Style

B. Mesa Style

A. Hoare Style

If wait(&lock) is invoked after signal(&lock) is invoked, the wait call will...

A. wait

B. continue

A. wait

Do we always have a deadlock if all four deadlock conditions are met?

Yes or No

No

When starting a program, what happens after each step to switch from the kernel evel to the user level?

create a process and initialize the address space

load the program into the memory

When starting a program, what happens after each step to switch from the kernel evel to the user level?

set the HW pointer to the translation table

set the CPU to user mode

When starting a program, what happens after each step to switch from the kernel evel to the user level?
set the CPU to user mode

jump to the entry point of the program

When starting a program, what happens after each step to switch from the kernel evel to the user level?

load the program into the memory

initialize the translation table

When starting a program, what happens after each step to switch from the kernel evel to the user level?

initialize translation table

set the HW pointer to the translation table

Suppose you have a 16-bit machine with a page size of 16B. Assume that any unsigned integer can be a potential memory address. Also, assume that the machine can support up to only 32KB of physical memory. (1K =2 ¹⁰)

For paging-based memory allocation, how many page table entries (in decimals) do you need to map the virtual address space of a process, with pure paging alone?

4096

Suppose you have a 16-bit machine with a page size of 16B. Assume that any unsigned integer can be a potential memory address. Also, assume that the machine can support up to only 32KB of physical memory. (1K =2¹⁰).

Translate the virtual address 0x0000 to its physical address (base 16) via the segmented-paging scheme.   Assume that a program has two segments and a page size of 16B.  

segment number	page table base	page table bound
0	0x8000	0x8
1	0x0000	0x8

physical memory address 0x0000

virtual page number	physical page number
0x000	0x500
0x001	0x504
0x002	0x508
0x003	0x50B
...

physical memory address 0x8000

virtual page number	physical page number
0x000	0x100
0x001	0x104
0x002	0x108
0x003	0x10B
...

Please leave out '0x' in your answer.

1000

Suppose you have a 16-bit machine with a page size of 16B. Assume that any unsigned integer can be a potential memory address. Also, assume that the machine can support up to only 32KB of physical memory. (1K = 2¹⁰)

Translate the virtual address 0x0003 to its physical address (base 16) via the segmented-paging scheme.   Assume that a program has two segments and a page size of 16B.  

segment number	page table base	page table bound
0	0x8000	0x8
1	0x0000	0x8

physical memory address 0x0000

virtual page number	physical page number
0x000	0x500
0x001	0x504
0x002	0x508
0x003	0x50B
...

physical memory address 0x8000

virtual page number	physical page number
0x000	0x100
0x001	0x104
0x002	0x108
0x003	0x10B
...

Please leave out '0x' in your answer

1003

Suppose you have a 16-bit machine with a page size of 16B. Assume that any unsigned integer can be a potential memory address. Also, assume that the machine can support up to only 32KB of physical memory. (1K = 2¹⁰)

Translate the virtual address 0x8020 to its physical address (base 16) via the segmented-paging scheme.   Assume that a program has two segments and a page size of 16B.  

segment number	page table base	page table bound
0	0x8000	0x8
1	0x0000	0x8

physical memory address 0x0000

virtual page number	physical page number
0x000	0x500
0x001	0x504
0x002	0x508
0x003	0x50B
...

physical memory address 0x8000

virtual page number	physical page number
0x000	0x100
0x001	0x104
0x002	0x108
0x003	0x10B
...

Please leave out '0x' in your answer.

5080

caching

Storing copies of data at places that can be accessed more quickly

temporal locality

Recently referenced locations are more likely to be referenced soon

spatial locality

Reference locations tend to be clustered

cache pollution

Leaving behind cache content with no localities

compulsory misses

Data brought into the cache for the first time

capacity misses

Caused by the limited size of a cache

write-through caching policy

Immediately propagates update through various level of caching

write-back caching policy

Delaying the propagation until the cached item is replaced

What is the effective access time of memory (in decimals) through L1 and L2 caches for the following hardware characteristics?

	access time	cache hit rate
L1 cache	1 clock cycle	75% or 3/4
L2 cache	3 clock cycle	75% of 3/4
memory	4 clock cycle	100% or 1

2

demand paging

Allowing pages that are referenced actively to be loaded into memory

page fault

A referenced page is not in memory

Belady's anomaly

Adding more memory results in more page faults

thrashing

When the memory is overcommitted

For the following reference stream, what is the content of page 2 at the end of the reference stream under MIN?

E

A

R

N

R

E

A

R

N

E

A

R

1

2

3

E

For the following reference stream, what is the content of page 2 at the end of the reference stream under LRU?

E

A

R

N

R

E

A

R

N

E

A

R

1

2

3

R

For the following reference stream, what is the content of page 2 at the end of the reference stream under LFU?

E

A

R

N

R

E

A

R

N

E

A

R

1

2

3

A

device controller

Converting between serial bit stream and a block of bytes

device driver

An OS component that hides the complexity of an I/O device

memory-mapped I/O

Making no distinction between device addresses and memory addreesses

polling

A CPU repeatedly checks the status of a device

interrupt-driven I/Os

A device controller notifies the corresponding driver when the device is available

direct memory access

Using an additional controller to perform data movements

A keyboard is an example of ...

character device

A disk is an example of ...

block device

At a given moment, the disk head is at cylinder 46, and the queue contains cylinder requests: 10, 45, 52, 56, 70.

If the driver uses the FIFO, which request will be serviced last?

A. 10

B. 45

C. 52

D. 56

E. 70

E. 70

At a given moment, the disk head is at cylinder 46, and the queue contains cylinder requests: 10, 45, 52, 56, 70.

If the driver uses the SSTF, which request will be serviced last?

A. 10

B. 45

C. 52

D. 56

E. 70

A. 10

At a given moment, the disk head is at cylinder 46, and the queue contains cylinder requests: 10, 45, 52, 56, 70.

If the driver uses the SCAN, which request will be serviced last?  If there are multiple answers, pick the answer with the lowest block number.

A. 10

B. 45

C. 52

D. 56

E. 70

A. 10

Which disk allocation policy is least reliable?

A. linked-list allocation 

B. continuous allocation

C. index-based allocation

D. multi-level indexing 

A. linked-list allocation 

Which disk allocation policies offer efficient random accesses?  (check all answers that apply)

linked-list allocation 

continuous allocation

index-based allocation

multi-level indexing 

continuous allocation

index-based allocation

multi-level indexing 

Most files are…

large or small

small

Which namespace is most prone to name collisions?

A. flat name space 

B. hierarchical name space 

C. relational naming 

D. contextual naming 

A. flat name space 

Free blocks, directories, file headers, indirect blocks are an example of...

metadata

fsck

Ad hoc file system check

atomicity

All operations either happen or they do not

serializability

Transactions appear to happen one after another

durability

Once a transaction happens, it is recoverable and can survive crashes

Write a program create_files in any language to create a file foo, sleep for 5 seconds, and create a file bar. 

Right after you start the program, press Ctrl-C to prevent the program from completing.  What do you see in the directory?  

foo

bar

journal

nothing

foo

Write programs atomically_create_files and replay_journal so that files foo and bar are atomically created   First, atomically_create_files logs <begin transaction> into the journal file journal.  Second, atomically_create_files logs <create foo> and <create bar> into journal.  Third, atomically_create_files logs <commit> into journal.  A second replay_journal program can read the journal file to perform the actual file creations and delete journal.  If there is a crash before <commit> is written into journal, replay_journal just deletes journal.  If there is a crash before replay_journal can complete the creation of the two files, replay_journal can be run again to recreate both files.  Finally, after both files are created, replay_journal removes journal.

You can inject crashes by exiting at various points in various programs.  First, copy the program atomically_create_files to atomically_create_files_crash.  Insert a crash point between the logging of two file creation operations in atomically_create_file_crash.  

Run atomically_create_files_crash and run replay_journal.  What do you see in the directory at this point?

foo

bar

journal

nothing

nothing

Write programs atomically_create_files and replay_journal so that files foo and bar are atomically created   First, atomically_create_files logs <begin transaction> into the journal file journal.  Second, atomically_create_files logs <create foo> and <create bar> into journal.  Third, atomically_create_files logs <commit> into journal.  A second replay_journal program can read the journal file to perform the actual file creations and delete journal.  If there is a crash before <commit> is written into journal, replay_journal just deletes journal.  If there is a crash before replay_journal can complete the creation of the two files, replay_journal can be run again to recreate both files.  Finally, after both files are created, replay_journal removes journal.

You can inject crashes by exiting at various points in various programs.  First, copy the program replay_journal to replay_journal_crash.  Insert a crash point after recreating the first file in replay_journal_crash.  

Run atomically_create_files, run replay_journal_crash, and run replay_journal.  What do you see in the directory at this point? 

foo

bar

journal

nothing

foo, bar

Security is a form of...

policy or mechanism

policy

Which of the keys are used to encrypt (not decrypt) a message when anyone can create the message, but only A can read the message? Please check all answers that apply.

public key of A

private key of A

public key of A

confidentiality

Secret data remains secret

integrity

Unauthorized user should not be able to modify data

availability

Nobody can make a system unusable

authentication

Determining who the user is

authorization

Determining who is allowed to do what

enforcement

Making sure people can do only what they are allowed to do

access control list

Storing all permissions for all users with each object

capability list

Storing all objects a process can touch

Trojan horse

Seemingly innocent program that performs an unexpected function

What are some characteristics of IP transmissions?   Check all answers that apply.

machine-to-machine 

ordered

reliable

user-to-user

machine-to-machine 

What are some characteristics of UDP transmissions?   Check all answers that apply.

user-to-user 

machine-to-machine 

ordered 

reliable 

user-to-user 

What are some characteristics of TCP transmissions?  Check all answers that apply.

ordered

reliable

user-to-user

machine-to-machine 

ordered

reliable

user-to-user

Which networks have no arbitration?

point-to-point or broadcast

point-to-point

distributed systems

Allowing physically separate computers to work together

network

Physical connection that allows two computers to communicate

packet

A unit of transfer

protocol

An agreement between two parties as how information is to be transmitted

arbitration

Concerning the way to share a given resource

carrier sensing

Ethernet does not send unless the network is idle

routing

Concerning how a packet can reach its destination

Location transparency means the location of the execution is visible to the user.
true or false

false

Which write consistency model does NFS use?

A. write through

B. write back

C. other

A. write through

Which write consistency model does AFS use?

A. write through

B. write back

C. other

B. write back

Which write consistency model does xFS use?

A. write through

B. write back

C. other

C. other

Which of the keys are used to encrypt (not decrypt) a message when anyone can create the message, but only A can read the message?  Please check all answers that apply.

A. public key of A

B. private key of A

A. public key of A

Write programs atomically_create_files and replay_journal so that files foo and bar are atomically created   First, atomically_create_files logs <begin transaction> into the journal file journal.  Second, atomically_create_files logs <create foo> and <create bar> into journal.  Third, atomically_create_files logs <commit> into journal.  A second replay_journal program can read the journal file to perform the actual file creations and delete journal.  If there is a crash before <commit> is written into journal, replay_journal just deletes journal.  If there is a crash before replay_journal can complete the creation of the two files, replay_journal can be run again to recreate both files.  Finally, after both files are created, replay_journal removes journal.

You can inject crashes by exiting at various points in various programs.  First, copy the program atomically_create_files to atomically_create_files_crash.  Insert a crash point between the logging of two file creation operations in atomically_create_file_crash.  

Run atomically_create_files_crash and run replay_journal.  What do you see in the directory at this point?

journal

foo

bar

nothing

nothing