operating systems exam 2

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

Hoare style

do we have a deadlock if all four deadlock conditions are met?

no

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

wait

when starting a program and switching from kernel level to user level, what happens after creating a process and initializing the address space?

load the program into memory

when starting a program and switching from kernel level to user level, what happens after initializing the translation table?

set the HW pointer to the translation table

when starting a program and switching from kernel level to user level, what happens after loading the program into the memory?

initialize the translation table

when starting a program and switching from kernel level to user level, what happens after setting the CPU to user mode?

jump to the entry point of the program

when starting a program and switching from kernel level to user level, what happens after setting the HW pointer to the translation table?

set the CPU to user mode

practice page tables

practice address translation

What is caching?

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

what is temporal locality

recently referenced locations are more likely to be referenced again soon

what is spatial locality?

referenced locations tend to be clustered

what is cache pollution

leaving behind cache content with no localities

what are compulsory misses

data brought into the cache for the first time

what are capacity misses

caused by the limited size of a cache

what is write through caching policy

immediately propagates update through various levels of caching

- used for critical data

what is write back caching policy

delays the propagation until the cached item is replaced

- less expensive

study effective access time

what is demand paging

allowing pages that are referenced actively to be loaded into memory

- provides the illusion of infinite physical memory

what is a page fault

a referenced page is not in memory

What is Belady's Anomaly?

adding more memory results in more page faults

What is thrashing?

when the memory is overcommitted

ex: a process needs 30 pages but a machine only has 20

what is a working set

pages that are referenced within the past T seconds

understand reference streams

what is a device controller

converting between serial bit stream and a block of bytes

What is a device driver?

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

what is memory mapped I/O

a way to address a device: making no distinction between device addresses and memory addresses

what is polling

A way to access a device: A CPU repeatedly checks the status of a device

what is interrupt driven I/Os

A way to access a device: a device controller notifies the corresponding driver when the device is available

what is direct memory access

a way to access a device using an additional controller to perform data movements

what is a character device?

delivers or accepts a stream of characters, and individual characters are not addressable

a keyboard is an example of..

character device

what is a block device

stores information in a fixed size blocks, each one with its own address

A disk is an example of ...

block device

understand FIFO/ SSTF/ SCAN/ CSCAN

parallel parking is similar to which type of fragmentation/ allocation?

external fragmentation/ contiguous allocation

what is a monitor

a lock + condition variables

what is a lock

provides mutual exclusion to shared data using lock::acquire and lock::release()

what is a condition variable

provides queue for waiting threads inside a critical section. they make it possible to sleep inside of a critical section using the wait() signal() and broadcast() operations. THESE OPERATIONS CAN ONLY BE USED INSIDE LOCKED REGIONS

what is the difference between a semaphore and a monitor?

semaphores are used for both mutual exclusion and scheduling, monitors aim to separate these two concerns. wait() will always wait, p() may not. signal() with an empty queue does nothing, v() increments semaphore.

What are 2 differences between a Hoare and Mesa Monitor?

with Hoare (used in textbooks), the Signal() operation transfers the CPU directly to a waiting thread. with Mesa (used in real OS's) Signal() only puts a waiting thread on the schedulers ready queue

what is a downfall of Mesa monitor?

by the time the waken thread gets to the CPU, the waiting condition may no longer be true and needs to be retested

what is the difference between a reader and a writer

readers never modify the database, writers read and modify the database

What is the readers-writers problem?

we want one writer at a time, but many readers at the same time

what is the basic solution to the reader writer problem

reader:

1.waits until there are no writers

2.accesses database

3.wakes up waiting writers

writer:

1.waits until there is no active reader or writer

2.accesses database

3.wakes up waiting readers or writers

can we implement monitors with semaphores?

no, condition variables only work inside of a lock. using semaphores inside a lock may cause deadlock

what is a deadlock

occurs when threads are waiting for resources with circular dependencies

what are nonpreemptive resources

resources that cannot be taken away from its current thread without failing the computation

what is a preemptive resource

resources that can be resolved by reallocation of resources (ex: CPU)

what is starvation

thread waits indefinitely

true or false: a deadlock implies starvation

true

What are the 4 deadlock conditions?

1. limited access (lock protected resources)

2. no preemption (if someone has the resource it cannot be taken away)

3. wait while holding (holding a resource while requesting and waiting for the next resource)

4. circular chain of requests

which is true about deadlocks:

1. they can happen with any kind of resource

2. they cannot be resolved for each resource independently

3. round robin cannot prevent deadlocks

4. can occur whenever there is waiting

all are true

what is the dining lawyers example

each dining lawyer needs two chopsticks, if each grabs the chopstick on their right before the left at the same time, we have a deadlock

what are some deadlock prevention techniques

1. infinite resources (very large disk)

2. no sharing (independent threads)

3. allocate all resources at the beginning (grab both chopsticks at once)

4. make every one use the same ordering when accessing a resource

5. no waiting

6. preempt resources (copying memory content onto a disk)

7. Bankers algorithm

8. combination of techniques

(remove one of the four deadlock conditions )

What is the banker's algorithm?

a thread states its maximum resource needs in advance

- sum of requested resources > total resources

-OS allocates resource dynamically as needed

what are deadlock detection and recovery steps

1. scan the resource allocation graph

2. detect circular chains of requests

3. recover from the deadlock

describe the resource allocation graph

thread A is waiting for resource X that is owned by thread B. thread B is waiting for resource Y that is owned by thread A

once a deadlock cycle is detected, what can we do?

1. kill a thread and force it to give up its resources

2. rollback actions of a deadlocked thread (need checkpointing)

what is checkpointing

taking snapshots of system states from time to time.

what is a system call

a user process asks the OS to do something on the processes behalf

what is interprocess communication

how processes communicate among address spaces

What is uniprogramming without memory protection?

each application runs within a hardwired range of physical memory addresses

- one application runs at a time

- applications typically use the lower memory addresses and OS uses the higher ones

What is multiprogramming without memory protection

when a program is copied into memory, a linker loader alters the code of the program

what is multiprogrammed OS with memory protection

memory protection keeps user programs from crashing one another and the OS

what are 2 hardware supported mechanisms

1. address translation

2. dual mode operation

how do we switch from kernel to user mode

1. create a process and initialize the address space

2. load the program into memory

3. initialize translation tables

4. set the HW pointer to the translation table

5. sets the CPU to user mode

6. jumps to the entry point of the program

how do we switch from user mode to kernel mode

system calls, hardware interrupts, segmentation faults

1. set cpu to kernel mode

2. save current program counter

3. jump to the handler in the kernel

what is the difference between context switching between threads and processes

to switch among processes we need to save and restore pointers to translation tables. much slower.

what are software supported mechanisms

protection - compilers generate code that is provably safe

what is base and bound translation

each process is loaded into a contiguous region of physical memory addresses

- processes are protected from one another

- OS can move a process around

- negative effect: external fragmentation

what is external fragmentation

memory wasted because the available memory is not contiguous for allocation

what is a segment

a logically contiguous memory region

what is segmentation based translation

use of a table and base-and-bound pairs

what is paging based translation

memory allocation via fixed sized chunks of memory, or pages

- uses a bitmap to track the allocation status of memory pages

-negative impact: internal fragmentation

what is internal fragmentation

allocated pages are not fully used

what is segmented paging translation

breaks the page table into segments

what are paged page tables

two level tree of page tables

- can be accelerated with TLB's

true or false: caching works well with programs with little localities

false- does not work well

what are translation lookaside buffers

tracks and stores recently translated memory addresses for short term reuses

what is a TLB lookup

sequential search of the TLB table

what is a virtually addressed cache

TLB between the CPU and the translation tables

what is a physically addressed cache?

TLB between the translation tables and the main memory

what is the formula for effective access time

=P(hit) (hit cost) + P(miss) (miss cost)

what is a cache hit

When requested data is found in cache

what is a cache miss

a lookup is resolved outside of the cache

what are types of cache misses and their definitions?

1. compulsory misses: data brought into the cache for the first time. ex: booting

2. capacity misses: caused by the limited size of a cache

3. misses due to competing cache entries

4. policy misses

—> C3-PO

what are some design issues of caching

1. how a cache entry lookup is performed

2. which cache entry should be replaced when the cache is full

3. how to maintain consistency between the cache copy and the real data

what are some ways to perform TLB lookups?

1. direct mapping- assigns each virtual page to a specific slot in the TLB

2. set associativity- used N TLB banks to perform lookups in parallel

3. fully associative cache- allows looking up all TLB entries in parallel

what are the steps to carry out a page fault

1. choose a page

2. if the page has been modified, write its contents to storage

3. change the corresponding page table entry and TLB entry

4. load new page into memory from storage

5. update page table entry

6. continue the thread

—> OS performs these steps while also running other processes (ex:hiring and firing someone)

what are transparent page faults

invisible mechanisms, a process does not know how it happened

what are some page replacement policies and their meaning

1. random replacement- replace a random page

2. FIFO- toss out the oldest page

3. Optimal (MIN)- replaces the page that will not be used for the longest time

4. Least Recently Used- replaces the page that has not been used for the longest time

5. Least frequently used- replaces the page that is used least often

what is the difference between a compulsory miss and a page fault

a compulsory miss can occur at various levels in the memory hierarchy, page faults occur when a page is not in the main memory

What is the clock algorithm?

replaces an old page, but not the oldest page

What is the Nth chance algorithm?

a page replacement variant of the clock algorithm, a page has to be swept N times before being replaced

what is device management

the OS component that manages hardware devices

what is a network device

transmits data packets

what are the components of a device controller

device registers and a data buffer

what are some ways to access a device?

1. polling

2. Interrupt driven I/Os

3. Direct Memory Access

4. double buffering