Quiz 5 Flashcards
A program must be in what for it to run?
In memory
What are the only sources of storage can the CPU access directly?
Main memory and registers
Why can main memory cause stalls?
Because accessing it may require multiple cycles
What is between main memory and CPU registers?
Cache
What is the order of memory from smallest to largest?
Register->Cache->Main Memory->External Storage
How does the OS ensures that a process can only access those addresses in its address space?
It uses a pair of base and limit registers to define the logical address space of a process
What must the CPU do to insure that every memory access generated in user mode is between the base and limit for the user?
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.
Where do programs brought into memory execute from?
The input queue
What binds relocatable addresses to absolute addresses?
Linkers or loaders
What are the three stages where the binding of instructions and data to memory addresses can occur?
Compile time, Load Time and Execution Time
When memory addresses are bound during compile time what type of code can be generated?
Absolute code, assuming that the memory location is known a priori
When memory addresses are bound during load time what type of code can be generated?
Relocatable code
What is a logical address?
An address generated by the CPU
What is a physical address?
Address seen by the memory unit
When are logical and physical addresses are the same?
During compile time and load-time address-binding schemes
When do logical and physical addresses differ?
During execution time address binding schemes
What is the logical address space?
The set of all logical addresses generated by a program
What is the physical address space?
The set of all physical addresses generated by a program
What is the memory management unit?
A hardware device that maps virtual addresses to physical addresses
During a simple scheme what occurs?
The base register is called a relocation register
The value in the relocation register is added to every address generated by a user process
During a simple scheme what does the user program deal with?
Logical addresses
What is dynamic loading?
Loading only what you require into memory while executing a program
When are routines loaded during dynamic loading?
When they are called
Is special support needed from the operating system when you use dynamic loading?
No
What is static linking?
The system libraries and program code is combined by the loader into the binary program image
What is dynamic linking
When linking is postponed until execution time
What is used to locate the appropriate memory resident library routine?
The stub
What do stubs do?
Replaces itself with the address of the routine it stands in for and executes the routine
What is an early method of allocating memory?
Contiguous allocation
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
What does the limit register do with contiguous allocation?
It insures that the logical addresses are less than it
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
What are the three algorithms for dynamic storage?
First fit, Best fit and Worst fit
How does the first fit algorithm allocate holes?
It allocates holes large enough to fit the process
How does the best fit algorithm allocate holes?
Allocates the smallest hole big enough to fit the process
How does the worst fit fit algorithm allocate holes?
Allocate the largest hole
What are the two types of framentation?
External fragmentation and Internal Fragmentation
What is External Fragmentation?
Total memory space exists to satisfy a request, but it is not contiguous
What is internal fragmentation?
Allocated memory is slightly larger than the request memory, and is not being used by the process
For the first fit algorithm how much memory is lost due to fragmentation?
50%
What can be done to reduce external fragmentation?
Compaction, ie shuffling memory contents to place all free memory together in one large block
What are frames?
A section of physical memory divided into a block
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
What are pages?
Sections of logical memory divided into chunks
What is a page table?
A table that keeps track of the pages in a program
What are the two sections of an address generated by the CPU?
A page number, and a page offset
What is a page number?
An index into a page table
What is a page offset?
A number added to the physical memory address that is sent to the memory unit
Where is the page table located?
In main memory
What does the page table base register point to?
The page table
What does the page table length register do?
Indicate the size of the page table
What is used to resolve the two memory access problem?
A fast lookup hardware cache called a translation look-aside buffer
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
What occurs on a translation look aside buffer miss?
A value is loaded into the translation look aside buffer for faster access
What is effective access time?
The time it takes for a memory to be accessed using a TLB
How is memory protection implemented in page tables?
By indicating if a read-only or read-write access is allowed
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
What does invalid means in reference to a valid-invalid bit?
That a page is not in the process’ logical address space
What is reentrant code?
A single copy of read only code shared among processes
What does each process keep a separate copy of when using pages?
The code and data
What are the three ways of dividing the page table into smaller units?
Hierarchical Paging
Hashed Page Tables
Inverted Page Tables
How does hierarchical page tables function?
By breaking up the logical address space into multiple page tables, then paging the page table
How does Two Level Paging function?
By breaking up the page number into another section
What are Inverted Page Tables?
Page tables that store the information about the process that holds a page rather than the page itself
What is Roll Out Roll In?
A swapping variant used with priority-based scheduling algorithms, swaps lower priority processes with higher priority processes.
Does swapped out processes need to swap back into the same physical addresses?
Depends on the address binding method
What is the modified version of swapping?
Swapping is allowed only if a threshold of memory is allocated
What is one constraint on swapping?
Pending I/O
What is double buffering?
When you have to transfer I/O to kernel space then back to I/O device
The Intel IA-32 Architecture supports what types of segmentation?
Normal segmentation and segmentation with paging
What is Virtual Memory?
Separation of user logical memory from physical memory
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
What are the two ways virtual memory can be implemented?
Demand paging or Demand Segmentation
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
What is demand paging?
Bringing a page into memory only when its needed
What is a lazy swapper?
A swapper that only swaps a page into memory when the page is needed
What is a valid-invalid bit?
A bit that shows if a page is in memory or is not in memory
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
What is a free frame list?
A pool of free frames for satisfying page swaps
What is zero-fill-on-demand?
The content of a frame being zeroed out before it is allocated to another process
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
What is Effective Access Time?
(1-p)x memory access + p (page fault overhead + swap page out + swap page in)
What is copy on write?
It allows parent and child processes to share pages in the same memory
The dirty bit ensures what?
That only modified pages are written to disk
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
What issue may arise due to using the FIFO algorithm?
Belady’s Anomaly, ie more page faults occuring with more frames
What is the issue that may arise with the FIFO algorithm?
Bayle’s Algorithm, ie more page faults occurring with more frames
What is the optimal algorithm?
Replace the page that will not be used for the longest period of time
What is the LRU algorithm?
Replace the page that has not been used in the most amount of time.
What are the two ways of implementing the LRU algorithm?
Counters and Stacks
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
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
What are the two major allocation schemes?
Fixed allocation and Priority allocation
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
What is Global replacement?
A replacement frame is selected from the set of all frames
What is local replacement?
Each process selects from only its own set of allocated frames
What is the benefit and downsides of global replacement?
Benefit-greater throughput is more common
Downside-Execution time varies greatly
What are the benefits and downsides of local replacement?
Benefit-more consistent per process performance
Downside-possibly underutilized memory
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
What is thrashing?
Slowdown caused by a process having a very high page fault rate
What are the two main forms of secondary storage?
Hard disk drives and nonvolatile memory
What are some of the benefits and downsides of nonvolatile memory devices?
Benefits: Faster
Downsides: Shorter life span, more expensive, and less capacity
How are disk drives addressed?
As large 1d logical blocks
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
What is the FCFS disk scheduling algorithm?
The head moves to the first pin in the queue
What is the SCAN algorithm?
The disk arm starts at the end of the disk and moves toward the other end
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
What is physical formatting?
Dividing a disk into sectors that the disk controller can read and write
What is the RAID structure?
Having multiple disk drives holding copies of the same data to increase reliability
What is RAID 0?
Non-redundant striping
What is RAID 1?
Mirrored disks
What is RAID 4?
Block interleaved parity
What is RAID 5?
Block interleaved distributed parity
What is a port?
A connection point for a device
What is a Bus?
A shared direct access
What receives interrupts?
The Interrupt handler
What is dispatched to correct the interrupt handler?
The Interrupt Vector
What is used for exceptions?
The interrupt mechanism
What does the Direct Memory Access controller do?
Bypasses the CPU to transfer data directly between I/O device and memory
What are the various interfaces for devices?
Character-stream/block, Sequential/random-access, Synchronous/asynchronous, Sharable/dedicated, Read-write, Read-only, Write-only
