OC Flashcards

Question

Kernel Mode

Answer 1

Kernel Mode - Code has access to all CPU instructions - Code has access to all Memory addresses - Only accessible to most trusted parts of the OS

Answer 2

- Code does not directly access hardware or memory - Uses OS API to do so - Crashes are recoverable

Answer 3

Most common on Linux is bash. Sometimes Desktops are called graphical shells. They are sorted: application programs system programs hardware

Answer 4

The lowest interface provided by the OS to users System calls to manipulate processes, files, memory, inter-process communication, etc. Process management: fork, waitpid, execve, exit, … File management: open, close, read, write, lseek, stat, unlink, … Folder management: mkdir, rmdir, mount, umount Memory: brk, malloc, free, ...

Answer 5

Runs entirely in kernel mode * Including drivers * Any crash in a procedure brings the system down Each procedure in the system can call any other * No layering * No restrictions Can have minimum structure * A service procedure per system call * A service utility used by one or more service procedures E.g., Unix, Linux, OpenVMS, MS-DOS, Windows 9x

Answer 6

The system is divided into layers LAYER FUNCTION 5 the operator 4 user programs 3 input/output management 2 operator-process communication 1 memory and drum management 0 processor allocation and multiprogramming

Answer 7

2-10 bugs per thousand lines of code - Linux kernel is around 5M lines of code - Microkernel OS minimises code that runs in kernel mode

Answer 8

Combines Monolithic and Microkernel approaches - Runs almost all OS service in kernel space - Used in Windows NT (including 10) - Linus Torvalds doesn't find enough difference between hybrid and monolithic kernels

Answer 9

Computer resources could be shared between processes/users using either: * Time-multiplexing: processes take turns at the resource E.g., CPU core, printer (actual printing), * Or Both (space-multiplexing)

Answer 10

Computer resources could be shared between processes/users using either: Space-multiplexing: multiple processes can use/share the resource at the same time - E.g., hard-drive, RAM, printer’s buffer (if available) * Or Both (Time-Multiplexing)

Answer 11

All! Running, Ready, Blocked

Answer 12

I/O operations are usually much slower than CPU instructions

Answer 13

The Scheduler chooses the next process to run. Process Queue * The process queue(s) can be ordered in different ways - FIFO - Priority

Answer 14

* Fairness: each process gets a “fair share”

Answer 15

* Throughput: number of processes that complete their execution per time unit

Answer 16

* Turnaround time: time from submission to completion

Answer 17

* Waiting time: the amount of time a process spends in the ready queue

Answer 18

* Response time: the amount of time from submission to the first response

Answer 19

* A running process will release the CPU only when it exits or is blocked Non-preemptive scheduling is typically more suitable for batch systems than interactive ones as jobs are submitted in advance. If no clock interrupts are available, non- preemptive scheduling is the only option

Answer 20

* A running process can be suspended after some time * Requires a clock interrupt at the end of time intervals (e.g., 50Hz, 60Hz)

Answer 21

Switching the CPU from process A to a new one

Answer 22

Steps * Switch from user mode to kernel mode * Save A’s state (e.g., registers) * Select process B * Load B’s state * Start B The time it takes is the Dispatch Latency

Answer 23

The CPU is allocated to processes in their order of arrival * FIFO process queue - Each process owns the CPU until it is done or blocked This is a non-preemptive algorithm FCFS suitable for * Batch systems

Answer 24

Advantages * Simple to implement Disadvantages * Waiting time can be large if short requests wait behind the long ones * Not suitable for multiprogramming systems

Answer 25

For each process, determine the length of its next CPU burst. Run processors in their ascending burst length order. SJF is both a non-preemptive and preemptive algorithm. SJF suitable for batch systems In SJF, if A (L=20) is available at t=0 and B (L=1) arrives at t=1 * A will run from 0 to 20, B runs from 20 to 21

Answer 26

Advantage * SJF minimises the average waiting time Disadvantages * Difficult to get a good estimate of the burst length - Easier if similar tasks ran in the past * Starvation - The longest process(es) might never get to run

Answer 27

SRT takes into consideration the fact that processes arrive at different times * When a new process arrives, interrupt the running process if its remaining time is longer than the new process - With SRT * A runs from 0 to 1 * At 1, B arrives, B’s length (1) is shorter than A’s remaining time (19) * Run B from 1 to 2, Run A from 2 to 21 SRT is preemptive Typically used in interactive systems where response time is critical

Answer 28

The most intuitive multiprogramming algorithm * Split the timeline into equally long segments 1. Give each process a segment 2. Once all present processes had a segment each, go to 1. * The length of the segment is called quantum - Usually 10-100ms * At the end of the timeslot, the process is pre-empted More suited for interactive systems

Answer 29

If the quantum is too short * The cost of context switches becomes the main performance criteria If the quantum is too long * Becomes FCFS Performance criteria * Length of time quantum * Number of context switches * Length of CPU bursts

Answer 30

Advantages * Simple to implement (circular queue) * Very suitable for multi-programming Disadvantages * Challenging to find the optimal value of the quantum * Assumes all processes are equally important

Answer 31

Each process has a priority value * Lower integer value  higher priority - The scheduler picks processes in their descending priority order Two variants * Preemptive: pause the current process if a higher priority one arrives * Non-preemptive: current process cannot be interrupted by higher-priority processes

Answer 32

Advantages * Can define more sophisticated policies - E.g., SJF can be seen as priority scheduling where the priority value is the length of CPU burst time Disadvantages * Starvation for low-priority processes - Can include an ageing factor: increase the priority of waiting for processes with time

Answer 33

Semaphores are an abstract data type used for synchronization between multiple threads or processes in a concurrent system. Semaphores can be used to protect shared resources or critical sections of code, by ensuring that only one thread or process can access them at a time. They can also be used to signal events between threads or processes

Answer 34

The waiting time is always larger than or equal to the response time.

Answer 35

The time spent by a process in the ready queue waiting for CPU time

Answer 36

The time between a user request and the first response produced by the system.

Answer 37

A requested virtual memory page is not present in RAM.

Answer 38

The size of a virtual memory page has to be identical to the size of a page frame.

Answer 39

A file that uses 8 bits out of each byte

Answer 40

Batch Systems

Answer 41

Nothing, the current process has a higher priority

Answer 42

False, only the last memory page of a process will, on average, contain 50% useful data.

Answer 43

- a network interface - a terminal

Answer 44

preemptive

Answer 45

- A process can have multiple threads in it - Threads from the same process share the process' local variables

Answer 46

The access request will fail because 1000<2000 In dynamic relocation, the OS maps the logical address of a process to a physical address by adding the base address of the process to the logical address. Therefore, in this case, the logical address of the process is 2000, and the base address is 3000, which gives a physical address of 5000.

Answer 47

a function is called.

Answer 48

No need to read bytes 1 to n-1 before reading or writing byte n

Answer 49

To calculate the number of page frames in physical memory, we need to divide the total physical memory size (e.g. 2GB = 2^31 bytes) by the page size (e.g. 2^12 bytes) = 2^19 pages. we need to round down the number of pages to the nearest power of 2 that is less than or equal to the number of page frames. The largest power of 2 that is less than or equal to 2^19 is 2^18, so the number of page frames is: 2^18 = 262,144

Answer 50

Hoare implementation of monitors transfers ownership of the monitor immediately to the thread that is woken up by a signal. This means that the woken thread gains exclusive access to the monitor and continues executing its critical section without interference from other threads.

Answer 51

Mesa implementation only wakes up one waiting thread when a signal is sent. The woken thread then competes with other threads that are waiting to acquire the monitor by using a lock or semaphore mechanism. This means that the woken thread may not immediately gain access to the monitor and may have to wait until it acquires the lock or semaphore

Answer 52

Producer-Consumer. The producers generate data items and add them to the buffer, while the consumers remove data items from the buffer and process them. The problem is to ensure that the producers do not add items to the buffer when it is full, and the consumers do not remove items from the buffer when it is empty.

Answer 53

sometimes unblock a waiting thread that called acquire().

Answer 54

- Guarantees that ownership is released at the end of methods that invoke the mutual exclusion protection - less error-prone.

Answer 55

- Clear recommended programming pattern - Has separate and clear syntax for mutual exclusion - Programming less prone to errors - No constructor arguments are required.

Answer 56

Need: * Long-term storage * Bigger size * Non-volatile * Easier sharing * With hardware abstraction - Read block k - Write block k

Answer 57

- Files are persistent logical units of information - Created and manipulated by processes - File (Management) System is the part of the OS dedicated to file structures, names, uses, etc. - Process, Address Space and Files are the most important abstractions an OS provides

Answer 58

Big names for end-user computers include: * 1984: FAT-16 created by IBM and Microsoft and used in MS-DOS, then in Window 95 and 98 * 1987: Minix V1 FS created by Andrew Tanenbaum for Minix 1.0 * 1992: ext and ext2 (1993) created by Remy Card for Linux * 1993: NTFS 1.0 introduced in Windows NT 3.1 * 1996: FAT-32 introduced in Windows 98 * 1999: ext3 * 2006: ext4

Answer 59

Windows * Extensions dictate the choice of the program to open the file, e.g., jpg, pptx, etc. Linux * Less binding between extensions and programs

Answer 60

Files types: * Regular: your files, ASCII or binary * Directories (folders): contain collections of files * “Character” special files: model serial I/O devices, such as terminals, printers and networks * “Block” special files: model disks Under Linux, use "ls -l“

Answer 61

ASCII files * Lines terminated by a carriage return, line feed, or both (Windows) Binary files start with magic numbers that identify their formats * 50 4B 03 04 (PK??) for zip (and derivatives, e.g., JAR) * 7F 45 4C 46 (.ELF) for ELF files * 25 50 44 46 2d (%PDF-) guess! * 4D 5A (MZ) Windows Executables, Mark Zbikowski * https://en.wikipedia.org/wiki/List_of_file_signatures OS must, by default, be able to parse its own executable formats

Answer 62

Sequential: access a file byte-by-byte or record-by-record * Inconvenience: if you want to read the nth byte, then you must read everything before it! * Can rewind a file, name from magnetic tape age! - Before disks Random access: access any byte/record out of order

Answer 63

Attributes (aka metadata) include: * Protection information * Creator * Creation time * Owner * Hidden Flag * Time of last access * Time of last change * Current size

Answer 64

Check permissions using "ls –l some_path" * -rwxrw-r-- 1 user group 2 Jan 24 19:59 test.txt * https://wiki.archlinux.org/index.php/File_permissions_and_attributes - chmod [u/g/o/a][=/+/-][r/w/x] file - chown user:group file - lsattr and chattr to list and change attributes

Answer 65

* How files and folders are implemented * How disk space is managed * How to make to the file system efficient and reliable * How to integrate the FS with the rest of the OS

Answer 66

Units A. Track B. Geometrical sector C. Track sector D. Cluster Block vs. Sector * blockdev --getbsz /dev/sda

Answer 67

512B on traditional HDD * 4096B on newer ones * Smallest storage unit - SSDs simulate sectors

Answer 68

Different ways to stores files in blocks 1. Contiguous allocation 2. Linked list allocation 3. Linked list with a Table 4. i-nodes

Answer 69

Pros * Easy to implement * Fast to store a file Cons * Creates unused fragments of memory - Used in CD-ROM

Answer 70

Pros * No more empty fragments Cons * Takes longer to read all blocks of a file * Slow random (vs. sequential) access * You can easily end up with a disk full of fragmented files * “Pointer” bytes wasted - Storing a block uses a bit more than a block

Answer 71

Store pointers in a table for faster access * File Allocation Table, implemented it in MS-DOS Pros * Faster access Cons * Table size grows linearly with disk size * 1TB disk with 1 KB blocks has 1 billion entries * For performance, have the FAT in RAM

Answer 72

An i-node stores information about file blocks + its properties - An i-node stores a list of block addresses of a file - The OS loads in RAM i-nodes of active files * If each file has N blocks and there are K active files, then only N*K addresses loaded But N is not a constant * Use the last pointer to point to another i-node Used in * Unix File System - A Unix directory is a list of pairs of filenames and i- node numbers * ext- ext4 - ls-i to display the i-node number of a file - “struct inode” in linux/fs.h * NTFS

Answer 73

A collection of platters Each platter is covered with magnetic layer * On both faces Heads can be positioned on tracks

Answer 74

Different in SSD! Disks merge requests from all processes in one queue Performance Criteria: time taken to get data 1. Access time: time to get to the first byte Seek time: taken to move the arm to the right cylinder Rotational latency: needed to get the right sector under the head 2. Disk bandwidth: number of transferred bytes divided by the time between the first request and last byte transfer Seek time is usually the longest, will focus on it

Answer 75

Scenario (Tanenbaum) * Range of cylinders: 0-39 * Head starting position: cylinder 11 * Request queue: 1, 36, 16, 34, 9, 12 Disks can store pending requests to cylinders as separate linked lists * Run requests of a given cylinder in one go

Answer 76

Process request in the same order they were received in Arm moved by (11,1, 36, 16, 34, 9, 12): * 11-> 1: 10 * 1-> 36: 35 * 36-> 16: 20 * 16-> 34: 18 * 34-> 9: 25 * 9-> 12: 3 * Total: 111 arm moves

Answer 77

Instead of making non-optimal arm moves by going to the next received request Move to the closest requested cylinder

Answer 78

Arm moved by (11,1, 36, 16, 34, 9, 12): * 11-> 12: 1 * 12-> 9: 3 * 9->16: 7 * 16->1: 15 * 1->34: 33 * 34->36: 2 * Total: 61

Answer 79

Problem with SSF * Say, during processing of request for 16 (1 waiting) - Request comes for 8: 8 runs, 1 waits - Request comes for 13: 13 runs, 1 waits - Etc. and 1 waits … * On a heavily loaded disk, the arm will tend to be in the middle and requests on the extremities will starve Similar issue with elevators of tall buildings!

Answer 80

- Maintain 1 bit that gives the direction - Find a request in the current direction - Direction is reversed when no more requests left in the current direction - Say, the bit is initially set to UP ...

Answer 81

Arm moved by (11,1, 36, 16, 34, 9, 12): * 11-> 12: 1 * 12-> 16: 4 * 16-> 34: 18 * 34->36: 2 * 36->9: 27 * 9->1: 8 * Total: 60

Answer 82

Properties * Usually slower than SSF, but covers the entire disk * Upper bound for covering all requests: twice the size of the entire range Circular Elevator Algorithm * Always in the same direction * Once no more requests in the chosen direction, start over again * 11, 12, 16, 34, 36, 1, 9 - instead of 9, 1 in Elevator

Answer 83

On a lightly loaded hard-drive, all algorithms "converge to" FCFS! Elevator and derivatives perform better on heavily loaded hard-drives File allocation has its word in the performance of file access

Answer 84

Reminder: disks are divided into sectors Sector Zero of a disk is the MBR * Used to boot the computer The partition table is at the end of the MBR * Give the type, start and end of each partition * One of the partitions is marked as active partition

Answer 85

When a machine is booted * Executes the MBR * The MBR program locates the active partition * MBR program reads the first block of the partition Aka the Boot Block * The Boot Block program loads the OS from the partition

Answer 86

All programmers dream of a memory that is: * Private: their program's memory is inaccessible to other processes * Infinitely large * Infinitely fast * Nonvolatile: does not lose content when powered down * Inexpensive?!

Answer 87

Memory hierarchy: a sequence of layers of memory chunks, the first is directly connected to the CPU When you move away from CPU, the memory is * Slower, Larger and Cheaper The memory manager is heavily involved in the management of this hierarchy * Allocates memory to processes, knows free memory, etc.

Answer 88

The simplest scenario: processes directly access physical memory An instruction like * MOV R1, 4th_byte * accesses the actual 4th byte of memory Cannot have 2 programs in RAM at the same time: what if both access Byte 4? Three possible implementations (+minor variations)

Answer 89

One process in memory at a time * (a) in original mainframes, rarely used now * (b) the OS in Read-Only-Memory; embedded and handheld devices * (c) early personal computers used ROM for the BIOS

Answer 90

Only one process can run at a time * Still can swap processes between RAM and disk Processes can access OS memory in scenarios (a) and (c) and might crash it Obsolete for computers, but still in use for very simple systems * Your washing machine, fridge, kitchen machine, etc.

Answer 91

Program Status Word: Early IBM 360 * Can swap processes between RAM and disk * Split memory in 2KB blocks, each has a 4-bit protection key * Each process has a Program Status Word * A process can access a chunk if its PSW matches the protection key * Only the OS can change the PSW

Answer 92

Code in both programs refer to the same set of addresses * JMP 28, in process 2 (white), fails in (c)

Answer 93

Code in both programs refer to the same set of addresses Solution: Static Relocation * Process P2 (white) is loaded at address 16384 * Each reference to an @ by 2 is incremented by16384

Answer 94

The OS must set the 4-bit key of each block of 2KB of the process memory * Time-consuming In an instruction like MOV R1, 400 you need to know if 400 is an address Need some form of memory abstraction * Access to abstract addresses rather than real ones

Answer 95

The use of keys and PSW addresses the protection problem * But not the relocation one IBM's static relocation addresses the relocation problem * But slow Both non-scalable

Answer 96

An address space is an abstraction of the physical memory * The set of all memory addresses that a process can access Numbered in a different way to the actual physical addresses being used * Identical values of addresses from different processes refer to different physical locations Address 400 of P1 could be 0x10640 Address 400 of P2 could be 0x20880

Answer 97

Used in CDC 6600 andIntel 8088 Uses base and limit registers A process's base address is where it was loaded The limit gives the size of the program * Access to an @>limit generates a fault For each memory access, add the base’s value

Answer 98

Intel 8080 did not provide a limit register Cost * Addition of @s to base, a bit of a problem - Propagation of the carry bit * Comparison to limit, OK - What if two programs, combined, don't fit in memory? * Two approaches: swapping and virtual memory

Answer 99

Swapping simply consists in backing up a process (or more) on disk if the next process to load doesn't fit in memory * Note: the whole process memory is copied

Answer 100

Swapping creates "holes" in memory: small ranges of unused memory Solution? Compact memory by moving all used slots up or down to remove the holes * BUT: this is quite time-consuming - If you have 16GB of RAM that copies 8B in 8ns, it could take 16s

Answer 101

Processes can grow during execution * Stack: for every function call (a return frees memory) * Heap: for each memory allocation instruction OS might already provide room for growth If the process exceeds the max size, then needs to be relocated Another Limitation: Bloatware

Answer 102

A process might not fit in memory But also, a collection of processes might not fit in memory * Swapping entire processes is resource-consuming * SATA disks transfer rates of 100s MBps, takes seconds to swap out a process of 1GB and similar time to swap in a similar process

Answer 103

 Solution from the 60s  Slice a program into multiple overlays  Only load the overlay manager (OM) * The overlay manager loads overlay 0 * Once done, asks the OM to load overlay 1  Overlays kept on disk, swapped in on demand  Slicing a program is done by its creator * A nightmare! Error-prone

Answer 104

Needed to make the OS slice programs Virtual Memory * Each process has an address space * The @ space is cut into chunks, aka memory pages, by the OS * A memory page is mapped onto a contiguous range of physical addresses E.g., range 20480000-20484095 of virtual mem. maps onto 10240000-10244095 of physical mem. * When a process references a virtual address, its corresponding physical page is brought from the desk, if not already loaded in RAM

Answer 105

Does the translation of virtual addresses into physical addresses E.g., translates virtual @1 into physical @ 1024000001

Answer 106

 Consider a machine with * 32KB physical memory * 4KB pages * Uses virtual memory to simulate a memory of 64KB  A page fits in a page frame * 16 virtual pages * 8 physical page frames  Sizes of memory addresses? * 16 bit virtual, 15 bit physical

Answer 107

The OS keeps track of which pages are loaded in RAM * A present/absent bit If referenced address is in a page not present in RAM, the CPU traps to the OS 1. Page fault trap 2. The OS chooses a page from RAM and evicts it from its page frame - Backs it up to disk if its content has changed 3. Brings the requested page from the disk

Answer 108

Pages currently in RAM are the process' working set Thrashing when a process keeps causing page faults

Answer 109

Pages currently in RAM are the process' working set Thrashing when a process keeps causing page faults

Answer 110

Hardware comes with its pre-defined page size, e.g., 4096B (4KB) The OS can define its software page size to, say, 2 hardware pages On average, half of the last page will be unused * Internal fragmentation * This pushes to use small page sizes * But very small pages results in higher management cos

Answer 111

Page information stored in a page table * The number of a virtual page is used as index * If the present/absent bit is 1 The cell contains the page location in RAM * Else, not loaded Need to access the page table for each memory reference Worse, need to access the page table in order to read next instruction to execute Big decision: where do we store the page table? * The table can be large - 4KB pages, 32-bit address => 1 million pages - One-page table per process! - Naive approaches * Store the page table in main memory * Load the whole page table of a process into the MMU

Answer 112

Most programs access a small number of pages most of the time Add Translation Lookaside Buffer (TLB) to MMU * Part of paging hardware Stores frequently accessed frames * Acts as a cache for the page table * Rarely more than 256 entries If referenced memory address is in TLB, then no need to access the page table If not, then fetch the page entry from the page table and load it into the TLB Valid bit indicates whether page is in use or not

Answer 113

Effective access time assumes * The requested virtual page is in RAM Given * It takes 30 nanoseconds to search the TLB * It takes 100 nanoseconds to access memory * An 80%t hit ratio, i.e., desired page number in the TLB 80% of the time  Finding the Effective Access Time for a memory address * If the page number is in the TLB: 30ns TLB + 100ns memory * Otherwise, not in the TLB (30ns)  Search memory for the page table and frame number (+100ns)  Search the desired byte in memory (100ns)  230 nanoseconds in total * effective access time = 0.80 x 130 + 0.20 x 230 = 150ns

Answer 114

Each component of the program can be given a segment A segment is a contiguous set of addresses Segments sizes might be different

Answer 115

Required to decide on which page to evict * Should not evict a page that is going to be used soon If a page has been modified, it must be written back to disk

Answer 116

Estimate the time it will take before you need to access each page Order the pages in the ascending order of * E.g., page 3 will be used next, then page 17, then page 23, …, then page 5 Evict the last page * E.g., page 5 Pick the one which will not be used before the longest time Not possible unless we know when pages will be referenced (crystal ball) Used as ideal reference algorithm

Answer 117

Uses two bits: * R: recently used * M: modified Periodically, set R to Zero A page belongs to one of four classes * Class 0: not referenced, not modified * Class 1: not referenced, modified * Class 2: referenced, not modified * Class 3: referenced, modified Evict a page from the lowest class

Answer 118

Maintains a list ordered by ascending arrival time Evict the head of the list Problem * If a page in the list is used again, it does not change its position * The oldest might be still in heavy use

Answer 119

Similar to FIFO, but checks the R bit If 1 * Put the page at the end of the list, set R to 0 If 0 * Evict

Answer 120

“Least” not as in a counter * Not “Least Frequently Used” (LFU) Evict the page that has not been used for the longest time Maintain a list of pages according to their recency of usage * From most recent (head) to least recent (tail) Resource consuming, will potentially need to frequently move pages in the queue

Answer 121

A unique identifier for each process

Answer 122

The PID of the parent process

Answer 123

The current state of the process (e.g., running, blocked, suspended, etc.). Process Priority: The priority level assigned to the process by the operating system.

Answer 124

The priority level is assigned to the process by the operating system.

Answer 125

The resources allocated to the process by the operating system (e.g., memory, CPU time, I/O devices).

Answer 126

A unique identifier for each thread within a process.

Answer 127

The current state of the thread (e.g., running, blocked, suspended, etc.).

Answer 128

The set of registers used by the thread for storing its execution context.

Answer 129

The memory address pointing to the current top of the thread's stack.

Answer 130

Data structures specific to a particular thread, such as thread-local storage or thread-specific variables.

Answer 131

The process is waiting for a resource (e.g., I/O) to become available, and it cannot continue until the resource is ready.

Answer 132

The process is currently running on the CPU.

Answer 133

The process is waiting for the CPU to become available, and it is ready to execute.

Answer 134

A process that was waiting for an I/O operation or another event to complete becomes ready to run again once the event has finished or the resource becomes available.

Answer 135

A process in the ready queue is selected by the scheduler to run on the CPU.

Answer 136

A process that needs to perform an I/O operation or another event that cannot be completed immediately must wait for the event to complete, and therefore, it becomes blocked.

Answer 137

A process that is preempted by the scheduler or finishes its CPU burst returns to the ready queue, waiting for another opportunity to run on the CPU.

Answer 138

The operating system schedules processes in the order they arrive, with the first process in the queue being the first to receive CPU time.

Answer 139

The operating system allocates a fixed time slice or quantum of CPU time to each process in turn, with processes being rotated through the CPU based on their arrival time and the length of their CPU bursts.

Answer 140

The operating system assigns each process a priority level based on its characteristics, such as its level of interactivity or its importance to the system, and schedules processes with higher priorities before those with lower priorities.

Answer 141

A race condition is a situation that occurs when two or more processes or threads access a shared resource or data concurrently and try to modify it at the same time, leading to unpredictable or incorrect behaviour. Proper synchronization techniques and mutual exclusion mechanisms such as locks, semaphores, or monitors can be used to prevent race conditions and ensure safe access to shared resources.

Answer 142

A critical region is a section of code or a segment of a program where shared resources, such as variables, data structures, or I/O devices, are accessed and modified by multiple processes or threads concurrently. Since the execution of the critical region by multiple processes or threads can lead to race conditions and inconsistencies, it is necessary to ensure mutual exclusion and synchronization of access to the shared resources. To achieve this, critical regions are typically protected by synchronization mechanisms such as locks, semaphores, or monitors that allow only one process or thread at a time to access the critical region and ensure that the modifications to the shared resources are made atomically and in a consistent order. The use of critical regions and synchronization mechanisms is essential to prevent race conditions, ensure data integrity and consistency, and avoid conflicts and deadlocks in concurrent software systems.

Answer 143

The TSL (Test and Set Lock) instruction is a low-level synchronization primitive that is used to implement mutual exclusion and critical sections in concurrent software systems. The TSL instruction typically takes two arguments: a memory location or a variable, and a register. The instruction atomically tests the value of the memory location or variable, and if it is zero, sets it to a non-zero value and stores the old value in the register. The TSL instruction guarantees that the entire operation is executed atomically and is not interrupted by other threads or processes. However, the TSL instruction is a low-level primitive and can be prone to several issues such as busy waiting, starvation, or deadlocks if not used correctly. Therefore, higher-level synchronization primitives such as locks, semaphores, or monitors are typically used instead of the TSL instruction in modern concurrent programming.

Answer 144

Semaphores are an abstract synchronization primitive used to control access to shared resources in a concurrent system. They provide two basic operations: wait and signal, which can be used to coordinate the execution of multiple threads or processes. Semaphores are a fundamental building block for many higher-level synchronization mechanisms such as locks, monitors, and condition variables.

Answer 145

Mutual exclusion can be implemented using a semaphore, also known as a mutex. The mutex semaphore is initialized to 1, indicating that the critical section is initially free. When a thread wants to enter the critical section, it first executes a wait operation on the mutex semaphore. If the value of the semaphore is 1, indicating that the critical section is free, the thread decrements the value of the semaphore to 0 and enters the critical section. If the value of the semaphore is 0, indicating that the critical section is already being used by another thread, the wait operation blocks the calling thread until the value of the semaphore becomes 1. When the thread leaves the critical section, it executes a signal operation on the mutex semaphore, which increments the value of the semaphore to 1 and wakes up any waiting threads. This ensures that only one thread can be in the critical section at any given time, providing mutual exclusion.

Answer 146

Concurrency refers to the property of a system in which multiple independent tasks or processes can make progress simultaneously, potentially overlapping in time.

Answer 147

Parallelism refers to the execution of multiple tasks or processes simultaneously using multiple computing resources, such as multiple CPUs, cores, or nodes.

Answer 148

One example of concurrency that is not parallelism is a single-threaded web server handling multiple requests from different clients. While the server can only execute one request at a time, it can handle multiple requests concurrently by switching between them in rapid succession. While the worker thread is busy, the server can switch back to the main thread and handle other incoming requests in a similar manner. This way, the server can handle multiple requests concurrently, even though it is not using multiple processors or cores.

Answer 149

On a single-core system, latency and throughput are often inversely related: reducing latency usually comes at the cost of reducing throughput, and vice versa. This is because increasing the speed at which tasks are executed (to reduce latency) often requires more resources, which can reduce the number of tasks that can be executed in parallel (thus reducing throughput). Pipelining (using more than one core) can help to mitigate this by allowing multiple tasks to be executed simultaneously, potentially increasing both throughput and reducing latency. By splitting tasks into smaller sub-tasks and assigning them to different cores, pipelining can increase the total amount of work that can be done in a given period of time (throughput) while also reducing the amount of time it takes for a task to be completed (latency).

Answer 150

The Unix construct that can be used to implement a stream between two processes is a pipe. A pipe is a communication mechanism that allows the output of one process (the producer) to be connected to the input of another process (the consumer) so that data can be transferred between them. The pipe behaves like a unidirectional stream, with data flowing from the producer to the consumer.

Answer 151

Yes, the pipe approach can be used when more than one producer and/or consumer is involved. Multiple producers can write data to the same pipe, which can be read by a single consumer. The consumer can use techniques such as polling or blocking to read data from the pipe as it becomes available. Similarly, multiple consumers can read data from the same pipe, which is produced by a single producer. The producer can write data to the pipe as it becomes available, and the consumers can use techniques such as polling or blocking to read data from the pipe as it arrives.

Answer 152

1. The data is transferred in fixed-size chunks, with a well-defined boundary between each chunk. 2. The producer and consumer threads operate independently, without requiring any synchronization or coordination between them. 3. The producer thread writes data to a shared buffer, and the consumer thread reads data from the same buffer. 4. The buffer is implemented using lock-free data structures, such as circular buffers or linked lists. This allows the producer and consumer threads to access the buffer without requiring any locks or other synchronization primitives.

Answer 153

A register used to store the address of the latest instruction run for a program. Each program has a program counter.

Answer 154

A file that uses 8 bits out of each byte

Answer 155

No need to read bytes 1 to n-1 before reading or writing byte 1

Answer 156

when a function is called

Answer 157

chmod a+x file

Answer 158

The size of the page frame has to be identical to the size of a page frame

Answer 159

A requested virtual memory page is not present in RAM

Answer 160

False, only the last page of a process will, on average, contain 50% of useful data.

Answer 161

The access request will fail because 1000<2000

Answer 162

2- SRT is preemptive

Answer 163

Latency refers to the amount of time it takes for a single task to complete. It is the delay between the initiation of a request and the time when the response is received. It is usually measured in units of time, such as seconds, milliseconds, or microseconds.

Answer 164

Threads – Abstracts & hides CPUs – OS shares CPUs over Threads – Hence schedules threads to CPUs Process – Abstracts & hides computer resources (except CPUs) – Shares computer resources (RAM, Disc and I/O) over processes

Answer 165

Thread Context = all info needed to restore a Thread to run in a CPU e.g. program counter, stack pointer, thread state, thread register values, pointer to thread code, pointer to parent process etc.

Answer 166

* Running thread calls an OS service e.g. * I/O service * Synchronisation primitive * Delay function * etc.

Answer 167

Pre-emptive Scheduler * All non pre-emptive reasons plus interrupts e.g. * Timer interrupt for time slicing * I/O interrupt (e.g. disc or comms controller has finished DMA, GUI button pressed etc.) * Software exception

Answer 168

The code that is responsible for sharing the CPU(s) between threads. Note that this can be: a) Part of a standard Operating System (e.g. Linux). b) Part of a ‘program’ e.g. part of Java’s JVM (executes in user space). c) A combination of (a) and (b).

Answer 169

The OS will most likely run on the last interrupted CPU or where a Thread calls an OS service

Answer 170

Note that the OS can switch threads across CPUs (this will be dependent upon the scheduling algorithm) * But also note that a thread will execute on multiple CPUs at the same time

Answer 171

- Speed of execution on multicore systems (inc. logical cores) - Responsiveness - Ease of programming

Answer 172

Disadvantages * You need to understand and program in a multithreaded paradigm

Answer 173

In a multithreaded OS: * Threads used to share CPU(s) * Context Switching between Threads is generally fast * Context and status stored in TCB * Processes used to share other resources (e.g. memory, I/O systems etc.) * Processes can have many threads * Generally threads can access all a parent processes resources * Switching between processes generally much slower than a Thread Context Switch. * Process info. stored in its PCB (process control block)

Answer 174

where the answer depends upon the scheduling of the threads!!!! (code is not "thread-safe") Solution: Protect with Critical Region

Answer 175

“Critical Region” = section of code that can only be executed by one thread at a time

Answer 176

A thread that has control (ownership) of one critical region prevents access to all critical regions protected by that lock.

Answer 177

You can use multiple locks to protect multiple critical regions * A thread that has control (ownership) of one lock does not prevent other threads from gaining control of other locks and their critical regions

Answer 178

Any mutable object that can accessed by more than one thread

Answer 179

Prevent concurrent access to shared objects and variables

Answer 180

“Critical Region” = section of code that can only be executed by one thread at a time

Answer 181

– Use for Mutual Exclusion – Use for thread synchronization

Answer 182

Monitor (instances) contain a set of mutually exclusive methods. They’re similar but more flexible than critical regions. Thus once a thread has entered a monitor (i.e. started to execute any of its methods) it is said to have ownership of the monitor. Once it finishes executing a method – then it releases ownership. If a thread has ownership then all other threads will be blocked when they attempt to enter the monitor.

Answer 183

Use synchronized key word and a single implicit condition variable per synchronised object

Answer 184

Uses explicit locks (e.g. ReentrantLock) and explicit condition variables that are properties of their locks

Answer 185

We can declare and use Condition variables with locks in order to synchronise the operation of threads

Answer 186

* Ownership: the thread that has MX control of the monitor * Signaller: a thread that calls lock.signal() * Waiter: a thread that calls lock.await()Monitor Terminology

Answer 187

The key property that waiting for a condition provides is that it atomically releases the associated lock and suspends the current thread.

Answer 188

* OS selects (say) t1 from cv1 queue * Signaller releases ownership to waiter (t1) and t1 gains ownership and starts running * Note that if the signal is not at the end of the signaller’s (t3’s) method call, then ownership will revert back to the signaller (t3) at some stage (but after t1 releases ownership) so that it (t3) can finish execution of its method – Gotcha: signaller releases MX control and must then regain it

Answer 189

* OS selects (say) t1 from cv1 wait queue * waiter (t1) added to MX (ownership) queue and signaller (t3) continues. * Signaller (t3) exits monitor method and releases ownership * Next thread queued on ownership Q (say t1) moved to ready Q …

Answer 190

1. Decouple Timing of Consumer and Producer 2. Act as Collector for Multiple Producers 3. Act as Distributor for Multiple Consumers

Answer 191

1. Decouple Timing of Consumer and Producer 2. Act as Collector for Multiple Producers 3. Act as Distributor for Multiple Consumers

Answer 192

* Pass by value to thread = not part of shared state * Passed by reference to thread = Part of shared state

Answer 193

Always Runnable – in either ReadyToRun or Running (on a CPU) * Can use lots of processor cycles and make system unresponsive! For safety can add sleep into loop * Prevents processor hogging but increases average latency

Answer 194

Three OS-provided software mechanisms for achieving communication between two processes are: Pipes: A pipe is a unidirectional communication channel that allows the output of one process to be connected to the input of another process. Pipes are typically used for simple, sequential communication between two processes. Sockets: Sockets are used for communication between processes over a network. They provide a standardized interface for communication, allowing processes to communicate with each other regardless of their location or underlying hardware. Shared memory: Shared memory allows multiple processes to access the same physical memory space, allowing for efficient communication between them. This can be used for high-performance, low-latency communication between processes that require frequent exchange of data.

OC Flashcards

(223 cards)