Test 4

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

non-deadlock bugs

1 / 149

Tags and Description

150 Terms

1

non-deadlock bugs

atomicity violation and order violation

New cards
2

atomicity violation

The desired serializability among multiple memory accesses is violated (i.e. a code region is intended to be atomic, but the atomicity is not enforced during execution).

New cards
3

order violation

The desired order between two (groups of) memory accesses is flipped (i.e., A should always be executed before B, but the order is not enforced during execution)

New cards
4

solution for atomicity violation

add locks around shared variable references

New cards
5

solution for order violation

enforce ordering using condition variables

New cards
6

deadlock

-the presence of a cycle -Thread 1 is holding a lock L1 and waiting for another one, L2 -Thread 2 holds L2 and is waiting for L1 to be released

New cards
7

why do deadlocks occur

In large code bases, complex dependencies arise between components Encapsulation - hidden details of implementation that make software easier to build in a modular way (does not mesh well with locking)

New cards
8

conditions for a deadlock

Mutual exclusion - threads claim exclusive control of resources that they require Hold and Wait - threads hold resources allocated to them No preemption - resources cannot be forcibly removed from threads that are holding them Circular Wait - circular chain of threads such that each thread holds one or more resources that are being requested by the next thread in the chain

New cards
9

true or false: if only one of the four deadlock conditions is met a deadlock can occur

false

New cards
10

how to prevent circular wait

total ordering - strict ordering of threads partial ordering (difficult to achieve) partial ordering - useful way to structure lock acquisition to avoid deadlock

New cards
11

how to prevent hold-and-wait

by acquiring all locks at once, atomically

New cards
12

what are the disadvantages of hold-and-wait prevention

encapsulation works against you - requires us to know exactly which locks must be held and to acquire them ahead of time likely to decrease concurrency - all locks must be acquired early on (at once) instead of when they are truly needed.

New cards
13

how to prevent no preemption

use thread libraries that provide a more flexible set of interfaces to help avoid problems of multiple lock acquisition

New cards
14

livelock

not a deadlock, but no progress is being made for the processes

New cards
15

solution for livelock

add random delay before looping back and trying the entire thing over again, thus decreasing the odds of repeated interference among competing threads. Not a great solution, encapsulation problems still arise

New cards
16

problems with no preemption

livelock

New cards
17

true or false: using powerful hardware instructions, you can build data structures in a manner that does not recquire explicit locking.

true

New cards
18

wait-free

can build data structures in a manner that does not require explicit locking

New cards
19

how to prevent mutual exclusion

use lock-free and wait-free data structure designs

New cards
20

true or false: livelock can occur with mutual exclusion

true

New cards
21

how can you avoid deadlocks

smart scheduling

New cards
22

what does deadlock avoidance require

Some global knowledge of which locks various threads might grab during their execution, and subsequently schedules said threads in a way as to guarantee no deadlock can occur

New cards
23

what are downsides of avoiding deadlocks with scheduling

length of jobs is increased, can limit concurrency

New cards
24

detect and recover

allow deadlock to occur than take some action, i.e. computer freezes, you reboot it

New cards
25

true or false: a deadlock detector is always running

false, runs periodically

New cards
26

true or false: in event of a deadlock the system should be restarted

true

New cards
27

monitor

-high level synchronization primitive -guarantees functions are mutually exclusive -provides condition variables such that a process can step outside the monitor while waiting for a condition and prevent other processes from entering the monitor

New cards
28

true or false: adding locks to a data structure makes it thread safe

true

New cards
29

what is the problem with synchronized counter

scales poorly

New cards
30

perfect scaling

more work done in parallel time taken to complete task is not increased

New cards
31

how does a sloppy counter (approximate counter) work

-a single local counter per CPU core -a single global counter -a lock for each local counter and one for the global counter ex: on a machine with four CPUs you have four local counters and one global counter

New cards
32

Hand-over-hand locking (lock coupling)

add a lock per node of the list instead of having a single lock for the entire list when traversing he list, the code first grabs the next node's lock and then release the current node's lock

New cards
33

downsides of lock coupling

increased time to acquire the lock

New cards
34

Michael and Scott Concurrent Queues

-there are two locks one for the head -one for the tail -enable concurrency of enqueue and dequeue

New cards
35

dummy node

allocated in the queue initialization code enable the separation of head and tail operations

New cards
36

Concurrent hash table

-hash table does not resize -built using the concurrent lists -uses a lock per hash bucket

New cards
37

true or false: simple concurrent hash table scales poorly

false, magnificently

New cards
38

persistent storage

keep data intact even if there is a power loss -hard disk drive -solid-state storage drive

New cards
39

premature optimization

performance problems should only be remedied once they exist -there is not value in making something faster if doing so will not improve overall performance of the application

New cards
40

file

a linear array of bytes a unit of storage

New cards
41

inode number

low level name of a file -corresponds to the location of the file's contents

New cards
42

directory

-like a file, has a low-level name -contains a list of (user-readable name, low-level name) pairs

New cards
43

metadata

data that describes other data information about a file

New cards
44

directory hierarchy (tree-structured)

how all files and directories are stored root directory (/), uses separator to name subsequent sub-directories until desired file or directory is named

New cards
45

relative pathname

concatenation of file names starting with current directory

New cards
46

directed acyclic directory hierarchy

organizes directories such that any directory at a given level may point to zero or more files or other directories at lower levels but also permits any file or directory to have more than one parent directory

New cards
47

general graph structure

using symbolic links, only allows a single parent directory for any file or directory but provides symbolic links to support file sharing

New cards
48

absolute pathname

The full pathname to a certain file or directory, starting from the root directory.

New cards
49

why are cycles bad in directory hierarchies

-a cycle can lead to an infinite loop in algorithms that search the hierarchy for a given file -file deletion becomes more difficult -a reference count is not sufficient to prevent the creation of unreachable subgraphs in the directory hierarchy, which can only be removed using a garbage collection algorithm

New cards
50

what is an extent

-a disk pointer plus a length (in blocks) -a file consists of one or more extents -less flexible but more compact, work well when there is enough free space on the disk and files can be laid out contiguously

New cards
51

reference count (link count)

allows the file system to track how many different file names have been linked to this particular inode

New cards
52

symbolic link (soft link)

  • a file itself of a different type (not like a hard link, can't edit the reference to edit the original) the original file can be accessed through the file name as well as the symbolic link name

New cards
53

hard link

Enables you to create one file and then establish links to that file in other folders, as though the file is in all of the folders. -somewhat limited: you can't create one to a directory, you can't hard link to files in other disk partitions

New cards
54

true or false: a hard link creates a copy of the file

false, just refers to the inode of the original file

New cards
55

why unlink instead of deleting a file

when you create a hard link, it links a human readable name to the file and puts that link into a directory, if you just remove the file, you would still have access to it, so you have to unlink it

  • the reference count helps with this

New cards
56

dangling reference

problem with symbolic links -removing the original file name causes the link to point to a pathname that no longer exists

New cards
57

permission bits

nine characters -what the owner of the file can do to it -what someone in a group can do to the file -what anyone can do

New cards
58

superuser

trusted user who can access all files regardless of privileges -root -inherent security risk

New cards
59

inode

index node -holds file metadata -length, permissions, location of blocks, type, size, time

New cards
60

open()

-system call returns file descriptor (an integer) -system wide open-file table contains copy of FCB of each file -per-process open-file table contains pointers to appropriate entries in system-wide open-file table

New cards
61

true or false: an open file has a current offset

true, used to determine where the next read or write will begin within the file

New cards
62

how to implicitly update the current offset

add n bytes of read or write to the current offset

New cards
63

how to explicitly update the current offset

use lseek() -changes how the offset is set -has 3 arguments: -fildes - file descriptor -offset - positions file offset to a particular location within the file -whence - determines how the seek is performed

New cards
64

what does fsync() do

-forces all dirty (not yet written) data to the disk -returns once all writes are complete -allows one to avoid the problem of losing data if the machine crashes

New cards
65

true or false: renaming a file is implemented atomically

true

New cards
66

contiguous allocation

every file is mapped to a contiguous sequence of disk blocks -the FCB points to the first disk block -the file length determines how many blocks are occupied by the file

New cards
67

advantages and disadvantages of contiguous allocation

-fast sequential access because neighboring blocks do not require seek operations -fast direct access because a target block number can be computed using file position and block length -disk fragmentation - over time the disk consists of variable length sequences of free and occupied blocks and needs search algorithms to find free areas of appropriate size -inability to expand a file if the block following the last file block is not free, the entire file must be copied to a larger area -difficulty in deciding how much space to allocate to a new file to allow for potential expansion

New cards
68

clustered allocation

links together sequences of contiguous blocks -the last block of any cluster points to the beginning of the logically next cluster -the last block records the number of blocks belonging to the next cluster to facilitate direct access within each cluster -the number of blocks in the first cluster is recorded in the FCB along with the pointer

New cards
69

advantages and disadvantages of clustered allocation

-can easily expand a file - if the block following the last file block is free, then the last cluster is extended like with contiguous allocation -if the block following the last file block is occupied, then a new cluster is started and the last block points to the first block of the new cluster -improved sequential access over the purely linked allocation since accessing with cluster does not require seek -slower sequential access than contiguous allocation since each cluster requires a disk seek -inability to perform direct access since the location of the target block cannot be computed

New cards
70

Linked allocation

each file is a linked list of blocks -file ends at nil pointer -no external fragmentation -free space management system called when new block needed

New cards
71

advantages of linked allocation

-simple -no has external fragmentation -improve efficiency by clustering blocks into groups

New cards
72

problems with linked allocation

-reliability -locating a block can take many I/Os and disk seeks -internal fragmentation

New cards
73

FAT (File Allocation Table)

-an array where each entry corresponds to a disk block -keeps track of which disk blocks belong to a file by linking the blocks in a chain of indices

New cards
74

advantages of FAT

-has the advantages of linked allocation, including file expansion ability -blocks can be cached in main memory -sequential access is more efficient since no seek operations are necessary to follow pointers -direct access is possible because the location of the desired block can be found efficiently by scanning the chain of indices

New cards
75

indexed allocation

Each file has its own index block(s) of pointers to its data blocks random access

New cards
76

advantages and disadvantages of indexed allocation

-Ability to efficiently expand a file by simply adding a new block number to the index table -no external fragmentation -a small table limits the maximum size of any file and a large table wastes disk space

New cards
77

what is the performance of contiguous allocation

good for sequential access and random access

New cards
78

what is the performance of linked allocation

good for sequential access, not random access

New cards
79

what is the performance of indexed allocation

single block - not good, could require index block reads then data block reads clustering - yes, can improve throughput and reduce CPU overhead

New cards
80

how do we store inodes in the file system

inode table

New cards
81

true or false: inodes are unique

true

New cards
82

bitmap

each bit indicates whether a block is free or allocated free = 0 in use = 1

New cards
83

superblock

contains information about the layout of blocks for particular file system -the number of inodes, begin location of inode table

New cards
84

true or false: when mounting a file system, OS reads superblock first

true, to initialize various information

New cards
85

multi-level index

A tree data structure to keep track of the disk location of each data block in a file. indirect pointer points to a block that contains more pointers -inode has fixed number of direct pointers (12) and a single indirect pointer

New cards
86

true or false: most files are small

true, 2K is common size

New cards
87

true or false: the average file size is shrinking

false, growing, 200K is average

New cards
88

true or false: most bytes are stored in large files

true, a few big files use most of the space

New cards
89

true or false: file systems don't contain many files

false, almost 100K on average

New cards
90

true or false: file systems are roughly half full

true, even as disks grow, file systems remain 50% full

New cards
91

true or false: directories are typically large

false, many have few entries, most have 20 or fewer

New cards
92

read()

read from a file -read in first block of the file, consulting the inode to find the block -update inode with newest access time -update in-memory open file table for file descriptor and offset

New cards
93

what happens when a file closes

-If the current content of the r/w buffer is modified, then save the buffer in the corresponding block on the disk. -Update the file length in the FCB. -Free the OFT entry. -Return the status of the close operation to the calling process. the file descriptor is deallocated

New cards
94

write()

update file with new contents -generates 5 I/Os -read data bitmap -write bitmap (to reflect its new state to disk) -two to read and write the inode -write the block itself

New cards
95

true or false: creating a file allocates space for the directory, which causes low I/O traffic

false, high I/O traffic

New cards
96

true or false: cache reduces write I/Os

false, because write traffic has to go to disk for persistence, but does avoid read I/Os with large cache

New cards
97

what is used for write performance benefits

buffering -by buffering the number of writes in memory, the file system can then schedule subsequent I/Os -avoiding writes by delaying them

New cards
98

collision

when two file names hash to the same location

New cards
99

advantages and disadvantages of hash table

decreases directory search time only good if entries are fixed size or use chained-overflow method

New cards
100

why do you have two copies of the FAT

to have a backup in case of system failure

New cards

Explore top notes

note Note
studied byStudied by 3 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 13 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 8 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 39 people
Updated ... ago
4.0 Stars(1)
note Note
studied byStudied by 20 people
Updated ... ago
5.0 Stars(2)
note Note
studied byStudied by 189 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 13 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 156 people
Updated ... ago
5.0 Stars(1)

Explore top flashcards

flashcards Flashcard51 terms
studied byStudied by 21 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard124 terms
studied byStudied by 20 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard101 terms
studied byStudied by 4 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard55 terms
studied byStudied by 5 people
Updated ... ago
5.0 Stars(2)
flashcards Flashcard170 terms
studied byStudied by 6 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard153 terms
studied byStudied by 16 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard150 terms
studied byStudied by 37 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard50 terms
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)