Definitioner Flashcards
1
Q
What is stored in the Process Control Block?
A
Process scheduling state, structuring information, privileges, state, pid, program counter, CPU registers, information of page table.
2
Q
What is PCB role?
A
Used and modified by OS utilties (scheduling, memory, I/O resource access). The set of PCBs defines the current state of the operating system.
3
Q
What is the process control block?
A
Is a data structure in the operating system kernel contraining information needed to manage the scheduling of a particular process.
4
Q
Where is PCB stored?
A
In some OS it is stored in the beginning of the kernel stack of the process. (within the OS kernel).
5
Q
What is context switch?
A
Is the process of storing the state of a process, so that it can be restored and execution resumed from the same point later. It is essential to virtualization of CPU.
6
Q
What information is stored and recieved when performing a context swithc between threads?
A
No TLB flush is necessary, they share same adress space.
7
Q
What happens during a context switch?
A
The processimage (registers of the process, PC) is stored in PCB. A handle to the PCB is added to a queue of processes that are ready to run. It restored the PCB of next process scheduled to run. PC from that PCV is loaded and execution can continue.
8
Q
What makes context switch costly?
A
TLB flushes,
9
Q
Thread control blocks
A
No need to switch page tables (same address space).
10
Q
Thread-local storage
A
The stack of the relevant thread.
11
Q
Parallelism
A
Do work on multiple CPU using threading, one thread per CPU
12
Q
Race condition
A
Arises if multiple threads of execution enter the critical section at roughly the same time; both attempt to update the shared data strucutre, Results is nondeterministic
13
Q
Critical section
A
Code that can result in race condition. Piece of code that accesses a shared resource, usually a variable or data structure.
14
Q
Mutual exclusion
A
Guarantees one thread at a time executing within critical section.
15
Q
Atomically
A
As a unit, all or none.
16
Q
Condition variable
A
To wait for a condition to become true, is an explicit queue that threads can put themself on when conditions are not met, another thread can wake that thread by signaling that condition.
17
Q
Semaphore
A
A semaphore used as a lock is called a binary semaphore. Is a powerful and flexible primitive for writing concurrent programs. Simple and utility.
18
Q
Spin-waiting
A
Endlessly checks the value of flag
19
Q
Preemptive scheduler
A
One that will interupt a thread via a timer.
20
Q
Yield:
A
A system call that moves the caller from running state to ready state (process deschedules itself)
21
Q
Priority inversion:
A
A thread of higher priority tries to acquire an lock that is already lock, it will do it indefiently.
22
Q
Two-phase lock:
A
Uses a spinlock, if not lock is acquired during first spin phase, a sacond phase is entered, where the caller is put to sleep, and only woken up when the lock becomes free later.
23
Q
Compare-and-swap
A
Test whether the value at the address is equal to expeted, then update memory location with the new value, if not do nothing.
24
Q
Overlap
A
Avoid blocking program due to slow I/O.
25
Advantages with threads
Threads better then processes when sharing data between eachother.
26
Perfect scaling
Even though more work is done, it is done i parallel, and hence the time taken to complete the task is not increased.
27
Sloppy counter
One local counter per CPU core and one global counter, local values are periodically transferred to the global counter. If threashold is low scalabiity is low but global value more accurate.
28
Big kernel lock
One big lock, not good on multi-CPU systems
29
True or false
Concurrent counters not scalable using locks.
30
Reader-Writer lock
When acquiring a read lock, reader first acquires lock and then increments the readers var to track how many readers are currently inside the data structure. The reader also acquires the write lock.
31
How to combat deadlock
reak the symmetry, let one of that philisopher grab the right before the left. (dijkarsta solution)
32
Atomicity violation
The desired serializability among multiple memory accesses is violated. (locks around shared-variable references can solve it)
33
Order violation
The desired order between two memory accesses is flipped. (enforce ordering using condition variables)
34
Encapsulation:
Hiding code, using abstraction.
35
Conditions for deadlock
hold-and-wait, no preemption, circular wait
36
Hold-and-wait:
Threads hold resources allocated to them while waiting for additional resources.
37
No preemption
Resources (locks) cannot be forcibly removed from threads that are holding them.
38
Circular wait
here existst a circular chain of threads such that each thread hold one or more resources that are being requested by next thread in chain.
39
Total ordering:
Strict ordering of which locks to acquire prevents circular wait.
40
How to prevent hold and wait
Hold and wait can be prevented by having a lock for the locks we are acquiring. It is likely to decrease concurrency becuase we are not acquiring the locks when truly needed.
41
Livelock:
Two threads could both be repeatedly attempting this sequence of locking, trylocking, unlocking..
42
How to avoid deadlocks
Avoid deadlocks by avoid the need of mutex. (By using powerful hardware instructions to build data structures which does not require expkicit locking).
Deadlock avoidance: Schedules threads to guarantee no deadlock can occur. Can reduce perfomance as time for total completion can increase.
Detect and recover: IF deadlocks are rare this strat is ok. It finds deadlock and restart.
43
Event-based concurrency
Wait for an event to occur, check for type, and do the small amount of work it requires (I/O req, scheduling other events)..
44
Event handler
The code that processes each event. Blocking when thread does systemcall. Can be solved with asynchronous I/O and signal handlers.
45
Signal handler
Some code in the application to handle an incomming signal.
46
Manual stack management:
In a thread-based program the state the program needs is on the stack of the thread.
47
Event-based problems
If an event-handler page faults it will block. On multiple cores when need an eventhandler on each CPU and locks over the critical sections. Hard to implement.
48
Memory bus (proprietary)
CPU & memory
49
General I/O bus
PCI, connecting Graphics card
50
Peripheral bus
SCSI, SATA, USB
51
Status register:
Can be read to see the current status of the device.
52
Command register:
To tell the device to perform a certain task.
53
Data register:
To pass data to/from the device. OS controlls the device behaviour through these registers.
54
Programmed I/O
When the main CPU is involved with the data movement.
55
Interrupt handler
Operating system code that will finish the request. We utilizze interrupts for overlap. The OS can do something else while waiting for disk.
56
Two-phased hybrid approach
Using both polling and interrupt, good if we dont know the speed of the device.
57
Coalescing:
A device which needs to raise an interrupt first waits for a bit before delivering the interrupt to the CPU.
58
Deriect Memory Access (DMA)
DMA enginge is a very specific device within a system that can orchestrate transfers between devices and main memory without much CPU intervention.
OS programs the DMS engine, DMA controllers raises an interrupt and the OS knows transfer is completed.
59
I/O instructions:
These instructions specify a way for the OS to send data to specific device registers. These instructions are usually privileged.
60
Memorymapped I/O:
The hardware makes device registers available as if they were memory locations. Access registers with load (to read), store (to write) the address.
61
Device driver:
A piece of software in the OS knowing the detail of how an device works.
62
IDE interface
Wait for drive to be ready, write parameters to command registers. Start the I/O. Data transfer, handle interrupts, error handling.
63
Hard disk drive
Drive consists of large number of sectors (512-byte blocks). Each can be writted or read. Disk array of sectors. 0-n-1 is address space of drive.
Single 512-byte write can be atomic.
64
Torn write
Only a portion of a larger write may complete.
65
Disk scheduling:
Know how long each request will take, and will try follow principle SJF (shortest job first). By estimating seek and possible rot delay of a request.
66
Disk head
Reads and writes to disk.
67
Rotational delay
Time it takes for the desired sector to rotate under the disk head.
68
Disk arm:
Moves diskhead acress the surface to position head over desired track.
69
Seek:
The arm moves head to desired track.
70
Transfer:
FInal phase of I/O, data is either read from or written to the surface.
71
How is the information retrieved and taken from disk?
Seek -> Wait for rotational delay -> transfer
72
Multi-zoned disk drives
Disk is organized into multiple zones.
73
Cache (track buffer)
So it can stored read memory and read multiple sectors on that track to save time.
74
Write back:
Acknowledge the write completed when it has put the data in its memory.
75
Write through:
Acknowledge the write completed after write actually been written to disk. Can be dangerous if application require data to be written in a certain order for correctness.
76
Random workload:
Issues small reads to random locations on the disk.
77
Sequential workload:
Reads a large number of sectors consecutively from the disk without jumping around.
78
SSTF,
Shortest Seek Time First: Orders the queue of I/O request by track picking nearest track. This is abstracted to the OS, so it can instead implment nearest block first (NBF). Can lead to starvation.
79
SCAN:
Moves back and forth acress the disk servicing request in order across the tracks a sweep.
80
F-SCAN:
Freezes the queue to be serviced when it is doing a sweep. SCAN is called elevator algorithm.
81
I/O merging:
Is important at the OS level, reduce the number of requests sent to disk, (merge the requests for blocks 33 and 34) into a single two-block request.
82
Work-conserving
Send I/O request, even a single one asap to the drive.
83
Anticipatory disk scheduling:
By waiting new and "better" request may arrive at the disk and overall efficiency is increased.
84
Redundant Array of Inexpensive Disks (RAID):
A technique to use multiple disks in concert to build a faster bigger more reliable disk system. Transparency improves deplayability of RAID. RAIDs consists of a microcontroller that runs firmware to direct the operation of the RAID, volatile memory such as DRAM to buffer data blocks as they are read and written.
At a high level, a RAID is like a specialized computer system (processor, memory, disks).
85
Fail-stop fault model:
Disk can either be in state working or failed. A working disk, all blocks can be read or written.
86
Three objectives of RAID
Capacity, reliability, performance
87
RAID Level 0 (striping):
Spread the blocks of array across the disk in a round-robin fashion.
88
File:
A linear array of bytes. Has a low-level naem which user is not aware of. Name = inode number
89
Directory:
Has a low-level name and contains a list of entries (user-readable name, low-level name). Filename makes system easier to use and more modular.
90
File descriptor:
Is an integer, private per process and is used to access files. (Pointer to an object of type file).
91
fsync()
The file system responds by forcing all dirty (not yet written) data to disk, returns when all writes a complete. Often forgotten to fsync the directory file is within.
92
Metadata:
Data about files.
93
Inode
Containing metadata (persistent data structure kept by the file system that has information like metadata in it).
Inode can refers to dta blocks with direct pointers (disk addresses) inside the inode. Can limit the size of the file becuase inodes are limited in size and cant have to large amount of pointers.
94
Remove:
unliks the file.
95
Mkdir:
A directory is created, has two entries (one entry refer to itself, and the other one refers to its parent). Me = . parent = ..
96
link:
Create another name in the directory and refers it to the same inode number of the original file. You have two human names that refer to the same file.
97
Link count/reference count:
Allows file system to track how many links are to that inode. If reference count reaches zero file system free the inode and related data blocks (and truly delete file).
98
What you cant hard link
You cant create a hard link to a directory (create a cycle in the directory tree); you can't hard link to files in other disk partitions.
99
RAID Level 1 (mirroring):
consists of an exact copy (or mirror) of a set of data on two or more disks; This layout is useful when read performance or reliability is more important than write performance or the resulting data storage capacity.[13][14]
100
RAID Levels 4/5 (parity-based redundancy).
consists of block-level striping with a dedicated/distrubited parity disk. Double writing load. Parity deive used to provide fault tolerance.
101
Partitionering
Is the creation of one or more regions on a hard disk, so that an operating system can manage information in each region seperatly. (making the storage device visisble to an operarting system). Writing information into blocks of a storage device.
102
Directory:
Has a low-level name and contains a list of entries (user-readable name, low-level name). Filename makes system easier to use and more modular. Specific type of file that store name -> inode-number mappings.
103
Mounting
akes an existing directory as a target mount point and essentially pasta a new file system onto the directory tree at that point. Unifies all file systems into one tree.
104
Filesystem
Is a way that an operating system organizes files on a disk.
105
Data region
Region of the disk we use for user data.
106
Inode table:
Holds an array of on-disk inodes.
107
Allocation structures:
Are data blocks free or allocated. Free list (points to first free block) or bitmap
108
Bitmap:
One bitmap for data region, and one for the inode table (inode bitmap).
109
Superblock:
Contains information about this particular file system (how many inodes and data blocks are in the file system, where inode table begins, and magic number
110
Allocation structures:
Track which inodes or data blocks are free or allocated.
111
Indirect pointer
Points to a block which contains more pointers, each point to user data.
112
Multi-level index approach:
Indirect pointers to indirect pointers.
113
Fat allocation table
Uses linked list as a data structure to point to data blocks. Doesnt have inodes but directory entries to store metadata. Hard link is not possible.
114
Free space management:
Track which inodes and data blocks are free and which are not so file system can find space for new allocated file or directory.
115
File system cache:
Becuase the number of I/O each open, write and read system call invokes
116
Dynamic partitioning:
Many modern operating systems integrate virtual memory pages and file system pages into a unified page cache.
117
Write buffering
Delays writes, the file system kan batch some updates into a smaller set of I/O. Buffering number of writes to memory.
118
Static buffering:
Easier to implement, more predictable perfomance.
119
Dynamic buffering:
Achieve better utilization, but can be more complex to implement.
120
File system purpose
Tries to give an abstraction of data with files and directories.
121
Amortization:
The process of reducing an overhead by doing more work per overhead.
122
Sub-blocks
A bigger block divided into smaller pieces that store data until it grows to size of a block and is transfered to that block and then is freed for future use.
123
Parameterization:
FFS would figure out the specific performance parameters of the disk and use those to decide on the exact staggered layout scheme.
124
fsck (file system checker):
Checking after reboot for filsystems inconsitancy, space leaks and such, fixs them. Cant find fault when inode points to garbage. Runs before the file system is mounted and made available
125
Fsck does
Check superblock looks reasonable, compares file system size is greater than the blocks that have been allocated.
126
Free blocks
Next fsck scans the inods, indirect blocks.. to build an understanding of which block are currently allocated within the file system. Trust the inodes and correct bitmaps
127
Circular log:
Journaling file systems treats log as a circular data structure, re-using it over and over.
128
Journaling (write-ahead logging):
techniques for providing atomicity and durability (two of the ACID properties) in database systems. In a system using WAL, all modifications are written to a log before they are applied. Usually both redo and undo information is stored in the log.
129
Crash scenarios:
Incosistency in file system data structures, space leaks, return garbage data to a user.
