Operating Systems
Processes, threads, context switching, virtual memory, BIOS.
46 flashcards · Computer Science · by lakesare
Concurrency VS parallelism?
Concurrency: instructions of one process are interleaved with the instructions of another process. Parallelism: tasks literally run at the same time (e.g. on a multicore processor)
How does OS achieve concurrency?
By context switching. When OS decides to transfer control from the current process to some new process, it performs a context switch by: saving context of the current process, restoring context of the new process, passing control to the new process. The new process picks up exactly where it left off.
What's a process?
It's an OS abstraction, which allows us to pretend that we have exclusive use of hardware. Multiple processes can run concurrently on the same system, and each process appears to have exclusive use of the hardware.
What's a system call?
A computer program makes a system call when it makes a request to OS.
What's a virtual memory?
Abstraction by OS, that lets programs consider memory a large array of bytes. The actual implementation uses a combination of RAM, disk storage, special hardware, and operating system software to provide the program with what appears to be a monolithic byte array.
What's BIOS?
Low-level software that resides in a chip on the motherboard. BIOS stands for Basic Input Output System.
Name 2 things BIOS is responsible for.
It's used to perform hardware initialization during the booting process (power-on startup), Manages data flow between OS and attached devices such as the hard disk, video adapter, keyboard, mouse and printer).
Name 3 things BIOS does on power on.
Performs the POST (Power-On Self-Test) BIOS loads the first 512 bytes from the hard drive of the selected boot device – these 512 bytes are what is commonly known as the MBR (Master Boot Record). MBR contains Bootstrap Code, and it gets executed: look up the active partition from the partition table, and load that code into the memory for execution by the CPU. After initializing required hardware, the BIOS goes through a pre-configured list of non-volatile storage devices ("boot device sequence…
What is MBR (Master Boot Record)? Name 2 things stored in MBR.
MBR is first 512 bytes from the selected boot device. It stores: Bootstrap Code Partition Table Every hard disk has an MBR.
What's a boot device?
Device from which the operating system is loaded (hard disk, CD, flash card, etc). Typically, the BIOS will allow the user to configure a boot order. If the boot order is set to "first, the DVD drive; second, the hard disk drive", then the BIOS will try to boot from the DVD drive, and if this fails (e.g. because there is no DVD in the drive), it will try to boot from the local hard drive. Links: wikipedia on boot devices
What's an active partition?
Any partition at MBR's partition table can be marked as active. Bootstrap code looks at its partition table, and finds a partition marked as active. It expects an operating system to be located on it. Once we switch on the power button of the computer, booting process begins. After a series of Power-On-Self-Test (known as POST), BIOS will find and pass boot control to Master Boot Record (MBR). Then, MBR reads master partition table to find the primary partition which is marked as active - artic…
What are drive partitions?
When we divide one HDD/SSD into multiple logical drives ("volumes") that your OS will treat as if they are completely different HDDs. Each volume is named with C:, or D:. It's useful when we want to dual boot e.g. Linux and Windows.
Name 3 things kept at a Process Control Block (PCB)?
PCB is associated to the pid (process id) pid state (New, Ready (to be executed), Running, Waiting (for I/O), or Terminated) program counter (address of the next instruction to be executed for the process) priority Memory Pointers (which indicate the start and end address of the process in memory) Accounting Information, which includes the amount of CPU time used, time limits, etc. I/O Status Information, listing the files and I/O devices associated with the process. The PCB is maintained for a…
What's scheduling?
Process of OS deciding in what order should processes be executed.
Name direct and indirect costs of a context switch.
direct: loading values of a new process into CPU indirect: cache misses The kernel must stop the execution of the running process, copy out the values in hardware registers to its PCB, and update the hardware registers with the values from the PCB of the new process.
Name 3 types of schedulers.
long-term: decides which processes are to be admitted into the RAM (into a ready queue) medium-term: temporarily removes processes from RAM and places them in hard disk or vice-versa short-term: decides which of the ready, in-memory processes is to be executed (allocated a CPU) Links: wikipedia on types of schedulers
Name 4 scheduling schemes.
FIFO (First In First Out): simply queues processes in the order that they arrive in the ready queue. SJF (Shortest Job First): the process with the shortest execution time is selected. Fixed priority: a priority is associated with each process, and the CPU is allocated to the process with the highest priority. Round-Robin: each process is given a small unit of time, called a time quantum (10–100 milliseconds), and the ready queue is treated as a circular queue. The scheduler goes around the rea…
What's a job queue?
Processes in hard memory that are waiting to be put into the main memory by the long-term scheduler.
What's a ready queue?
Processes in main memory that are waiting to be allocated to the CPU by the short-term scheduler.
What's multiprogramming?
When OS allows execution of multiple processes in parallel. In a multiprogramming system there are one or more programs loaded in main memory which are ready to execute. Only one program at a time is able to get the CPU for executing its instructions (i.e., there is at most one process running on the system) while all the others are waiting their turn. Links: wikipedia multiprogramming
Sometimes main memory is filled up with processes, but CPU is idle. How is this possible?
All processes long-term scheduler assigned are I/O bound (mostly require I/O operations rather than CPU operations).
What's an I/O queue?
Processes in main memory that are waiting to be allocated to some I/O device by the short-term scheduler.
What's a page?
Fixed-length contiguous block of virtual memory, described by a single entry in the page table.
What is the smallest unit of virtual memory in OS?
A page.
What's a page table?
OS-kept table mapping of pages to frames. When a process requests access to data in its memory, it is the responsibility of the operating system to map the virtual address provided by the process to the physical address of the actual memory where that data is stored.
What are pinned pages?
Pages that are never swapped to a secondary storage.
What's paging VS demand paging VS swapping?
Paging is memory management scheme by which a computer stores and retrieves data from disk for use in RAM. There are two paging techniques - when OS starts a process, we need to load it from disk into RAM: swapping: loads all pages of a process. demand paging: lazy loading, will only load pages when they are demanded/referenced. Swapping is when some processes in main memory, which are waiting on I/O, can be temporarily moved out of main memory onto disk; this will leave some free space in main…
In what queue are processes in RAM?
Either ready (for CPU) or I/O queue.
Who performs swapping?
Medium-term scheduler. The medium-term scheduler temporarily removes processes from main memory and places them in secondary memory (such as a hard disk drive) or vice versa.
Swapping is an I/O operation, therefore it's quite slow. Name 2 ways to make swapping faster.
separate disk: put the swapped-out processes into a special chunk of disk, separate from the file system paging: reduce amount of the code that needs to be swapped, through simple/demand paging
Pages vs frames?
pages: chunks of virtual memory frames: directly corresponding chunk of physical memory Virtual addresses are used by the program executed by the accessing process, while physical addresses are used by the hardware, or more specifically, by the RAM subsystem.
What's memory management unit (MMU)?
Part of the CPU (or sometimes a separate IC) that facilitates mapping of virtual addresses's pages to RAM's frames. Part of MMU - TLB (Translation Lookaside Buffer) stores a cache of recently used mappings from the operating system's page table.
Where is page table stored?
Page Table is in RAM, cached by the TLB (translation lookaside buffer) in MMU. BUT it can be swapped out to a disk like all the other RAM pages. Great SO answer: https://stackoverflow.com/a/48857206/3192470
Name 2 reasons for using larger pages.
page table size would need to be large if we used per-cell virtual VS physical mapping TLB (Translation Lookaside Buffer) in MMU is a cache of page to frame, and less pages means less cache misses
Virtual address space: 232 bytes Each page: 4 KiB What's the size of page table?
1 KiB is a kibibyte (unambiguously denotes powers of 1024 - kilo binary byte). each page take up: 4 KiB = 4 * 210 = 212 amount of entries in a page table = 232 / 212 = 220 Links: wikipedia with this example
Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the size of the page table?
phys memory: 64MB = 64*220 = 226 bytes virt memory: 232 bytes page size: 4 kB = 4 * 210 = 212 bytes amount of page table entries = amount of pages in virtual memory = amount of addresses in virt memory / page size = 232 / 212 = 220 entries. number of frames in phys memory = phys memory / page size = 226 / 212 = 214 frames. each page table entry takes 14 bits + 1 valid/invalid bit. BUT memory is byte-addressable, therefore we need to take up 16 bits => 2 bytes. size of the page table = 2 bytes (…
Suppose there are 20 pages in a virtual memory. How many entries are there in a page table?
20.
Assume a 4GB (232 byte) virtual and physical address space and a page size of 4kB (212 bytes). How many entries does the page table have?
The page table needs one entry per page. we see that the 232 byte address space must be split into 2^20 pages. This means the page table must have 2^20 entries.
When does a page fault occur?
When page table doesn't have a frame for the page we requested. Sometimes, a PT entry prohibits access to a virtual page, perhaps because no physical random access memory has been allocated to that virtual page. In this case, the MMU signals a page fault to the CPU. Contrary to what "fault" might suggest, valid page faults are not errors, and are common and necessary to increase the amount of memory available to programs in any operating system that utilizes virtual memory.
When does a segmentation fault (segfault) occur?
Raised by hardware with memory protection when software attempts to access a restricted area of memory. Segmentation is a virtual memory management technique similar to paging. Memory is divided into "segments" (which, unlike pages, can be different sizes). Programs may be restricted to reading or writing memory within their own segments. A miscalculated address might lead your program to read or write outside its allocated segment, triggering an interrupt.
How does demand paging work?
Pages are loaded only when they are referenced. A program begins execution with none of its pages in RAM. As the program commits page faults, OS copies the needed pages from disk into RAM. Pages that are not executed during a particular run are never loaded into memory.
What is thrashing?
Either a very slow system or one that has come to a halt, happens when too many computer processes compete for inadequate memory resources.
Name 3 cases when thrashing may occur.
Paging thrashing: constant state of paging, rapidly exchanging data in memory for data on disk. TLB thrashing: when TLB is too small for the working set of pages. Cache thrashing: where main memory is accessed in a pattern that leads to multiple main memory locations competing for the same cache lines, resulting in excessive cache misses.
Describe steps of translating page into a frame.
Every page table entry is either valid (in RAM) or invalid (in disk). Attempt to access page: If page is valid - continue processing instruction as normal. If page is invalid - a page-fault occurs. If page is invalid: If memory reference actually exists on hard disk - page in the required page. If not, the process is terminated (illegal memory access).
What's a virtual address space for a process?
Set of virtual memory addresses that it can use. A virtual address does not represent the actual physical location of an object in memory; instead, the system maintains a page tablefor each process, which is an internal data structure used to translate virtual addresses into their corresponding physical addresses. Each time a thread references an address, the system translates the virtual address to a physical address. The virtual address space for 32-bit Windows is 4 gigabytes (GB) in size and…
What's meant by a page size?
Page size is the amount of bits that can fit into this page! Page is a set of virtual addresses (that map to frame - a set of actual physical RAM addresses).Size of a page = amount of bits that can fit into this page!So, if the system is byte-addressable, it's 8*number of RAM addresses in a page.