Wikinotes

Maintainer: admin

The final exam will take place on Monday, December 10th, from 6pm to 9pm, in Bronfman (room 422 if your last name is Ach-Kle, 423 otherwise). Chapters covered: 1-11. A standard, non-graphing calculator is permitted. No notes, no textbooks. Only material that has been covered in class will be tested. There will be 10 short- and long-answer questions, possibly containing multiple parts. It will focus on examples and applications to test your understanding as opposed to straight definitions (though you should know the definitions as well).

This page will contain a point-form summary and sample questions (both student-created and collected from outside sources) for each chapter. Answers to selected exercises in the textbook (7th edition) will also be provided. If you notice any errors, feel free to edit the page directly (or contact @dellsystem about it).

Under construction.

1 Chapter 1: Introduction
- 1.1 Sample questions
- 1.2 Answers to textbook exercises
  - 1.2.1 Question 1.10
  - 1.2.2 Question 1.15
2 Chapter 2: Operating-system structures
- 2.1 Sample questions
- 2.2 Answers to textbook exercises
3 Chapter 3: Processes
- 3.1 Sample questions
- 3.2 Answers to textbook exercises
  - 3.2.1 Question 3.5
4 Chapter 4: Threads
- 4.1 Sample questions
- 4.2 Answers to textbook exercises
  - 4.2.1 Question 4.4
5 Chapter 5: CPU scheduling
- 5.1 Sample questions
  - 5.1.1 Short-term scheduling
  - 5.1.2 Scheduling algorithm factors
- 5.2 Answers to textbook exercises
6 Chapter 6: Process synchronisation
- 6.1 Sample questions
- 6.2 Answers to textbook exercises
7 Chapter 7: Deadlocks
- 7.1 Sample questions
- 7.2 Answers to textbook exercises
  - 7.2.1 Question 7.12
8 Chapter 8: Main memory
9 Chapter 9: Virtual memory
- 9.1 Sample questions
- 9.2 Answers to textbook exercises
10 Chapter 10: File-system interface
- 10.1 Sample questions
- 10.2 Answers to textbook exercises
11 Chapter 11: File-system implementation
- 11.1 Sample questions
- 11.2 Answers to textbook exercises

OS: program, between user and hardware
- goals:
  - execute user programs, solve user problems
  - make computer convenient to use
  - use hardware efficiently
- allocates resources fairly and efficiently
- controls execution of programs to prevent errors, etc
4 components of a computer system
- hardware: computing resources
- OS: controls, coordinate hardware use
- application programs
- users
kernel: one program always running; everything else = system/application program
- monolithic: put as much as possible in the kernel; used by windows and GNU/linux
- microkernel: put as little as possible in the kernel, have everything else run in user space; used by Mac OS (Linus Torvalds thinks this is dumb)
bootstrap program: stored in ROM/EPROM, aka firmware (and not RAM, because RAM is volatile, lol)
- loads kernel, begins its execution; bootstraps everything else
computer system organisation
- CPUs and device controllers compete for access to shared memory, using a common bus
- I/O devices and CPUs can execute concurrently
- each device controller is responsible for a particular device (or multiple devices, e.g., disks), has a local buffer
- data is first stored in controller's local buffer
- CPU moves data between local buffers and main memory
- when device controller is done, it causes an interrupt to let the CPU know
  - CPU looks up memory address of the relevant interrupt handler (aka interrupt service routine) based on the type of interrupt, using the interrupt vector table
  - the address and PC of instruction that is currently being interrupted is saved (along with registers)
  - control is transferred to interrupt handler
  - incoming interrupts are ignored to prevent a lost interrupt
  - once the interrupt handler has completed, returns to previous instruction (return address, flags popped from stack - what flags?)
- trap: software-generated interrupt (caused by error or user request)
- interrupts form the basis of modern operating systems
- interrupt timeline diagram, explained in words:
  - at first, CPU is executing user process
  - then, I/O device receives data, takes some time to complete the transfer
  - once the transfer is complete, CPU processes the interrupt; I/O device is idle again
  - CPU returns to executing user process
  - I/O device remains idle until another I/O request occurs - repeat the process
- System call: request to OS, user waits for I/O completion
- Device status table: contains type, address and state for each I/O device
  - When an interrupt occurs, OS updates the DST entry for the device to indicate interrupt
- direct memory access:
  - special controller (DMA controller) takes care of transmitting data to/from main memory, without involving the CPU
  - increased data throughput
  - CPU can do other work while data is being transferred
  - data can be transferred faster (useful for sound, network, graphics cards)
storage structures
- main memory: only large storage media that CPU can access directly; volatile, quick to access, limited in size
- secondary: disk storage i think? not sure, access managed via disk controller
- hierarchy:
  - registers
  - CPU cache
  - main memory
  - electronic disk
  - magnetic disk
  - optical disk
  - magnetic tapes lol
- caching
  - performed at many levels (hardware, OS, software)
  - copied from larger but slower storage to a smaller, faster one
  - I'm sure everyone knows how caching works by now
computer system architecture
- usually one general-purpose processor, and possibly special-purpose ones too (e.g., GPU)
- multiple cores = still one processor, just more than one core on a single chip (efficient for communication and power usage)
- multiprocessor systems:
  - asymmetric (master-slave) or symmetric (peers)
  - increased throughput, shared peripherals, graceful degradation
  - each CPU still has its own registers and cache
- clustered systems
  - multiple computers working in tandem
  - asymmetric or symmetric clustering
  - usually shared storage via a storage area network (SAN)
operating system structure
- multiprogramming: organises jobs so that CPU always has one to execute (fair scheduling)
- timesharing: always 1 process running in memory
  - other jobs kept in memory, OS switches between processes very quickly
  - if all the processes don't fit in memory, they're swapped to disk (virtual memory)
- dual-mode: user mode, kernel mode
  - some instructions are "privileged" - can only be executed in kernel mode
  - system calls are executed in kernel mode, returns to user mode after (if relevant)
  - mode bit: 1 for user mode, 0 for kernel mode
  - programs can leave user mode by triggering interrupt
  - there is a timer to prevent user programs from causing infinite loops and whatnot; when a counter reaches 0, OS generates interrupt
Processes
- process: program in execution
- needs resources: CPU, memory, I/O, files, initial data
- single-threaded process: has one PC, instructions executed sequentially
- multi-threaded: one PC per thread (more detail later)
- the OS must take care of:
  - creating, deleting user/system processes
  - suspending and resuming processes as necessary
  - providing mechanisms for process synchronisation
  - providing mechanisms for process communication
  - handling deadlock
memory management: keeps track of what is being used, deciding which to swap, allocating and deallocating shit etc
storage management
- OS provides an abstraction for physical storage devices; logical storage unit = file
- file system management: access control, creating/deleting, mapping files onto physical location, etc
I/O subsystems
- hide details of I/O devices
- take care of memory management, including buffering, caching, spooling (simultaneous peripheral operations on line), drivers, etc
computing environments
- client-server (fileserver, webserver, etc)
- peer-to-peer (distributed)

Name the four components of a computer system.

Hardware, operating system, application programs, users

What is a bootstrap program?

Program that loads the kernel and begins its execution, bootstrapping everything else

Difference between the two, name one OS that uses each method.

Monolithic: put as much as you can inside the kernel itself; used by GNU/Linux, Windows
Microkernel: put very little inside the kernel, and let most things be user programs; used by Mac OS

Draw a diagram showing how CPUs, devices, device controllers and main memory are connected in a standard computer system.

CPUs on same level as device controllers, devices connected to controllers, CPUs and controllers connected to main memory via a shared bus

Draw a diagram illustrating the interrupt model, and explain what happens.

i hope this isn't on the midterm
Process running->interrupt, OS save data, parameter to pass and PC on register and or stack, enter kernel mode, execute interrupt handling, save result on register and stack, return to user mode, restore PC and processing continue.

Draw the interrupt timeline.

lol

What is a trap, and how are they caused?

Software-generated interrupt, caused by errors or user requests

What information does a device status table contain?

Type, address, and state for each I/O device

How does direct memory access work, and what are its benefits?

A special controller, called a DMA controller, takes care of transmitting data to and from main memory so that the CPU doesn't have to. Benefits: increased data throughput, CPU can do other work when the data is being transferred, data can be transferred faster (useful for sound, network, graphics cards, etc).

What factors determine the storage structure hierarchy and what are its components?

Closer to CPU: faster, more volatile, more expensive, smaller. Hierarchy: registers, CPU cache, main memory, electronic disk, etc.

Types of multiprocessor systems, and benefits of multiprocessing in general

Asymmetric (master-slave), symmetric (peers). Benefits: increased throughput, shared peripherals, graceful degradation.

Benefits of placing multiple cores on a single chip?

More efficient for communication and power consumption

How does timesharing work? What happens if there are too many processes to fit in main memory?

one process running in memory, other jobs waiting to run, OS switches between jobs quickly (creating the illusion of interactive computing)

Swapped to disk

Difference between user and kernel mode, mode bits for each

Kernel: for privileged system programs, mode bit 0; user: for application programs, mode bit 1

Difference between a program and process

Process: program in execution

Purpose of interrupts, what are traps, can traps be generated intentionally by user programs

A trap is usually a specific type of interrupt (a software interrupt), caused by errors or user requests. Purpose: to return control to the OS, wherein it will perform some action in kernel mode. Can be generated intentionally by the user program if the user wants to quit or something.

Mechanism for preventing programs from modifying the memory of other programs

table specifying what locations in memory belong to which table. basically paging

Operating system services, provided for users:
- user interface (GUI or CLI)
- program execution
- I/O operations
- file system manipulation
- inter-process communication
- error detection (could occur in hardware, I/O, or user programs)
services needed for efficient operation of system
- resource allocation
- accounting (keep track of resource usage)
- protection (resource usage is controlled properly)
- security (from outsiders)
system calls: programming interface to OS-provided services
- usually accessed via APIs (different one for each type of OS) - more portable, etc
- three methods for passing parameters to OS:
  - registers (limiting)
  - block, or table, in memory; address of block passed as parameter in a register
  - pushed onto stack by program, popped off by OS
system programs
- can be simply interfaces to system calls, or more complex
- file management: create, delete, copy, rename, etc
- status info: date, du, top, etc
- file modification: sed, vim, etc
- programming support: compilers, assemblers, interpreters
- program loading and execution: gdb, loaders
- communication: email, scp, ssh, IPC, etc
OS design
- user goals: convenient to use, easy to learn, reliable, safe, fast
- system goals: easy to design and implement, reliable, flexible, error-free, efficient
- policy: what will be done
- mechanism: how to do it
- the two should be separate. e.g., scheduling is controlled by loadable tables in solaris - can be time-shared, real-time, etc
- MS-DOS (like soup):
  - not modular, interfaces and levels of functionality not well separated
  - applications can access basic I/O routines, write directly to disk/display
- UNIX (like lasagna):
  - system programs, then the kernel (everything below syscall interface)
  - kernel provides file system, CPU scheduling, memory management, etc
  - traditional structure: some layers, but a lot of functionality per level
- layered approach: N + 1 layers; 0 is hardware, N is user interface
  - each layer only uses functions defined in lower layers
- microkernel (like chocolate???):
  - easier to extend
  - easier to port to new architectures
  - more reliable (less code running in kernel mode)
  - more secure
  - performance overhead of user space to kernel space communication
- modular kernels (like with solaris): Lego
  - each module talks to others over defined interfaces
  - similar to layers but more flexible, as any module can call any other module
virtual machine: provides interface identical to underlying hardware
- separate execution environment
- protected
- can communicate with each other
- can share some files, etc
- paravirtualisation: guest OS is provided with system similar to (but not identical to) hardware
  - guest OS must be modified to run on paravirtualised hardware
  - smaller virtualisation layer, more efficient use of resources
system boot
- bootstrap loader locates the kernel, loads it into memory, starts it
- can be a 2-step process: boot block loads bootstrap loader, etc
- execution then starts at a fixed memory location
- stored in firmware (ROM) not RAM because RAM is volatile and at an unknown state when the system starts up, and because ROM needs no initialisation and cannot be easily infected by a virus

What are the three methods for passing parameters in a system call?

Registers, memory block (or table) - address passed as parameter in register, stack

Benefits of microkernels? Disadvantages?

Benefits: easier to extend, more portable, more reliable, more secure

Disadvantage: performance overheard of user space to kernel space communication

What is a virtual machine etc

Application program that provides interface identical to underlying hardware so that it can run other operating systems, unmodified

What is paravirtualisation

When the interface is similar but not identical to the underlying hardware. Smaller virtualisation layer, more efficient use of resources. The guest OS must be modified, though.

Why in ROM and not RAM

Well, RAM is volatile, don't know what state it could be in when you start up a system. Also, ROM needs no initialisation and cannot easily be infected with a virus.

5 file-management activities of an OS

Creating, deleting, renaming, copying, listing

Pros/cons of using the same system call interface for manipulating files and devices?

Pros: easier to use and remember

Cons: more overhead maybe? some things aren't really applicable to both

Why is separation of mechanism and policy desirable

Easier to change

Advantages of using virtual machines

For the user: can run multiple OSes at a time, they're all isolated (so more secure), easier and faster to set up

Process includes:
- program counter
- stack (for temporary data - function params, return addresses)
- data section (global variables)
in memory, we have:
- stack
- heap, which grows upwards as the stack grows downwards (towards each other), it doesn't seem to count though
- data section
- text (program code)
process states:
- new: being created
- ready: waiting to be assigned to a processor
- running: being executed
- waiting: waiting for something to occur (e.g., I/O completion, signal reception)
- terminated: done
only one process can be running on one processor at a time
process control block, data structure in OS kernel, for storing process info; includes:
- process state
- program counter (address of next instruction)
- CPU registers
- CPU scheduling info
- memory management info
- accounting info (CPU used, time used, process number, etc - stuff you see using top)
- I/O status info (list of devices allocated and open files)
- (the first three are saved when interrupt occurs)
switching between processes
- CPU executes process, then along comes an interrupt of some sort
- the process state is saved into PCB₀
- OS handles interrupt
- now it's time for another process, which uses PCB₁ to execute
- OS loads state from PCB₁, then the other process executes
- etc
process scheduling queues (implemented via linked lists)
- job queue: set of all processes in system
- ready queue: set of all processes residing in main memory that are ready to execute
- device queues: set of processes waiting for each I/O device
- processes migrate between queues (or rather, the PCBs do)
schedulers
- long-term scheduler: decides which processes should be loaded from disk and brought into the ready queue (in memory)
  - invoked very infrequently, can be slow
  - controls degree of multiprogramming
- short-term scheduler: decides which process should be executed next and allocates CPU for it
  - invoked frequently, must be fast
- medium-term scheduler: removes processes from memory to reduce degree of multiprogramming
I/O-bound: more time spent doing I/O (so many short CPU bursts); CPU-bound: more time doing computations (so long CPU bursts)
context switching
- info saved in PCB
- overhead, no useful work done
creating process babies
- parent processes create child processes, and so on (--> tree)
- processes identified by pid, integer
- different resource sharing schemes:
  - parent, child share all
  - child has access to some of parent's
  - parent, child share nothing
- different execution schemes:
  - concurrent execution
  - parent waits until children die
- child is first a duplicate of parent, with the same program and data, then has a new program loaded into it
- UNIX examples
  - fork: new process, identical to parent
  - exec: after fork, process' memory space replaced by new program
- solaris example
  - root of tree: scheduler, pid = 0; creates other processes, etc
termination
- after a process executes its last statement, it asks the OS to delete it (exit)
- return status is passed to the parent, if the parent used wait
- OS deallocates the process' resources
- parents can abort their children - reasons include
  - child is using too many resources
  - whatever the child is doing is no longer useful
- if parent exists, the children may all be terminated (depends on OS)
inter-process communication
- processes can be independent or cooperating
- cooperating processes can share data, etc - need communication
- shared memory, via some location in memory accessible by both processes
- message passing, via kernel
- producer-consumer problem: which paradigm to use?
  - unbounded buffer vs bounded buffer
  - if bounded (which is the only feasible one really), producer needs to wait if full; consumer, if empty (in all cases)
  - shared memory solution for a bounded (circular) buffer:
    - save a pointer to the first free position (in), and a pointer to the first full position (out)
    - producer: while there are no free buffers, wait; when there are, add an item, increase the pointer to the first free position
    - consumer: while there are no items, wait; when there are, remove an item, increase the pointer to the first full position
  - can only use BUFFER_SIZE - 1 elements
  - empty when in == out
  - full when (int + 1) % BUFFER_SIZE == out
- message passing:
  - IPC facility provides send, receive functions
  - if processes P and Q want to communicate, they first establish a link, then exchange messages
  - can be direct (must explicitly name the other process) or indirect (using mailboxes)
  - direct communication links:
    - send(P, message) and receive(Q, message)
    - each link associated with exactly 2 processes
    - between two processes there can be at most one link
    - can be unidirectional or bidirectional (more common)
    - disadvantages: hard-coded identity, hard to make changes later
  - indirect:
    - "mailboxes"; but really, just ports lol
    - each port has unique ID
    - processes can only communicate if they share a common port
    - link can be associated with many processes
    - each pair of processes can share several links
    - can be uni or bidirectional
    - operations: create mailbox, send/receive, destory
    - send(A, message) where A is the mailbox, etc
  - link: only two processes?
  - only one process can execute receive operation at a time?
  - round-robin scheme - sender throws it out randomly, some receiver gets it, sender gets notified as to who
- message passing: blocking or not, on part of sender or receiver
- queue of messages attached to link
  - zero capacity: sender waits for receiver (rendez-vous)
  - bounded (finite) capacity: sender waits if queue full
  - unbounded (infinite) capacity: sender never waits, is this even possible?
- Examples
  - POSIX shared memory
    - process creates shared memory segment, returns an ID
    - processes wanting access to that segment must attach to it by ID (call returns pointer)
    - can write to that memory segment (using the pointer)
    - can detach it from its address space when done
  - Mach:
    - message-based (everything! even system calls)
    - all tasks are created with 2 mailboxes (which are created with port_allocate(): kernel, and notify
    - three system calls: msg_send, msg_receive, msg_rpc (remote procedure call, to execute something elsewhere)
  - Windows XP:
    - message-based using "local procedure call" (can only be used by local processes)
    - communication channels established using ports (sort of like mailboxes)
    - client opens handle to subsystem's connection port, sends a connect request
    - server creates two private communication ports, sends one to client, keeps the other one
    - corresponding ports are used by server and client to send/receive messages
    - INSERT DIAGRAM LATER
client-server communication
- sockets (endpoints for communication)
  - IP address + port
  - different services listen on different ports, e.g. ssh on 22, typical web servers on 80, etc
- remote-procedure calls
  - allows clients to invoke a procedure on a remote host as if it were local
  - client-side stub locates server, marshalls parameters, sends them over (underlying details abstracted)
  - server-side stub receives messages, unmarshalls parameters, performs procedure
  - INSERT DIAGRAM LATER (or describe it at least)
- remote method invocation (java only)
  - java program on one machine can call a method on a remote java object
  - basically the same as RMI except there are objects involved
  - THERE IS A DIAGRAM HERE. it doesn't really say much though. look it over anyway

What is associated with process in memory etc

Stack (which grows downward), heap (which grows upward), data section (for global variables), text (program code)

Five process states?

New, ready, running, waiting, terminated

What's contained in a PCB, and which of these things are saved (updated) when an interrupt occurs?

Process state
Program counter
CPU registers
CPU scheduling info
Memory management info
Accounting info
I/O status info

First three are saved when an interrupt occurs

Types of queues? What are the elements of these queues?

Job queue (all processes), ready queue (those residing in main memory that are ready to execute), device queues (those waiting for each I/O device, so a different one for each device). Elements: PCBs

Describe the types of schedulers and how often they're invoked, etc.

Long-term scheduler: decides which processes to bring into main memory (ready queue), invoked infrequently

Short-term scheduler: which process should be executed next (from ready queue to CPU), invoked frequently

There is also a medium-term scheduler which is probably less important but apparently it removes processes from memory once in a while.

What is an I/O-bound process? What is a CPU bound process?

I/O-bound: spends a lot of time doing I/O (and thus waiting for that). Characterised by many short CPU bursts.

CPU-bound: guess

What happens during context switching

Registers, PC, process state saved in PCB (no useful work done)

What does fork do, and how does it differ from exec

Fork creates a new process identical to the parent. Exec uses fork, then replaces the child process' memory space with that of a new program.

Why would a parent abort a child?

If the child is consuming too many resources (e.g., milk) or the child is not doing anything useful (a very common occurrence).

How can two processes communicate and shit (the two main methods)

Message-passing and shared mailboxes

Describe the bounded buffer thing.

in: pointer to first free position; out: pointer to first full position

Producer needs to wait when full (when (in + 1) % BUFFER_SIZE == out). Otherwise, add an item, increase in.

Consumer needs to wait when empty (when in == out). Othewise, remove an item, increase out.

Describe direct communication. Advantages? Disadvantages?

A process specifies another process by name, establishes a link between the two. Advantages: simple; disadvantages: hard-coded identity, hard to make changes later

what is it

Ports ("mailboxes"), each has unique ID, processes put shit in ports

what is it

Sender randomly throws a message into the air, some receiver gets it and consequently will be the next to get married. Sender gets notified as to who.

Types of queues (for messages, attached to link)?

Zero capacity (sender must wait for receiver - they must meet)
Bounded (sender waits if queue is full)
Unbounded (sender never waits, but this isn't really feasible lol)

Describe IPC implementations for POSIX, Mach, Windows XP.

POSIX: shared memory. Process creates shared memory segment, which returns an ID. Processes wanting access to that segment attach to it by ID (this function returns a pointer to that memory segment), and can then write to it using the pointer. Can detach from segment when done.

Mach: message-based (everything is, even system calls). All tasks are created with 2 mailboxes.

Windows XP: message-based using local procedure call. Communication channels established using ports. Whatever

What does a socket consist of

IP address and port

What is this, how does it differ from remote method invocation

Allows clients to invoke procedures on remote hosts as if they were local. Client-side "stub" locates server, marshalls parameters, sends them over; server-side stub unmarshalls, executes procedure.

Remote method invocation is a Java-only thing that allows programs on one machine to call methods on remote objects. Same as above except, objects.

Pros and cons of: (a) sync/async communication; (b) automatic and explicit buffering; (c) send by copy and send by reference; (d) fixed-size and variable-size messages.

(a) sync is blocking, so it can slow down processes. Sometimes it's necessary though.

(b) Explicit buffering has to be dealt with by the programmer, and it can be cumbersome; however, it's easier to fine-tune it to the requirements of the program.

(d) Fixed-size easier to deal with for the receiver maybe? Could be wasteful of space though

The rest of the questions in this chapter are insane

Thread: unit of CPU utilisation, forms basis of multithreaded computers
- things unique to each thread: thread ID, program counter, register set, stack
- things threads from the same process share: code, data (statically-created variables), OS resources (open files, signals)
- single-threaded process: code + data + files, then registers + stack
- multi-threaded: code + data + files, then each thread gets its own registers and stack
- Benefits of threading
  - Greater responsiveness (if one thread is blocked or busy, can keep going - e.g., webservers)
  - Resource sharing (memory, other resources)
  - Cheapter than creating new processes in terms of allocating memory and resources (context-switching is easier)
  - Scalability: threads can run in parallel on multiple processors (I don't really see how this is best characterised as "scalability"; perhaps making full use of resources?) scalable in term of webserver, you can throw more hardware at it and it will run to respond to more web request. I guess it is also more independent and volatile.
- In the client-server model: client sends request, server spawns new thread to handle request, server resumes listening for requests
Single vs. multicore
- on a single-core system, threads are allocated in a cycle: t1, t2, t3, t4, t1, t2, t3, t4 etc (this is what is meant by concurrency apparently?)
- on a multicore system, concurrency means that threads are actually executed at the same time. could be t1 t3 t1 t3 on one core, t2 t4 t2 t4 on the other, etc
- challenges of multicore systems:
  - how to divide up activities? need to find parts of application that can be divided into smaller tasks that can run in parallel
  - how to split data? must be divided to run on separate cores (? how does this make sense)check map reduce,data must be able to be processed in a divide and conquered way, like merge sort or some other polynomial algorithm=same processing step executed by looping entry of some array which is independent of each other.
  - data dependency: what if one task depends on the results of another?
  - testing/debugging: many different execution paths
user-level thread libraries:
- POSIX threads
- win32 threads
- Java threads
Kernel threads: handled by the kernel
Multithreading models, per process (user-to-kernel):
- many-to-one (many user-level, single kernel)
  - examples: solaris green threads library, gnu portable threads
  - thread management done by user space thread library (efficient)
  - but only thread can access the kernel at a time, so if any user thread makes a blocking syscall entire process will block
- one-to-one (one kernel thread per user thread)
  - examples: windows nt/xp/2000, linux, solaris 9+
  - benefits: more concurrency (syscalls are not blocking for other threads)
  - downsides: can result in decreased performance as you have to create many kernel threads, etc
  - also, some OSes limit the number of kernel threads possible at any given time
- many-to-many
  - examples: solaris before 9, windows nt/2000 with threadfiber package (how cute)
  - many user threads mapped to the same number of or fewer kernel threads
  - OS can create as many user threads as it needs to, since it doesn't have to create a kernel thread for each one
  - true concurrency: corresponding kernel threads can run in parallel on a multiprocessor (what does this have to do with anything)
- two-level model
  - examples: IRIX, HP-UX, Tru64 unix, solaris before 9
  - like the many-to-many model, except user threads can be bound to kernel threads as well (so a superset of many-to-many)
thread libraries
- APIs for creating, managing threads
- can be implemented in user space
  - calling a function in library results in a local call (not sys call) in user space
- or, using the kernel-level library provided by OS
  - code, data structures of library exist in kernel space
  - invoking APi function usually results in sys call
- pthreads: a POSIX standard for APIs for thread creation and sync
  - provided as user-level or kernel-level
  - the behaviour is specified by this standard, but it can be implemented differently by different OSes
  - examples: Solaris, Mac OS X, FreeBSD, Linux (there is even a windows implementation)
- Java threads
  - managed by the JVM, implemented using underlying thread library provided by OS
  - these threads can be created by extending the Thread class or implementing the Runnable interface
various issues (and non-issues) relating to threads
- behaviour of fork()
  - should it duplicate only the calling thread or all threads of that process?
  - some unix systems thus have two versions of fork()
  - exec, when invoked by a thread, will replace all the threads in that process. wait wtf? how? and why is this relevant to fork? I think it is more about, if we duplicate process,how does it affect the thread in the resulting process, is it duplicated, or just restart, or ignored....
- thread cancellation (premature termination)
  - how to deal with resource allocation, or if it's updating a data segment shared by other threads?
  - asynchronous cancellation: terminates the thread immediately (bit of a misleading name)
  - deferred cancellation: thread periodically checks if it should be cancelled, giving it the chance to die nobly
    - aside: signal handling (i think this section should count as an aside, even though it has its own slide)
    - signal handlers used to notify processes that specific events (e.g., kill events) have occurred
    - event generates signal, signal gets delivered to process, signal is handled
    - many options as to whom the signal is delivered to:
      - only the relevant thread
      - every thread in the process to which the relevant thread belongs
      - certain threads in the relevant process
      - a specific thread that receives all signals for the process
- thread pools
  - create some threads, throw them into a pool in which they wait around for work to be doled out, the poor creatures
  - faster to make an existing thread service a request than to create a new thread
  - number of threads in application bounded by the size of the pool
  - of course, this has the slight disadvantage of having to create all the threads at the very beginning (slower startup maybe)
- thread-specific data
  - so that each thread can have its own copy of data
  - supported by most threading libraries
  - e.g., transaction system (?)
- scheduler activation: scheme for communication between a user-thread library and the kernel
  - both the many-to-many and the two-level models require communication to ensure correct number of kernel threads
  - the mechanism for this communication is via upcalls (like the opposite of a system call?), from the kernel to the thread library
  - for indicating that a user thread is about to block
threads in different OSes
- windows XP
  - each app runs as a separate process
  - each can have one or more threads
  - thread library included in win32 api, one-to-one
  - fiber library (many-to-many) available too
  - each thread contains thread ID, register set, separate user/kernel stacks, private data storage area (last three collectively known as context)
  - primary data structures of a thread:
    - ethread: executive thread block (thread start address, pointer to parent block, pointer to kthread) - kernel space
    - kthread: kernel thread block (scheduling and sync info, kernel stack, pointer to teb) - kernel space
    - teb: thread environment block (thread identifier, user stack, thread-local storage) - user space
- linux
  - called tasks not threads
  - one-to-one
  - threads created by calling clone() (allows child task to share address space of parent task, or process)
  - amount of sharing that takes place is controlled by flags
    - CLONE_FS: file-system info shared
    - CLONE_VM: same memory space
    - CLONE_SIGHAND: share signal handlers
    - CLONE_FILES: share open files (how does this differ from CLONE_FS?)
  - NPTL (Native POSIX Thread Library) supported by most modern distros, POSIX-compliant

What is unique to each thread? What do threads from the same process share?

Unique: Thread ID, program counter, register set, stack

Shared: code, data (statically-created variables), OS resources (open files, signals)

^

More responsive
Can share memory, other resources
Cheaper than creating processes, context-switching is easier
More scalable? for multiple processors

What are the multithreading models, describe them, pros, cons, etc

Many-to-one (many user-level threads per kernel thread). Only one thread can access kernel at each time, so if one thread makes a blocking call, entire process blocks
One-to-one (one kernel per user): not blocking so more concurrency, but decreased performance as you have to create many kernel threads; also, some OSes limit number of kernel threads that can be created, so the number of user threads is limited too
Many-to-many (many user to some kernel): true concurrency, OS can create as many user threads as it wants, etc. Variant: two-level model, where you can have one user thread per kernel thread maybe

Different methods for dealing with thread cancellation

Asynchronous: terminates it immediately

Deferred: thread periodically checks to see if it should be cancelled

What are thread pools, pros and cons

Create a bunch of threads, throw them into a pool. There they wait to be given stuff to do. Pros: faster for existing thread to service request than to make a new thread. Cons: increased startup time to create all the threads, etc

Which of the following components of program state are shared across threads in a multithreaded process?

Heap memory, global variables. Stack, registers are per-thread.

Multiprogramming - needed for efficiency; ensures that CPU always has something to do
- only a subset of all jobs kept in memory; one job is selected and run at a time, via job scheduling
- when the OS has to wait (e.g. for I/O device), it switches to another job
- maximum CPU utilisation is attained this way
- CPU-I/O burst cycle: CPU executes, then waits for I/O (cycle)
- for ex, do some calculations (CPU), read from file (I/O), do more calculations (CPU), write back to file (I/O), etc
- most CPU bursts are really short
  - you really need to think that processing and I/O are two different jobs, even they are in the same program
CPU scheduler
- short-term: looks through ready-to-execute processes in memory and selects one for the CPU to run next
  - can take place when a process is switching from running to waiting (I/O), or is terminating (non-preemptive in this case - no other choice, has to find another program to run)
  - or, when from running to ready (interrupt), or waiting to ready (completion of I/O) - preemptive, because why? what?--> scheduler dispatcher
- dispatcher
  - gives the new process selected by the scheduler control of the CPU
  - requires switching context, switching to user mode, and jumping to the proper location in the user program
- things to consider when designing a scheduling algorithm, slash choosing processes (which is it? can it be both??):
  - maximise cpu utilisation: keep CPU as busy as possible
  - maximise throughput: number of processes completing per unit of time
  - minimise turnaround time: amount of time it takes for a process to complete, start to finish
  - minimise waiting time: amount of time process has been waiting in the ready queue
  - minimise response time: time taken from request submission until response (think interactive process, gui, it give impression it is instantaneous, but it is just doing a little bit all the time; or in networking, instead of downloading an image in one shot and showing it to you after it finish downloading, showing you bit and bit of it in case you are not interested...)
- types of scheduling
  - first-come, first-served
    - ex: P1 has burst time of 24, P2 of 3, P3 of 3
    - If they arrive in order, then, Gantt chart: P1 from 0 to 24, P2 from 24 to 27, P3 from 27 to 30
    - average waiting time: $(0 + 24 + 27) / 3 = 17$
    - If they arrive like P2 P3 P1, then, Gantt chart of P2 from 0 to 3, P3 from 3 to 6, P1 from 6 to 30
    - average waiting time: $(0 + 3 + 6) / 3 = 3$ - much better!
    - known as the convoy effect: short processes waiting for long processes, etc
  - shortest-job first
    - optimal, but, knowing length of request is hard (estimate, exponential averaging : $estimatedET_{n+1}=actualET_n * alpha+estimatedET_n * (1-alpha))$
    - only takes last burst into account
  - priority scheduling
    - SJF is priority
    - problem: starvation, low-priority jobs never execute
    - solution: aging, increase priority with age
  - round-robin
    - everything gets max q units of number of time
    - with lots of jobs, equivalent to FIFO
    - preemptive
    - small amount of CPU time
    - time unit must be large compared to context switch time or overhead is too high
    - higher turnaround than SJF, better response (which decreases as time quantum increases)
  - multi-level queue
    - foreground: RR, background, FCFS
    - each has its own scheduling algorithm
    - processes permanently assigned to a queue
    - scheduling done between queues
    - fixed priority (foreground first, then background): possibility of starvation
    - time slice: 80% to foreground, 20% background
  - multi-level feedback queue
    - 2 RRs, different q, and FCFS
    - low q, then high q, then FCFS
  - thread scheduling
    - distinguishes between user, kernel threads
    - process-contention scope, scheduling competition is within the process
    - system-contention scope: kernel thread has all the other threads in system to compete with
  - Multi-processor scheduling
    - homogeneous processors
    - asymmetric
    - symmetric
    - processor affinity (hard/soft)
    - complications: non-uniform memory access, etc
    - multicore processors: cores on same chip, faster and less power, but scheduling is harder
    - memory stall: when processor accesses memory, spends a lot of time waiting
- windows XP
  - priority based, preemptive
- linux
  - same, constant-time, smaller priority values --> higher priority (like, runs first)
- evaluating algos
  - deterministic modeling
  - simulation

When is the short-term scheduler invoked?

When an executing process is forced to wait (e.g., for the completion of I/O), or is terminating.

What are the factors that should be considered when designing a scheduling algorithm?

CPU utilisation: should be maximised
Throughput (process completing / time): max
Turnaround time (time taken for the average (?) process to complete): min
Waiting time (time a process waits in the ready queue): min
Response time (time it takes for a process to be responsive⁵): min

Which of the following scheduling algorithms could result in starvation? FCFS, SJF, RR, priority.

Not FCFS. SJF could unless you add aging (in which case it's called priority). Not RR. MLQ could, incidentally.

Consider a system implementing multilevel queue scheduling. What strategy can a computer user employ to maximize the amount of CPU time allocated to the user's process?

Don't run background processes?

Question omitted

(a) FCFS (aging)

(b) LIFO (discriminatory aging)

See http://www.csee.umbc.edu/courses/undergraduate/421/spring06/homework1-soln.pdf

Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes.

(a) FCFS: Not really. No discrimination.

(b) RR: Shorter processes usually get to finish faster, and don't have to be preempted. That's it though.

need to prevent concurrent access to shared data (inconsistency can result)
- to do this, need mechanisms to ensure orderly execution of processes
- otherwise, we get race conditions (multiple processes accessing/manipulating data concurrently)
  * consumer/producer problem
  * for example, if we just want to increment the variable x with x++
  - what actually happens is: set a register to x, increment the register, set x to the value of the register
  - if this is done concurrency with another register, you'll obviously have problems
  - to solve this: synchronisation
- also known as the critical section problem (for n processes)
  - each process has a "critical section" in which common variables may be changed
  - the solution to this problem must satisfy:
    - mutual exclusion: only one process can be in its critical section at a time
    - progress: can't get stuck in a situation where processes are waiting to enter their critical sections but can't even though no other process is
    - bounded waiting: after a process has made a request to enter its critical section (but before it is granted), only a limited number of other processes are allowed to enter theirs. in other words, wait time should be bounded
    - assumption: processes execute at non-zero speeds
- peterson's solution, for 2 processes
  - assumes that LOAD, STORE instructions are atomic (which isn't always true)
  - two shared variables: turn, flag[2]
  - algorithm:
    - enter a while (1) loop
    - set flag[i] = TRUE (to indicate that you want to enter your critical section)
    - set turn = j (give the other process a chance to go)
    - while (flag[j] && turn == j), do nothing
    - then, enter your critical section
    - leave it, set flag[i] = FALSE
    - pretty self-explanatory
  - proving that it satisfies mutex and progress is fairly simple, just think about it (contradiction)
    - atomic assignment ensures that processes that will fight for control and one will win
    - if i is in the critical section, flag[j]=false or turn=i
    - if j is in the critical section, flag[i]=false or turn=j
    - if both process are in the critical section: flag[i]=flag[j]=true, turn=i=j;
    - flag can only be true for one and turn can only equal one value: contradiction!!!
hardware support for synchronisation (the critical section thing)
- interrupt disabling for single-processor systems
  - allows code that is running to execute without preemption (execution critical section will not be interrupted by "signal", in c, you can register a program to listen to a specific signal alarm, when that signal/interrupt happens, program will switch control to the signal handler...signal is per process, thus not scalable)
  - not really feasible with multiple processors, since you have to send a message to all processors
  - also, this isn't scalable
- atomic hardware instructions
  - test memory word, set value (TestAndSet, what kind of capitalisation is this)
    - pass in a boolean
    - the function sets the boolean variable lock to TRUE
    - returns lock's original value
  - or, swap contents of two words in memory
    - uses a temp variable
implementations of locking
- acquire lock, execute critical section code, release lock
  - use TestAndSet, pass in the lock variable
  - while its value is true (meaning someone has it), do nothing
  - once it returns FALSE, execute critical section code
  - at the end, set lock (which is set to true in TestAndSet) to false
- can also be implemented by swapping
  - set key, lock to TRUE
  - while key == TRUE swap the lock and key
  - once lock has been set to false (by the other process), this will return false
  - so, exit the while loop, execute critical section
  - then, set lock to false
- semaphores - simpler, abstraction onto of 2 algorithm mention previously and now also use as a variable to be specified for a task you need to lock
  - integer variable
  - two operations: wait(), signal()
    - wait: while the semaphore is < 1, do nothing; then, decrement it
    - signal: just increment it
  - counting (just integer values) vs binary (basically a mutex lock)
    - counting is used when you have N resources available
    - initialise it to N (wait() = N--)
  - provides mutual exclusion:
    - initialise the semaphore to 1
    - call wait() (does nothing until we can acquire a lock)
    - execute the critical section
    - signal (basically releases a lock)
- deadlock: when two or more processes are waiting for something that will NEVER HAPPEN (basically, they are waiting for each other, and thus are stuck)
  - example: two semaphores, S and Q
  - process 1 does wait(S) and wait(Q) in that order
  - process 2 does wait(Q) and wait(S) in that order
  - if processes 1 and 2 begin at the same time, then they'll both get stuck on their second wait
- starvation: when a process is denied the resources it needs to complete (e.g., CPU time, memory, love, etc)
- priority inversion: when a lower-priority process holds a lock needed by a higher-priority process
the bounded-buffer problem, or, producer-consumer problem
- you have a producer, and a consumer, and a fixed-size queue (N buffers, each of which can hold one item)
- shared variables:
  - semaphore mutex, initialised to 1
  - semaphore full, holds the number of full buffers, initialised to 0
  - semaphore empty, holds the number of empty buffers, initialised to N
- algorithm for producers:
  - wait(empty) (if there are no empty buffers, do nothing)
  - wait(mutex) (wait until we acquire the lock)
  - add the item to the buffer
  - signal(mutex) (release the lock)
  - signal(full) (increase the number of full buffers)
- algorithm for consumers:
  - wait(full) (if there are no buffers containing things, do nothing)
  - wait(mutex) (wait until we acquire the lock)
  - remove an item from the buffer
  - signal(mutex) (release the lock)
  - signal(empty) (increase the number of empty buffers)
  - do stuff with the item that has been removed
the readers-writers problem
- there is some data shared among processes
- some can only read (readers)
- others can both read and write (writers)
- multiple readers can read at the same time, but only one writer is allowed
- shared variables:
  - the dataset
  - integer readcount, initialised to 0 (the number of readers)
  - semaphore mutex, initialised to 1 (it's a lock for updating readcount)
  - semaphore wrt, initialised to 1 (so that writing can be done initially)
- algorithm for writers:
  - wait(wrt) - can't write unless no one else is reading or writing
  - write, etc
  - signal(wrt) - release the lock
- algorithm for readers:
  - wait(mutex) - no concurrent updates to readcount
  - increment readcount by 1
  - if readcount == 1, call wait(wrt) (don't read if someone else is writing, and prevent new writers from writing)¹
  - signal(mutex) - allow other readers to join in
  - read
  - wait(mutex) - no concurrent updates to readcount
  - decrement readcount by 1
  - if readcount == 0, call signal(wrt) (if there are no more readers, allow writers to write; otherwise, keep starving them)
  - signal(mutex) - release the lock
  - pretty cool
- the version of this problem studied in class seems to be the readers-preference version
the dining philosophers problem
- let's say there are 5 bowls of rice (one for each person) and 5 individual chopsticks
- each philosopher needs two² chopsticks to eat his rice
- philosophers can alternate between thinking (not using chopsticks) and eating (using chopsticks)
- shared data:
  - semaphore chopstick[5], for protecting each chopstick
- algorithm for philosopher i:
  - wait(chopstick[i]) (wait for the left chopstick to be free, and grab it)
  - wait(chopstick[(i+1) % 5]) (wait for the right chopstick to be free, and grab it)
  - eat rice until satiated or bored
  - signal(chopstick[i]) (release the left chopstick)
  - signal(chopstick[(i+1) % 5]) (release the right chopstick)
  - think until hungry or bored
- algorithm for chopsticks:
  - just kidding, chopsticks have no free will³. and philosopher will starve to death thinking about this problem dellsystem
- problems with the previous algorithm:
  - a deadlock could occur, if all the philosophers take their own left chopsticks simultaneously, _too bad they are eating rice, dumpling will solve all problem....or eating with their hand, but I guess they are too polite to do it. _
- solutions:
  - philosphers 0, 2 and 4 pick their left (or right) chopstick first; philosophers 1 and 3 pick up their right (or left) chopstick first
  - philosophers can only acquire both chopsticks at a time (if both are available)
- this is a classical synchronisation problem, which is representative of many other concurrency-control problems

What are they

Mutual exclusion (only one process can be in its critical section at a time)

Bounded waiting (no starvation)

Progress (can't get stuck at a point where nothing is in its critical section)

What are they

2 processes, LOAD and STORE are atomic

What does this do? How can you use this method to implement locking?

Takes a boolean, sets it to true, returns the original value.

Locking: test_and_set(lock); while that returns true, do nothing; the moment it returns false, you have the lock

How can you implement locking by swapping two variables?

one variable called key, set to true. continually swap lock and key. once lock has been set to false, key will be set to false; then, we can proceed as we've acquired the lock (it's set to true at this point). at the end, set lock to false again.

Nah.

recap: deadlocks occur when there is a set of blocked processes, each holding a resource, and waiting to acquire a resource held by another process
- example: two processes, each using one disk drive in a 2-disk system, each needs another
- processes can never finish executing, and system resources are tied up at the same time, so it's a very bad situation
modelling this situation
- $m$ resource types: $R_1, R_2, \ldots, R_m$ (things like CPU cycles, memory space, I/O devices)
- each resource type has $W_i$ instances (available for use)
- a process can use a resource by requesting it, waiting until that request is granted, using the resource, then releasing it
for deadlock to arise, the following four conditions must hold simultaneously:
- mutual exclusion: only one process can use a resource at a time
- hold and wait: a process holding 1+ resources is waiting to use other resources (that are currently being used)
- no preemption: a resource can only be released by a process once it has completed its task
- circular wait: there is a set of waiting processes $\{P_0, P_1, \ldots P_n\}$, with $P_0$ waiting for a resource being used by $P_1$, $P_1$ waiting for a resource being used by something in $\{P_2, \ldots, P_n\}$, and $P_n$ is waiting for $P_0$
request-allocation graph formulation
- turn all the processes into vertices
- turn the resources into vertices as well (note that each resource can have multiple edges pointing out of it, depending on the number of available instances)
  - claim edge: dashed lined from process to a resource: process may request resource in the future
- request edge: directed edge from a process to a resource
- assignment edge: directed edge from a resource to a process
- remove the request when the request is granted (well, turn it into an assignment edge)
  - assignment edge become a claim edge once the process finish using the resource
- cycles:
  - if the graph contains no cycles, there is no deadlock
  - if the graph contains a cycle, and there is only one instance per resource type in the cycle, definitely deadlock
  - if there is a cycle and there are several instances per resource type, maybe deadlock (banker algorithm is more effective for multiple resource instance deadlock detection)
  - i guess beyond the "no cycles" one there are no hard rules?
methods of handling deadlocks (implemented by the OS)
- ensure that deadlocks are never encountered
- graceful recovery from deadlocks
- ignore the problem and pretend that they never happen lol
  - this is used by most operating systems
  - the application programmer is responsible for ensuring that deadlocks do not occur
preventing deadlocks by ensuring that not all the deadlock conditions hold:
- mutual exclusion: don't implement this for shareable resources (like read-only files)
  - of course, certain resources cannot escape this (e.g. no printing 2 documents on the same page)
- hold and wait: ensure that when a process is waiting for a resource, it isn't using any other resources
  - no wait: processes must request all the resources it needs before beginning execution (can result in starvation)
  - no hold: processes can only request new resources when not using any
  - of course, this can result in low resource utilization (less than is optimal)
- no preemption: if a process is waiting for a resource, release all of its current resources
  - keep track of which resources it lost, obviously
  - only restart the process when it can acquire all the resources it needs at once
  - applies to things where state can be easily stashed and popped (CPU registers, memory space)
- circular wait: impose a total ordering on resource types, and require that each process requests resources in order
dynamic deadlock avoidance (ensure that the system will never enter an unsafe state)
- periodically check the state of resource allocation to make sure that circular waiting cannot happen
- simplest method: have each process declare the max number of resources (a priori info needed) of each type it will need
- when a process requests a resource, system needs to check that allocating it will leave the system in a safe state (non-deadlocked)
- slightly more formal definition for safe state: you can order the processes such that the resources that any process needs can be satisfied by the free/available resources plus the resources held by all previous processes
- so if the resource that a process needs are immediately available, it just has to wait for the other processes to finish, that's it (nothing circular)
- safe state: no deadlock
- unsafe state: possibility of deadlock
- if you have a single instance per resource type: use a resource-allocation graph
  - claim edge: directed edge from a process to a resource, meaning that the process may request that resource at some point (uses a dashed line)
  - when the process actually requests the resource, change it to a request edge
  - and when the resource is actually allocated, convert to an assignment edge
  - when the resource is released, convert it back to a claim edge
  - claim edges must be drawn before a process can begin executing
  - now, if a process requests a resource, can we grant that request?
  - ONLY if converting the request edge to an assignment edge does not result in a cycle (include the dashed lines obviously... this is a bit confusing, I guess in this case, we assume that the process cannot complete the task by just using the "claimed" resource , it may also need the resource it is already allocated. we could say thus that it is unsafe and just have every high chance of deadlock)s
  - for this reason it only applies if all resource types have only one instance
- multiple instances per resource type: banker's algorithm
  - each process claims, at the start, the max number of resources it needs (of each type)
  - when a process requests a resource, it may have to wait (obviously lol)
  - when a process receives all its resources, it must release them eventually (it can be a bastard, and "yes" itself to hell)
  - shared variables:
    - n: number of processes
    - m: number of resources
    - available[m]: array listing the number of instances available for each resource at any given time
    - max[n][m]: 2D array. For each process, there is an array listing the max number of instances needed per resource type(what it claim it need)
    - allocation[n][m]: like above but the number of resource instances already allocated in each entry
    - need[n][m]: number of instances of a resource that a process still needs (relative to the current number being used), set equal to max - allocation
  - safety algorithm (for periodically checking that the system is in a safe state):
    - create an array of length m, called work; copy available over to it
    - create an array of length n, called finish; initialize entries to false
    - find a process to execute by finding i such that finish[i] == FALSE and need[i] < work (for every entry in both arrays)
      - need[i] < work is really confusing remember that work is initialized to available resource, so you are essentially comparing what amount of resource this process need and what resource are available (the later == resource that are free before you do work, and resource free after you done the work of other processes)
    - update work, add allocation[i] to it (for each entry - equivalent to releasing all held resources)
    - set finish[i] to true (indicates that the process is finished)
    - if finish[i] == TRUE for all i, then we're good
  - resource-request algorithm (to check if a request can be granted to a process i)
    - let request[i] be the request array for the process (each entry is the number of instances requested for each resource)
    - if any entry in this array exceeds the corresponding entry in need, error (cuz then it has exceeded what was supposed to be its max for some resource)
    - if any entry > corresponding entry in available, force the process to wait, since there are simply not enough resources available to service it
    - now, "pretend" to allocate requested resources to this process, by modifying the state as follows:
      - available = available - request[i] (update the number of instances available for each resource)
      - allocation[i] = allocation[i] + request[i] (update the number of instances being used by the process)
      - need[i] = need[i] - request[i] (update the number of instances the process still needs for each resource)
    - if this resulting state is safe(which we check with banker's algorithm), then we can go ahead and allocate etc
    - if it's not, the process must wait, and we can restore the old state
  - applying the banker's algorithm to a concrete example
    - not going to give the example itself because tables and lists are hard to combine
    - but the idea is: to prove that the system is in a safe state, find a sequence (ANY sequence) that satisfies the safety criteria
    - to check if a particular request can be granted, just run through the algorithms, etc
    - questions involving this are highly likely to appear on the final

-->3 types of resources : A, B, and C
     Max      Alloc      Avail          Need = (Max-Alloc)
     ABC      ABC        ABC             ABC
                         332
P0    753      010   4th  10,5,7          743 
P1    322      200   1th  743             122
P2    902      302   3th  10,4,7          600    ---> this is already safe if run banker 
P3    222      211   0th  543             011    1. if Avail > Need
P4    433      002   2th  745             431    2. then Need= Need +Alloc
                                                3. loop 1, 2 until find ordering of <P3, P1, P4,P2,P0>... more than one ordering works

--> if P0 request (1,0,2): WIP

deadlock detection
- if neither deadlock prevention nor deadlock avoidance algorithms are employed, deadlocks can, of course, result
- in that case, we need to make use of deadlock detection algorithms, and have a recovery scheme planned
- if each resource type has only one instance, we can use the following algorithm:
  - first, construct a "wait-for" graph, where the nodes are processes (and keep it updated, etc)
  - there is a directed edge from a process to a process it is waiting for (because that process is using a resource the first process needs)
  - periodically search this graph for a cycle - if there is one, there is a deadlock
  - making the corresponding wait-for graph for an arbitrary resource-allocation graph sounds like a good question for the final, so make sure you know this
- if each resource type can have several instances:
  - n = number of processes
  - m = number of resource types
  - available[m]: array, holding the number of instances available for each resource at any point in time
  - allocation[n][m]: 2D array, number of instances of each resource used by each process
  - request[n][m]: holds the current request for each process
  - detection algorithm:
    - set work = available
    - create an array of length n called finish
    - for each i, if sum(allocation[i]) = 0, set finish[i] = TRUE (if a process isn't using resources, we can ignore it)
    - find an index i such that finish[i] == FALSE and request[i] <= work (find a process that is still running, whose current request can be satisfied)
    - then, set work = work + allocation[i] and set finish[i] = true (incorporate the running of this process into our calculations)
    - if we've gone through all the indices, and if not all(finish), then we have a deadlock
    - also likely to be asked on the exam

-->3 types of resources : A, B, and C, here I already order the process from the fewest resources requested to the most resources requested
     Alloc    Requested    Work=Work+Alloc
     ABC        ABC          ABC
P0    010      000            work=000+010=010 
P2    303      000            work=010+303=313
P4    002      002            work=313 > 002, 313+002=315
P3    211      100            work=315 > 100, 315+211=526 
P1    200      202            work=536 >202,  work= 736

?

Mutual exclusion - two processes cannot use the same resource simultaneously

Hold and wait - a process using a resource is waiting to use another resource that currently being used

No preemption - resources can only be released when a process has completed

Circular wait - waiting cycle (implies hold and wait)

Implemented by the OS

Preventing: ensuring that at least one of the conditions never occurs, dynamic avoidance (banker's algorithm, etc)

Recovering: dynamic detection, then recover somehow (abort all, or some, processes; or, take away resources from some processes)

Ignoring the possibility of deadlocks

Why can't we just use the resource-allocation graph algorithm everywhere?

Doesn't apply when there is more than one instance of each resource type.

What is the optimistic assumption made in the deadlock-detection algorithm? How could this assumption be violated?

That as soon as a process' resource requests are satisfied, it will complete, and will release all its resources. It could be that it'll still take quite a while to complete, and the immediate reassignment of its resources will lead to a deadlock.

for a program to run (as a process), it must be read from disk into memory
- recall: the only storage media the CPU can access directly are main memory and registers (with the CPU cache between registers and main memory)
- accessing registers can be done within one clock cycle
- accessing main memory can take many clock cycles
each process has a separate memory space, defined by base and limit registers
- base: smallest legal physical memory address
- limit: the size of the address space
processing of a user program:
- the variables used are symbolic addresses in the source program
- the source program is then compiled/assembled to an object module
- the compiler binds the symbolic addresses to relocatable addresses ("x bytes from start of module")
- loader/linkage editor then binds the relocatable addresses to absolute addresses
- in fact, final-address-binding can happen at various stages
  - at compile time, if the memory location is known beforehand, absolute code can be generated (although if the starting location changes, code must be recompiled)
  - at load time, if relocatable code is generated by the compiler
  - at run time, if the process can be moved (in memory) during execution (needs hardware - MMU - support)
logical vs. physical address spaces
- logical address: virtual
- physical address: the one used by the memory unit (like latitude/longitude vs. street names, etc)
memory management unit (MMU)
- hardware device mapping virtual to physical addresses (dynamically)
- uses TLB
- allows user programs to deal with virtual rather than physical addresses
- makes use of a relocation register: given a virtual address, it adds the value of that register to it, then uses that as the physical address
dynamic loading
- routines are not loaded into memory until they are needed (called)
- results in better memory usage
- useful for things like error routines (large amounts of code, called infrequently)
- can be handled by the process itself - the calling routine will call a relocatable linking loader to load the desired routine in memory if it is not already in it
- no special support from the OS is needed
- however, it falls on the programmer to make use of dynamic loading in their programs
dynamic vs static linking
- static: system libraries are treated like any other object module and are combined by the loader into the binary
- dynamic: the linking happens at execution time
- advantage: more space efficient
- a code stub handles locating the library if it's in memory already, or loading it if it is not
- the stub then replaces itself with the address of the routine for the library, which is then executed
- needs support from the OS, to check if the routine is in the process' memory address (what does this mean???)
- useful for libraries

processes can be temporarily swapped to disk (known as the backing store), then brought back into memory to continue execution
roll out, roll in: lower-priority processes are swapped out in favour of higher-priority processes
the time it takes to swap something to disk is proportional to the amount of memory swapped (as the limiting factor is the transfer time)
ready queue: holds the list of ready-to-run processes which have memory images on disk

main memory is usually divided into two partitions: a "high" partition, and a "low" partition
since the interrupt vector is usually in low memory, the OS is usually placed in low memory as well
then, user processes are placed in high memory
relocation registers (base, limit) used to protect processes
if the logical address is less than the limit register, then you add the base register to it to get the physical address
otherwise you get a trap (addressing error, maybe segfault)
multiple-partition allocation
- hole: block of available memory
- holes of various sizes are scattered throughout memory
- when a process begins execution, it is allocated memory from a large-enough hole
- OS keeps info on which partitions are free and which have already been allocated
- ways of satisfying requests:
  - first-fit: allocate the first hole that is big enough
  - best-fit: allocate the smallest hole that is big enough (requires searching the entire list, unless it has been ordered by size)
  - worst-fit: allocates the largest hole that is big enough (same as above)
  - usually first-fit and best-fit use storage more effectively
  - first-fit is typically fastest
fragmentation
- external fragmentation: there is enough space in all of memory to satisfy a request, but it is not contiguous (due to processes being loaded and removed from memory, etc)
- internal fragmentation: when the amount of memory allocated is larger than that requested, so there's some space within partitions that is not being used
- external frag. can be reduced by compaction (shuffling memory contents to place all the free blocks together)
- compaction is only possible if relocation is dynamic (done at execution time)

allows the physical address space of a process to be noncontiguous
physical memory is divided into fixed-size blocks called frames (size between 2⁹ and 2²⁴ bytes per page)
virtual memory is divided into fixed-size blocks called pages
OS keeps track of all free frames
to run a program, you need as many free frames as it needs lol
then you have a page table to translate virtual to physical addresses
the virtual address consists of two parts:
- page number: used as an index into the page table, contains base address of each page in physical memory
- page offset: combined with base address, defines the physical memory address
if the page size is 2ⁿ bytes, the page offset is n bits
if there are 2^m possible virtual addresses, then the page number is m-n bits
so in virtual memory you have pages, and each page corresponds to a frame in physical memory
- that mapping is defined in the page table (so index 0 corresponds to frame 1)
- then, a thing in a page corresponds to the same location in the frame itself, etc
from virtual address to fetching the thing in memory, it goes like:
- the page table index is used to look up the frame index via the page table
- the page offset is added to the end of the frame index
- goes to that location in physical memory, fetches the relevant byte
implementation of the page table
- one scheme: kept in main memory
  - page table base register: starting address of the page table
  - page table length register: size of it
  - in this scheme, accessing anything requires two memory accesses: one to find the page table, then another to get the thing itself (which is inefficient)
- another scheme: special hardware caches to speed up lookup
  - associative memory or translation lookaside buffers (cache for the page table)
  - if the desired page is not in the TLB, then go to memory, etc
calculating the effective access time when looking up something
- let $\epsilon$ be the amount of time it takes to look up a page in the TLB
- assume it takes 1 unit of time to look up something in memory
- hit ratio for TLB: $\alpha$
- time taken if the page is in the TLB: $(1 + \epsilon)$ since you look it up in memory afterwards
- time taken if it's not: $2 + \epsilon$ since you have to look it up in the TLB anyway, then access memory to find the page table translation, then again to find the thing itself
- then effective access time is $(1 + \epsilon) \alpha + (2+\epsilon)(1-\alpha) = 2 + \epsilon - \alpha$
memory protection
- protection bit associated with each frame
- corresponding valid/invalid bit attached to each entry in the page table
- if the page is in the process' logical address space, then it's valid; otherwise, invalid
- for example, if that page is not being used by the process, then it would be marked invalid
- note that page tables are per-process ..........
shared pages
- common code can be shared in a paging scheme
- read-only (reentrant) code shared among multiple processes (maybe different users)
  - must appear in the same location in the logical address space of all processes (?)
  - i.e., the frames are shared (so the page tables for these different processes have some overlap)
  - reentrant: non-self-modifying, can never change during execution
- processes can also have their own private code and data, can appear anywhere in virtual memory etc

hierarchical paging
- since modern OSes support very large virtual address spaces (2³² or 2⁶⁴, etc), the page table itself can become very large
- solution: use a multiple-level page table scheme
- you have an outer page table, and each entry points to the location of an inner page table (not standard terminology)
- then each entry in each inner page table points to a frame in physical memory
- basically you're paging the page table itself
- example: 32-bit addresses, page size of 2¹⁰ bytes
  - page number: 22 bits, page offset: 10 bits
  - then, the page number has a 12-bit page number page number (lol) and a 10-bit page number page offset
  - the 12-bit page number page number is used for the outer page table, then the 10-bit page number page offset is used for the inner page table
- of course, you can also have three-level paging schemes, etc
- example: 64-bit addresses, page size still 2¹⁰
  - if 2 levels: 12 bit offset, 10 bit inner page, 42 bit outer page
  - if 3 levels: 12 bit offset, 10 bit inner page, 10 bit middle page, 32 bit outer page
hashed page tables
- common for > 32-bit address spaces
- the page number is hashed; collisions are handled by using buckets
- frame found by hashing it, then searching along the bucket chain
inverted page tables
- usually, each process has one page table, which has one entry for each page the process is using
- con: lots of memory used just to store page tables
- solution: one entry for each frame of memory
- each entry contains virtual address of page, and information about the owning process
- so there's only one page table needed in the system, and only one entry per page (reduces duplication, so, less memory needed overall)
- however, when a page reference occurs, you need to search through this larger table, which would be slower (since can't index it directly)
  - the inverted page table is sorted by physical address
  - go through entries one by one, find the physical address matching the virtual address (also the process ID)
  - can use a hash table to limit the search a bit. but each access to the hash table would add a memory reference
- also, harder to implement shared memory pages
  - since in shared memory, multiple virtual addresses are mapped to one physical address
  - but in this scheme, there is only one virtual page entry for each physical page

memory-management scheme that corresponds to a user's view of memory
collection of variable-sized segments (not ordered)
program: collection of segments
segment: logical unit, like an array, method, function, program, section of variables, etc
just a way of grouping together things logically (even though they may not be grouped together physically)
a logical address consists of a 2-tuple: segment number, offset
segment table: maps the above logical address to physical addresses
- each entry (one per segment) has a base and a limit
- hardware view:
  - segment number is translated using the segment table, to get the limit and base for this segment
  - the offset is compared with the limit; if it exceeds it, we get a trap
  - then, the base is added to the offset, and used as the physical address

What are the two storage media that the CPU can access directly, and how do their access times compare?

Main memory, and registers. Accessing registers can be done in less than 1 clock cycle, whereas accessing main memory can take multiple.

At what stages can final address binding happen?

At compile time, to generate absolute code (code must be recompiled if starting location changes - is this ever used?)

At load time, if the compiler has generated relocatable code

At run time, if the process can be moved in memory during execution (requires MMU support)

Wtf is an MMU

Memory management unit. Hardware device, translates virtual addresses to physical addresses so that programmers don't have to deal with physical addresses. Uses a TLB, etc.

What is the difference between dynamic loading and linking? What are the advantages of both compared to their static counterparts?

Dynamic loading: parts of a process that are not needed right away are not brought into memory until they are called. Useful for things like error handling routines, which are typically large blocks of code that get called infrequently. Results in a smaller memory footprint. It falls upon the programmer to make use of dynamic loading in their programs by calling a "relocatable linking loader" that will either locate a part in memory (if it is there) or else bring it into memory.

Dynamic linking: system libraries and other commonly-used code are linked at execution time, with the programmer making use of a "code stub" that locates the library in memory and replaces itself (during execution time) with the address of that routine. Needs support from the OS, to check that the desired routine is in the process' memory space. Also results in a smaller memory footprint.

Define this.

A large storage device, commonly a disk, to which things in memory can be swapped.

Main memory is usually divided into two partitions. What are they called and what goes into each?

High: user processes. Low: interrupt vector, OS.

Ways of satisfying allocation requests? Which is fastest?

First-fit: first hole that is big enough. Fastest if the list of holes is not ordered by size.

Best-fit: smallest hole that is big enough

Worst fit: largest hole that is big enough (why would even do this??)

Difference between internal, external

External fragmentation: when you have small holes scattered throughout memory, and you can't use them because they're just too small individually. For example, there is a hole of size 10, and three others of size 4 (all non-contiguous), and a process comes along requesting a hole of size 6, which is granted. Then you're just left with (at best) 4 holes of size 4. If a process comes along needing a hole of size 16, well, it can't be given because the holes are not contiguous

Internal fragmentation: when you have leftover space (not being used by anything) within the partitions being used, due to the way blocks are allocated. For instance, if a process requests 15 bytes, but it's given 16 because it has to be a power of 2 (etc).

What is it, what is a requirement for this to be possible, when can it be done

Compaction is a way to reduce external fragmentation, and consists of shuffling the contents of memory so as to place all the holes together. This is done at execution time and thus is only possible if relocation is dynamic.

Difference?

Pages: used in the logical (virtual) view of memory. Frames: physical view. One-to-one correspondence.

Explain what the bits of a virtual address mean if a virtual address is 32 bits, and the page size is 16 kilobytes.

16 KB = 2⁴ * 2¹⁰ so 2¹⁴ bytes. You need 2¹⁴ bits to indicate the page offset for any byte on a page. The remaining 18 bits can be used for the page index, and so there needs be 2¹⁸ pages in order to store 2³² bytes.

How is the page table stored?

In main memory, with base and limit registers. To speed up lookup, a special hardware cache (TLB) is used to store part of the page table.

Let's say the hit ratio for the TLB is 0.9, and it takes 100 units of time to look something up in memory. To look something up in the TLB takes 1 unit of time. What's the EAT?

101 for anything in the TLB, so 101 * 0.9. Then, 201 for anything not in the TLB, since you have to look up the page table in memory as well, so 201 * 0.1. Total: 90.9 + 20.1 = 111.

What is? Use?

Non-self modifying, or read-only, code. Never changes during its execution. Can be shared among processes.

Why do we even need pages in the first place

To allow memory usage to be non-contiguous

What are the different structures, and how do they work

Hierarchical paging: paging the page table.

Hashed page tables: hash the page number, then handle collisions using a bucket chain.

Inverted page tables: one entry per frame (not per-process), sorted by physical address. Less memory used, but slower, and harder to implement sharing.

Taken from stack overflow (actual source: some exam):

A computer has a 64-bit virtual address space and 2048-byte pages. A page table entry takes 4 bytes. A multi-level page table is used because each table must be contained within a page. How many levels are required?

2048 is 2¹¹, so each table can hold 2⁹ entries. Since 11 bits are required for the page offset, 53 bits remain to encode the entry for each page level. 53/9 is 6 (rounded up), so we need 6 levels.

Another calculation question:

32-bit virtual addresses, 4 KB pages, 2 levels of paging. What do the bits in an address mean?

4KB = 2¹² bytes in each page. So, 12 bits required for the page offset. Apparently the other two are both 10 bits each, though I don't know why (source).

What are they

Logical addresses (consisting of a segment number and an offset) are mapped to physical addresses

N/A

background
- virtual memory allows for the separation of logical (user) memory from physical memory
  - the logical view consists of: a stack that grows downwards, a heap that grows upwards, a data section, and a code section (with shared libraries in the middle between the heap and the stack)
- for programs, this means that not everything needs to be in memory for execution to begin
- also, the logical address space can be much larger than physical address space
- and, address spaces can be shared by different processes
- process creation is more efficient
- can be implemented via demand paging, and demand segmentation
demand paging
- a page is brought into memory only when it is needed
- less unnecessary I/O and less memory needed
- a page is determined to be "needed" when there is a reference to it
  - if a reference is invalid, abort
  - if a reference is to a page that is not in memory, it will be brought into memory
- to execute a process, we swap the pages for it into memory (lazily)
- pager: swapper that deals with pages (does this really need its own term)
- valid/invalid bits for the page table
  - like those used introduced in the memory protection section, but serving another purpose as well
  - valid: legal and in memory
  - invalid: either illegal or not in memory
  - all entries initially set to invalid
  - if we ever need to lookup an invalid entry, we get a page fault, so the OS needs to:
    1. look at another table (one stored within the PCB) to decide if it was an invalid memory reference or just a swapped-to-disk page
    2. find an empty frame from the free frame list
    3. read the page from disk and swaps it into the frame
    4. modify the table in the PCB
    5. update the validation bit and the entry in the page table
    6. restart the instruction that caused the page fault
- effective access time:
  - let $p$ be the page fault rate
  - let $t$ be the time it takes to handle a page fault
  - let $m$ be the time it takes to access memory (to read a page, say)
  - EAT: $(1-p) \cdot m + p \cdot t$
- the time it takes to handle a page fault is determined by:
  - time to service the interrupt
    - save user registers, process state
    - check if the interrupt is a page fault
    - check if the page reference is legal
    - if so, find the location of the page on disk
  - time to read in the page to a free frame (usually slowest)
    - influenced by disk latency, seek time, queueing time on the device
  - then, time to restart the instruction that was interrupted (why is this here)
- example for calculating EAT:
  - m = 200 nanoseconds = 0.0002 milliseconds
  - t = 8 milliseconds
  - p = 0.001
  - EAT = $(1-0.001) \cdot 0.0002 + 0.001 \cdot 8 = 0.0001998 + 0.008 \approx 0.0082$ milliseconds so 8.2 microseconds or 8200 nanoseconds
  - this shows that even if page faults are relatively rare, they can still introduce huge slowdowns (40x slower in this case)
  - obviously, we want to keep page-fault-rate low
  - if we want to keep it below, say, 5%, then we need for the EAT to be less than 210
  - the calculation's not hard, just make $p$ the variable
copy-on-write
- a benefit of virtual memory realised during process creation
- normally, the fork() system call duplicates the parent's pages for the child
- however, many ungrateful children invoke exec() immediately after birth, making this copying unnecessary
- copy-on-write allows the parent and child to initially share the parent's pages in memory
- only if either process modifies a shared page is that page copied
- results in more efficient process creation (so that fewer pages need to be allocated to child processes)
page replacement
- what happens when we need to swap a new page into memory but there are no free frames????????
- in that case, we need some sort of page replacement policy to get rid of pages we don't need
- such a policy should minimise the number of page faults (obviously)
- basic algorithm:
  - find location of desired page on disk
  - find a free frame, if one exists
  - if no free frames exist, find a victim frame, write it to disk (if dirty), and change the page and frame tables accordingly
  - bring the desired page into the newly freed frame, update tables
- makes use of a dirty bit in the page table so that only modified pages are written back to disk when they are evicted from memory
- evaluating different page replacement policies
  - FIFO: remove the least-recently-added pages first
  - belady's anomaly: for some page replacement policies, more frames can result in more page faults (which seems paradoxical)
  - OPT/MIN: theoretical algorithm (lol) that has the lowest page-fault rate and will never suffer from belady's anomaly
    - you evict the page that will not be used for the longest period of time
    - obviously this is impossible to implement in practice unless you know the future
    - however, it's useful as a comparison point for other page replacement policies ("how does this algorithm behave compared to OPT")
  - LRU: use recent history to simulate OPT
    - evict the page that was least recently used
    - implementation: every page entry has a "counter" (really a timestamp for the last use)
    - when we need to evict one, we just replace the page with the smallest timestamp
    - this has the added overhead of needing to search the table to find the LRU page each time, and we also need to write the timestamp to memory during every memory access
    - still, it's pretty efficient as it tends to reduce the number of page faults compared to most other algorithms
allocation of frames
- how do we allocate the fixed amount of free memory among the various processes running on a system?
- two methods: fixed, priority
- fixed allocation - doesn't take priorities into account; 2 methods
  - equal allocation:
    - all animals are equal
    - each process gets the same number of frames
  - proportional allocation:
    - some are more equal than others
    - frames allocated according to the size (virtual memory) of a process
    - how do they know that???
    - for example, if there are 2 processes, one of size 5, and one of size 10, and there are 30 frames, the first would get 10 frames, the second would get 20
- priority allocation - takes priorities into account
  - high-priority processes are given more memory to speed their execution
  - uses a proportional allocation scheme using priority rather than size (or possibly both priority and size)
thrashing
- if a process has too few frames, its page fault rate will be very high
- result: low CPU usage, so the OS thinks it needs to increase the degree of multiprogramming, so it adds more processes, then it all goes to hell
- then the OS will spend more time paging than executing processes (i.e., thrashing)
- to prevent this, we must provide a process with as many frames as it needs
- how do we know this magic number?
- working-set strategy: looks at how many frames a process is actually using
  - purpose: to prevent thrashing while keeping the degree of multiprogramming as high as possible
  - makes use of the locality model of process execution
    - locality: set of pages commonly used together
    - for instance, when a function is called, a new locality is defined
    - thrashing occurs when the size of the locality is greater than the total memory size
  - in the working-set model, we have a parameter $\Delta$ (working-set window) which is a fixed number of page references
  - working-set size of a process: number of pages referenced in the most recent $\Delta$
  - need an optimal size of $\Delta$ so that we get exactly one locality (not less, not more), or at least, estimate it better
  - the total number of frames we need is the sum of all the working set sizes (for all the processes)
  - if this number > total number of available frames, then we'll have thrashing
  - so, we need to suspend a process
  - if we have extra frames, then we can start a new process
  - for example, if the last few pages referenced were: 12323434343334
    - then, if $\Delta = 10$, we look at the last 10 page references --> pages 3 and 4
  - not entirely sure how this is supposed to work

What is this? What do valid and invalid bits mean for the page table in this scheme?

A page is only brought into memory when there is a reference to it (lazy loading). Valid = page is in memory. Invalid = page is illegal or not in memory.

What are page faults, and what happens when they are encountered?

When we hit a reference to a page marked invalid in the page table (so either illegal or just not in memory). The OS needs to look at another table in the PCB to check if it's illegal, and, if not, finds an empty frame using the free frame list, reads the page from disk into the frame, updates all the tables, then restarts the instruction.

Accessing memory takes 0.0005 (ignore the unit). The page fault rate is 0.01, and it takes 2.0 to handle a page fault. What's the EAT?

$(0.0005 \cdot 0.99) + (\cdot 2.0 \cdot 0.01) = 0.020495$ which is a ~40x slowdown

Same numbers as above, but we want to find the highest page fault rate that will result in a 10x slowdown

$0.0005 \cdot (1-p) + 2.0p = 0.0005 + 1.9995p = 0.005$, so $1.9995p = 0.0045$ and $p \approx 0.0023$

What is it? Benefits?

During process creation (with fork), instead of copying all the parent pages over for the child, let the child share the parent's pages and only copy when one process writes to a page. More efficient process creation and less memory wasted.

List them

FIFO: replaces the first one in

OPT: theoretical, replaces the one that will be used latest

LRU: replaces the least recently used one (smallest timestamp). overhead: searching the entire table, and updating the page table whenever you need to access a page

What is Belady's anomaly? Give a page replacement algorithm that does not suffer from it.

When increasing the number of frames increases the number of page faults for a page replacement policy. OPT does not (though LRU tries).

Methods of allocating frames?

Fixed allocation, equal.

Fixed allocation, proportional to size of memory used by a process.

Priority allocation, based on priority (and possibly size).

What is thrashing

OS is constantly paging rather than doing useful work. Page fault rate is high, OS thinks it needs to add more processes to improve CPU utilisation, etc.

How does this work

Looks at the number of frames a process is using to try and prevent thrashing while having as many processes running as possible. We look at the number of different pages used by a process per locality. Make sure the sum of working set sizes for all processes is smaller than the number of pages available in memory, etc.

N/A

attributes (kept in dir structure, which is on disk)
- name
- system identifier
- type
- location
- size
- protection (permissions)
- time, date, user identification
operations
- create: allocate space in system, make new entry in directory
- write: given file name and info to be written, system searches for it, keeps a write pointer
- read: ^ but read pointer
- reposition in file: seek, pointer value changes
- delete: find file, release space, delete dir entry
- truncate: delete contents, keep attributes
open() system call avoids constant searching for dir entry (saves it in memory; close() frees)
- takes file name, copies dir entry into open file table, returns pointer
- per-process table (pointer, rights), system-wide (location, access dates, file size)
- to manage open files, need pointer, open count, location, access rights
access methods
- sequential
- direct
- index
- can simulate sequential on direct
- direct on sequential is inefficient
storing files on disks
- partitions
- raw or formatted
- RAID protection
- volume = entity with filesystem
directory structure
- collection of nodes pointing to files
- operations
  - search for file
  - create
  - delete
  - list
  - rename
  - traverse
- single-level directory for all users: dumb
- two-level, one for each user: bad for cooperation
- tree-structured: each file has unique path name
  - acyclic graph
  - hard links?
  - multiple abs path names
  - reference list: delete files when no references to it exist
  - self-reference?
  - check that there are no cycles
mounting
sharing, etc, nothing special
failure
- directory corruption, disk-controller failure, etc
types of access (for right management):
- read
- write
- execute
- append
- delete
- list

What are they?

Name
System identifier
Type
Location on disk
Size
Permissions
Time, date, user identification

Purpose? What does close do?

To cache file info in memory, to avoid constantly searching for the dir entry. Close frees that memory. It takes the file name, copies the the dir entry into the open file table, and returns the pointer.

What's stored in the per-process table? System-wide table?

Per-process: pointer (to file contents, in memory), access rights

System-wide: location on disk (?), access dates, file size

N/A

Structure
- Organised into layers somehow
- File system resides on disk, provides efficient and convenient access to disk
- File control block: storage structure, contains info about file (owner, permissions, location on disk)
- Device driver controls physical device
Implementation
- Boot control block: contains info needed by system to boot OS from volume
- Volume control block (per volume): contains details for that partition (number of blocks, block size, etc)
- File control block:
  - permissions
  - file create, access, write dates
  - file owner, group
  - file size
  - pointers to data blocks
Directories
- linear list of file names is very inefficient
- instead, we use a hash table
- linear list to store the directory entries, hash data structure for accessing pointers
- pros: directory search time decreases
- cons: collisions, etc
Allocation methods
- contiguous allocation: each file occupies a set of consecutive blocks on disk
  - dir entry indicates address of starting block, number of blocks
  - pros: simple, sequential access is easy, direct access isn't too hard
  - cons:
    - wasteful of space (can result in external fragmentation)
    - files cannot grow in size after they are first created (like arrays in C)
- linked allocation: file is linked list of disk blocks
  - blocks can be stored anywhere
  - directory contains pointer to first, last blocks of file
  - each block contains pointer to next block
  - pros: no external fragmentation, because any free block can be used; files can grow; simple
  - cons: random access is inefficient, lots of space overhead for pointers
  - FAT (file allocation table): used by MS-DOS
    - variation on linked allocation
    - dir entry contains block number of first block in file
    - a section of disk at the beginning of each volume is reserved for a table
    - that table contains the next block number for each block in the file
    - unused blocks indicated by value of 0
    - last block contains EOF value
    - pros: random access is fast
- indexed allocation
  - all pointers stored in index block (one for each file)
  - _i_th entry in the index block points to _i_th block of file
  - directory contains address of index block
  - pros:
    - direct access
  - cons:
    - pointer overhead of index block (usually greater than the pointer overhead for linked allocation)
    - if most files are small, then linked allocation wins - only one pointer per block for linked, but an entire index block for indexed
  - optimal size for index blocks? if small, less overhead, but may not be able to hold enough pointers
  - linked scheme: link together several index blocks
    - one block contains n file block addresses
    - large files may need several index blocks
    - multi-level index: one index block points to other blocks, etc
    - example: 4096-byte blocks, each pointer 4 bytes, 2-level index
    - store 1024 = 2¹⁰ pointers per index block
    - 2 levels of indexes, so 1024² = 10²⁰ data blocks
    - so 10²⁰ * 4096 = 10²⁰ * 10¹² = 10³² = 4 * 10³⁰ = 4 GB
  - combined scheme: used in UFS (UNIX file system)
    - keep first 15 pointers of index block in file's inode (FCB for UNIX)
    - first 12 pointers: directly to blocks (so small files don't need separate index blocks)
    - the 13th: points to index block containing addresses of file blocks
    - 14th points to double indirect block (pointer to index block containing pointers to file block, what is this i don't even)
    - 15th: triple indirect block
Free space management
- disk space is limited, need to reuse space from deleted files
- to keep track of free disk space, system maintains free space list for free blocks
- usually implemented as a list (bit vector, length n where n is the number of blocks)
  - if 1, free; if 0, occupied
  - block number calculations are supported by the hardware somehow
    - to find the first free block number: number of bits per word * number of 0-value words + offset of first 1 bit, what
  - this bit map requires extra space
  - if block size = 2¹² bytes, and disk size = 2³⁰ bytes (1 GB), then you need 2¹⁸ bytes for the bit map (so 32 KB)
  - but, it's easy to get contiguous blocks
- another solution: linked list (free list)
  - link together all the free disk blocks
  - pointer to the first free block in a special location on disk (also cached in memory)
  - harder to get contiguous space
  - but, less space is wasted
- grouping: modification of the linked list approach
  - first free block stores the addresses of n free blocks, and then one other block which is not actually a free block but instead contains address of another n free blocks
  - faster to find a large number of free blocks using this method
Recovery
- files, directories kept in main memory (for speed) but also disk (for consistency)
- system failure/crash can result in data loss or inconsistency
- consistency checking: compares data in dir structure with data blocks on disk, etc
- fsck for Unix, chkdsk for windows
- journaling (like ext3/4 for linux)
  - each update to file system recorded as transaction
  - same techniques used by databases to guarantee FS consistency
NFS
- Sun Network File System
- implementation/specification of software system for accessing remote files across LANs/WANs
- part of Solaris, SunOS operating systems
- Ethernet: family of computer networking technologies for LAN, part of IEEE standard
- independent machines can access shared file systems transparently (i.e. user doesn't need to see the details)
- remote directory mounted over a local file system directory
- the mounting operation isn't "transparent", though
- cascading mount: allowed in some NFS implementations (remote file systems mounted on a remote file system can be accessed, etc)

What's in a file control block

Permissions
Create, last accessed, last modified dates
File owner, group
File size
Pointers to data blocks

How

Linear list (like an array? linked list?) to store the dir entries, hash data for accessing pointers to files

What are they, pros and cons of each

Contiguous, linked allocation, indexed allocation.

Contiguous: consecutive blocks. wasteful of space (results in external fragmentation), files cannot grow in size.

Linked: Linked list, each thing has some content and pointer to next thing. No external fragmentation, and files can grow, but random access is inefficient and there's lots of space overhead for the pointers.

Indexed: pointers stored in index block (one for each file), basically an array. Dir entry contains address of index block. Direct access is fast, pointer overhead is greater than for linked if files are small

Given x-byte blocks, each pointer = y bytes, 2-level index. Can store x / y pointers per index block. 2 levels of indexes, so (x/y)² data blocks. So x²/y² * x = x³/y³ bytes that can be stored total

Describe the different solutions

Bit vector: length n, where n is the number of blocks. 1 if free, 0 if occupied. To find the first free block number: number of bits per word * number of 0-value words + offset of first 1-bit block. If block size is x, and disk size is y, you need y/x bytes for the bit map. Easy to get contiguous space.

Linked list: each element is a free disk block, pointer to first block from special location in disk and memory. Harder to get contiguous space but less is wasted.

Grouping: like linked list. First free block stores addresses of n free blocks, and then a pointer to the next thing like this. Faster to find a large number of free blocks.

What is it

Like transactions with databases. For guaranteeing consistency.

What is it

NFS, when you mount a remote file system somewhere on a machine, then that is mounted by another machine

Can blocks be partially written to? That is, can part of one block be used for something, with the other part being used for something else?

No. Even if only one bit in the block is actually written to, the entire block is considered used. (I couldn't find the right place for this in the notes above.)

N/A

Note that this check actually does prevent concurrent read and write operations, not just for the first reader. Here's why. Let's say someone is writing, and along comes reader 1 who wants to read. Well, since readcount will be 1 at this point, reader 1 will have to wait until the writer (wait(wrt)), which is what we want. What happens if reader 2 comes along, before the writer has finished writing? Well, since mutex is still 0 (as we haven't reached the signal(mutext) line in the thread for reader 1), then reader 2 will be stopped on the first line (wait(mutex)). Only when the writer has finished writing will reader 1 be able to proceed, followed shortly by reader 2.
On the other hand, if someone is reading the data and a writer comes along, the writer won't be able to acquire a lock on wrt because the first reader has already taken it. Only when all the readers are done reading will the writer be able to write. How much wood could a woodchuck chuck if a woodchuck could chuck wood?
We can see immediately that this is indeed a "readers-preference" algorithm, for as long as there is a never-ending stream of readers, writers are starved. Which sounds almost paradoxical but it really does happen. ↩
Have you tried eating rice with just one chopstick? It's really hard. ↩
Do philosophers? Have some rice and think about it.⁴ ↩
At least I make myself laugh ↩
The textbook definition never really made sense to me, but it seems that this is only relevant for "interactive" processes. Not completely sure. I suppose one could just memorise the textbook definition and regurgitate it when asked, though that is of course far from ideal. ↩

Final review

1Chapter 1: Introduction¶

1.1Sample questions¶

1.1.1Components of a computer system¶

1.1.2Bootstrap programs¶

1.1.3Monolithic kernels and microkernels¶

1.1.4Computer system organisation¶

1.1.5The interrupt model¶

1.1.6Interrupt timelines¶

1.1.7Traps¶

1.1.8Device status tables¶

1.1.9Direct memory access¶

1.1.10Storage structure hierarchy¶

1.1.11Multiprocessor systems¶

1.1.12Multicore systems¶

1.1.13Timesharing¶

1.1.14Modes¶

1.1.15Processes¶

1.2Answers to textbook exercises¶

1.2.1Question 1.10¶

1.2.2Question 1.15¶

2Chapter 2: Operating-system structures¶

2.1Sample questions¶

2.1.1Parameter-passing¶

2.1.2Microkernels¶

2.1.3Virtual machines¶

2.1.4Paravirtualisation¶

2.1.5Bootloaders¶

2.2Answers to textbook exercises¶

2.2.1Question 2.5¶

2.2.2Question 2.6¶

2.2.3Question 2.9¶

2.2.4Question 2.14¶

3Chapter 3: Processes¶

3.1Sample questions¶

3.1.1Processes in memory¶

3.1.2Process states¶

3.1.3Process control blocks¶

3.1.4Process scheduling queues¶

3.1.5Schedulers¶

3.1.6I/O and CPU bound processes¶

3.1.7Context switching¶

3.1.8Forking and execing¶

3.1.9Abortion¶

3.1.10Inter-process communication¶

3.1.11Producer-consumer problem¶

3.1.12Direct communication¶

3.1.13Indirect communication¶

3.1.14Round-robin communication¶

3.1.15Message queues¶

3.1.16IPC in various operating systems¶

3.1.17Client-server communication¶

3.1.18Remote procedure calls¶

3.2Answers to textbook exercises¶

3.2.1Question 3.5¶

4Chapter 4: Threads¶

4.1Sample questions¶

4.1.1Things associated with threads¶

4.1.2Benefits of threading¶

4.1.3Multithreading models¶

4.1.4Thread cancellation¶

4.1.5Thread pools¶

4.2Answers to textbook exercises¶

4.2.1Question 4.4¶

5Chapter 5: CPU scheduling¶

5.1Sample questions¶

5.1.1Short-term scheduling¶

5.1.2Scheduling algorithm factors¶

5.2Answers to textbook exercises¶

5.2.1Question 5.5¶

5.2.2Question 5.8¶

5.2.3Question 5.9¶

5.2.4Question 5.10¶

6Chapter 6: Process synchronisation¶

6.1Sample questions¶

6.1.1Requirements for the critical-section problem¶

6.1.2Assumptions for Peterson's solution¶

6.1.3Test and set¶

6.1.4Swapping implementation of locking¶

6.2Answers to textbook exercises¶