COP4600 Final Combined With Corrrect Answers

COP4600 Final Combined What pieces of hardware are in the CPU? - ANS Registers, ALU, and control unit Hardware which serves as the CPUs memory. There are special and general purposed of these - ANS Registers Hardware which does arithmetic and logical computations - ANS ALU Hardware which tracks state/status. Also controls other components - ANS Control unit Instruction cycle responsible for loading the instruction - ANS Fetch Instruction cycle responsible for finding the opcode/operands of the instruction and interpreting it - ANS Decode Instruction cycle responsible for carrying out the instruction - ANS Execute Protected instructions can only be executed in a ____________ - ANS Protected state Legacy boot process - ANS BIOS What does BIOS stand for? - ANS Binary Input Output System The ________ bootstraps the boot sector - ANS Bootloader What does bootstrap mean? - ANS Loading up the computer Why are the bootsector and bootloader separate? - ANS Bootsector is too small Where is the BIOS init stored? - ANS The motherboard What boot process is usable on x86-64 (i386) standalone PCs? - ANS BIOS What boot process has standard for ARM chipset systems? - ANS Neither Which boot process has standardized NVRAM locations for system variables? - ANS UEFI Which boot process uses a dedicated bootloader partition? - ANS BIOS Which boot process is usable on x86-64 (x64) standalone PCs? - ANS Both Newer boot process - ANS UEFI Which boot process simplifies diskless systems? - ANS UEFI What are the functions of an OS? - ANS Loading programs onto machine, controlling I/O devices, managing resources (memory, CPU), multi-tasking execution, data protection (permissions), and task interaction (pipes, networking) Mode for directly manipulating hardware - ANS Kernel mode T/F: No device is directly accessed without the kernel - ANS True T/F: Only system libraries can invoke system calls - ANS False T/F: The system call invokes code written by system developers, while a procedure call invokes code written by an application programmer - ANS False A running program is in ______ - ANS Execution When we run a program, we create a _________ for it - ANS Process Features of a process - ANS Has some address space, associated with specific resources, computational element/object, and has one or more threads of execution When we make a _______, we add a stack frame to the call stack - ANS Procedure call Which pointer points to the beginning of the stack frame? - ANS Frame pointer Which pointer points to the beginning of the call stack? - ANS Stack pointer A ___________ involves a switch into kernel mode for execution - ANS System call Invocation of a system call causes a what? - ANS Kernel trap What must be stored in a kernel trap? - ANS Current address, registers, etc What gets the address from the interrupt vector during a kernel trap? - ANS OS dispatcher Generation of pre-OS in which there was a control room in which a human operator ran programs (plugboards) - ANS Generation 0: The operator When was Generation 0 of OS? - ANS 1940s When was Generation 1 of OS? - ANS 1950s Generation of OS in which a resident monitor was used to execute common tasks (basic job loading, config, etc) for the operator. Users would reserve time on the system. Precursor to modern concept of OS - ANS Generation 1: resident monitor Generation of OS in which job systems allowed many programs to be run in succession. A programmer would submit a job on punch cards. The punch cards would be read by a card reader onto magnetic tap. An operator would transfer prepared jobs to processing unit on input tape. Results would be written to output tape, which would be read and printed - ANS Generation 2: Batch systems Batch system in which the OS sets up the next job and removes the current. Programs are run sequentially - ANS Uniprogrammed batch systems Fence in memory which defines end in user memory and beginning of OS memory - ANS Fence register Issues with uniprogrammed batch systems - ANS Mainly I/O so idle CPU Batch system in which when one job was running, the OS would set up and began to run next. They would take turns on the CPU. In this system, the CPU was on idle when all jobs were in system - ANS Multiprogrammed batch systems Formula for CPU utilization - ANS 1 - p^n (p = fraction of time process is in I/O wait; n = # jobs) When were batch systems prevalent? - ANS 1950s/1960s Gen of OS which had multiple users on the same system - ANS Generation 3: Time sharing systems Gen of OS which was uniprogrammed (ex DOS) - ANS Generation 4: Early PC OS Gen of OS which logins, multitasking, etc. First one was Unix - ANS Generation 5: Network OS OS which sends off execution to a remote system and gets the results back - ANS Distributed OS OS which had multiple independent systems with intertwined actions - ANS Cooperative autonomous systems Set of instructions with finite initial store and state, starting pointing, and unambiguous ordering until the endpoint - ANS Algorithm The sequence of instructions that embody an algorithm (source to assembly to machine code) - ANS Program A task to be completed. Often a program awaiting execution or a process during execution - ANS Job The conceptual process model requires: - ANS Unique PC, independent execution, and maintenance of model by OS ______ imitates parallel execution on a processor. Each process uses the CPU in turn. Registers hold state of process while running. System switched processes. State is stored elsewhere when the process is swapped - ANS Pseudoparallelism Processes are created by what things? - ANS System initialization (init), process request (fork), user request (UI), and batch job Processes are terminated by what things? - ANS Normal exit, abnormal exit, fatal error, and signalling/kill via process Voluntary ways processes are killed? Meaning they kill themselves - ANS Normal and abnormal exits Involuntary ways processes are killed? Meaning the OS kills it - ANS Fatal error and signalling/kill via process Hardware exceptions are generally _______ termination - ANS Involuntary Part of OS which handles CPU scheduling. Usually 2-3 unique systems - ANS Scheduler Roles of the scheduler - ANS Handle interrupts (I/O, etc), decides which process gets to run and when, and balances process needs to avoid problems (i.e. starvation) Process state in which the instructions are executing in main working memory - ANS Running Process state in which it is runnable in main working memory, but it is not currently executing instructions - ANS Ready Process state in which it is waiting in main memory waiting for an external event - ANS Blocked Process state when it is not in RAM, but it is waiting on an external event - ANS Swapped out and blocked Process state when it is not in RAM, but ready to execute upon load - ANS Swapped out and ready Process state in which process is not in RAM but is preparing to run - ANS Initializing Process state in which the process is not in RAM and cleaning up following execution - ANS Exiting T/F: Shared memory space is required for the process model - ANS False What information is stored in the process control block - ANS Process, memory, and file management Instruction part of process. Contains binary code instructions - ANS Text Segment which has the data in an executable. Where static variables are stored - ANS Data Segment for allocated memory (new/malloc) and shared memory across stack frames - ANS Heap Segment for stack frames and function variables - ANS Stack The PCB treats devices as _______ - ANS Files The heap grows ____ while the stack grows ____ - ANS Up, down What info is available in an executable? - ANS Header, text, data, and symbols Part of the executable which contains linkages (ex. library functions) - ANS Symbols Part of the executable which contains basic info such as organization of the executable itself - ANS Header Which process segment contains pointers? - ANS Stack What is stack/heap overflow? - ANS No space left between stack/heap Why do context switches occur? - ANS Blocking operations, CPU yield operations, CPU sharing, and asynchronous evemts Examples of blocking operations which cause context switches - ANS IO and sleep Examples of asynchronous events which cause context switches - ANS Hardware interrupts, signals, and exceptions What are signals? - ANS Software interrupts What must the OS do during context switches - ANS Store register values, track memory addresses, and update process state if necessary When Device raises the signal line which is checked every instruction. The hardware jumps to interrupt vector and a ______ has occured - ANS Hardware interrupt T/F: Hardware interrupts can be ignored only in protected state - ANS True What happens when a process receives a signal it is registered to catch - ANS 1) Kernel receives signal via system call 2) IF PCB has registered handler for the target, the signal is stored and the handler queued 3) If there is no registered handler, the target is terminated 4) Normal function continues What happens during a hardware interrupt? - ANS 1) Device raise line 2) Controller sends interrupt 3) CPU asks interrupt 4) Controller sends IRQ# What hardware causes the trap to kernel mode? Responsible for the context switch, looking up routine according to interrupt #, and changing the protection state - ANS Dispatcher (IRQ) T/F: Signals are invoked by the kernel and process - ANS False T/F: Signals involve a syscall - ANS True T/F: On multicore systems, the interrupt controller can be programmed to send different interrupts to different processor cores - ANS True Why must hardware interrupts be super fast? - ANS They constantly happen and prevent all processes from running Location of the next instruction to execute after returning from a procedure call is found in the _____ segment - ANS Stack Constants are found in the what segment of a process? - ANS Data Parameters passed to a procedure/method are located in the what segment of a process? - ANS Stack In what segment of a process can memory leaks occur? - ANS Heap In what segment are global variables found? - ANS Data Where are dynamically allocated variables located? - ANS Heap Where are instructions to be executed located? - ANS Text T/F: In batch systems, the user was the operator - ANS False T/F: I/O-bound jobs underutilize the CPU in uniprogrammed systems - ANS True T/F: A major motivation for multiprogramming batch systems was improving resource utilization - ANS True T/F: Memory protection was not needed in uniprogramming batch systems - ANS True T/F: Batch systems had to implement multiprogramming - ANS False T/F: Stack and heap allocation always happens when an OS handles an interrupt? - ANS False What happens whenever an OS must handle an interrupt? - ANS PC is stored, CPU registers are stored, and ISR is invoked In a ______, hardware and system tasks are in kernel space - ANS Microkernel In a ______, hardware, file system, and device drivers are in kernel space - ANS Monolithic kernel Can an interrupt be interrupted? - ANS Yes Hardware mechanism which prevents and sets the hierarchy of interrupts - ANS Interrupt mask Interrupt with 4 specific qualities: 1) PC saved in a known state 2) All instructions PC were fully executed 3) No instructions after the PC have been executed 4) Execution state of PC instruction is known - ANS Precise interrupt In a _________ interrupt, the instruction will finish execution before the interrupt is serviced - ANS Precise Interrupt when instructions are left incomplete/partially executed - ANS Imprecise interrupts T/F: We can always get a precise by rolling back incomplete instructions - ANS Not always Three types of schedulers - ANS Admission, memory, and CPU Scheduler which decides which and when a job runs. Deals with queued data/tasks. Long-term scheduler - ANS Admission Scheduler which decides which jobs to swap in/out of main memory. Deals with user interaction. Medium term scheduler - ANS Memory Scheduler which decides which ready process runs next. Usually only pulls from RAM. Short-term scheduler - ANS CPU Goals of the admission scheduler - ANS Get a good mix of jobs in RAM, predict job needs and behavior Goals of the memory scheduler - ANS Prevent thrashing When excessive paging operations are taking place and the system appears to be very slow or has come to a halt, the process is ________ - ANS Thrashing Which scheduler is most concerned with speed? - ANS CPU In which system is the CPU schedulers goals response time, proportionality, and the users. They will sacrifice optimal solutions for UX. They have to prevent the impression of starvation - ANS Interactive system In which system is the CPU schedulers goals predictability and deadlines. If deadlines are missed, BAD things happen - ANS Real time In which system is the CPU schedulers goals throughput, turnaround time, and CPU utilization - ANS Batch system When is CPU scheduling ABSOLUTELY required - ANS When a process exits and when it blocks on I/O or a semaphore When is CPU scheduling usually done, but not required - ANS When a new process is created, when an I/O interrupt occurs, and when a clock interrupt occurs Type of scheduling algorithm when a process is executed for a certain amount of time, then it loses the CPU and the OS regains control - ANS Preemptive Type of scheduling algorithm which expects the process to give up the CPU - ANS Nonpreemptive What scheduling algorithms are nonpreemptive - ANS First come first server, shortest job first, priority, and optimal What scheduling algorithms are preemptive - ANS Round robin, shortest remaining time first, preemptive priority, and compatible time sharing systems Scheduling algorithm in which jobs are run in order of arrival - ANS First come first serve Scheduling algorithm in which the ready job that will finish first is run first. Nonpreemtive - ANS Shortest job first Scheduling algorithm in which the ready job with highest priority is run first - ANS Priority Scheduling algorithm which uses future knowledge of arrivals to optimize - ANS Optimal Scheduling algorithm in which jobs run in order of arrival, with max quantum (end of queue if preempted) - ANS Round robin Scheduling algorithm in which the ready job that will finish first is run first. Preemptive - ANS Shortest remaining time first Scheduling algorithm in which the ready job with highest priority is run first. Preemptive - ANS Preemptive priority Scheduling algorithm which attempts to approximate SRTF. Uses growing quanta allocations. The longer a process goes, the lower its priority goes. Processes get allocated entire quanta spots regardless of how much time is left (i.e. giving 8 when only needs 5) - ANS Compatible time sharing systems T/F: If all jobs are ready, SJF is optimal - ANS True Which is the fastest preemptive Scheduling algorithm if there's no context switch cost? - ANS SRTF T/F: All priority systems run the chance of starvation - ANS True Scheduling algorithm which approximates SRTF via observed process history. - ANS Shortest process next Formula for CPU time of 1 process with shortest process next Scheduling algorithm - ANS E(sub i) = aE(sub i - 1) + (1- a)T(sub i) Proportionate Scheduling algorithms - ANS Guaranteed, lottery, and fair share Scheduling algorithm in which each process gets tickets. A ticket is picked at random. The more tickets a process has, the higher probability of it being selected - ANS Lottery scheduling Scheduling algorithm in which CPU time is allocated to each user, not process. Can use lottery approach and prioritize users - ANS Fair share scheduling Tasks which happen repeatedly (check altitude, etc) - ANS Periodic tasks Tasks which are a result of external events (temp in core too high) - ANS Aperiodic tasks Real time systems in which a missed deadline results in a disaster - ANS Hard real time Real time systems in which a missed deadline results in an annoyance - ANS Soft real time When can we schedule dynamic real time systems? Use c as the tasks compute time and p as the tasks period - ANS ∑(c/p) ≤ 1 __________ is when a low priority task blocks a high priority task - ANS Priority inversion How can we solve priority inversion? - ANS Grant low priority task temp promotion to resolve A _______ (lightweight process) is part of a process that has its own execution history, program counter, and stack - ANS Thread What elements are unique to a process but not a thread? - ANS Text, data, and heap Benefits of threads over processes - ANS Lower mem cost, information sharing, reduced creation/destruction time, and reduced context switch time (to a sibling thread) _____ space threads are supported by the OS, _______ space threads are implemented in a library - ANS Kernel, user Threads which have separate thread table stored in the kernel. Threads can be run in multiple CPUs - ANS Kernel space Threads which have thread table stored in each process - ANS User space In which space does a syscall in a thread block all other sibling threads? Why? - ANS User bc kernel can't see threads and the entire process is run in 1 CPU In which space can you switch from executing a thread in process A to a thread in process B at any point (with a context switch)? - ANS Kernel Dangers of threads - ANS Corrupt data state, race conditions, lost data, and duplicated data Threading in which one kernel thread contains all user threads (including their thread table). The kernel thread table on has kernel threads listed - ANS Hybrid Why would processes need to communicate? - ANS Transmission of data, notification of event, and updating status Issues with IPC - ANS Synchronizing the processes and actually transferring the info IPC in which process directly writes to a shared memory space. Requires programmer support - ANS Shared memory IPC which avoids memory specific problems and handle synchronization issues. Needs library or OS support and some assembly - ANS Message passing Examples of message passing systems - ANS Pipes and networks Message passing system which can be named/unnamed. They are created on the fly for use by localhost and are set and used - ANS Pipes Message passing system which uses TCP/UDP to communicate host to host - ANS Networks Which IPC system can result in race conditions - ANS Message passing Regions of code that we must protect - ANS Critical region What 4 rules must we maintain to avoid race conditions - ANS 1) No assumptions may be made about speed or # of CPUs (concurrency) 2) No two processes may be simultaneously within their related CRs (safety) 3) No process running outside CR may block other processes inside it (liveness) 4) No process should have to wait forever to enter its critical region (liveness) Failure of maintaining safety (consistent data and state) for process synchronization may result in what - ANS Invalid state of application data or application functional state Concept that all processes will eventually complete - ANS Liveness When every process depends on one that is block and no progress is made - ANS Deadlock When some processes wait indefinitely - ANS Starvation Approaches to process synchronization - ANS Busy waiting, monitors, shadow copies, messaging, barrier synchronization, and semaphores and mutexes When there is a giant wait loop waiting on a condition. Can be software or hardware based. Also called spin lock - ANS Busy waiting Signaling type system which requires language support. Use condition variables (no variable memory) and guarantee at most one process at a time - ANS Monitors Software locks which require OS support. They use atomic operations to facilitate locks - ANS Semaphores and mutexes Process synchronization which uses copies to update data - ANS Shadow copies Synchronization process which requires all processes to reach a specified point before they can continue - ANS Barries Mutual exclusion variables which lock and unlock only. Intended for single process at a time CR - ANS Mutex T/F: Once locked, only the locking thread can unlock a mutex - ANS True Shared memory variables which up (increment) and down (decrement). Only down blocks. They provide resource counting/tracking - ANS Semaphore T/F: Any thread with access to the semaphore can increment/decrement - ANS True What type of semaphores can be used to enforce a precedence graph? - ANS Binary semaphores T/F: Spin locks yield the CPU when waiting for a resource to become available - ANS False ______ trades turns between two lines of execution. It is extremely inefficient - ANS Strict alternation Why does busy waiting with flagging interest fail? - ANS Flagging and locking are not atomic (could be interrupted right after interest is flagged causing infinite loop) Solution which combines flagging and alternation approaches. After flag, switch turns. Loop while other's turn and other's interested - ANS Peterson solution Problem which occurs when one or more producers and consumers act on the same finite data buffer. Also called the bounded buffer problem. - ANS Producer-consumer problem T/F: Multiple producers/consumers should be able to write/read buffers at the same time - ANS True T/F: two producers/consumers can write/read to same entry at same time - ANS False Problem which occurs when several processes need more than one lock to act. Causes circular deadlock - ANS Dining philosophers problem Problem in which one or more readers/writers work on a single database (data store) at the same time. Deals with persistent data - ANS Readers writers problem T/F: never can 2 or more writers write to db at same time - ANS True T/F: a reader can reader from db while a writer is writing - ANS False T/F: If write lock is held, all other read and write requests are blocked - ANS True In a reader preference policy, what bad things could happen? - ANS Writers could starve Tentative write lock which lets us signal intent to lock the db. Allows tentative reading while waiting for a write lock. Prevents other writers from obtaining an alpha lock - ANS Alpha lock T/F: Main benefit of overlay systems is that they allow a process to be larger than the available memory - ANS True T/F: External fragmentation is a problem with contiguous memory allocation - ANS True Absolute memory address aka location on memory chip - ANS Physical address Relative memory address. Will be translated by hardware and OS to actual location - ANS Logical address When can addresses be resolved? - ANS Development time, compile time, link time, load time, and run time T/F: If using physical addresses, addresses do not have to be resolved before run time for any - ANS False When an address hard coded it is resolved at _______ - ANS Development time When an address is resolved by the compiler it is resolved at _____ - ANS Compile time When an address is resolved by the linker it is resolved at _____ (e.g. static libraries) - ANS Link time When an address is resolved by the loader it is resolved at _____ (e.g. shared libraries) - ANS Load time When an address is a process address space it is resolved at _____ - ANS Run time ______ and _____ registers are used to protect processes by defining memory boundaries. They are set at every context switch - ANS High, low ____ and _____ registers are used to define the start and max of a process's boundary. They are checked on every run - ANS Base, limit Memory allocation algorithm which uses the first hole big enough for the process - ANS First fit Memory allocation algorithm which uses the next hole big enough using circular array - ANS Next fit Memory allocation algorithm which finds the smallest hole big enough - ANS Best fit Memory allocation algorithm which finds the largest hole available - ANS Worst fit Memory allocation which uses separate lists of commonly requested sizes - ANS Quick fit Memory partitioning scheme which uses partitions of fixed size - ANS Multiple fixed partitions Memory partitioning scheme which uses partitions of variable size to accommodate process load - ANS Multiple variable partitions Fragmentation which results from memory allocated to a process but not in use - ANS Internal fragmentation Fragmentation which results from memory not allocated to a process but too small to use - ANS External fragmentation Solutions to external fragmentation - ANS Fixed memory partitions, compaction, and paging and segmentation Cons of memory compaction - ANS SUPER slow (have to copy over all of memory) Part of memory stored on disk which is swapped in and out as needed. Completely user space approach. Could create thrashing - ANS Overlays Using virtual address space that maps to physical memory. Eliminates external fragmentation by only allocating page. Requires explicit OS support - ANS Virtual memory Exists in user space to track program /data sections and loads them on an as-needed basis - ANS Overlay manager Cons of fixed partition memory approaches - ANS Susceptible to internal fragmentation Used by the CPU to calculate physical addresses from virtual ones quickly. Exists on the CPU die - ANS Memory management unit (MMU) Solutions to a large page table - ANS Page the page table or inverted page table T/F: Virtual memory space may be bigger than physical memory - ANS True T/F: Physical memory space may be larger than virtual memory - ANS False Type of cache which has frequently used memory lines of text segments (may also be data) - ANS Instruction cache Type of cache which has recently/frequently used lines of data/stack segments - ANS Data cache Type of cache which has popular page table entries - ANS Translation lookaside buffer (TLB) T/F: all caches use associative (content-addressable) memory - ANS True Loaded pages are referred to as ______________ - ANS Page frames Formula for memory access time - ANS (cache hit)*(time to access cache) + (cache miss)*(time for disk) Paging algorithm in which the oldest page is evicted first - ANS FIFO Weird thing in FIFO were even if the number of frames increases, there are always situations were the fault rate increases - ANS Belady's anomaly Paging algorithm which evicts the most stale page - ANS LRU Paging algorithm which tracks the number of times a page is used, evicting the least used page. Good locally - ANS NFU Cons of NFU algorithm - ANS Requires lots of resources Cons of LRU algorithm - ANS Very inefficient bc it requires in place list modifications Describe aging paging algorithm - ANS R bit is set on read/write. M bit is set on write. R bit is cleared on clock tick. M bit is cleared when copied to disk. Unreferenced and unmodified pages are selected. Evict lowest page (RM bit combo) Paging algorithm which uses aging in a round robin approach. However, just looks at R bit - ANS Clock/second chance Paging algorithm which uses a time window to define a working set of pages that are most active - ANS Working set Paging algorithm which combines clock and working set - ANS WSClock What is invoked when a page fault occurs? - ANS Page fault handler Concept which stores segments into their own partitions to allow more flexible process growth policy - ANS Segmentation Type of segmentation in which each text, data, heap, and stack are in their own segment - ANS Fine grained Type of segmentation in which text, data, and heap are in their own segment and so is stack - ANS Coarse grained Why does coarse grained segmentation work? - ANS Bc text and data are a fixed size What functionality must a file system have? - ANS Locate free space, persistently store information, and allow concurrent access by more than one process Useful, but not required features of a file system - ANS Human accessible info, data protection, and identifying types of data/what programs can read the data Conceptually, a file is a storage that is _____________ and is _____________ - ANS Logically named, persistent 3 ways a file can be represented - ANS Byte sequence, record sequence, and tree based File representation that is mainly used - ANS Byte sequence File representation that is mainly used by legacy and specialized systems - ANS Record sequence Difference between byte and record sequence for file representation - ANS A record is multiple bytes long 4 ways to determine the file type - ANS Extension, magic number (file signature), file attributes, and reading the contents Issues with identifying the file type by its extension - ANS It's a security issue if the the extension is wrong Issues with identifying the file type by its magic number - ANS Magic numbers are not uniform across machines (are uniform in the machine) Where are the file attributes and location information stored? - ANS File control block 2 ways files can be accessed - ANS Sequentially and random access File access in which bytes are access ed in linear order. Some media types can rewind. Examples include tapes and pipes - ANS Sequential access File access in which data be accessed in any random order. The cursor can be moved via a seek. Examples include HDD, SSD, and floppy disks - ANS Random access Term which refers to adding a file to a directory - ANS linking Term which refers to removing a file from a directory - ANS unlinking When is a link created? - ANS On file creation When is a file considered deleted? - ANS When link count = 0 (file is not actually deleted, just unlinked) Can a file have multiple links? - ANS Yes 2 types of links - ANS Regular (hard) link, and symbolic (soft) link Link which holds the reference (inode, etc) of the file. Can only occur within the same file system. Can be used on directories (depending on OS) - ANS Hard link Link which holds the path of the file. Can span file systems. Can be used on directories - ANS Soft link Dangers of hard links? Soft links? - ANS Circular link; Link rot What is a circular link? - ANS A parent dir and child dir hold a hard link to each other What is link rot? - ANS A file is deleted, but a soft link still exists How is file deletion prevented when a file is open? - ANS It's link count is incremented A _______ is a special file type that holds FCB of other files. It is marked as such by its own FCB - ANS Directory 2 types of directory implementations - ANS Inline and reference Directory implementation in which each file has a block for its attributes which is directly followed by its data (F1, F2, F3, etc.) - ANS Inline approach Directory implementation in which each file has a block for its attributes and a pointer to its data (F1*, F2*, F3*, etc.). There can be a fixed length for a directory - ANS Reference approach How are file paths resolved? - ANS Recursive lookup (think ab a tree) What tells us the file system type, format, and organization? - ANS Super block Where are the boot block and super block located? - ANS On disk partition _______ a file system makes it accessible to programs through the OS - ANS Mounting Can you mount different file systems on top of one another? - ANS Yes File allocation scheme in which a file's contents are stored purely in order on the drive. Good for embedded hardware and read-only FS (CD/DVDs) - ANS Contiguous allocation What type of fragmentation does contiguous allocation for file systems suffer from? - ANS External File allocation scheme in which each block holds a pointer to the next. Random access requires iterating through blocks until the file is found. However, you can allocate/deallocate at will - ANS Linked list allocation File allocation scheme in which the linked lists are stored as a table in memory to minimize disk access. It's super fast because you only need to go to disk to read data blocks. Examples are USB and SSD cards - ANS Chained table allocation (FAT) File allocation scheme in which locations of each block are stored in an index node (inode). A pure index system limits file size - ANS Indexed allocation Formula for max file size - ANS (# blocks) * (block size) = (block size / pointer bytes) * (block size) File allocation scheme which indexes the index block, using direct/indirect blocks. It increases max file size, but each level added increases access time - ANS Multi-level indexed allocation File allocation scheme which uses direct blocks with an additional single indirect pointer. The number of blocks is reduced by one to make room for the next pointer. Has a potentially unlimited file size - ANS Chained indexed allocation What file allocation schemes require visiting every block in the file up to block n in order to find that block? - ANS Linked list and FAT Larger block size ______ data rate on a spinning disk - ANS Increases Larger block size ______ external fragmentation - ANS has no effect (it's internal fragmentation) Larger block size _______ max file size - ANS increases Larger block size _____ storage utilization rate - ANS Decreases (bc of internal fragmentation) Larger block size _______ on FS consistency rate - ANS has no effect 3 ways to keep track of free blocks for FS - ANS Linked list, bitmap, and storing pointers to free blocks on disk (can cause thrashing, so have more than one partially full list) How does the block cache work? - ANS Linked list of blocks in memory and hashtable pointing to blocks Where does most data loss stem from - ANS Human error When a FS stores the same info on 2 disks. Every write is duplicated and reads go to whichever system is least loaded. Failures can be automatically switched over - ANS Mirroring Backup which only backs up part of the system - ANS Selective dump Backup which doesn't back up a file if it isn't changed - ANS Incremental backup System which provides FS performance gains through parallel hardware access. Uses striping and redundant storage to allow fast recovery. Hot swap is possible - ANS RAID (Redundant arrays of independent disks) Term for when data is spread across multiple disks - ANS Striping Term for when while the system is running, a bad disk can be removed and replaced with a good one - ANS Hot swap RAID which is purely striping (no redundancy) - ANS RAID 0 RAID which is purely mirroring (no striping) - ANS RAID 1 RAID which uses striping at bit level and can detect, but not fix errors. Mostly theoretical - ANS RAID 2 RAID which uses mirroring and strips - ANS RAID 10 Which of these actions has a recovery option with no potential loss of information? 1) Block marked as both free and in use 2) Block marked in free list twice 3) Block marked in use twice - ANS 1) Yes. Mark as in use 2) Yes. Make it one listing 3) No. Most likely corrupt 2 types of I/O devices - ANS Block and character I/O device which sends and receives the entire block of data. Is addressable. Random access. Like memory - ANS Block I/O device which sends and receives individual bytes. Not addressable. Can be one or two way. Like a stream - ANS Character CPU IO which uses memory addressed communication. The device memory is considered part of main memory. There is no automatic interrupt and some assembly instructions are required - ANS Memory mapped (MMIO) CPU IO which uses isolated addressing communication. There is unique assembly instruction and distinct address space - ANS Port-mapped (PMIO) Two types of CPU IO (also called programmed IO) - ANS MMIO and PMIO Two types of coprocessor IO - ANS DMA and dedicated channels Coprocessor IO which uses memory addressing communication. It allows devices to directly write to system memory. The controller acts as the coprocessor - ANS Direct memory access (DMA) Coprocessor IO which uses isolated addressing communication. It was used in mainframe days - ANS Dedicated channels IO which requires action on part of the CPU to store and fetch from devices - ANS Programmed IO When a device must be surveyed to determine when they are ready to read/write. Everything is done in the CPU. Common is user devices (most CPU intensive) - ANS Polling When a device can interrupt to alert the CPU it is ready. Needs semiglobal memory and code is in driver and kernel. - ANS Interrupts IO where you don't need to directly handle IO, the controller does that. It unblocks the user after the controller acks. It is the least CPU intensive - ANS DMA Order following IO from highest to lowest CPU load: Interrupts, polling, and DMA - ANS Polling, interrupts, and DMA Timers when check to see if timers have expired when other kernel traps occur (syscalls, TLB misses, page faults, interrupts, or idle CPU) - ANS Soft timers Terminals which communicate over a standard serial cable connection - ANS Direct connection terminals Terminals which communicate via video memory (char based) - ANS Memory mapped terminals Unique code which represents keyboard data for key press/release. Is unique per keyboard - ANS Scan codes These are used by the OS to connect keys/combos to chars/input - ANS Keymaps Mouse movement is measure in what? - ANS Mickeys What 3 bytes are sent in an input packet for mouse movement? - ANS Overflow and buttons, x movement, and y movement 2 types of touchscreens - ANS Resistive and capacitive Touchscreen which measures resistance via a plastic (bendable) surface. It only reliably captures one set of coordinates. It is super cheap to make and can work with nonconductive materials - ANS Resistive Touchscreen which measures capacitance across glass (rigid) surface. It gets the current from our fingers. It can reliably capture multitouch and is more expensive to produce. It doesn't work with nonconductive material - ANS Capacitive 2 display types - ANS character or bitmap Display which writes chars into video RAM (ex SSH) - ANS Char display Display which writes pixel values (24 bits) (ex RDC). It can act like a char display - ANS bitmap display Scrolling displays support scrolling via a ______ adjustment. This means video memory can change and locations aren't fixed - ANS pointer 2 internet protocols - ANS Open systems interconnection (OSI) and internet protocol (IP) Internet protocol which was the original ISO standard. Emphasizes model before implementation and is based on strictly controlled layers - ANS Open systems interconnection (OSI) Internet protocol which was created for ARPAnet. Emphasizes incremental implementation and model, and is based on a loosely layered model - ANS Internet protocol (IP) 4 IP layers - ANS Access, network, transport, and application IP layer which uses protocols such as FTP, TFTP, HTTP, SMTP, POP, and game protocols - ANS Application IP layer which uses protocols such as TCP and UDP - ANS Transport IP layer which uses protocols such as IPv4 and IPv6 - ANS Network IP layer which uses ethernet and electrical connections to transmission medium - ANS Access Benefits of IP over OSI - ANS More flexibility, less complicated, easier to implement, and worked from the start What is included in the network system for a modern OS? - ANS Protocol stack (TCP/IP), network driver, and network interface Is IP a packet switching network protocol? How so? - ANS Yes. It breaks info into packets Is the size of the data sent over the network the same size of just your data? - ANS No, padding is added at each layer What is network byte order? - ANS Big endian What byte order do Intel processors use? - ANS Little endian Byte order where most significant bytes are first? - ANS Big endian Byte order where least significant bytes are first? - ANS Little endian Put 0x000A in little endian - ANS 0x0A, 0x00 Put 0x000A in big endian - ANS 0x00, 0x0A The IP address identifies what? - ANS The machine What type of addressing does IPv4 use? IPv6? - ANS Quad addressing; octect addressing How many bits is a IPv4 address? an IPv6? - ANS 32; 128 What base is an IP4 address in? IPv6? - ANS Decimal; hex What does : mean in a IPv6 address? - ANS Replace with 0s When an IP address is listed as 127.0.0.0 / n, what does the n represent? - ANS How many bits are fixed/reserved How many addresses are there for localhost in IPv4? IPv6? - ANS 255; 1 3 types of delivery mechanisms for IP - ANS Unicast, multicase, and broadcast IP delivery mechanism where one machine sends to a single destination - ANS Unicast IP delivery mechanism where one machine sends to a group destination - ANS Multicast IP delivery mechanism where on machine sends to all network hosts (everyone). It needlessly eats up traffic - ANS Broadcast Is multicast allowed on IPv4? IPv6? - ANS Yes; no The port identifies the what? - ANS Process 2 types of transport protocols - ANS transmission control protocol (TCP) and user datagram protocol (UDP) Transport protocol which is connection oriented. It needs constant connection but will retransmit lost data, data is delivered in order, and data is delivered as a stream. It is also bidirectional - ANS TCP Transport protocol which is connectionless. It uses a best effort delivery system in which packets may arrive out of order and data is delivered as datagrams - ANS UDP Which of these is true of TCP or UDP? 1) Built on top of IP 2) Use port #'s 3) Process to process - ANS All for both Which is cheaper, UDP or TCP? - ANS UDP Abstraction through which an application may send and receive data - ANS Socket Is a pipe a type of socket? - ANS Yes Which of these is true about sockets? 1) They provide interface to TCP/IP and UDP/IP 2) They are a generic interface for many protocols 3) They represent a connection endpoint - ANS All true Are there reserved ports in TCP/IP? - ANS Yes T/F: One send call corresponds to one receive call and vice versa in TCP? - ANS False How do you know how much data was received from a send call in TCP? - ANS The return value What 3 things is flow control responsible for? - ANS Prevents network congestion, buffering, and windowing Which transport protocol will not 1) establish connections before sending data 2) Provide acks of data receipt 3) Guarantee that messages will arrive 4) Detect lost messages and retransmit them 5) Ensure data is received in order it was sent 6) Provide mechanism for congestion/flow management - ANS UDP Benefits of UDP - ANS 1) Cheap 2) Server only needs 1 socket 3) Can send/receive multiple addresses at same time 4) There are no partial messages How is a TCP connection established? - ANS 3 way handshake Term for the amount of bytes of data each peer is willing to accept in TCP - ANS Advertised window Is the window size constant in TCP? - ANS No. Increase on data read and decrease on data receive Is the send window the same size as the receive window of the sender's counterpart? - ANS Yes 2 sections of the send window - ANS 1) bytes that have been sent but not acked 2) bytes that can be sent (ready or empty) Steps in a resource session - ANS acquisition, utilization, and release Step in a resource session which is responsible for locking the resource - ANS Acquisition Step in a resource session which is responsible for using the resource - ANS Utilization Step in a resource session which is responsible for unlocking the resource - ANS Release What occurs as a result of this: For a some set of processes (S), each process in S is waiting for an event and only processes in S can trigger the events that the other processes in S are waiting on - ANS Deadlock 4 required conditions for deadlock to occur - ANS Mutual exclusion in resource use, processes can hold and wait, there is no resource preemption, and there is a circular wait condition A process holding and waiting on a resource can cause what? - ANS livelock 4 deadlock handling strategies - ANS Ostrich, detect and recover, dynamic avoidance, and structural prevention Deadlock handling strategy which involves doing nothing - ANS Ostrich approach Deadlock handling strategy which involves analysis on a resource request to avoid deadlock. It works by avoiding to enter unsafe states - ANS Dynamic avoidance Deadlock handling strategy which involves writing code in a way such that deadlock is impossible. It is the least costly strategy - ANS Structural prevention Graph which is used to model processes and spot deadlock - ANS Holt graph In a Holt graph, what does this mean? P-R - ANS Request In a Holt graph, what does this mean? P-R - ANS Required How to detect deadlock in a Holt graph? - ANS Cycle What algorithm can detect cycles? - ANS Depth first traversal Issues with Holt graph - ANS Only works for unique resources and is not efficient What 4 matrices are needed to detect deadlock? - ANS Existing (E), available (A), current (C), and requests (R) What is recorded in the existing matrix for deadlock? - ANS The total amount of each resource What is recorded in the available matrix for deadlock? - ANS The amount of each resource available (E - colsum(C)) What is recorded in the current matrix for deadlock? - ANS How many of each resource each process holds What is recorded in the requests matrix for deadlock? - ANS How many of each resource each process requests (does not include what it already has) 3 ways to handle deadlock - ANS Preemption, rollback, and killing processes 2 states of resource allocation for dynamic avoidance - ANS safe and unsafe State where resources can be allocated to guarantee deadlock avoidance - ANS Safe state State where some possible future could result in deadlock - ANS Unsafe state What two things does each process have for dynamic avoidance? - ANS Current count and max count for each resource What 3 assumptions are made in dynamic avoidance? - ANS 1) No resources fail 2) No process needs more than available resources 3) Any process that gets its resources will complete Algorithm for identifying state safety which treats the max matrix as the requested - ANS Banker's algorithm How to prevent deadlock with structural prevention? - ANS Avoid at least one condition altogether (mutual exclusion, hold and wait, no preemption, or circular wait) An intermediate store which is ideally non-exclusive (memory, disk) to avoid deadlock. Basically a queue of jobs. Can introduce problems if you run out of space - ANS Spool What does spooling solve? - ANS Mutual exclusion How solve hold and wait problems? - ANS Deny processes holding a lock to get another, require all lock requests to be simultaneous, and use multi resource locks What is used to send multi-locks in one requiest - ANS Lock server What can be used in the absence of preemption support for some resources? - ANS Checkpoints and rollbacks What are issues with checkpoints and rollback? - ANS Resource intensive and can lead to livelock Way to address lack of preemption support by facilitating rollback by preventing work until all locks have been acquired - ANS Two phase locking First phase of two phase locking where you get all required locks. Locks will be released on failure to acquire - ANS Growth Second phase of two phase locking where you do work and release locks as you no longer need them, or all at the end - ANS Shrinking Two phases of two phase locking - ANS Growth and shrinking How to prevent circular wait? - ANS Resource organization or conflict graph How does a conflict graph work? - ANS Edges between resources needed together, nodes are colored (adjacent nodes different colors), nodes must run in color order Deadlocks that occur when processes depend on data from one another - ANS Communication deadlock Can communication deadlock be solved by ordering? - ANS No How to solve communication deadlock? - ANS Measure timeouts and retransmit Can communication deadlock occur in TCP? - ANS No When no process is making progress, just all failing together (still getting chance to run) - ANS Livelock Is livelock considered deadlock? - ANS No Required conditions for livelock - ANS Synchronization and bad timing How to solve livelock? - ANS Flip order or desynchronize (random sleeps) When one process never makes progress but others do - ANS Starvation Required conditions for starvation - ANS Bullies (usually smallest first approaches) and bad timing Examples of starvation - ANS Dining philosophers and readers/writers If a process gets a limited time to run, is this starvation? - ANS No