UF COP4600 - Exam 1

UF COP4600 - Exam 1 Algorithm - ANS set of instructions with finite initial store and state, a starting point, and unambiguous ordering until the endpoint Process (general definition) - ANS a program in execution = program + state Program - ANS sequence of instructions that embody an algorithm Job - ANS a task to be completed Why need an O.S.? - ANS - load program onto computer - access and supervise I/O devices - manage resources - protect private info - facilitate program interactions 2 main OS Roles? - ANS 1. resource manager 2. extended machine 3 types of resource management - ANS 1. process manager (who executes) 2. memory manager 3. I/O management Purpose of extended machine - ANS allows user to not think about low-level things. (file storage for example) What OS is not? - ANS - not UI - not development tools - not libraries (even if it may use them) 3 general OS types - ANS - interactive (laptop/pc) - batch (priority is pre-defined queued tasks) - real time (well-defined task priorities like in avionics or cars) 5 generations of OS - ANS '45-'55 : vacuum tubes / plugboards '55-'65 : transistors/batch '65-'80 : ICs and timesharing '80-now : PCs '90-now : mobile computers and multicore systems Multiprogramming v. Uniprogramming - ANS multiple = 2+ programs' data concurrently in main memory (RAM) (uni is just 1 at a time) T/F: modern systems do not allow direct reads from the disk, rather a syscall is passed to the kernel which then returns the info (if allowed) - ANS True 2 types of named calls - ANS 1. procedure calls 2. system calls Procedure Calls - ANS - essentially a function call - no context switch to kernel space (faster bc no OS help necessary) - local vars and parameters - frame pointer (where stack was before call) - stack pointer (where new bottom of stack is) Segments of Process in Memory - ANS - TEXT(lowest): code being executed - DATA(middle growing up): static + dynamic - STACK(highest growing down): activation frames of calls System Calls - ANS - provide interface to OS services - context switch to kernel mode - has sys lib entry point - invocation causes kernel trap - sys call number identifies a sysfunc from table - returns to library, returns to user program - parameters stored at specific mem. locations Hardware Interrupts - ANS - hardware device sends interrupt request signal to the CPU through interrupt controller - CPU acks interrupt (implicitly checks for interrupts before each new instruction is loaded) - interrupt controller sends specific IRQ # - current CPU instruction interrupted and dispatcher finds correct handler, executes - CPU resumes in user mode - type of ASYNCHRONOUS TRAP Handle an interrupted interrupt process? - ANS - solved with interrupt masks - a CPU feature that allows computer to ignore an interrupt request until mask bit is disabled - stores interrupt data in a (sometimes dedicated) register until ready - implement protection states that allow for hierarchical interrupting Precise Interrupt Qualities (4) - ANS 1. PC saved in known state 2. All preceding instructions fully executed 3. No instructions after PC have been executed 4. Execution state of PC instruction is known Imprecise Interrupts - ANS - instructions are left incomplete or partially executed - could simulate precision by rolling back incomplete instructions - modern systems use mostly just precise interrupts Process Model requirements: - ANS 1. unique ProgCounter, mem space, stack and program pointer 2. independent execution from other processes (both requirements maintained by OS) Pseudo-parallelism - ANS - imitates parallel execution on single processor by taking turns - processes run for fractions of a second (quantum) and either return CPU control or are pre-empted - registers hold state of process while running - state is stored elsewhere when process is swapped Process Creation - ANS - sys initialization (init) - process request (fork) Process termination - ANS - Normal exit (voluntary) - Abnormal exit (voluntary) - Fatal error (involuntary) - Killed by another process (involuntary) Process Control Block - ANS - process mgmt: reg. values, process parent, stack ptrs. - mem mgmt: text seg. ptr, heap seg. ptr, data seg. ptr, stack seg. ptr - file mgmt: root and working directory Summarize 4 general parts of memory - ANS 1. stack: data to return to procedure call, local vars 2. heap: dynamic allocations 3. data: constants, global, static vars 4. text: instructions to execute Scheduler's Job - ANS respond after interrupts and balance needs/turns of all relevant processes Process states - ANS 1. Running 2. Ready 3. Blocked (yields CPU) 4. Swapped out, blocked (not in RAM, waiting on external event) 5. Swapped out, ready (not in RAM, ready to execute upon load) 6. Initializing (preparing to run) 7. Exiting (cleaning up) Process State Diagram - ANS Context Switching causes: - ANS VOLUNTARY: - blocking operations (I/O) - cpu yield operations INVOLUNTARY: - cpu sharing (time expired or more important process comes) - async events (hardware interrupts, signals (software interrupts), exceptions) Context Switching process: - ANS - store register values - track memory addresses - update process state if necessary Signals (software interrupts) gen. def - ANS - sent by kernel or process - some signals restricted - can catch / ignore most Handling signals - ANS - kernel receives signal via system call (syscall flags target process PCB to show signal pending) - if PCB has registered handler the signal is stored and handled upon next CPU turn - if no registered handler, target process is terminated T/F: A process can have multiple threads. - ANS True Thread - ANS - part of a process - has own execution history (state), program counter, registers, stack Elements unique to process but not thread: - ANS - text - data (global/static vars) - heap - signals/handlers - open files (meaning some data is shared between threads so CAUTION!) Benefits of Threading - ANS - break up complicated tasks into smaller ones - improve efficiency compared to new processes, threads are: - lower mem cost and allow info sharing through common mem - reduced creation/termination time - reduce context switch time (switching threads easier than switching processes) User v. Kernel Threading - ANS - generally differentiated by location of process's thread table: user threading keeps it within PCB space, kernel threading keeps it in kernel space (with global processes table) - kernel threads are OS-specific - syscalls block entire user process, but only single thread for kernel processes - user threads all share one CPU, kernel threads use multiple CPUs Hybrid Threading - ANS - mix of user and kernel threading - thread table of user process in kernel space (like kernel threading) - each thread of user process is threaded again and holds its own threading table for its sub-threads Dangers of Threading - ANS - corrupt data state (wrong, lost or duplicated) - race conditions Inter-process Communication uses: - ANS - coordinate actions - transmit data - notification of events - updating status Why is shared memory a bad way to solve inter-process communication? - ANS - requires shared space - caching and consistency issues - requires explicit syncing Message Passing general - ANS - allows inter-process communication - library or OS support needed - system handles syncing - no mem-specific problems - some assembly required - handled by kernel and usually a file based transaction - 2 main types: pipes (same machine ) and network sockets (same and diff machines) - can be used for mutual exclusion problem Message Passing Protocol - ANS - connecting to and addressing recipients - formatting and encoding info - data buffering and flow control - message delivery and ordering (guaranteed and secure?) - synchronization (block on send and/or receive?) Race Condition - ANS - flaw that occurs when two processes or threads attempt to access the same resource - first to access resource wins, can result in bad computations What is the general solution to race conditions? - ANS Critical Regions! - allow certain parts of code to perform atomically wo interruption Requirements to avoid race conditions: - ANS 1. Concurrency: no assumptions about speed/# of CPUs 2. Safety: no two related processes can be in critical regions (CR) at same time 3. Liveness: no external process can block a process's CR and no process should wait forever to enter CR 2 Synchronization Criteria - ANS 1. Safety: data and state remain consistent 2. Liveness: all procedures will eventually complete (no deadlocking or starvation) 6 approaches to synchronization? Which are OS dependent? - ANS 1. busy waiting with spin lock (no) 2. monitors (no) 3. shadow copies (no) 4. messaging (YES) 5. barrier synchronization (YES) 6. semaphores and mutexes (YES) Shadow Copies - ANS - solves issue of multiple processes reading and writing - steps: 1. make original data read only 2. make copy of og data 3. update copy with new info 4. change data ptr to new copy 5. delete old copy Barriers (for syncing) - ANS - requires all processes to reach a specified point before they can continue - should not have any busy waiting because it will always let slow processes catch up before continuing (assuming barrier is necessary at that point of execution) Monitors (for syncing) - ANS - yields CPU so no busy waiting - language construct that uses "conditional vars" to block and unblock - resolved semantically so no variable in memory - guarantees only 1 process at a time purpose of Mutexes and Semaphores? - ANS - SYNCHRONIZATION - shared memory variables provided by OS as blocking-based locking mechanism (no busy waiting) Mutex - ANS - single bit lock of 0/1 - 2 operations: lock() and unlock() - only the locking process/thread can unlock it - for use in critical regions Semaphore (gen. def) - ANS - array of locks (integer) rather than one like a mutex (but can be unlocked by any thread/process) - operations are create(), up(), down() - provides resource counting/tracking for multiple resources Semaphore Operations - ANS - creation: with starting count (number of allotted resources) - down: if 0, decrement and do CR and eventually up, else block and add to queue - up: if queue empty, increment S and continue, else exit to unblock first in line Busy Waiting and the Peterson Solution - ANS PROBLEM: strict alternation trades turns between two processes which is bad because one process may be ready multiple times before the other one is once..... so flag interest. but flagging and locking are not atomic. SOLUTION: add a variable for turn. wait to enter CR while other process is interested and has the turn Atomic Locking - ANS 1. Test and Set Lock 2. Swap or could use Mutexes, while this requires OS support it does allow process to yield CPU Dining Philosophers Problem and Criteria - ANS A problem demonstrating the pattern of circular deadlock among several competing processes. Concurrency: no assumptions about length of any process Safety: any two processes that are not logically adjacent can eat simultaneously Liveliness: no process can prevent another from eating nor go starved General Solution to Dining Philosopher's - ANS relinquish resources if one does not have all necessary to act Producer-Consumer Problem and Criteria - ANS - the bounded buffer problem - one or more producers/consumers act on same finite data buffer - producers place data, consumers TAKE data Concurrency: no speed assumptions Safety: No writing simultaneous writing by producers nor consumptions by consumer and no pre-emptive reads Liveness: no busy-waiting if not readin or writing Correctness: no overwriting (wait to be cleared) and no empty reads Producer-Consumer Solution - ANS Kinda semaphores, but not really. the critical region bottleneck (bc only one process can touch buffer at a time) is worse with more concurrent players. so, we lock individual entries of the buffer instead instead! Readers-Writers Problem and Criteria - ANS A problem with one or more readers that only read and one or more writers (which may also read) working on a single database simultaneously. LIKE Producer-Consumer EXCEPT DATA STORE IS PERSISTENT. so many can read at a time or consecutively Concurrency, Safety and Liveness Readers-Writers Solution - ANS Kinda semaphores, but not really. time is wasted by writers that are reading. so.... Alpha locks signal intent to lock data store. If writer has a-lock others can read but not write. then from a-lock they get write-lock. basically like a half-lock T/F: There is a significant difference between theoretical and actual efficiency when measuring scheduling efficiency. - ANS True 3 scheduler types: - ANS - admission (long term): generally used for batch systems or maybe deciding software updates on a pc - memory scheduler (medium term): is main memory available? swaps out blocked jobs - CPU scheduler (short term) T/F: Main memory is also known as RAM - ANS True Common Scheduler Goals - ANS Fairness, Policy enforcement, Balance (CPU used well) Batch Scheduler Goals - ANS - minimize mean turnaround - maximize processor utilization - use priority basis Interactive Scheduler Goals - ANS Response time (especially to I/O), Proportionality Real-Time Scheduler Goals - ANS Meet deadlines, predictability When is CPU scheduled? - ANS 1. (MUST) on process exits/blocks 2. (usually) on process creation, i/o interrupt or clock interrupt (for pre-emptive) Scheduling Decision Points - ANS - turn-around time = finish - arrival - mean turnaround - fairness (like max CPU time) - makespan = finish of last job - start time of job set - realtime deadlines (on real-time schedulers) Non-Preemptive Scheduling Algorithms - ANS - shortest ready job first (requires time knowledge from history and code analysis) - first come first served (not great) - priority - optimal (great, but using future knowledge) T/F: Pre-emptive schedulers issue timer interrupts after a certain number of quantum to 'check in' on process. - ANS True T/F: Interactive systems almost always use preemptive schedulers for the sake of user experience over efficiency. - ANS True Preemptive Scheduling Algorithms - ANS - shortest remaining time first (optimal if no context switch cost) - round robin (order of arrival and varies with turn-quanta size) - priority - compatibility time sharing Round Robin Turn Time Debate - ANS - long enough to reduce context switching, but short enough to give user a good experience T/F: Preemptive priority scheduling often works in tandem with another deciding algo. (like Round Robin). - ANS True Compatible Time-Sharing System (CTSS) - ANS a system that gives processes a certain number of turns then moves them down a level of priority. but they get higher time turns at lower priority levels. Proportionate Scheduling - ANS - prioritized by actual CPU usage - lottery scheduling where processes have different amounts of tickets - CPU time allocated to user, not process Real Time Scheduling and Tasks, Categories - ANS Tasks are either periodic or aperiodic (interrupts). Schedulers are either hard (serious consequences) or soft (just inconvenient to miss deadlines) Roles of Memory Management - ANS 1. Addressing 2. Protection 3. Allocation Two Addressing Approaches - ANS 1. physical (absolute location on mem. chip) 2. logical (relative location that is translated by hardware/OS) When can physical addresses be resolved? - ANS - dev time - compile time - link time - load time - run time Fence register - ANS Register TO PROTECT KERNEL MEMORY SPACE ( usually used in uniprogrammed systems.) Holds physical address that acts as the line between user space and kernel space High/Low registers - ANS registers used in multiprogramming environment to act as fence on both sides. set at every context switch Base/Limit registers - ANS a lot like high/low registers but use a base address (low) and limit (size of mem range) to do logical addressing Problems of Memory Allocation - ANS - how track free space? - how find process space? - right size for blocks? - should extra space be allocated for process (stack/heap)? Bitmaps - ANS - way to track free memory - essentially a map of memory blocks with 0s representing open space T/F: Linked lists can be used to track open memory blocks using nodes that include the starting address and length of each grouping/opening. - ANS True, but bad for finding holes. 'Hole-List-Ic' Approach - ANS - linked list to keep track of ONLY OPEN memory blocks - separate list is kept with processes and their respective memory groupings Process Memory Allocation Algos. - ANS - first fit (take first opp) - next fit (take 2nd opp) - best fit (smallest hole big enough) - worst fit (largest available) - quick fit (separate lists of commonly requested sizes) T/F: Multiprogram environments must be partitioned to allocate a certain memory segment to each process. - ANS True T/F: Under MFP, partitions may have different fixed sizes. - ANS True Multiple Fixed Partitions - ANS - pre-existing cut out partitions of differing sizes - can either have shared queue (any process can take any eligible partition) or separate queues (small process to small partition only, large to large only) Multiple Variable Partitions - ANS - no defined partitions, just take what you need - process takes next eligible space atop the stack - EXTERNAL FRAGMENTATION problem where small memory pockets exist as unusable Solutions to External Fragmentation - ANS - mfp - compaction - paging and segmentation Memory Compaction - ANS - process memory blocks are slid to the bottom of the stack and therefore all gaps (besides above) are closed. like rocks falling to ground Memory Overlays - ANS - part of main mem stored on disk and swapped in/out as needed - no OS involvement needed - require overlay manager to track program and/or data sections and load them as-needed Virtual Memory - ANS - process gets virtual address space that is broken into pages or segments - process uses virtual addresses and OS translates them - SEGMENTATION: breaks up processes into its components and OS swaps out parts as necessary - PAGING: breaks mem into even chunks which are swapped in and out of physical memory (with OS help) T/F: Paging cannot trigger external fragmentation. - ANS True MMU (Memory Management Unit) - ANS a hardware device that handles the details of address translation in a system with virtual memory (virtual to physical translator) Page Table - ANS - table containing the virtual to physical address translations in a virtual memory system - typically indexed by the virtual page number and contains the physical page number for that virtual page if the page is currently in memory Cache Types - ANS - instruction - data - translation lookaside buffer Cache Issues - ANS - what is line size / replacement policy? - cache consistency Translation Lookaside Buffer (TLB) - ANS A cache that keeps track of recently used address mappings to try to avoid an access to the page table. Cost of Accessing a page - ANS = (1 - Pcm)*Tc + (Pcm*Tmm) where: - Pcm is probability of cache miss - Tc is time to access cache - Tmm is time to access main memory T/F: Overlays are a user-space approach while segmentation utilizes the OS. - ANS True Standard cache line size - ANS 32-256 bytes Effective Access Time (EAT) - ANS = ((1 - P_inTLB)*(T_readPageFromRam+T_readTLB+T_readRAM)) + (P_inTLB*(T_readTLB+T_readRAM)) Reference Strings - ANS - string variable that tracks when logical address pages are accessed (in order) - duplicates are removed for redundancy Paging Algos. - ANS 1. FIFO 2. LRU (least recently used) (better than FIFO)