Operating Systems Exam Notes Part 1 PDF

Operating Systems – Exam Part 1 Notes March 2007 Paper: (3) Motivations for existence of operating systems: o Abstraction → hide complexity of lower levels Concurrency → being able to use resources simultaneously o Program portability, by the means of standard...

Operating Systems – Exam Part 1 Notes March 2007 Paper: (3) Motivations for existence of operating systems: o Abstraction → hide complexity of lower levels Concurrency → being able to use resources simultaneously o Program portability, by the means of standardized interfaces o Resource management → address needs of individual users o Sharing of functional that all applications need What is the ‘blocking factor’ in a file system? o The ratio of logical blocks to physical blocks (2) Motivations for making a program multi-threaded: o Deal with natural concurrency o Hide latency o Improve performance on multiprocessor platform What is working set and what determines the lower/upper limit to its size? o Working set = set of physical memory pages currently dedicated to a running process. o Upper limit → degree of multiprogramming o lower limit → avoiding occurrence of page faults When is busy waiting an acceptable synchronization technique and when is not? o Acceptable: when synchronization between separate processors (physical activities) is needed o Unacceptable: when synchronization between separate processors is not needed → on a single processor for example 4 correctness concerns in concurrent programs or systems: o functional correctness, minimal waiting, absence of deadlocks, fairness What is the return path from kernel and where is it used? o Path: the sequence of checks executed upon resuming user-space execution. It is executed (used) upon returning from a system call or interrupt (2) Machine instructions that can be used for implementing binary semaphores: o Fetch&Add, Test&Set, Compare&Swap Consider the statements x:= y and x:= 5 +z, where x,y shared variables, z is local variable. May these statements be regarded as atomic? o 1st assignment contains two references to shared variables → not atomic o 2nd assignment contains just 1 reference to shared variable → atomic  What is a local variable? o A variable that is accessible by just one thread October 2007 Paper: 2 Principles of Condition Synchronization: o At places where the truth of a condition is needed → check and block o At places where a condition may have become true → signal waiters Difference between ‘streaming’ and ‘message-based’ communication. Give an example of each: o Streaming → no fixed message structure, sequence of underlying unit (e.g. multimedia) o Message-based → coupling of send and receive (e.g. email) Advantages (min 2) of using multiple threads over using multiple processes: o Multiple processes → possibility of distribution, shielding of tasks from interference and errors, concurrency o Multiple threads → concurrency, natural structuring of program, easier handling of shared data In what ways does the kernel gain control? o Interrupt, trap, execution Show the steps in a conditional critical region: o 1. Lock, 2. While not condition do wait od, 3. Critical section, 4. Possible signals, 5. Unlock What is meant by “mailbox communication”? o Communication between multiple senders and multiple receivers via a common queue or other data structure January 2008 Paper: Give the classic classification of input/output devices in 3 categories: o Terminals: block devices, streaming devices and communication devices Describe the 2 places for standardization in the use of input/output devices and their integration into the operating system: o 1. At the OS/API level → provide a unified interface to applications o 2. At the driver level → integrate devices in a standard way into the OS (3) Reasons to use buffering in a kernel o Sharing, caching, solve speed differences, solve use/kernel problems (5) Properties of an ideal memory manager: o Multi-programming, no memory waste, no extra complexity, no extra hardware required, unlimited memory size, no contiguous storage  When is a set of tasks D called a deadlocked set? o A set of tasks is called deadlocked if: ▪ All tasks in D are blocked or terminated (normally or abnormally) ▪ There is at least one non-terminated task in D ▪ For each non-terminated task t in D, any task that might unblock t is also in D Assuming the OS can detect a deadlock state, what can the OS do to recover from deadlock? o Pre-empt resources, roll-back to safe state, kill processes Difference between symbolic linking and mounting? o Symbolic linking → name in new name system + closure from the content of a file o Mounting → closure and pre-fixing are added (transparently) to the resolution algorithm (so merging two name spaces) What is an incremental indexed file organization: o A file is accessed via indirection blocks that contain references to other blocks. These other blocks may be reference blocks once more or data blocks. The depth of this hierarchy determines the maximal file size. In an incremental scheme this depth increases with length; initially, a single indirection is used; for content after a certain maximum size, two indirections are used, etc. Advantage of an incremental indexed scheme compared to multi-level scheme: o In multi-level scheme, the depth is fixed, thus giving also small files an access penalty for the largest possible file. The advantage is therefore that small files are accessed faster. Which information must be stored in a directory entry? o File name (Entry name to be precise) o Reference to description and access point Tasks of the synchronous part of the device driver: o Check if data is available o Prepare the device for generating the data (if required) o Stop caller (if required) Reasons to have bottom and top halves of an interrupt handles + what are their tasks: o Top half: quick response to interrupt handling, prepare for another interrupt ▪ Tasks: re-enable the interrupt, save additional state not saved by hardware, take away volatile states from interrupting device asap  o Bottom half: full processing of the interrupt, serving OS data structures and user processes ▪ Tasks: process obtained info, return from interrupt, wake up waiting process and select new one for continuation (3) Goals of different RAID levels and how are they achieved o Increase performance (level 0,1): distribute one logical disk over 2 physical disks o Reliability (level1-6): full copy, error correcting codes, parities o Avoiding hot-spots (level 5+6): distribute parities September 2008 Paper: 3 Rules of Thumb to avoid deadlock in action synchronization: o Avoid cycles in semaphore calls o Avoid greediness o Let critical sections terminate What does interference among concurrent processes or threads mean? o Assumptions or knowledge that one process has about the state are disturbed by actions of another process When can we regard an assignment in Pascal or C to be atomic + what is the underlying assumption? o When there is at most 1 reference to a shared variable, it is atomic. Assumption is that interrupts are implemented correctly wrt an internal processor state (registers), and that read and write operations are atomic for the type of that variable January 2009 Paper: What does the concept “fairness” mean. Give a simple example of fair and non-fair behavior: o Fairness refers to ensuring that all processes or threads receive a reasonable share of system resources without undue preference or bias o Fair behavior: A round-robin CPU scheduling algorithm giving each process equal CPU time in turn o Unfair behavior: A high-priority process monopolizes the CPU, starving lower-priority processes indefinitely Difference between a process and a thread: o Process → independent unit with its own memory space o Thread → lightweight unit within a process, sharing memory and resource Difference between a mode switch and a context switch:  o Mode switch → switch between user mode and kernel mode, takes very little time o Context switch → switch between process or threads, saving and restoring states, costs more time Difference between signal-and-continue and signal-and-wait signaling policies of a monitor: o S-A-C → signaling thread continues execution after signaling o S-A-W → signaling thread waits, and the waiting thread runs immediately What is meant with the term “race condition” (Give an example) o Race condition means when the outcome depends on the non- deterministic timing of threads/processes. An example is when two threads are updating a shared counter without synchronization, leading to incorrect results 4 criteria that determine deadlock occurrence: o Mutual exclusion, hold and wait, no pre-emption, circular wait What is system reliability? o The ability of a system to function correctly over time without failures What is meant by spatial locality, locality of reference and temporal locality? o Spatial locality → accessing nearby memory locations o Locality of reference → the principle that series of references are close to each other wrt to some measure o Temporal locality → re-accessing recently used memory locations What is the asynchronous part of a device driver? o The part that is triggered by the device, namely the interrupt handler Explain the two places in the i/o system where standardization occurs: o Device-independent software interface (e.g. system calls) o Device driver interfaces for hardware Loading a new page implies overwriting an old one o Explain why it is generally better to replace an unmodified page: ▪ Because it avoids the overhead of writing the page back to disk o Give circumstances when replacing a modified page is advisable: ▪ When the modified page isn’t needed any longer, and there is no benefit to keeping it in memory June 2009 Paper: Under what circumstances is busy waiting acceptable? And where is it applied? o Under the circumstances that the waiting time is guaranteed to be short, typically in synchronization between processors in critical sections o I tis applied when it is the only thing that may happen on that processor. Typical in special-purpose hardware for devices 3 Ways to pass control to the kernel: o System calls, interrupts and exceptions 2 Ways devices are mapped to the instruction set of a computer, and what are the advantages and disadvantages? o 1st way: memory-mapped I/O ▪ Adv: unified addressing simplifies programming ▪ Con: consumes address space o 2 way: port-mapped I/O nd ▪ Adv: dedicated I/O instructions ▪ Con: requires separate instructions What are the advantages (At least 2) of corrections over fixed partitions? o Reduces fragmentation → memory allocated as needed o Efficient utilization → no predefined partition sizes Which (possibly conflicting) requirements determines the choice of the page-size in a virtual memory system? o It should be a power of two o It should be a large value to keep the page tables and their memory footprint small o It should be a small value to reduce internal fragmentation November 2009 Paper: What is scheduling, and what is a schedule? o Scheduling → allocate resources to tasks (processes or threads), which includes decision-making policies to determine the order in which active processes should compete for the use of resources and the actual binding of a selected task to a resources o Schedule → function that maps a time and a resource to a task What is a task attribute, and what is a scheduling metric? Give both examples o Attribute is a property a task has. It can be static or dynamic. Examples: arrival time, computation time, required resource, deadline, etc.  o A scheduling metric is an observed property. It is the result of applying scheduling policies on a task. Examples: response time, turnaround time average overshoot, etc. A spinlock is a common approach to implementing mutual exclusion. What are its advantages and disadvantages, and where is it used? o Advantage: work with multiprocessors o Disadvantage: busy waiting, cost time, doesn’t work for a single processor o It is used to protect shared resources from single access by multiple threads or processes o Because upon a signal it is not known which processes proceeds; hence, the condition may have become false again January 2010 Paper: What is priority inversion? Give an example o The situation in scheduling that a high priority process is blocked by a process of middle priority, through blocking on a resource shared between this high and a (third) low priority process. During this blocking, arbitrary processes of a middle priority can overtake. An example of this is: a thread T1 running at priority 4 gets pre-empted by a higher priority thread T2 with a priority of 8 after acquiring a lock. What is system availability? o The probability that a system is functioning according to specifications Give 3 approaches to deal with deadlock o Avoidance, prevention and detection November 2010 Paper: Steps in processing a system call: o 1-3: pushing parameters o 4: call library function o 5: put code for read in reg o 6: trap: switch mode and call particular handler o 7: handles calls read function handler o 8: handler performs read actions (Account of store data at address) o 9-11: control back to caller What is interference of concurrent programs? o The truth of an assertion that on local reasoning would be true is falsified In Posix, the value of a semaphore can be inspected. Is this useful in a program? If yes, explain with an example o You can use it to avoid blocking of a process, for example by inspecting the semaphore from time to time doing something useful in between. Disadvantage is that the value is not stable; you cannot assert that the value is 0 after you have tested that October 2013 Exam: Fundamental aspects in which various CPU scheduling frameworks may differ from each other: o When to schedule: when to activate the scheduler and go into decision mode o Who to schedule: what is the priority function for currently active processes. The highest priority process is scheduled next o What arbitration rule: who to schedule in case of equal priority 2 basic concepts for inter-process communication and describe them: o Shared memory → memory space reserved by the kernel, addressable by both processes o Message passing → communication channels between processes (e.g. pipes, sockets) Having small files lead to internal fragmentation in file systems. Give 2 ways to solve this problem: o Add the file content in the file descriptor o Use contiguous allocation for small files o Use blocks of variable size  o Answer is 12 October 2014 Exam: What is the distinction between a process address space and the main memory address space? o Process address space → a logical view of memory assigned to a process, isolated and virtual o Main memory address space → the physical memory available in the system, shared by all processes  o A: T + M + C o B: T + M + C January 2015 Exam: What is an interrupt? How is it handled? o Interrupt → a signal from hardware or software to the CPU to temporarily halt the current process and handle a specific event. o Handling → the CPU saves the current state, executes the corresponding interrupt service routine (ISR), and then restores the previous state to resume execution File systems often contain many small files. Explain with an example how a file system can be optimized to deal with this. What exactly is the problem with small files? o Small files waste storage due to internal fragmentation (unused space in fixed-sized blocks) o Example optimization → use inode structures with direct, indirect and small block sizes to efficiently store small files. Or, combine small files into a single block with an index o Answer: not atomic, race condition observed January 2016 Exam: What is the unit of work in a computer system? o A PROCESS is a unit of work in a computer system Name the two different modes of operation of an operation system. In which of these two modes do system calls run? o 1. User Mode o 2. Kernel Mode o System calls run in Kernel Mode Why should a web server not run as a single-threaded process? o Because it can handle only one request at a time. This leads to poor performance and delays, especially when multiple clients send simultaneous requests. o Answer: 13 bits o Q9 Answer: 12 page faults, contents of frame → [0,1,3,6] o Q10 Answer: 15 page faults, contents of frame → [0,1,6,5] January 2017 Exam: What is an operating system kernel? o The kernel is the core part of the operating system that manages hardware resources, system calls and low-level operations  Name one advantage of using a thread pool o It reduces the overhead of creating and destroying threads for each task by re-using existing threads Give the steps that make up a condition critical region o 1. Entry section → check if the process can enter the critical region o 2. Critical section → perform operations on shared resources o 3. Exit section → release the critical region o 4. Remainder section → execute non-critical operations An operating system should be able to work with new devices of device vendors, even with new types of devices with completely new device interfaces. What is done in practice to make this possible? o Device drivers are developed to abstract the hardware-specific details, allowing the OS to communicate with new devices. o Answer: o Action A (Running → Waiting): The process performs an I/O request or waits for an event. o Action B (Running → Ready): The process is pre-empted by the scheduler (e.g., time slice expiration). o Action C (Waiting → Ready): The I/O operation or event the process was waiting for is completed. o Action D (Ready → Running): The scheduler selects the process to run on the CPU. What is thrashing, and when does it happen? o Thrashing is a condition where excessive paging activity occurs, causing the system to spend more time swapping pages in and out of memory than executing actual processes. October 2017 Exam: What is a system call? Mention two types of system calls o A system call is an interface for programs to request services from the operating system’s kernel. Examples are file manipulation (open, read) or process control (fork, exit) What is meant by virtualization of hardware? What is a virtual machine? o Virtualization of hardware → creating a virtual version of physical hardware to allow multiple environments to run simultaneously o Virtual machine → an emulation of a computer system that runs an OS and applications like a physical machine Mention two actions taken by a kernel during a context switch o Save the state (registers, program counter) of the current process o Load the state of the next process to be executed Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Is this system deadlock-free? Explain answer o Yes, deadlock-free because each process needs at most 4 resources, and there are 4 resources in total. Give two examples of permanent file attributes o File name and file size Mention at least two problems that may occurs in the absence of I/O buffering when reading blocks of data from a disk o Increased CPU overhead due to frequent direct I/O operations o Slow performance due to mismatch between CPU and disk speeds o Answer  Explain internal fragmentation and external fragmentation of memory and what is their difference o Internal → occurs when allocated memory is larger than the requested memory, leaving unused space within the allocated block o External → occurs when free memory is split into non-contiguous blocks, making it difficult to allocate to processes despite sufficient total free memory o Difference → Internal fragmentation wastes space inside allocated blocks, while external fragmentation wastes space outside allocated blocks due to non-contiguous free areas. November 2018 Exam: What is the relationship between an application programming interface (API) and the system-call interface? o API provides a high-level interface for application developers to perform operations, while the system-call interface translates these API calls into low-level system calls executed by the operating system A device driver must have access to device controller registers for input and output operations. Name two ways in which the driver can access these registers o Memory mapped I/O → registers are mapped in the system’s memory address space and accessed like regular memory o Port-mapped I/O → registers are accessed using specific I/O instructions What does a process control block include? o It includes the information on the process’s state A ____ saves the state of the currently running process and restores the state of the next process to run o CONTEXT SWITCH fill in the blank o Answer: fill in 754 in the blanks January 2020 Exam: What are the two levels of abstraction provided by the I/O subsystem? Give a one line explanation for each o Logical I/O → abstracts the details of devices, allowing applications to work with files or streams o Device I/O ➔ manages low-level interactions with hardware devices through drivers Which of the following are true statements? o An interrupt is a signal from I/O hardware to the CPU that transfers control to an interrupt service routine → TRUE o Upon an interrupt, the operating system preserves the CPU state by storing registers and program counter → TRUE o A trap is a signal from the CPU to a device controller (hardware), informing it that the CPU is ready for I/O → FALSE Name two advantages of using an API over direct system calls: o Portability → APIs provide a consistent interface across different OS o Ease of use → APIs abstract complex system calls, simplifying application development o Answer: PSS for P1 → 100 + (120/2) = 160 KB, PSS for P2 → 150 + (!20/2) = 210 KB January 2021 Exam: Main difference between a thread and a process? o Different threads of a same process share the same memory address space. Processes have different memory address spaces  Advantage of using a Direct Memory Access (DMA) o The processor can execute other tasks in parallel to the execution of the memory transfer. 2 advantages of using virtual memory over dynamic memory partitioning: o It simplifies data sharing o It avoids external fragmentation o The whole address space doesn’t need to be saved contiguously in memory What does the operating system do during a context switch? o It saves the context of execution (i.e. processor registers, PC, file and I/O status) of one process in its PCB and loads the context of execution of another process Give 2 examples of stream I/O devices and two examples of block I/O devices: o Stream → keyboard, mouse, sensor, actuator o Block → hard drive, SSD, tape, USB stick  Explain a problem that may arise if the memory manages swaps out a process that is waiting on an input operation: o It may corrupt the memory address space of another process that is loaded in main memory in the place of the waiting process April 2021 Exam:  Explain the many-to-one multi-threading mapping model. Give one disadvantage of that model: o All user threads created by a process are mapped, and therefore executed by a single kernel thread. A disadvantage of such approach is that threads cannot execute in parallel at the same time. Give one advantage and one disadvantage of using dynamic memory partitioning instead of static memory partitioning: o Advantage → there is no internal fragmentation o Disadvantage → there is external fragmentation What is the difference between a stream I/O device and a block I/O device? o Stream → transfers data as a continuous flow o Block → transfers data in fixed-sized blocks Give at least 2 reasons for which it is useful to use a buffer when performing I/O operations o Resolve speed difference and/or latency problems between consumer and producer o Resolve granularity difference between data produced and expected February 2022 Exam: Give an example of a situation where it is better to use processes than threads to parallelize your application: o Better to use processes when memory is low and when you need strong isolation between tasks, such as in a web server handling multiple client requests, where each client runs in a separate process to ensure faults or security breaches in one client do not affect others.  What is a TLB (Translation Look-aside Buffer)? o A TLB is a small cache memory in the processor that keeps track of the locations of the most recently used pages in main memory. It accelerates address translation and thus memory accesses in comparison to using the page or frame table. Give two problems solved by using virtual memory: o Process size is no longer restricted to main memory size → allows processes to use more memory than physically available by swapping data between disk and RAM o Eliminates external fragmentation when used with paging → paging divides memory into fixed-size blocks, ensuring efficient utilization without gaps between allocations