Quiz 5 Flashcards
1
Q
A program must be in what for it to run?
A
In memory
2
Q
What are the only sources of storage can the CPU access directly?
A
Main memory and registers
3
Q
Why can main memory cause stalls?
A
Because accessing it may require multiple cycles
4
Q
What is between main memory and CPU registers?
A
Cache
5
Q
What is the order of memory from smallest to largest?
A
Register->Cache->Main Memory->External Storage
6
Q
How does the OS ensures that a process can only access those addresses in its address space?
A
It uses a pair of base and limit registers to define the logical address space of a process
7
Q
What must the CPU do to insure that every memory access generated in user mode is between the base and limit for the user?
A
It checks if the address is larger than the base register and smaller than the base + limit register, if this is not the case it causes an error.
8
Q
Where do programs brought into memory execute from?
A
The input queue
9
Q
What binds relocatable addresses to absolute addresses?
A
Linkers or loaders
10
Q
What are the three stages where the binding of instructions and data to memory addresses can occur?
A
Compile time, Load Time and Execution Time
11
Q
When memory addresses are bound during compile time what type of code can be generated?
A
Absolute code, assuming that the memory location is known a priori
12
Q
When memory addresses are bound during load time what type of code can be generated?
A
Relocatable code
13
Q
What is a logical address?
A
An address generated by the CPU
14
Q
What is a physical address?
A
Address seen by the memory unit
15
Q
When are logical and physical addresses are the same?
A
During compile time and load-time address-binding schemes
16
Q
When do logical and physical addresses differ?
A
During execution time address binding schemes
17
Q
What is the logical address space?
A
The set of all logical addresses generated by a program
18
Q
What is the physical address space?
A
The set of all physical addresses generated by a program
19
Q
What is the memory management unit?
A
A hardware device that maps virtual addresses to physical addresses
20
Q
During a simple scheme what occurs?
A
The base register is called a relocation register
The value in the relocation register is added to every address generated by a user process
21
Q
During a simple scheme what does the user program deal with?
A
Logical addresses
22
Q
What is dynamic loading?
A
Loading only what you require into memory while executing a program
23
Q
When are routines loaded during dynamic loading?
A
When they are called
24
Q
Is special support needed from the operating system when you use dynamic loading?
A
No
25
What is static linking?
The system libraries and program code is combined by the loader into the binary program image
26
What is dynamic linking
When linking is postponed until execution time
27
What is used to locate the appropriate memory resident library routine?
The stub
28
What do stubs do?
Replaces itself with the address of the routine it stands in for and executes the routine
29
What is an early method of allocating memory?
Contiguous allocation
30
What was the two partitions of the main memory?
The low memory, which contained the resident operating system and the high memory which was held user processes
31
What does the limit register do with contiguous allocation?
It insures that the logical addresses are less than it
32
What is variable partition?
The memory is segmented into various sizes and when a process arrives it gets placed into one of these segments large enough to accommodate it
33
What are the three algorithms for dynamic storage?
First fit, Best fit and Worst fit
34
How does the first fit algorithm allocate holes?
It allocates holes large enough to fit the process
35
How does the best fit algorithm allocate holes?
Allocates the smallest hole big enough to fit the process
36
How does the worst fit fit algorithm allocate holes?
Allocate the largest hole
37
What are the two types of framentation?
External fragmentation and Internal Fragmentation
38
What is External Fragmentation?
Total memory space exists to satisfy a request, but it is not contiguous
39
What is internal fragmentation?
Allocated memory is slightly larger than the request memory, and is not being used by the process
40
For the first fit algorithm how much memory is lost due to fragmentation?
50%
41
What can be done to reduce external fragmentation?
Compaction, ie shuffling memory contents to place all free memory together in one large block
42
What are frames?
A section of physical memory divided into a block
43
What are the qualities of the memory of a frame?
The size of the memory is a power of 2, it is between 512 bytes and 16 megabytes
44
What are pages?
Sections of logical memory divided into chunks
45
What is a page table?
A table that keeps track of the pages in a program
46
What are the two sections of an address generated by the CPU?
A page number, and a page offset
47
What is a page number?
An index into a page table
48
What is a page offset?
A number added to the physical memory address that is sent to the memory unit
49
Where is the page table located?
In main memory
50
What does the page table base register point to?
The page table
51
What does the page table length register do?
Indicate the size of the page table
52
What is used to resolve the two memory access problem?
A fast lookup hardware cache called a translation look-aside buffer
53
What is an address space identifier?
A number in each translation look aside buffer that identifies each process to provide address space protection for said process
54
What occurs on a translation look aside buffer miss?
A value is loaded into the translation look aside buffer for faster access
55
What is effective access time?
The time it takes for a memory to be accessed using a TLB
56
How is memory protection implemented in page tables?
By indicating if a read-only or read-write access is allowed
57
What does valid mean in reference to a valid-invalid bit?
The associated page is in the process' logical address space and is thus a legal page
58
What does invalid means in reference to a valid-invalid bit?
That a page is not in the process' logical address space
59
What is reentrant code?
A single copy of read only code shared among processes
60
What does each process keep a separate copy of when using pages?
The code and data
61
What are the three ways of dividing the page table into smaller units?
Hierarchical Paging
Hashed Page Tables
Inverted Page Tables
62
How does hierarchical page tables function?
By breaking up the logical address space into multiple page tables, then paging the page table
63
How does Two Level Paging function?
By breaking up the page number into another section
64
What are Inverted Page Tables?
Page tables that store the information about the process that holds a page rather than the page itself
65
What is Roll Out Roll In?
A swapping variant used with priority-based scheduling algorithms, swaps lower priority processes with higher priority processes.
66
Does swapped out processes need to swap back into the same physical addresses?
Depends on the address binding method
67
What is the modified version of swapping?
Swapping is allowed only if a threshold of memory is allocated
68
What is one constraint on swapping?
Pending I/O
69
What is double buffering?
When you have to transfer I/O to kernel space then back to I/O device
70
The Intel IA-32 Architecture supports what types of segmentation?
Normal segmentation and segmentation with paging
71
What is Virtual Memory?
Separation of user logical memory from physical memory
72
What are some of the benefits of using virtual memory?
Only need a part of the program in memory for execution
Logical address space can be larger than physical address space
Address spaces can be shared by several processes
Allows for more efficient process creation
More programs running concurrently
Less I/O needed to load or swap processes
73
What are the two ways virtual memory can be implemented?
Demand paging or Demand Segmentation
74
How is logical address space normally allocated in reference to the stack and heap?
The stack starts at the max and grows down while the heap starts at the bottom and grows upward
75
What is demand paging?
Bringing a page into memory only when its needed
76
What is a lazy swapper?
A swapper that only swaps a page into memory when the page is needed
77
What is a valid-invalid bit?
A bit that shows if a page is in memory or is not in memory
78
What are the steps in handing a page fault?
Find a Free frame
Swap the page into a frame via scheduled disk operation
Reset tables to indicate page is in memory
Restart the instruction that caused the page fault
79
What is a free frame list?
A pool of free frames for satisfying page swaps
80
What is zero-fill-on-demand?
The content of a frame being zeroed out before it is allocated to another process
81
What are the stages in demand paging in the worst case?
1 Trap to the operating system
2 Save the user registers and process state
3 Determine that the interrupt was a page fault
4 Check that the page reference was legal and determine the location of the page on the disk
5 Issue a read from the disk to a free frame
6 While waiting allocate the CPU to some other user
7 Receive an interrupt from the disk I/O subsystem
8 Determine that the interrupt was from the disk
9 Determine that the interrupt was from the disk
10 Correct the page table and other tables to show page is now in memory
11 Wait for the CPU to be allocated to this process
12 Restore the user registers process state and a new page table and resume the interrupted instruction
82
What is Effective Access Time?
(1-p)x memory access + p (page fault overhead + swap page out + swap page in)
83
What is copy on write?
It allows parent and child processes to share pages in the same memory
84
The dirty bit ensures what?
That only modified pages are written to disk
85
What is the steps for a basic page replacement?
1 Find the location of the desired page on a disk
2 Find a free frame, if one is present use it otherwise free a frame using a page replacement algorithm
3 Bring desired page into the new frame, update page and frame tables
4 Restart the instruction that caused the trap
86
What issue may arise due to using the FIFO algorithm?
Belady's Anomaly, ie more page faults occuring with more frames
87
What is the issue that may arise with the FIFO algorithm?
Bayle's Algorithm, ie more page faults occurring with more frames
88
What is the optimal algorithm?
Replace the page that will not be used for the longest period of time
89
What is the LRU algorithm?
Replace the page that has not been used in the most amount of time.
90
What are the two ways of implementing the LRU algorithm?
Counters and Stacks
91
Explain the implementation of LRU algorithm using stacks
Keep a stack of page umbers in a double link form, when a page is reference you move it to the top, however this results in each update becoming more expensive
92
Explain the implementation of LRU algorithm using counters
Each page entry has a counter, and this counter gets updated every time a page is referenced and copied over into the page that was updated
93
What are the two major allocation schemes?
Fixed allocation and Priority allocation
94
What are the two types of fixed allocation?
Equal allocation, each process gets the same amount of frames
Proportional allocation, allocation is given to the size of each process
95
What is Global replacement?
A replacement frame is selected from the set of all frames
96
What is local replacement?
Each process selects from only its own set of allocated frames
97
What is the benefit and downsides of global replacement?
Benefit-greater throughput is more common
Downside-Execution time varies greatly
98
What are the benefits and downsides of local replacement?
Benefit-more consistent per process performance
Downside-possibly underutilized memory
99
What is the strategy to implement a global page replacement policy?
Memory requests are satisfied from the free-frame list, and page replacement is triggered when the list falls below a certain threshold
100
What is thrashing?
Slowdown caused by a process having a very high page fault rate
101
What are the two main forms of secondary storage?
Hard disk drives and nonvolatile memory
102
What are some of the benefits and downsides of nonvolatile memory devices?
Benefits: Faster
Downsides: Shorter life span, more expensive, and less capacity
103
How are disk drives addressed?
As large 1d logical blocks
104
What is disk bandwidth?
Total number of bytes transferred divided by the total time between the first request for service and the completion of the last transfer
105
What is the FCFS disk scheduling algorithm?
The head moves to the first pin in the queue
106
What is the SCAN algorithm?
The disk arm starts at the end of the disk and moves toward the other end
107
What is the C-SCAN?
A varient of the SCAN goes from one end of the disk to the other sericing requests as it goes
108
What is physical formatting?
Dividing a disk into sectors that the disk controller can read and write
109
What is the RAID structure?
Having multiple disk drives holding copies of the same data to increase reliability
110
What is RAID 0?
Non-redundant striping
111
What is RAID 1?
Mirrored disks
112
What is RAID 4?
Block interleaved parity
113
What is RAID 5?
Block interleaved distributed parity
114
What is a port?
A connection point for a device
115
What is a Bus?
A shared direct access
116
What receives interrupts?
The Interrupt handler
117
What is dispatched to correct the interrupt handler?
The Interrupt Vector
118
What is used for exceptions?
The interrupt mechanism
119
What does the Direct Memory Access controller do?
Bypasses the CPU to transfer data directly between I/O device and memory
120
What are the various interfaces for devices?
Character-stream/block, Sequential/random-access, Synchronous/asynchronous, Sharable/dedicated, Read-write, Read-only, Write-only
