Operating Systems Flashcards
What is kernel mode
TLDR: It gives unrestricted access to both user and OS memory, hardware, and system resources.
Explain variable partition scheme and what the hole is
It is when memory is separated into partitions, and each variably sized partition contains one process.
Initially, when all memory is available, this space is one large block called the hole
What is a problem suffered by first fit and best fit solution? Explain.
External fragmentation is a problem. This is when there is enough total memory space to satisfy a request, but the available spaces are not contiguous.
What is the 50 percent rule?
First fit analysis finds that given N blocks allocated in memory, another 50 percent of those blocks (0.5N) are lost to fragmentation.
What is compaction, under what conditions does it need to work?
Compaction is shuffling the holes in memory to place all free memory together.
This is only possible if relocation is dynamic and done at execution time by changing the base registers.
What is contiguous allocation?
OS is held in low memory with interrupt vectors. User processes are held in higher memory. (Memory is divided into 2 partitions).
It is when each process is stored in a single contiguous section of
memory
What is non contiguous allocation
Allows a process to acquire several memory blocks at different locations in memory. A process is split up into different partitions in memory. Reduces memory wastage from external and internal fragmentation.
Done through paging and segmentation.
Internal fragmentation (L17)
Allocated memory for a process may be larger than than requested memory, left with a small hole. This size difference between memory being used and the memory allocated, all within a partition.
In terms of paging, what is the worst case fragmentation? (L17)
Worst case fragmentation is when one frame only contains one byte.
Explain how segmentation works. (L17)
Programs are a collection of segments for things like main page, procedure, arrays, variables. The logical address consists of a tuple <segment number, offset>.
There is a segment table that has the segment number as index with a corresponding base address (which is the physical address where the segment starts in memory) and the limit (length of segment in main memory). The offset has to be less than the limit to be placed into main memory.
This has external fragmentation.
Explain the difference between segmentation and paging. (L17)
Long ass table, look it up in mindmap.
What is demand paging?
It’s like swapping and paging but processes are split into pages.
Demand paging is when you execute partially loaded processes. This is when processes are split into pages so that processes do not need to fully be in main memory for a part of a process to run, so each program takes less memory to run. Demand paging allows logical memory to exceed your physical memory, which allows for a higher degree of multiprogramming capabilities. How this is done is through using a secondary memory (swap space) (hard disk) to simulate the RAM by mapping some pages of a processes into it. Those pages are swapped into and out of main memory when a page fault occurs and is kept track of using a page table.
Essentially when a context switch occurs, the new process begins to execute after loading the first page and remaining pages are fetched (similar to paging system with swapping)
What is virtual memory?
Virtual memory is the technique that allows the execution of processes that are not completely in memory by storing part of s a program (pages) outside of main memory in a secondary storage space. Therefore, logical address space can exceed physical memory space and programs can take less memory to run.
This increases CPU utilisation and throughput, with no increase in response time or turnaround time, increasing degree of multiprogramming.
What is a page fault? How is it handled?
A page fault is when a page is marked invalid when you try to access it.
- Check internal table to see if reference was to a valid or invalid memory access.
- If invalid, terminate process. If page is just not in memory, then page it in.
- Find a free frame.
- Schedule the secondary storage operation to read the designated page into the newly allocated frame.
- When storage read is completed, modify the process’ page table to indicate it is in memory.
- Restart instruction and process accesses page. We save the state of interrupted process when page fault occurs.
What is degree of multiprogramming?
The degree of multiprogramming describes the maximum number of processes that a single-processor system can accommodate efficiently. It is the number of processes in ready state.
What does it mean when a bit is set to valid or invalid on a page table? What are two ways a bit can be invalid?
When a bit is set to valid in a page table, it means that page is available in the memory for the CPU to access (a memory resident). When a bit is set to invalid in the page table, it means that the page is either valid and in secondary storage or not loaded into the logical address space. Access to a page marked invalid causes a page fault, which traps to the OS.
What hardware is required to support demand paging?
- A page table is needed to mark validity
- Secondary memory is needed to swap pages into and out of main memory.
- The ability to restart instruction when a page fault occurs.
What is copy on write?
Copy on write is when a page of a process is copied when it is modified.
Parent and child processes can share pages in main memory. If either processes modify a shared page, only then is the page copied. This allows for more efficient process creation as only modified pages are copied.
Instead of immediately creating a copy of data when a process is duplicated, the system allows the copies to share the same memory space unless one of the copies are modified.
What is vfork()? Should it always be used?
vfork() is available on UNIX and is a variation of fork(). Instead of copy on write, parent process is suspended when a child process is using that address space of the parent’s. However, they must be careful to not modify address space. This should only be used when a child process calls exec() immediately.
What causes a need for page replacement?
When main memory is full and there are no free frames, but you need to bring in a page from secondary memory to continue a process, you need to find a page in memory that is not in use and page it out.
What is standard swapping and why is it no longer in use?
Entire processes can be temporarily swapped out of memory to a hacking store. Mostly idle processes are a good candidate. Makes it possible for total physical memory space of processed to exceed physical memory.
Most systems swap pages rather than entire processes now.
Explain the steps of basic page replacement.
- You find the location of a desired page in secondary store.
- If there are no free frames, use page replacement algorithm to select a victim frame. Write the victim frame to secondary store, update page/frame table accordingly.
- Read desired page into the newly freed frame, change page/frame table.
- Continue process by restarting the instruction that caused the trap (page fault)
How is overhead from basic page replacement reduced with a modify/dirty bit?
Each page or frame has a modify/dirty bit associated with it in the hardware. Bit is set by hardware whenever a page is modified so we know to write page to storage. If bit is not set, no need to write it to memory as it is already there (when a page is swapped into main memory, the page still exists in secondary storage).
What is the idea behind page fault algorithms?
We want the lowest page fault rates on both first access and re-access with algorithms. An algorithm is evaluated by running it on a string of memory references (reference string) and computing the number of page faults on that string.
If we have a reference to a page, then any references to page p that immediately follow will never cause a page fault.
Result of algorithm depends on number of frames available (higher # of frames, lower # of faults)
What is the FIFO algo for page replacement?
TLDR: The FIFO algorithm removes the oldest page that came into memory first.
Each page is associated with the time that page was brought into memory. When a page must be replaced, the oldest page is chosen.
There is no need to keep track of when a page is brought in as we have a FIFO queue in memory.
Con: it may remove active pages
Belady’s anomaly: this algorithm may even increase page fault rates as number of frames increase.
What is optimal page replacement and what are the cons?
Optimal page replacement is when you replace the pages that will not be used for the longest period of time.
This is hard to implement because you can’t read into the future (oracle)
Instead, this is used as a comparison algorithm instead.
What is the least recently used algorithm?
This uses past knowledge and replaces the page that has not been used for the longest time.
Time of its last use is associated with each page. It is generally a good algorithm and frequently used.
This requires substantial hardware…
What are two ways to implement the LRU algorithm?
- Counters: Every page table entry has a counter and every time a page is referenced, clock is copied into counter. When a page needs to be replaced, page table is searched for the smallest counter value.
- Static Implementation: A stack of page numbers if kept in a doubly linked form. If a page is referenced, it is moved to the top of the stack. This requires 6 pointers to be changed at worst. No search is done, but each update is a little more expensive as tail pointer points to the bottom of stack.
Describe a hard disk drive (HDD)
Hard disk drive is a secondary storage I/O device that contains many platters. Each disk platter is like a CD covered in magnetic material that stores info magnetically. The magnetic patterns are read. There is a read/write head above each platter.
Disk drive motor spins at 60 to 250 times per second.
Disks are usually removable.
What is transfer rates in regards to HDD
It is the rate at which data flows between the drive and the computer.
What is constant angular velocity?
It is when you are reading the tracks of a HDD, the rotating speed is constant and each track on the disk has the same number of sectors.
The density of bits decreases from inner to outer tracks to keep data rate constant.
Describe nonvolatile memory devices
Electrical rather than mechanical. If similar to hard disk drives, it is a solid state drive. Can also be USB’s.
More reliable, but more expensive per MB.
Shorter lifespan, less capacity, but faster.
No moving parts so no seek time or rotational latency.
How is data transfer carried out between secondary storage and the computer?
Secondary storage device is attached to a computer by the system bus or an I/O device. Data is transferred on bus carried out by special electronic processors called controllers. There are controllers on the computer’s end of the bus and the device’s end of the bus.
Explain address mapping and logical block address
Storage devices are addressed as a large one dimensional array of logical blocks. A (LBA) logical block address is used to refer to each sector of the drive.
For HDD’s: the sectors are mapped sequentially, through a track, then through a cylinder an the rest of the cylinders.
For NVM: chips/pages/blocks are mapped to array of logical blocks.
Ascending logical address = ascending physical address
What is disk bandwidth?
Disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the transfer.
Explain FCFS Scheduling for servicing disk I/O requests. What is the con of it?
It is when disk requests are serviced on a first come first serve basis.
The con is that there is a lot of head movements.
What is scan scheduling?
Disk arm/head is moved from one end of disk to another. When the head movement is reversed, disks requests are continued to be serviced (elevator algorithm). The con is that when a head is reversed, few requests are in the front, meaning that remaining requests (heavy density) at the other end will wait the longest.
However, less starvation and good for heavy load of requests.
What is C-Scan Scheduling?
Disk arm/head is moved from one end of disk to another. But the head movement is not reversed and returns to the beginning immediately once reaching the end without servicing any requests on the return trip. This allows for more uniform wait time as it treats cylinders as a circular list that wraps around from the last cylinder to the first.
However, less starvation and good for heavy load of requests.
What is SSTF?
This stands for shortest seek time path first. This services requests with the least seek time from the current head position. However, similar to shortest job first, this can lead to starvation. This is the most common as default. Increased performance over FCFS.
What is Look and Clook?
This is an alternate version of scan and C-Scan. However, this algorithm goes as far as the last request in each direction, then reverses immediately. Look is natural as a default choice.
What is pure demand paging?
Pure demand paging is an extreme case. It is when you start running a process with no pages in memory.
What is position/random access time?
It is the time necessary to move the disk head to the desired cylinder (seek time) and the time for desired sector to rotate to under the disk head (rotational latency)
What is a head crash?
If a disk head makes contact with disk surface, this is bad.
Describe the relationship between processes and main memory (L17).
Processes are kept in main memory as CPU is shared between processes.
Programs are brought from disk into memory and ran as processes.
The CPU can only access main memory and registers as storage and the memory only sees streams of addresses and read/write requests.
Accessing main memory may take many CPU cycles, causing CPU to stall. This is remediated through a cache that sit between memory and CPU.
What is a base and limit register? (L17)
To protect the memory, each process must have their own memory space by determining the range of legal addresses with a base and limit register. They help define a contiguous block of memory accessible to a program.
The base register holds the smallest legal memory address and the limit register specifies size of that range.
The CPU checks memory address generated by users to ensure it is between the limit for that user.
Base/limit registers can only be loaded by OS in kernel mode.
What is instructions binding and how does it work?
Before a program runs, it needs to be translated to see where those instructions go in the memory.
The binding of instructions to memory involves associating program instructions with specific memory addresses, ensuring that the CPU can correctly locate and execute these instructions during program execution.
This binding can occur at different stages, and the term “binding” refers to the process of connecting symbolic addresses in the source code to physical addresses in memory.
Compiler binds symbolic address (variable count) to a relocatable address (14 bytes from beginning of module).
The linker/loader binds relocatable address to absolute address (memory address)
Binding to memory address can happen at three stages
Compile time: If know at compile time the address, then absolute code can be generated.
If you don’t know at compile time where the code will reside in memory, then relocatable code will be generated. That code binding can be changed at load time, when program is loaded into memory for execution.
Execution time: binding is delayed until run time if the process can be moved from one segment of memory to another during execution. Need hardware for this, but most common.
What is a logical and physical address?
The physical address is the address in memory. This is the memory address that will be loaded into memory. A logical address is generated by the CPU (virtual address), it is a conceptual address space made for a program, not a real location in memory.
These would be the same address if binding happens at compile or load time.
What is the memory management unit (MMU) and the relocation register (L17)?
The hardware is responsible for mapping the logical address into a physical address and the relocation register (base register) is added to the logical address.
User programs never access the actual physical address. The logical address is not a real location in memory.
What is contiguous allocation? (L17)
Continuous allocation is when processes are contained in one single section of memory continuously.
