quiz 2

studied byStudied by 1 person
0.0(0)
get a hint
hint

What is a critical region?

1 / 138

Tags and Description

139 Terms

1

What is a critical region?

A part of the program where the shared memory is accessed

New cards
2

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

Mutual Exclusion, Progress, Bounded Waiting

New cards
3

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
4

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
5

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
6

Bounded Waiting for critical section problem

Assume that each process executes at a nonzero speed

New cards
7

Bounded Waiting for critical section problem

No assumption concerning relative speed of the N processes

New cards
8

What is a race condition?

outcome of execution depends upon order of access

New cards
9

How does a race condition occur?

2 thread access 1 shared variable

New cards
10

What is the definition of deadlock?

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

New cards
11

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

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

New cards
12

Mutual Exclusion

not required for sharable resources; must hold for nonsharable resources

New cards
13

Hold and Wait

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

New cards
14

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
15

Hold and Wait Disadvantage

Low resource utilization; starvation possible

New cards
16

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
17

No Preemption

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

New cards
18

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
19

Mutual Exclusion Disadvantage

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

New cards
20

Circular Wait

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

New cards
21

Circular Wait

Invalidating the circular wait condition is most common.

New cards
22

Circular Wait

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

New cards
23

Circular Wait

Resources must be acquired in order.

New cards
24

What is a safe sequence?

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

New cards
25

How does a safe sequence prevent deadlock?

If a system is in safe state, no deadlocks

New cards
26

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
27

Advantages of contiguous allocation?

No space need to determine next block location,

New cards
28

Advantages of contiguous allocation?

Sequential access required min head movement,

New cards
29

Advantages of contiguous allocation?

File descriptors are easy 2 implement,

New cards
30

Advantages of contiguous allocation?

Easily implemented

New cards
31

What is the idea behind address translation?

enabling private IP networks using unregistered IP addresses to go online

New cards
32

What is a virtual address?

generated by the CPU and also called logical address

New cards
33

What is a physical address

address seen by the memory unit

New cards
34

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
35

What is external fragmentation?

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

New cards
36

What is the idea behind paging?

break each process into individual pages

New cards
37

Advantages of Paging

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

New cards
38

Disadvantages of paging

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

New cards
39

Disadvantages of contiguous allocation?

Finding contiguous space for a new file may be impossible

New cards
40

Disadvantages of contiguous allocation?

Programmer must specify size before hand

New cards
41

Disadvantages of contiguous allocation?

External fragmentation occurs

New cards
42

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
43

What is Effective Access time?

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

New cards
44

What is Effective Access Time function?

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

New cards
45

Briefly explain the Banker's algorithm.

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

New cards
46

Producer-Consumer Problem

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

New cards
47

Bounded Buffer Solution

many producers and consumers share 1 buffer

New cards
48

critical region

accessing shared memory or file

New cards
49

Race Condition

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

New cards
50

how a race condition occurs

when two threads access a shared variable at the same time

New cards
51

nonpreemptive kernels

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

New cards
52

preemptive kernel

process can be preempted while in kernel mode

New cards
53

preemptive kernel example

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

New cards
54

preemptive kernel advantage

sys-calls do not block the entire system

New cards
55

preemptive kernel disadvantage

introduces more complexity to the kernel code

New cards
56

non-preemptive kernel advantage

less difficult to design

New cards
57

non-preemptive kernel disadvantage

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

New cards
58

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
59

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
60

Test and Set (atomic instruction)

test memory word and set value

New cards
61

Swap (atomic instruction)

swap contents of two memory words

New cards
62

Semaphores

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

New cards
63

Wait() (semaphore)

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

New cards
64

signal() (semaphore)

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

New cards
65

How wait() is used

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

New cards
66

How signal() is used

call the func function if the process receives a signal signum

New cards
67

Counting semaphore

integer value can range over an unrestricted domain

New cards
68

Binary semaphore

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

New cards
69

Semaphore as General Synchronization Tool can...

implement a counting semaphore S as a binary semaphore

New cards
70

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
71

busy-waiting advantage

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

New cards
72

busy-waiting disadvantage

waste of resource

New cards
73

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
74

spinlock advantage

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

New cards
75

spinlock disadvantage

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

New cards
76

mutex locks

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

New cards
77

how binary semaphore is used

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

New cards
78

how counting semaphore is used

coordinate access to resources and can implement as binary semaphore

New cards
79

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
80

When binary semaphore is used

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

New cards
81

Resource-Allocation Graph

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

New cards
82

monitor

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

New cards
83

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
84

condition variable

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

New cards
85

Bounded buffer solution using semaphores (producer)

produces item, has others wait for semaphore, then puts item in buffer, then locks the semaphore

New cards
86

Bounded buffer solution using semaphores (consumer)

has others wait for semaphore, move item to consumed, then locks semaphore before consuming it

New cards
87

Reader/Writer solution using semaphores (reader)

has others wait, then go to first line and has writer to stop writing, then reads it, then read count decreases and locks it

New cards
88

Reader/Writer solution using semaphores (writer)

wait for semaphore then writes the thing, then locks it

New cards
89

Dining Philosophers solution using monitor

imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available

New cards
90

How resource allocation graph has deadlock

when its in cycle and processes wait forever

New cards
91

Ignoring deadlocks

Reboot the system when there's a deadlock. E.g. Ostrich

New cards
92

Preventing deadlocks

Invalidate one of the four necessary conditions for deadlock.

New cards
93

Preventing deadlock example

safe sequence

New cards
94

Avoiding deadlock

requires that each process declare the maximum number of resources of each type that it may need, banker algorithm/resource allocation graph.

New cards
95

detecting deadlock

Periodically invoke an algorithm that searches for a cycle in the graph. e.g. resource allocation graph If there is a cycle, there exists a deadlock

New cards
96

advantages of ignoring deadlock

simple and straightforward, easy to implement

New cards
97

disadvantage of ignoring deadlock

reboot = breaks other programs

New cards
98

advantage of preventing deadlock

easy to understand

New cards
99

disadvantage of preventing deadlock

Low resource utilization; starvation possible

New cards
100

advantage of avoiding deadlock

eliminates deadlocks

New cards

Explore top notes

note Note
studied byStudied by 10 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 2 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 19 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 34 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 28 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 69 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 5 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 6582 people
Updated ... ago
4.7 Stars(30)

Explore top flashcards

flashcards Flashcard440 terms
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)
flashcards Flashcard54 terms
studied byStudied by 5 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard45 terms
studied byStudied by 8 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard54 terms
studied byStudied by 48 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard44 terms
studied byStudied by 8 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard34 terms
studied byStudied by 2 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard146 terms
studied byStudied by 6 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard75 terms
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)