Final Flashcards
(107 cards)
1
Q
Explain What CPU Registers are
A
Fast memory units on the CPU
- split into two categories: control and status registers and user-visible registers
2
Q
What is the Program Counter
A
A register which contains the address of the next instruction to be fetched
3
Q
What is the instruction Register?
A
Register containing instruction most recently fetched
4
Q
Explain the Basic Instruction Cycle
A
- CPU fetches next instruction from memory
- CPU executes instruction
- Program counter is consulted for next instruction and incremented
- CPU must wait for IO to complete
5
Q
Explain how Interrupts fit into the Instruction cycle
A
computers allow IO modules to interrupt the CPU. CPU checks for interrupts after each instruction
and if there are none fetches the next instruction from the current program. If an interrupt is found execution of program is suspended and interrupt handling is entered
6
Q
Explain what an Interrupt Handler is
A
A program that determines the nature of the interrupt and responds accordingly. It then transfers control of the program back to the stored interrupt point of the program
7
Q
List the 4 interrupt Classes
A
IO, Program exception, Timer, Hardware failure
8
Q
Explain what happens with Multiple interrupts
A
further interrupts are disabled during an interrupt. Others remain pending until current interrupt is resolved. Interrupts have priority
9
Q
Explain the three possible Communication techniques for IO operation
A
- Programmed IO - no interrupts (cpu must wait), IO module preforms actions on processors behalf
- Interrupt-driven IO - CPU can execute code during IO operation: it gets interrupted when IO happens - no needless waiting but takes a lot of processor time watching for interrupts
- Direct memory access - block of data is transferred directly from memory without going through CPU
10
Q
Explain Cache memory
A
Small cache of expensive but extremely fast memory which interacts with larger slower memory. Cache is checked first to determine if info is present, if it is, info is used from cache. Otherwise, data is copied from main memory and temporarily stored in the cache
11
Q
Explain Access Time
A
Time to bring referenced word into the processor
Access time for cache (T1) + access time for main memory (T2)= total access time (T)
if word in cache T= T1
12
Q
What is an operating system and what are its goals?
A
An operating system is a program that acts as an intermediary between a user and the hardware by managing resources and conflicts
Goals:
- Execute user programs
- make the computer convenient
- use hardware efficiently
13
Q
What is the Kernel
A
The one program running at all times on the computer. It operates on a different layer than things the user can access and is responsible for providing secure access to machines hardware.
14
Q
Explain the Computer System Structure
A
Can be divided into 4 components
Hardware - cpu, memory, IO devices
Operating System - controls and coordinates use of hardware
Application programs - define the ways system resources are used
Users
15
Q
Explain Storage structure
A
Main memory (RAM) - only large storage media CPU can directly access (volatile)
Secondary storage - extension of main memory that is non-volatile but can’t be directly accessed by CPU
16
Q
What are priveleged Instructions?
A
Instructions that can only be executed in Kernel mode
17
Q
What is the purpose of System Calls?
A
System calls allow user-level processes to request services of the operating system. system calls are
implemented using software interrupts. Realize that the OS is interrupt driven and that interrupts are received
both from the hardware and software as requests to perform some action.
18
Q
Explain the two types of Multiprocessing
A
Asymmetric Multiprocessing - each processor is assigned a specific task but they are all running simultaneously
Symmetric - each processor performs all tasks
19
Q
Explain Multi-programming
A
Multiprogramming organizes jobs so CPU always has one to execute. (a subset of total jobs kept in memory)
one job is selected and run. if a task has to wait on something (say an IO) OS switches to another job
20
Q
What is a Process?
A
A process is a program in execution
21
Q
What activities in regards to process management is the OS responsible for?
A
-Creating and deleting processes
-suspending and resuming processes
-providing mechanisms for process synchronization and communication
-providing methods to handle deadlocks
22
Q
List the 5 Process states
A
new: process being created
running: instructions being executed
waiting: waiting for event
ready: waiting to be assigned to processor
terminated: finished executing
23
Q
Explain the process control block (PCB)
A
Info associated with each process
- program counter - process state - Cpu registers - memory allocated to process - accounting info (cpu used, clock time elapsed) - IO devices allocated and open files
24
Q
Explain the purpose of process scheduling?
A
Maximizes CPU use by quickly switching processes onto the CPU for time sharing. The process scheduler selects next execution from available processes
25
What are the three scheduling queues?
Job queue - set of all processes
Ready queue - all processes residing in main memory (ready)
Device queues - set of all processes waiting for an IO device
26
What are the differences between the long-term scheduler (job scheduler), the short-term scheduler (CPU scheduler) and the medium-term scheduler?
LTS - selects which processes should be brought into the ready queue
- infrequent (seconds, mins) controls the degree of multiprogramming
MTS - can be added if degree of multiprogramming needs to decrease
- performs swapping: removes process from memory and stores it on disk, then brings it back to continue executing
STS - selects which process should be executed next and allocates CPU (milliseconds)
27
Explain the resource sharing options in Process creation
1. Parents and child process share all resources
2. Children share a subset of parents resources
3. no resources are shared
28
Explain the execution options with parents and child processes
1. parents and children execute concurrently
2. parents wait for children to terminate
29
Explain Process Termination
Process executes last statement and aks the OS to delete it. Process resources are deallocated by OS. Parent may terminate execution of child processes (if all children are terminated when the parent is it is called cascading termination)
30
Explain the Two models of Inter-process communication
1. Shared memory
2. Memory passing - processes use send(message) and receive(message) to share info.
31
What is the difference between indirect and direct communication in regards to processes?
Direct - processes name each other explicitly (send(P, message)), a link is established automatically and is associated with one pair of communicating processes (uni bidirectional)
Indirect - messages are directed and received from mailboxes, with each one having a unique id. processes can only communicate if they share a mailbox. a link can be associated with many processes and each pair of processes can share several links
32
Explain How Synchronization works in IPC
message passed may be blocking or non-blocking. Blocking is considered synchronous
blocking send has the sender send a request to the receiver and block until it receives an acknowledgement, non-blocking is asynchronous and has the sender send the message and continue operation
blocking receive has the receiver wait idle until a send message is received. non-blocking has the receiver receive a valid message or null if there is no message yet
33
Explain and list the different types of buffering attached to process links
Queue of messages attached to the link
1. zero capacity - 0 messages can be held and sender must wait for receiver
2. Bounded capacity - finite length of n messages (sender must wait if link is full)
3. unbounded capacity - infinite length, sender never waits just sends
34
What is an Ordinary Pipe
Unidirectional relationships between processes where one end writes and sends what is written to the other end where the other process reads
requires parent-child relationship
35
Explain the difference between named pipes and ordinary pipes
named pipes are like ordinary pipes but bidirectional and they do not require a parent child relationship
36
Explain the difference between threads and Processes
A process is a program being executed via a thread with code, data and other resources. it owns memory, files and resources
A thread is a way of making a distinction between the resources and the executing process. A process is made up of threads so there can be multiple threads which share memory code and files
37
Multicore programming
multi-core - multiple cores are placed on a single chip where each core appears as a separate CPU
38
Explain what Concurrency is?
Supports more than one task making progress
With 1 processor a scheduler provides concurrency
39
Explain the different types of parallelism
Parallelism: implies a system can perform more than one task simultaneously
Data parallelism - distributes subsets of the same data across multiple computing cores and performing same operation on each core
Task parallelism - involves distributing data but not tasks (threads) across multiple computing cores - each thread performs a unique operation
40
What is the difference between user and kernel threads
User threads - supported above kernel, kernel is unaware of them
Kernel threads - supported and managed directly by the OS
41
What are the three ways of establishing a relationship between user and kernel threads?
Many to one: many user to 1 kernel
many to many: many user to many kernel
one to one: 1 kernel to 1 user
42
Explain what signal handling entails with respect to threads
Signal handler processes signals which notify a process when an event has occurs
signal is generated -> signal is delivered to process -> signal is handled by default handler or user defined one
43
The target thread is the thread to be cancelled. How is cancellation handled?
Asynchronous cancellation terminates target thread immediately.
Deferred cancellation allows the target thread to periodically check if it should be cancelled. - this method is employed because cancelling asynchronously can cause issues if a thread is cancelled in the midst of updating data
- A flag indicates whether it is safe to cancel
44
Explain What the Short term (CPU) scheduler does
Schedules the next process, makes decisions when:
1. switches from running to waiting
2. switches from running to ready
3. switches from waiting to ready
4. when process terminates
45
What is the difference between pre-emptive and non-preemptive scheduling?
Preemptive scheduling allows a running process to be interrupted by a high priority process, whereas in non-preemptive scheduling, any new process has to wait until the running process finishes its CPU cycle
- preemptive can cause starvation if a low priority process is butted by many high priority ones
46
Explain the Scheduling criteria?
CPU utilization - keep cpu busy at all times
Throughput - # of processes that complete there execution/time (e.g. 5 seconds)
turnaround time - amount of time to execute particular process
waiting time - total time process in queue
response time - amount of time from when request was submitted until first response
47
Explain the pros and cons of the first come first serve Scheduling algorithm
- First come first serve
convoy effect - short processes can be stuck behind long ones
Pros - simple and easy, costs little time to make scheduling decision
Cons - high waiting time, convoy effect causes poor CPU utilization
48
Explain the pros and cons of Shortest-Job-First
Associate with each process the length of its next CPU burst and use the lengths to schedule the process with the shortest time
non-preemptive - once CPU given to the processes it can't be preempted
preemptive - if a new process arrives with CPU burst length less than remaining time of current execution preempt - optimal
Pros - ensures low average waiting time
cons - can cause starvation
49
Explain the pros and cons of Round Robin
each process gets a small unit of CPU time - after this time has elapsed the process is preempted and added to the end of the ready queue
Average waiting time under RR often longer
typically higher average turnaround then SJF but better response
50
Explain the pros and cons of Priority Scheduling
priority integer associated with each process and CPU allocated to process with highest priority
preemptive and non-preemptive
SJF can be seen as priority scheduling where priority is the predicted CPU burst time
starvation still a problem
51
What are the problems with Concurrency = Parallelism
Concurrency - multiple tasks which start, run and compete in overlapping time periods in no specific order
Parallelism - is about multiple tasks that run at the same time on a hardware with multiple computing resources
Concurrent processes often need to share data and resources. Results of actions performed by concurrent processes will then depend on the order in which their execution is interleaved (program can give different results each execution)
52
What is the critical Selection Problem
Each process has a critical section segment of code where it may be changing variables or writing to file....
If one process is in critical section no others can be
53
How does Peterson's algorithm solve the CSP (critical selection problem)
Algorithmic software solution
2 process example, 2 processes share 2 variables
int turn; boolean flag[2]
flag array indicates if a process is ready to enter the critical section flag[i] = true implies that Pi is ready
54
explain Atomic Access
All solutions to CSP are based on it
memory at a specific address can only be affected by one instruction at a time
55
explain how hardware locks solve the CSP
Two types of special atomic hardware instructions
-test memory word and set value:
shared boolean variable lock, initizalized to false. Each process wishing to execute CS code. solution results in busy waiting
-swap contents of two memory words:
compares contents of a memory location with a given value and IFF they are same modifies the contents that memory location to the new given value
56
Explain how mutex locks solve the CSP
Hardware solution
Mutex locks use an associated boolean variable available to indicate whether lock is available or not
57
Explain how Semaphores Solve the CSP
Hardware solution
has more sophisticated ways of communication than mutex locks for processes to synchronize
uses an integer value instead of boolean
58
What is a deadlock
When two processes try to go into the same nested critical section in a different order
like when two timid people come to a four way stop and neither starts up again until the other has gone
59
Explain the conditions that create a deadlock
1. mutual exclusion: only one process at a time can use a resource
2. Hold and wait: a process holding resources is waiting to require additional resources held by other processes
3. no preemption: a resource can be released only voluntarily by the process holding it upon its task completion
60
What is a safe state?
Safe state = guarantee of no deadlock
Unsafe state = possibility of a deadlock, deadlock avoidance prevents it from entering
System is in a safe state if there is a sequence of all processes such that for each Pj, Pi can still be satisfied with currently available resources
61
Explain What an avoidance algorithm does
It prevents the system from ever entering an unsafe state by knowing the future needs of any resource.
Single instance of resource type - use a resource-allocation graph
multiple instances - use bankers algorithm
62
How does deadlock detection work?
Allows system to enter a deadlock state and recovers it. It uses a wait for graph (where only nodes are processes) and periodically checks if there is a cycle (cycle = deadlock). It requires n^2 operations where n is num of processes
63
How does the system recover from a deadlock?
It aborts all deadlocked processes one at a time until the cycle is eliminated. Choosing order of elimination is done in many ways.
Resource Preemption - selects a victim to minimize cost and rollsback until a safe state and restarts the process from there. Can cause starvation where the same processes may always get picked as the victim
64
What is the purpose of Base and Limit Registers?
They define the logical address space
-base register contains value of smallest physical address
-limit register contains range of logical addresses
Address >= base && Address < base+limit -> access memory
otherwise it is a trap
65
What are the timings of address binding?
Programs on disk, ready to be brought into memory to execute form an input queue
Compile time: if memory location known prior
Load time: must generate relocatable code if mem location not known at compile time
Execution time: binding delayed until run time
66
What is the difference between logical and physical address space?
Logical address - generated by the CPU
Physical address - the physical memory seen by the memory unit
67
What is the MMU and what does it do?
Memory management unit is a hardware device that at run time maps virtual addresses to physical ones
e.g. value in relocation register (base register) is added to every address generated by a user process
68
Explain dynamic linking
Static linking - when system libraries and program code combined by the loader into the binary program image
Dynamic linking - essentially shared libraries. static linking but postponed until execution, a small piece of code called the stub is used to locate the appropriate memory resident library routine
69
What is swapping?
When a process is swapped temporarily out of memory to a backing store and then brought back into memory to continue execution
- total physical memory space of processes can exceed physical memory
- major part of swap time is transfer time
70
Explain the two swapping methods
Backing store - fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to those images
Roll out, roll in - swapping variant for priority based scheduling algorithms. lower priority process is swapped out so higher one can be executed
71
What is context switch time including swapping?
if next process to be put on cpu not in memory it needs to be swapped out with another
100mb process with transfer rate of 50mb/sec
-> swap out and swap in time of 2000ms (4000ms total)
72
What is a hole and how is it used?
A hole is a block of available memory
when a process arrives, it is allocated memory from a hole large enough to accommodate it
73
What is the Dynamic storage-allocation problem?
It is the problem of how to satisfy a request of size n from a list of free holes
- first-fit: allocate first hole big enough
- best-fit: allocate smallest hole big enough
- worst-fit: allocate largest hole
74
Requirements a solution to CSP must satisfy
Mutual exclusion: only one process can be in the critical section at any moment of time
Progress: if some processes want to enter the CS and there is no process in the CS, eventually one of the processes will
enter the CS.
Bounded Waiting: (starvation free) a process waiting to enter the CS can be overtaken only finite number of times
before being give access to the CS
75
Explain what fragmentation is and the two different types
When processes load and unload they fragment the available memory, leaving memory blocks too small to contain any processes and thus useless.
Internal fragmentation occurs when there is unused space within a memory block.
External fragmentation occurs when a storage medium, such as a hard disc or solid-state drive, has many small blocks of free space scattered throughout it.
76
How do you reduce external fragmentation?
Compaction, shuffle memory around to place all free memory together in one large block. however this is only possible if memory relocation is dynamic
77
What is segmentation?
A way of organizing processes in memory, a process is divided into segments.
It creates a segment table which maps a two-dimensional Logical address into a one-dimensional Physical address. It’s each table entry has:
Base Address: It contains the starting physical address where the segments reside in memory.
Segment Limit: Also known as segment offset. It specifies the length of the segment.
78
What does contiguous mean?
being in contact. two things are contiguous if they are touching on a boundary point
79
What is paging?
A memory scheme which eliminates the need to contiguous allocation of physical memory. It divides physical memory into fixed sized blocks called frames. Logical memory is divided into same size blocks called pages. A page table translates logical memory to physical addresses
A list of free frames is kept
80
How are pages located?
page number (p) - used as an index into a page table which contains base address of each page in a physical memory
page offset (d) - combined with base address to define exact address
p = m - n, d = n where logical address space = 2^m and page size 2^n
81
Explain what Translation look-aside buffer (TLB) is
Page table kept in main memory, page-table base register points to page table and page-table length register indicates the size. This means 2 memory accesses necessary for every instruction
TLB's solve this by directly storing page and frame number (Address space identifiers). like the cache if an address isnt in TLB it is loaded there form next time
82
How is memory protection done with page tables?
Memory protection bit is associated with each frame to indicate if read-only or read-write is allowed
a valid-invalid bit is attached to each entry in the page table and indicates that associated page is in the processes logical address space
83
Explain Hierarchical page tables
Page tables can get very large so it is hard to find contiguous space in main storage. The logical address space is broken into multiple page tables which point to each other
e.g. 2 level paging - 32 bit machine with a page number of 22 bits and offset 10 bits
can become p1 12 bits | p2 10 bits | d 10 bits
84
What is an inverted page table
Doesn't keep track of logical pages, but physical ones. It has one entry for each real page of memory
85
What is partial loading?
Code needs to be in memory to execute but the entire program is rarely used. Partial loading is the ability to execute a partially loaded program
86
What are the advantages of partial loading?
More processes can be maintained in memory since only parts are loaded. Memory won't fill up on bloated unused parts of processes. CPU utilization is increased too since more processes in ready state
87
What is virtual memory?
A storage allocation scheme in which secondary memory can be accessed as though it were apart of the main memory. Virtual addresses are mapped into physical addresses in memory.
88
What is demand paging?
A continuation of virtual memory, it brings a page into memory only when it is needed by using swapping
page is needed -> reference to it
- invalid reference = abort
- not in memory = bring to memory
89
What is the valid-invalid bit in regards to paging?
Each entry in a page table has a valid invalid bit where i = non-in memory v= in memory
90
What is a page fault?
A page fault occurs when a program references a virtual memory page that is not currently resident in physical memory. This happens when the required page has been paged out to disk or has not been accessed yet. When a page fault occurs, the operating system handles it by fetching the required page from disk and updating the page tables to reflect the new mapping.
91
What is copy-on-write?
An optimization which allows both parent and child processes to initially share the same pages in memory. It copies the pages if either process modifies them
92
What is page replacement and why is it necessary?
Page replacement occurs when we are trying to bring a page into memory and there are no free frames. The computer finds a page in memory and swaps it with that one trying to find one to replace that will cause the least page faults
93
List the three Page replacement algorithms and explain how they work
First in first out - OS maintains a queue of pages and first one in is first out
Optimal - replaces a page that wont be used for the longest period of time - impossible to determine and only used to evaluate other algs
Least Recently Used - time of last use is associated with each page and the least recently used one is replaced
94
Explain the frame allocation schemes
Equal allocation - split m frames among n processes equally (100 frames 5 processes = 20frames/process)
Proportional allocation - allocate according to size
si = size of process pi
S = sum of all si
m = total number of frames
ai = allocation for pi = (si/S) * m
95
What is the difference between global and local allocation?
Global replacement - process selects replacement from set of all frames. process execution time can vary greatly but it has a greater throughput
Local replacement - process selects only from its own frames. more consistent per-process performance but it can cause thrashing if there is not enough allocated frames
96
What is thrashing?
Thrashing is when a process doesn't have enough frames, which causes the page fault rate to be very high. A page fault occurs and a page is replaced because of it, then the replaced page is needed again so another page fault occurs
97
What is a file?
A continuous logical address space with a type, attributes and operations
A file is typically viewed as a numbered sequence of blocks or records
98
What is a directory and what structures can it have?
- directory is a collection of nodes containing information about a file
Single level directory - each entry leads to a file
two-level directory - separate directory for each user -> user directory leads to single level directory
Tree-structured directory - root directory at the top with any number of subdirectories which can lead to files or other directories
Acyclic-Graph Directory
99
Explain the Acyclic-Graph directory in detail
- result of shared sub-directories and files
when a file is changed both people view even though the file can have different names to both
Link - pointer to an existing file or sub-directory to ensure file is found even if name is different
100
List the Disk space allocation methods and explain them:
Contiguous allocation: each file occupies a set of contiguous blocks - normally best performance since its simple but it can be difficult to find space for files
Linked allocation: each file is a linked list of blocks -> locating a block could take many IO's and efficiency can be improved by clustering blocks
Indexed allocation: each file has its own index blocks of pointers to its data blocks - extra space for index
101
What is a bit map?
A bit map is a way of free space management
bit[i] = 1 -> block[i] is free
bit[i] = 0 -> block[i] is occupied
102
What is a free list
A way of free space management
A linked list is used where a free block is linked to another........ until the last free block
103
How does an HDD work
like multiple record players stacked on top of each other. It has multiple disks stacked on top of each other and arms that read a part of the disk. The disks are divided into cylinders which the head reads
104
Explain the disk structure
Disk drives are large 1-d arrays of logical blocks
1D array is mapped onto sectors of the disk sequentially - sector 0 is first sector of the first track on the outermost cylinder
105
What is the Scan algorithm?
Alg for reading info from the disk
Disk arm starts at one end and moves towards the other servicing requests the whole way, when it reaches the end it does the same thing but back toward the start
106
what is C-scan?
Like scan except instead of going to the end and then traversing back to the start, when the head reaches the end it travels back to the start without fulfilling requests.
107
Explain Raid structure
Redundant array of inexpensive disks
they store redundant data by mirroring or storing a duplicate of each disk on another disk
