[CSCI 51.02] Operating Systems - Lecture | Long Test 2 Flashcards

what are the 2 types of process involved in process creation?

parent and child process

what are the 2 things a parent can do after process creation?

1. continue execution and run concurrently with its children

2. wait until some or all children have finished before continuing execution

what is the common ancestor / root process of all processes in most unix systems? and what is its ID?

init; ID1

what is the system call in unix to create a new process?

fork()

what are the 2 possible numbers fork() will return, assuming it does not error?

0 (terminated), processID

what makes execve() system call different from fork()?

parent's memory space is replaced by child and parent "dies" without even returning an exit code. in fork() only a copy is created and assigned to child and parent still continues execution

(T/F) unix' kill command is a way for process to be terminated by another process

true

what system call does the process use to terminate?

exit()

what is the difference of independent and dependent processes?

independent: do not share any data and are not affected by other processes dependent: share data and can affect/be affected by other process via shared data

name 2 reasons why you'd want to be sharing data with other processes

1. Information sharing

2. Computation speedup

3. Modularity

4. Convenience

what is another name for threads?

lightweight processes

(T/F) a heavyweight process is effectively a multi-thread program

(F) it is a single-thread program

as a thread, what do you call other threads of the same program?

peers

what makes threads have less overhead and make context switching less expensive than heavy weight processes?

less memory management -> no need to copy program code as only thread-specific data needs to be saved and loaded

(T/F) threads have protection from other threads

false

what does IPC stand for?

interprocess communication

what are the 2 types of communication link that must exist between 2+ processes? describe each

unidirectional link: can either send or receive but not both

bidirectional link: all connected processes can send and receive

(T/F) in name referencing, the parameter for direct communication is the name or ID of a mailbox accessed by other processes

(F) this is indirect communication

(T/F) the links in direct communication are between exactly 2 processes and are usually unidirectional

(F) it is bidirectional

(T/F) in indirect communication, the mailbox is owned only by the system

(F) by process or the system

what is the different of symmetric and asymmetric direct communication?

symmetric: sender and receiver know each other's name

asymmetric: sender knows receiver's name, receiver will be notified of sender's name when receiving

what is the main disadvantage of direct communication?

limited modularity; processes must know each other and changes require updates

what does link capacity / buffer size determine?

# of messages that can reside in it temporarily

when link capacity has 0 capacity, what do you call the synchronization needed for a message transfer to take place?

rendezvous

what is the endpoint of communication?

a socket

what does RPC stand for?

Remote Procedure Call

what condition occurs when several processes access and manipulate shared data concurrently?

race condition

what is a critical section?

process may be manipulating shared data

to solve the critical section problem, what are the 3 requirements of a good algorithm? explain each

1. Mutual Exclusivity: if a process is in its critical section, no other process is allowed in theirs

2. Progress: if no process is in critical section and some process wants to enter theirs, only those not in their remaining sections will participate in decision of which will enter next

3. Bounded Waiting: there must be a limit on # of times other process can enter critical section after a process made a request and before the request is granted. tldr: processes shouldnt starve

(T/F) a basic implementation of all process looks like:

ENTRY section → CRITICAL section → EXIT section → REMAINDER section→ loop while (true)

true

what is an atomic function also known as?

linearizable function

(T/F) the process' busy waiting by looping continuously until a certain condition holds true to enter its critical section is called deadlock

(F) it is spinlock

instead of busy waiting, a process can block itself. what actually happens?

place process in waiting queue associated with process group and allow a context switch to occur

how does a blocked process unblock itself once a process leave its critical section?

wakeup operation

what is a semaphore?

a variable (special int) accessed through atleast 2 atomic (uninterruptible) operations: wait and signal

what is a deadlock?

a set of processes is in a deadlock state if every process in the set is waiting for a resource that can only be released by another process in the set

what are the 4 deadlock conditions? describe each

1. Mutual Exclusion: at least one resource is in non-shareable mode

2. Hold and Wait: there is a process holding at least one resource and is also waiting to acquire other resources held by other processes

3. No Preemption: resource can only be released voluntarily by a process after completing its task

4. Circular Wait

in a system resource allocation graph, what are resources represented?

squares and dots

what are the 3 methods for handling deadlocks?

prevention, avoidance, detection and recovery

what is mutex?

mutual exclusion (non-shareable resource): at least one resource is in non-shareable mode

in deadlock prevention, how would you remove the deadlock condition of "hold and wait"?

Process must successfully request all necessary resources before being allowed to execute. guarantee that a process does not hold a resource when requesting another

what is the risk when you try to remove the 'no preemption' condition for deadlock prevention?

starvation

whats the problem for trying to remove the 'mutual exclusion' condition in deadlock prevention?

okay for shareable resources (like read-only files) but impossible for non shareable resources (like printer). cannot prevent mutex for all resources

in the resource-allocation graph, a claim edge may be added, denoted by a dotted arrow. what does this mean?

process may request resource in the future

explain banker's algorithm as a solution for deadlock avoidance

• Ensure system does not allocate available cash (resources) such that it can no longer satisfy the needs of all of its customers (processes)

• System determines whether to allocate a resource or not

• If granting request maintains safe state, then allocate

• Otherwise, make the requesting process wait for other processes to release certain resources

in deadlock detection and recovery, what are the 2 methods for process termination? and what are their drawbacks?

1. abort all deadlock processes; expensive though as they may have already computed for a long time

2. partial termination so abort one process at a time until cycle is eliminated; have considerable overhead since the detection algorithm has to be called after each abort

what are the 3 factors to consider when you do resource preemption until deadlock cycle is broken?

1. Selecting a victim - choose process with minimal cost

2. roll back - restart process from some safe state; this is difficult to determine and will require system to keep information about the state of all processes as they run

3. Starvation - if a process has to be selected as a victim multiple times, ensure that it can only be picked a finite number of times

what is memory sharing?

computers keeping several processes in main memory

what are the 3 types of memory addresses?

Symbolic: program variables (int i, double x, etc)

Relocatable: aBaseAddress + someOffsetValue

Absolute: a number representing the actual address

what is address binding?

binding instructions/data to memory addresses

how many chapters does TWSA have?

3149

difference of compile, load, execution time binding?

1. Compile Time: compiler generates absolute code for execution in a fixed address

2. Load/Link time: compiler generates relocatable code, then link-loader computes addresses during link time

3. Run/Execution time: Think of it as either compile- or link-time binding, but relevant segment register values are added to all addresses and the sum is the actual address passed to the memory unit

(T/F) physical address is also known as virtual address, especially if the logical and physical address are not the same

(F) it is the logical address that is also known as virtual address

difference of logical and physical address?

logical: generated by CPU, known as virtual address

physical: address loaded into the memory unit, actual value "seen" by memory unit

(T/F) compile-time and execution-time bindings generate identical logical and physical addresses

(F) compile-time and load-time only

what does MMU stand for? and what does it do?

Memory Management Unit: maps virtual to physical addresses during run time

for better memory-space utilization, many programs typically employ what things? explain each

1. Dynamic Loading: subroutines are stored on disk in relocatable format and are not loaded until called. libraries/binaries are never loaded if never used

2. Dynamic Linking: programs that use shared dynamic-link libraries (.ddl) have stubs and these are used as pointers to DDL's procedures

3. Overlays: only keep needed instructions in memory, overwrites previous if no more space. similar to demand paging, but it is by developer and not by O/S

why do only writable data segments need to be swapped out of memory to a backing store while read-only code segments are just rewritten?

Because the read-only, the CPU already has access to the original version anyway so it can be overwritten.

what are the 2 segment registers? describe what each contains

1. Relocation Register: contains the value of the smallest physical address that the process occupies; added to the logical address to get the correct physical address

2. Limit Register: contains the value that a logical address for the process should not reach. if the logical address is >=, then an addressing error will be sent out

what are the 2 possible algorithms for contiguous memory allocation methods? describe them

1. Single-Partition Allocation: where high memory is used for one process at a time

2. Multiple-Partition Allocation: where several processes can reside in memory at the same time

what is the difference of fixed and dynamic multiple-partition algorithm?

Fixed: each partition is allocated a process; degree of multiprogramming limited to # of partitions

Dynamic: starts with one large unused memory block then when a process arrives, its allocated a block

what does atomic mean?

uninterruptible

in dynamic multiple-partition algorithms, what do you call the one large unused memory block it starts of with?

hole

in dynamic multiple-partition algorithm, whats the difference of first-fit, best-fit and worst-fit and what are its strengths?

1. First-fit: allocate first hole big enough for the process; search can start from beginning or end; generally, the fastest

2. Best-fit: allocate smallest hole big enough for the process; generally, the most efficient in space utilization

3. Worst-fit: allocate largest hole; this results in a larger leftover hole, which tends to be more useful than the leftover hole generated by the best-fit approach

what is fragmentation?

free memory is broken into useless little pieces after many allocations and deallocations

what is external fragmentation?

Refers to having enough total memory exists for an incoming process but it is NOT contiguous

(T/F) the 50% rule of external fragmentation states that 50% rule: given N allocated blocks, the next N/2 blocks will be lost due to fragmentation (⅓ of all blocks become unusable) when best-fit is used

(F) when first-fit is used

what is the solution for external fragmentation? explain the 2 algorithms for that solution

compaction: Shuffle memory contents to place all free memory together in one block

algo1: move processes to one end

algo2: create a big hole in the middle

difference of external vs internal fragmentation?

External: holes in the original big empty space

Internal: holes in the allocated memory blocks for each process. always happens when the memory given to process is larger than the requested amount.

what is paging?

Allows non-contiguous allocation and therefore solves external fragmentation problem

what are fixed-size blocks in paging in logical and physical memory?

logical: pages

physical: frames

what is a page table?

allows pages to point at frames using address translation hardware

what is the advantage of a page table structure in paging?

Most operating systems simply allocate the page table in the corresponding process' PCB. this results in increased context-switch time.

what is the advantage of shared pages in paging?

possibility of sharing code; can contain reentrant code

what is reentrant code?

Pure code (R/O, X/O) can be run even if another process is already running it, so only one copy is needed. But each process still needs its own data (R/W)

what is segmentation and what is it used for?

divide logical memory into segments. this provides a more intuitive view of memory from user's POV

each entry in a segment table consists of what?

segment base (starting address in physical memory) and a limit (length of segment)

(T/F) Segmentation eliminates internal fragmentation, but may cause external fragmentation. Compaction can be used to solve that.

true

what is a file?

unit of logical storage

purpose of file system?

provides a mechanism for online storage and access to both data and programs; most visible aspect of an O/S and readily available to users

(T/F) the file's inode stores all attributes of / information about the file except only for actual file data and file name.

(F) also except file location

for a file's data, the inode contains pointers to:

12 direct blocks

1 single indirect block

1 double indirect block

1 triple indirect block

difference of direct vs indirect block?

direct: file data

indirect: pointers to other blocks containing pointers

(T/F) file system is broken down into partitions (Mac) or volumes (PC)

(F) partitions is PC and volumes is for Mac

what are the 5 logical schemes of a directory structure? briefly describe each if possible

1. single-level: all files are in a single root directory

2. two-level: there is a dedicated user file directory for each user

3. tree-structured

4. acyclic graph

5. general graph

what are the 3 access groups in file protection?

owner (or user), group, universe (for others or public)

bytes in 1KB?

1024

4 allocation methods?

1. Contiguous Allocation

2. Linked Allocation

3. File Allocation Table (FAT)

4. Indexed Allocation

(T/F) contiguous allocation is prone to internal fragmentation

(F) external

what 2 information is needed for contiguous allocation in file management?

starting location and length of file

what is the problem of linked allocation in file management?

pointersize may become too large and each access has overhead due to block traversal

what does FAT stand for?

File Allocation Table

what is indexed allocation in file managent?

Each file has its own index block which contains pointers to all file blocks

(T/F) the pointer overhead in indexed allocation is larger than the one in linked allocation

true

what was file allocation table (FAT) superseded by?

New Technology File System (NTFS)

what kind of list does the system use to keep track of free disk space?

free space list

(T/F) in a bit vector, 0 = allocated and 1 = free

true

free space management methods?

1. Bit Vector

2. Linked-List

3. Grouping

4. Counting

(T/F) in linked-list free space management, the first free block is kept in secondary memory

(F) kept in main memory

in linked-list free space management, it uses what number to indicate a free/unused cluster?

0