quiz 2

studied byStudied by 1 Person
0.0(0)
Get a hint
hint

What is a critical region?

1/139

Studying Progress

New cards
139
Still learning
0
Almost done
0
Mastered
0
139 Terms
New cards

What is a critical region?

A part of the program where the shared memory is accessed

New cards
New cards

What characteristics are required of a solution to the critical section problem?

Mutual Exclusion, Progress, Bounded Waiting

New cards
New cards

Mutual Exclusion for critical section problem

If process Pi is executing in its critical section, then no other processes can be executing in their critical sections

New cards
New cards

Progress for critical section problem

If no process is executing in its critical section and there are some want to enter their cs, then selection of the process that will enter next can't postpone indefinitely

New cards
New cards

Bounded Waiting for critical section problem

A bound must exist on # times other processes allowed to enter critical sections after process made request to enter critical section/before that request is granted

New cards
New cards

Bounded Waiting for critical section problem

Assume that each process executes at a nonzero speed

New cards
New cards

Bounded Waiting for critical section problem

No assumption concerning relative speed of the N processes

New cards
New cards

What is a race condition?

outcome of execution depends upon order of access

New cards
New cards

How does a race condition occur?

2 thread access 1 shared variable

New cards
New cards

What is the definition of deadlock?

a process indefinitely waits for a resource that is held by another process

New cards
New cards

What are the four conditions necessary for a deadlock to occur?

Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait

New cards
New cards

Mutual Exclusion

not required for sharable resources; must hold for nonsharable resources

New cards
New cards

Hold and Wait

must guarantee that whenever a process requests a resource, it does not hold any other resources

New cards
New cards

Hold and Wait

Require process to request/be allocated all its resources before starting execution, or allow it to request resource only when process has none

New cards
New cards

Hold and Wait Disadvantage

Low resource utilization; starvation possible

New cards
New cards

No Preemption

If process holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held release

New cards
New cards

No Preemption

Preempted resources are added to the list of resources for which the process is waiting

New cards
New cards

No Preemption

Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting

New cards
New cards

Mutual Exclusion Disadvantage

unwise to allow user process to this ability (should be privileged) Only works on a single CPU system.

New cards
New cards

Circular Wait

impose total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

New cards
New cards

Circular Wait

Invalidating the circular wait condition is most common.

New cards
New cards

Circular Wait

Simply assign each resource (i.e. mutex locks) a unique number.

New cards
New cards

Circular Wait

Resources must be acquired in order.

New cards
New cards

What is a safe sequence?

sequence of processes that not leads to deadlock state and fulfilling requests with available resources

New cards
New cards

How does a safe sequence prevent deadlock?

If a system is in safe state, no deadlocks

New cards
New cards

Difference between contiguous and non-contiguous allocation of memory?

contiguous allocate consecutive blocks of memory, non-contiguous allocate separate block of memory to file/process

New cards
New cards

Advantages of contiguous allocation?

No space need to determine next block location,

New cards
New cards

Advantages of contiguous allocation?

Sequential access required min head movement,

New cards
New cards

Advantages of contiguous allocation?

File descriptors are easy 2 implement,

New cards
New cards

Advantages of contiguous allocation?

Easily implemented

New cards
New cards

What is the idea behind address translation?

enabling private IP networks using unregistered IP addresses to go online

New cards
New cards

What is a virtual address?

generated by the CPU and also called logical address

New cards
New cards

What is a physical address

address seen by the memory unit

New cards
New cards

What is internal fragmentation?

allocated memory being slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

New cards
New cards

What is external fragmentation?

total memory space exists to satisfy a request, but it is not contiguous

New cards
New cards

What is the idea behind paging?

break each process into individual pages

New cards
New cards

Advantages of Paging

NO external fragmentation, Fast to allocate and free, Simple to swap-out portions of memory to disk

New cards
New cards

Disadvantages of paging

Internal fragmentation, Assigning different levels of protection to different classes of data items not feasible.

New cards
New cards

Disadvantages of contiguous allocation?

Finding contiguous space for a new file may be impossible

New cards
New cards

Disadvantages of contiguous allocation?

Programmer must specify size before hand

New cards
New cards

Disadvantages of contiguous allocation?

External fragmentation occurs

New cards
New cards

What are the ways to deal with very large page tables efficiently?

use special fast-lookup hardware cache called translation look-aside buffers (TLBs)

New cards
New cards

What is Effective Access time?

(weighted) average time it takes to get a value from memory

New cards
New cards

What is Effective Access Time function?

EAT = (202) * 1-hit ratio + 102 * hit ratio

New cards
New cards

Briefly explain the Banker's algorithm.

allocate resources to process considering availability of resource and predetermined maximum need of process.

New cards
New cards

Producer-Consumer Problem

Producer process produces information in buffer that is consumed by a consumer process

New cards
New cards

Bounded Buffer Solution

many producers and consumers share 1 buffer

New cards
New cards

critical region

accessing shared memory or file

New cards
New cards

Race Condition

results when several threads try to access and modify the same data concurrently

New cards
New cards

how a race condition occurs

when two threads access a shared variable at the same time

New cards
New cards

nonpreemptive kernels

process cannot be preempted while in kernel/supervisor mode. Must wait until return to user mode or yields CPU

New cards
New cards

preemptive kernel

process can be preempted while in kernel mode

New cards
New cards

preemptive kernel example

Linux starting with version 2.6, Solaris, Windows 7/8/10

New cards
New cards

preemptive kernel advantage

sys-calls do not block the entire system

New cards
New cards

preemptive kernel disadvantage

introduces more complexity to the kernel code

New cards
New cards

non-preemptive kernel advantage

less difficult to design

New cards
New cards

non-preemptive kernel disadvantage

It can lead to starvation especially for those real-time tasks

New cards
New cards

Peterson's Solution

a classic software-based solution to the critical-section problem which has to two processes that alternate execution between critical sections/remainder sections

New cards
New cards

atomic instruction

allow us to either test-and-modify the content of a word, or two swap the contents of two words atomically/uninterruptibly

New cards
New cards

Test and Set (atomic instruction)

test memory word and set value

New cards
New cards

Swap (atomic instruction)

swap contents of two memory words

New cards
New cards

Semaphores

Synchronization tool that provides more sophisticated ways for process to synchronize their activities.

New cards
New cards

Wait() (semaphore)

wait function has an argument called S, while S is less or equal to 0, S decreases by 1.

New cards
New cards

signal() (semaphore)

signal function has an argument called S. S increments by 1.

New cards
New cards

How wait() is used

blocks the calling process until one of its child processes exits or a signal is received

New cards
New cards

How signal() is used

call the func function if the process receives a signal signum

New cards
New cards

Counting semaphore

integer value can range over an unrestricted domain

New cards
New cards

Binary semaphore

aka mutex lock, integer value can range only between 0 and 1; can be simpler to implement

New cards
New cards

Semaphore as General Synchronization Tool can...

implement a counting semaphore S as a binary semaphore

New cards
New cards

Busy-waiting

While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire().

New cards
New cards

busy-waiting advantage

thread has the processor and can resume immediately after the wait is finished

New cards
New cards

busy-waiting disadvantage

waste of resource

New cards
New cards

spinlocks

Mutual exclusion mechanism in which a process executes in an infinite loop waiting for the value of a lock variable to indicate availability.

New cards
New cards

spinlock advantage

threads get the chance to take advantage of their full runtime quantum

New cards
New cards

spinlock disadvantage

while waiting to acquire a lock, it wastes time that might be productively spent elsewhere

New cards
New cards

mutex locks

Protect a critical section by first acquire() a lock then release() the lock

New cards
New cards

how binary semaphore is used

control access to a single resource and can implement as counting semaphore

New cards
New cards

how counting semaphore is used

coordinate access to resources and can implement as binary semaphore

New cards
New cards

how mutex lock is used

declare a lock variable of type Mutex, then execute the Lock() method of that lock, then execute the Unlock() method of the lock.

New cards
New cards

When binary semaphore is used

when users are controlling access to shared device, like using a printer

New cards
New cards

Resource-Allocation Graph

A graph representing processes and resource instances in a system. Directed edges represent resource requests and allocations.

New cards
New cards

monitor

high-level abstraction that provides a convenient and effective mechanism for process synchronization

New cards
New cards

difference between semaphore and monitor

semaphore's signal and wait increase/decrease, monitor's signal and wait doesn't, and m is higher lvl proc sync tool

New cards
New cards

condition variable

enables a thread to efficiently wait for a change to shared state protected by a lock

New cards