All Lectures Flashcards
1
Q
What are the goals of an OS?
A
- Allow user to use applications
- Allow applications to use computer resources
- Allow users and applications to interact
2
Q
What are the three key abstractions of an OS?
A
Process
-Instance of a program
Memory (Address) Space
-The range of memory locations that a process can access
File
-A stream of data
3
Q
How does each layer in the system implement its set of services?
A
It implements its services by using the layer below it and providing its services to the layer above it.
4
Q
Identify and describe the two modes of the CPU
A
Supervisor (Kernel) mode:
- Access to all hardware, I/O and memory
- Can execute ALL CPU instructions
User mode:
- Program running on CPU is restricted from accessing all devices or memory
- Can only execute a restricted set of CPU instructions
5
Q
What is the kernel?
A
O/S that is loaded into memory when the computer starts up.
Resides in memory at all times
Runs in supervisor mode
6
Q
What are the roles that the kernel plays?
A
- protects the hardware and processes
- manages hardware and resources
- provides an execution environment for the processes
- creates and runs processes
- services process requests
7
Q
Define process
A
A process is a running instance of a program in memory.
8
Q
How does the kernel get control back from a process?
A
Through system calls and interrupts
9
Q
What happens when there is an interrupt?
A
CPU switches to kernel mode. CPU uses an interrupt id to index into the interrupt table. Invokes interrupt handler, switches back to user mode, returns to where the process was before the interrupt.
10
Q
What is the purpose of interrupts?
A
- Help the kernel gain control of the CPU
- Notify the kernel of I/O
- Help processes make requests to the kernel in a controlled way
- Notify the kernal of errors
11
Q
How does the kernel get control of the CPU if no interrupts occur?
A
The timer.
12
Q
What is the importance of the timer?
A
The timer allows the kernel to gain control of the CPU on a regular basis. No process can monopolize the CPU because kernel can switch to another process.
13
Q
How do processes make requests to the kernel?
A
Using a trap (software interrupt).
14
Q
What is context switching?
A
When an interrupt handler runs the current process has to be context switched out and the kernel context has to be context switched in
15
Q
How does context switching work?
A
The handler copies all registers from CPU to memory, initializes all registers to what the kernel expects, switches to the kernel stack, runs the handler
To switch back:
Switches to the processes stack, copies registers from memory to the CPU, returns from where the process left off
16
Q
What is a process composed of?
A
CPU context
•Memory space
•Thread of executtion
17
Q
Describe the CPU context of a process
A
General registers,
Program counter
Special purpose registers
18
Q
Describe the memory space of a process
A
Stack: local variables and return addresses
Heap: dynamically allocated memory
Data: global and static variables
Code: program code
19
Q
Describe the 5 process states.
A
New: process created Ready: ready to run Running: running on the CPU Blocked: waiting for a service Terminated: killed and needs to be cleaned up
20
Q
Describe the various process transitions
A
New->ready: admitted to scheduler
Ready->running: dispatched by the scheduler
Running->ready: interrupt due to timer or I/O
Running->blocked: service request (system call)
Blocked->ready service request completion
Running-> terminated: exit or kill
21
Q
How is a new process created?
A
Process creation is initiated by a process and performed by the kernel.
Parent process makes a fork() call and then the kernel
-makes a copy of the parent
-allocates a new PCB and PID
-copies parent’s PCB to new PCB
-sets new PID
-Marks new process as ready
-Sets return value of parent process to child PID
-Sets return value of child process to 0
22
Q
What is the ready queue?
A
An abstract queue which stores pointers to PCBs in the order that the processes are scheduled to run
23
Q
What is a scheduler?
A
The scheduler is responsible for deciding which process to run next. The scheduler is called by the OS whenever a process related event occurs
24
Q
What is the goal of the scheduler?
A
Maximize CPU utilization and Throughput. Minimize turnaround time, waiting time, and response time
25
What is non-preemptive scheduling vs preemptive scheduling?
Non-preemptive scheduling does not use a timer, and preemptive scheduling uses a timer.
26
What is meant by CPU Bound vs I/O Bound
A process is CPU bound if it predominantly does computation and little I/O blocking and lots of running.
A process is I/O Bound if it predominantly does I/O and little computation and lots of blocking and little running.
27
Describe a FIFO scheduler and its characteristics
First come first serve
- simple implementation
- non preemptive
- indiscriminate between CPU and I/O bound processes
- susceptible to the convoy effect
28
Describe a SJF scheduler and its characteristics
Shortest job first: priority of job is based on its CPU burst length
- Probably optimal
- nonpreemptive
- hard to implement
29
What is an exponential moving average and why would we need to know that>
An exponential moving average is a weighted average so that the most recent term has more weight than all previous terms:
```
Sum all (1-a)^i * atn
tn is the nth term, a is 1/2
```
We can use an exponential moving average to predict the CPU burst time.
30
What is priority based scheduling?
Single priority ready queue of all processes. Priority of job assigned by user. Process gets to run until it requests a kernel service.
- nonpreemptive
- predictable
31
What are the problems with non-preemptive schedulers?
Starvation: low priority or long processes may never get to run
32
What is RR scheduling?
Round Robin scheduling. FIFO queue where all processes run until there is an interrupt, the process ends, or they use up their quantum of time (timer goes off)
- simple implementation
- indiscriminate between CPU and I/O bound processes
- high waiting time,
- convoy effect
33
Describe MLFB scheduler and its characteristics
System adjusts priority based on CPU burst. All processes start out in the highest priority queue, if they use up their quantum they get kicked to the next queue down. The lowest queue is scheduled using RR.
- all processes get to run
- I/O bound processes get priority
- used in many systems today
34
What is parallel execution vs concurrent execution?
Parallel execution is when 2 or more operations are performed simultaneously.
Concurrent execution is when 2 or more operations appear to be performed simultaneously
35
What is the definition and benefits of cooperating processes?
Processes are cooperating if they can affect of be affected by other processes.
Benefits include:
- information sharing
- modularity
- computation
- security
36
What are the requirements for process cooperation?
IPC
| Process synchronization
37
Describe the composition of a thread
A thread comprises
- a single thread of execution
- cpu context
- stack
- shares remaining memory with all other threads
38
Why use threads?
Scalability: easier to use multiprocessor systems
Sharing; easier to share resources and data in concurrent setting
Economy: easier and cheaper to create a thread
Responsiveness: easier to create more responsive applications
39
How do threads access resources?
Resources are allocated to the process.
| All threads belonging to the same process can access the resource.
40
How is a thread created?
A stack is allocated from the heap of an existing process (cheap). A TCB is initialized.
41
What is a critical section?
The piece of code in which race conditions can occur.
42
What is destructive interference?
Concurrent operations resulting in incorrect program behaviour
43
What is a race condition?
situations that can result in destructive interference
44
What are our solution goals to the critical section problem (4 goals)
Mutual exclusion
Scheduler independent
Allows progress
Starvation free
45
What is mutual exclusion?
No two threads/processes may be simultaneously in a critical section
46
What is scheduler independent?
No scheduling assumptions may be made about threads/processes
47
What is allows progress
No thread/process outside a critical section may block other processes
48
what is starvation free
No process should have to wait forever
49
What is a lock?
A lock is a mutual exclusion mechanism to protect critical sections that prevent other threads from entering if another thread is present. Allows threads to wait and eventually enter.
50
What is a spin lock?
A spin lock is a lock mechanism that requires the thread to spin in a loop testing a condition of some sort.
51
What are the advantages and disadvantages of letting the OS/System be responsible for entering/leaving critical sections?
Advantages:
- no race conditions in critical sections
- programmers don't have to debug critical sections
- code becomes simpler
Disadvantages:
- code becomes system dependent
- routines are more expensive because of more system calls
52
What's wrong with locks?
Many implementations do not allow a thread to acquire its own lock. Many implementations require that the thread that owns the lock release it.
53
What is a semaphore?
An integer variable instead of a boolean lock variable.
Represents number of pending wakeups and sleeping processes.
Two atomic operations: acquire, release.
54
What makes monitors unique from other abstractions?
Other abstractions such as semaphores or locks are language independent.
All you need to do to acquire/release a lock or semaphore is to call a function.
Monitors abstract locks and semaphores from the user.
55
What is a condition variable?
A condition variable is declared inside a monitor and represents queues of processes/threads waiting for a specific condition to occur.
Supports two operations: wait and signal
56
How does a condition variable work?
When a process needs to wait for something to occur it performs a wait on the condition variable and gets added to the condition variable's queue. Then it leaves the monitor and is put to sleep.
Once the condition is met the process meeting the condition performs a signal on the variable which wakes the process at the head of the queue. Then the current process leaves the monitor allowing the next woken process to enter.
57
What are some conditions for deadlock?
Mutual exclusion:
Processes are hogging the resources
Hold and Wait:
A process will attempt to acquire all resources it needs and hold them and wait for all other resources to become available
No Preemption:
Processes can not be forced to release a resource
Circular Wait:
There is a set of processes and resources such as there is a cycle in the resource allocation graph that can not be broken.
58
What are the four ways to handle deadlock?
Do nothing.
Deadlock prevention.
Deadlock Avoidance.
Deadlock Detection and Recovery.
59
What are some options we have for preventing hold and wait?
- Allow each process to hold only one resource at a time. Requires a lot of excess copying.
- Processes must be allocated all their resources at the start of execution. Requires programmers to know up front all resources that may be required
- Processes may not own any resources when requesting resources. Processes may starve due to the combination of resources not being made available
60
How can we prevent preemption?
If a process is holding resources and requests another resource that is not available, then all of its resources are released and added to the request list. Some resources cannot be preempted. Starvation could occur.
Preempt resources only if they are requested by another process... but then run into the same problems as in option 1
61
How can we prevent circular wait?
Order resources and require that they be acquired in ascending order. Easy to implement but requires that developers write their code to follow the order.
62
What is a safe state?
A system is in a safe state if the sequence of resource requests by executing processes will not lead to deadlock (no cycles in the resource graph).
63
What is an unsafe state?
A system is in an unsafe state if the sequence of resource requests by executing processes may lead to deadlock.
64
What is a deadlock state?
A system is in a deadlocked state if the sequence of cycles have occurred in the resource allocation graph.
65
List the four types of IPC
Shared Memory
Message Passing
Signals
Pipes
66
What is shared memory (IPC)?
Memory shared between processes.
Processes can communicate by accessing shared memory.
Problems:
-Can't be used across multiple machines
:Hard to debug
67
What is message passing (IPC)?
To communicate processes ask the system to send a message on their behalf (ex. the Internet).
A message queue stores messages for the processes. To send a message processes must know the ID or name of the process they are sending it to. To receive a message it is not always necessary for the process to explicitly specify the receiver.
68
What are Synchronous vs Asynchronous sends?
In a synchronous send the sender waits to ensure the receiver has gotten the message before becoming unblocked. In an asynchronous send, the sender does not wait to see if the receiver has gotten the message.
69
What are pipes?
Pipes are a special form of message passing where two processes establish a direct connection (I'm pretty sure its a unidirectional connection). They can pass messages or data streams to each other. Pipes can either be local or interhost.
70
What are signals (IPC)?
Processes can asynchronously notify other processes, all processes must be running on the same machine and controlled by the same OS. One process asks the OS to notify another process on its behalf.
71
What is the definition of a file?
A stream or sequence of bytes
72
What are the types of files?
Regular, directories, hardware devices, virtual devices, pipes and sockets
73
Describe a regular file.
A sequence of bytes stored on secondary storage. Readable writeable seekable. Can be accessed sequentially or randomly
74
Describe a directory?
Special files containing lists of other files and directories also stored in secondary storage. Only accessible via special system calls. Map file names to file-system identifiers. Induce typically a tree-like structure.
75
What is hierarchical file organization?
Organizing files in a tree-like hierarchy.
Allow multiple directories where each directory may contain files and directories. The top directory is called the root. The location of the file in the directory tree is specified by the files path
76
What is a hardlink vs a softlink
A hard link always links to a valid file.
| A soft link is a link to another path which may or may not be valid.
77
Briefly describe the anatomy of a disk.
A hard disk consists of one or more platters where each platter is divided into tracks which is divided into sectors. Each sector contains the same number of bytes. Hard disks have two operations: read and write
78
What three data structures are used to support the file API?
File Control Blocks, System Wide File Table, Per-process file table
79
Describe the File Control Block
Each FCB stories various meta data about the file including but not limited to:
-Identifier, owner, size, location of the data
80
What are the basic operations of the file API?
open, close, read, write, lseek
81
Describe the system wide open file table
Each opened file is represented by an entry in a system wide open file table. Each entry contains a file identifier, reference count, pointer to the FCB, and file cache information
82
What is a file descriptor table?
The kernel allocates a file descriptor table for each process. Each entry contains an index into the SWOFT and a current offset pointer.
83
What is a file descriptor?
The index returned by the open operation is the file descriptor. To perform an operation on the file, the FD must be passed as one of the arguments to the system call. The FD is used to index into the FD table.
84
What are the three standard files?
stdin: standard input
stdout: standard output
stderr: standard error
85
What is a device block?
A device block contains references to device specific operations. The OS uses device blocks to locate corresponding operations when performing an operation on a device. (Multiple classes implementing the same interface)
86
What are the four allocation strategies?
Contiguous allocation, linked allocation, linked extents allocation, indexed allocation.
87
Describe contiguous allocation of files and list its pros and cons.
The FCB for the file stores the start of the file and the length of the file. The file is stored in contiguous blocks starting at B.
Advantages:
- simple to implement
- excellent read/write performance
Disadvantages:
- External fragmentation
- may need to move files as they grow
- may not be able to add files even when space exists
88
Describe linked allocation of files and list its pros and cons
The FCB stores start block B and end block C.
Each block stores a link to the next block in the file.
Advantages:
- avoids external fragmentation
- simple to implement.
Disadvantages:
- No contiguity
- horrible performance
- wastes space in each block for a link to the next.
89
Describe linked extents allocation of files and list its pros and cons
The FCB for the file stores the start block B and the length L of the file.
Blocks are groups together in one or more extents. Each extent starts with a header:
-N number of blocks in extent
-E: link to next extent
Advantages:
-Good read/write performance
Disadvantages:
:In worst case reduces to linked allocation
90
Describe indexed allocation of files and list its pros and cons
The FCB's are clustered together on the disk. Each FCB stores the indices of all blocks storing the data, and indices to blocks storing indices.
Advantages:
- decouples metadata from data
- provides flexibility for contiguous block allocation
Disadvantages:
- Uses space to store the metadata
- Significant overhead for small files
- Allocate many indices for large files
91
Describe the Unix file system
```
Indexed allocation based file system.
Comprises three main components:
-Inodes
-Indirect blocks
-data blocks
```
92
Describe the anatomy of an I-node
Typically 128 or 256 bytes.
Contains meta data about the file
Indices to the first 12 blocks of the files
An indirect block, double indirect block and triple indirect block
93
Describe how small files are stored in the unix file system
For files smaller than 48kb only the first 12 direct block indices are used. Each index refers to a 4kb data block that stores the file data. Only as many blocks as needed are allocated.
94
Describe how medium sized files are stored in the unix file system
For files between 48KB and 4MB+48KB in size all the direct blocks will be used.
The indirect block is also used, it refers to a 4KB block containing 1024 direct block indices. Only as many blocks as needed are used.
95
Describe how to store large sized files in the unix file system
For files larger than 4MB+48KB the double indirect and triple indirect blocks can be used if needed.
The double indirect block refers to a 4KB block containing 1024 Indirect block indices each referring to 1024 data blocks.
The triple indirect block supports terabyte sized files.
96
How are I-node blocks stored?
I-node blocks are located in fixed locations spread out on disk. Each block contains 16 or 32 I-nodes. The file system stores a map of all i-node block locations and uses it to locate the i-node number
97
What is an I-node free list?
A list of available inodes
98
What is a free block list?
a list of available regular blocks
99
What is the superblock?
the superblock stores all the data structures for managing the inodes and blocks.
(multiple copies of the superblock are stored on the disk as backups)
100
What is the clean flag?
When the file system starts up the clean flag (in the superblock) is set to false (if it was true). If the system crashes, the flag indicates that the file system should be checked. On a proper shutdown the clean flag is set to true and the superblock is written to the disk.
101
How can we manage free lists?
- Bit vectors
- Linked lists
- Index based (tree like) structure
102
Briefly describe an abstract directory structure
A directory is a file comprising a sequence of directory entries. Each directory entry stores one mapping from file name to file ID. The sequence is typically unordered.
103
What are the two most common options for implementing a directory
Linear list: easy to implement but find() is slow
| Hash Table: greatly speeds up find() but may have to deal with collisions or overloaded file tables
104
Describe caching in a nutshell
A cache works by storing a copy of the file data in memory and accessing the in-memory copy rather than the one in secondary storage (100000x faster to access).
If the file is in the cache, use the data from there. Otherwise first load the file into the cache.
When a file is closed the contents of the cached file may need to be written back to secondary storage.
105
Describe the unified buffer cache
The unified buffer cache caches files that are accessed either via memory mapping or the file API. The cache is limited to a fixed amount of memory. When a new file is read its blocks are loaded into the buffer. Implements LRU
106
Briefly describe the LRU algorithm
Store accessed items in a list.
When a file is accessed remove it from the list and add it to the end of the list, in this way the LRU item will always be at the front of the list.
When there is no more space in the list evict the file at the front of the list and add the new file to the end of the list.
107
Describe the backup process
Backups are typically done either as a full backup which makes a copy of all files, or in incremental backups which makes a copy only of files that have been changed since the last backup
108
What is the archive bit?
The archive bit indicates whether a file has changed since the last backup. During a backup all archive bits are cleared, when a file is modified the backup bit is set.
109
Describe check pointing
When a backup starts a check point is created. All files altered during the backup are made and altered as copies that do not replace the immutable version of the file until the backup is complete
110
What order of operations helps with system consistency?
```
Data blocks
Indirect blocks
Double Indirect blocks
Triple indirect blocks
I-Node blocks
```
111
What is journaling and how does it help with consistency?
The idea is to log all operations to a journal file and mark operations completed as committed in the log. If a crash does occur before operations are committed a scan of the journal is all that is required to fix any inconsistencies
112
What is a log-structured file system?
When performing updates never update an existing block, instead allocate a new block and append it to the log. In this way data blocks are never updated only inodes as new blocks are appended to the log. The problem with this is that the number of blocks we have will run out and even if we do free up space from old blocks it will be fragmented.
113
What does CIA stand for? Describe each item.
CIA stands for confidentiality, integrity and availability.
Confidentiality: computer assets are only accessible to authorized users.
Integrity: computer assets can only be changed by authorized users.
Availability: computer assets are available to authorized users.
114
What are 4 possible threats to security?
Interruption, Modification, Interception, Fabrication
115
What are the goals of security?
To protect against accidental and deliberate transgressions of users and processes.
116
What is a policy and what is a mechanism?
A policy is the way we want the system to behave.
A mechanism is the techniques we can apply to enforce a policy.
117
What mechanisms are used to get authentication?
something you know (ex pin number) and something you have (ex bank card)
118
What is the difference between authentication and authorization?
Authentication is who the user is, and authorization is what the user can do.
119
What is a protection domain
The set of files that a user has access to is a protection domain.
120
What is an access control matrix?
A structure used to store the mapping between objects, users, and access rights.
121
Describe an access control list
The list of all protection domains and their access rights for an object. The ACL is stored with the object being protected. Hard to track down all the permissions for one protection domain.
122
Describe a capability list
The list of all objects and access rights that belong to a domain of protection. Stored with the user. Hard to determine who has access to an object.
123
What are some access right issues?
Revocation, limited propagation, confinement
124
What is a MMU?
The memory management unit defines the logical address space of each process/OS. It translates logical addresses to physical addresses and generates an interrupt if an invalid logical address is issued. All memory access by the CPU goes through the MMU.
125
What is the physical address space vs the logical address space?
The physical address space is the address range of the physical memory. A logical address space is the address space visible to a process.
126
Why use logical address spaces at all?
Having separate logical spaces provides each process with an independent view of memory and thus makes programming easier (pointers and references are the same). We can allocate memory to multiple processes.
127
What is the contiguous allocation of processes?
Memory is divided into fixed size partitions and each process resides in its own partition. Each partition has a base (start of the partition) and a limit (end of the partition). A logical address is generated between 0 and limit-1.
128
What are the advantages/disadvantages of contiguous allocation for processes?
Pros:
- simple implementation
- fast translation
- fast process switching
Cons:
- external fragmentation
- process address space can not be increased
129
What are some of the strategies for memory allocation in a contiguous memory scheme? (pros and cons)
First fit:
- Fastest possible decision
- Not necessarily the best decision
best fit:
- Reduces memory waste in the short term
- More likely to create small holes of wasted memory
worst fit.
- Less likely to create small holes
- reduces ability to satisfy large memory requests
130
What is external vs internal fragmentation?
external fragmentation is small holes of memory in the free pool.
internal fragmentation is unused memory inside allocated chunks.
131
What is the fixed block sizes solution to memory allocation?
Fix allowable requests to a number of different sizes and use a list for free blocks of each size.
Allocate the smallest allowable block for each process. If the list is empty grab block from the next list up and subdivide it. This leaves no external fragmentation but internal fragmentation is still an issue.
132
Describe the buddy system.
The buddy system says to allocate memory in chunks of power of two.
When freeing memory, if a buddy of a block being freed is free (aka if they are next to each other), merge the two blocks. Keep repeating until no more merging is possible.
No fragmentation but internal fragmentation is still an issue.
133
What are some data structures used for managing memory?
Linked lists (common and simple)
Binary trees
List of lists
134
What is swapping?
One process at a time is in memory (logical == physical). Entire process memory is saved to disk when it stops or blocks or is preempted. Next process in ready queue is loaded from disk into memory and runs.
Pros:
-Simple, no MMU required
Cons:
-Expensive, slow
135
What is swapping WITH contiguous allocation?
Requires an MMU to perform address translation to allow multiple processes to be in memory at the same time. When memory is needed for another process one or more processes are swapped back to the disk to free up the memory. (similar to how a cache uses LRU)
Pros:
- Simple
- MMU can be simple
- Low overhead
Cons:
- Expensive
- Slow
- External fragmentation
136
What is segmentation?
Allow a process to comprise multiple segments and processes can use special segment selectors as part of their pointer. Processes may run with some or all segments in memory. There are 4 segment selectors (code, data and heap, stack, and extra)
```
Pros:
-Allocation flexibility
-Low overhead
-Cheaper to swap a segment than a process
Con's
-Processes are no longer contiguous
-MMU is complex
-Large segments are still expensive
-External fragmentation
```
137
Describe paging
Divide process memory into small equal sized "pages". Pages are numbered 0-N. Divide physical memory into equally sized frames.
A page can be stored in any frame, and the MMU maps pages to frames. The MMU takes the page number from the logical address of the page, and determines the frame number where the page data resides.
138
What is a page table and a multi-level page table?
Each process has a page table that contains an entry for each page in the memory space of the process. Each entry contains a frame number, a valid bit, access bits and access level. The MMU uses the page table to translate addresses.
A multilevel page table divides the page number into two parts, where the first level table entry points to the second level table entry which contains page descriptors. The second level table entry only exists if it is valid. Uses significantly less memory to create this table than a single level page table.
139
How does translation with page tables work?
MMU uses a page number to index into the page table. Then iff the entry is valid uses the 20 but frame number to access the memory.
Note that memory only be accessed if the page is valid so a process doesn't need all its memory to be allocated at creation. If the OS needs to extend the heap or the stack is can simply allocate more frames and update the page table.
140
What are some of the problems with page tables?
- Slower address translation
- Every memory operation requires an extra read which is expensive
- A page table is HUGE so each process must be allocated 4MB of memory PLUS the memory of the actually process.
141
What is the translation look aside buffer?
A cache for address translations using the page table to save additional reads.
142
Why is the TLB a problem when context switching, and how can we solve the problem?
If new processes use entries in the TLB they will access the old processes memory.
We can flush the TLB on context switch but it will be expensive to reload.
Or, we can associate address space IDs or process IDs with TLB entries so we only evict the TLB entries that we need to lose.
143
What is the concept of virtual memory?
The address space of a process is limited by the architecture of the MMU, not the physical memory.
The use of paging provides the process with a logical view of a large contiguous memory space which decouples the view from the physical memory space
144
What is demand paging (as opposed to paging)?
In demand paging, a process must allocate a page before using it. A process requests pages from the OS which allocates a page and updates the page table entries.
CPU sends virtual address to MMU which extracts a page number and loads the page table entry. If the page is valid, perform translation. Else if unallocated end program, else if nonresident, locate a frame and update page table entry. Return to process and try again
145
What are the three states of a page?
Unallocated (no data associated with the page)
Resident (page contains data and is assigned to a frame)
Nonresident (page might contain data but is not assigned to a frame)
146
What is a valid bit?
A valid bit is set to 1 or 0 and lets the system know the state of that page.
147
How does demand paging affect performance?
processes get the memory they need rather than what they want.
148
What is Copy-on-Write?
Demand paging allows us to perform copy on write,
When a new process is created, don't allocate any new memory. Duplicate the page table and mark all pages as read only, when any copy of the process attempts to write to a read only page and interrupt will occur and a new frame will be allocated. Both pages will be marked as read/write and the process will be able to make their change to the copy.
In this way, only pages that are modified need to be copied.
149
What is a guard page?
A guard page is a way of notifying the system when the stack needs to grow. When a guard page is written to, a new guard page will be allocated to the stack.
150
What is a library?
Libraries are bundles of compiled code that provide functionality to applications. The code is linked in as the last step of compilation.
Each process is linked with a small stub of code that asks the OS to load shared libraries. This code is run when the process starts and the libraries are loaded and mapped to the process space.
151
What is interprocess shared memory?
Unnamed memory segments can be allocated to memory so that when a process forks its children will have access to that segment.
Named memory segments can be allocated to shared memory and assigned a name in the file system so that other processes can use it.
152
How do we know whether to write a victim page to the disk before evicting it?
Keep track of whether the page has been modified using a dirty bit that is cleared when the page is loaded into memory and is set when a write is performed to the page. The OS can check if the bit is set and write back to the disk when the page is evicted.
153
How do we decide which page should be the next victim?
FIFO:
- Simple
- No correlation between whether a page has been used and its eviction
Optimal page replacement (replace the page that would not be used for the longest period of time)
-impossible to implement
LRU:
- Good performance, implementable
- requires significant hardware support (data structures, counters)
154
How can we approximate LRU to make page victim selecting more optimal>
Use a reference bit:
- The bit is set when a page is accessed and cleared by a timer at regular intervals
- Simple to implement and doesn't require much hardware
- crude approximation of LRU, some pages are less likely to be evicted than others
Use multiple reference bits:
- the timer shifts the reference bit to the right if its set and then clears the reference bit
- The OS will clear a page whos bit is least
Second change algorithm:
- Each page has a referenced bit which is set when the page is accessed. All pages are kept in a circular queue
- The OS moves around the circle to find a victim and sets reference bits to 0, then moves the pointer to the next page table entry.
- Simple to implement and cost is relatively low.
155
What is a memory mapped file?
Instead of processes allocating a buffer and reading into it, map the file directly into memory and access it as if it was loaded into the buffer. Using the mmap() function.
