operating system

tags: software hardware system

Chapter 1: Computer System

Structure

One or more CPUs, device controllers connect through common bus providing access to shared memory

Process Management
- Creating and deleting both user and system processes
- Suspending and resuming processes
- Providing mechanisms for process synchronization
- Providing mechanisms for process communication
- Providing mechanisms for deadlock handlin
Memory Management
- Von Neumann architecture
  - To execute a program, all (or part) of the instructions must be in memory
  - All (or part) of the data that is needed by the program must be in memory
- Allocating and deallocating memory space as needed
- Keeping track of which parts of memory are currently being used and by whom
- Deciding which processes (or parts thereof) and data to move into and out of memory
file system management
- Abstracts physical properties to logical storage unit - file
- Access control on most systems to determine who can access what
Mass-Storage Management
- mounting and unmounting
- fire-space management
- storage allocation
- disk scheduling
- partitioning
- protection
caching management
- Faster storage (cache)
- mportant principle, performed at many levels in a computer (in hardware, operating system, software)
I/O Subsystem
- buffering(storing data temporarily while it is being transferred)
- caching(storing part of data in faster storage for performance)
- spooling

operation

I/O is from the device to local buffer of controller
CPU moves data from/to main memory to/from local buffers
Device controller informs CPU that it has finished its operation by causing an interrupt

interrupt

software-generated interrupt :execption
Modern OS is interrupt-driven
Interrupt architecture must save the address of the interrupted instruction

Interrupt Handling

The OS preserves the state of the CPU by storing the registers and the program counter
type of interrupt
- polling
- vectored

I/O

handling I/O

Synchronous: After I/O starts, control returns to user program only upon I/O completion
- wait instruction idles the cpu until the next interrupt
- wait loop
Asynchronous: After I/O starts, control returns to user program without waiting for I/O completion
- system call:request to the OS to allow user to wait for I/O completion

storage structure

main memory
- cpu can access directly
- Dynamic Random-access Memory (DRAM)
- Typically volatile
HDD
Non-volatile memory (NVM)

Direct Memory Access(DMA)

Used for high-speed I/O devices able to transmit information at close to memory speeds
Device controller transfers blocks of data from buffer storage directly to main memory without CPU intervention
Only one interrupt is generated per block, rather than one interrupt per byte

Symmetric Multiprocessing Architecture

Dual-Core Design	Non-Uniform Memory Access System

Virtualization

have different kernel

cloud computing

Software as a Service (SaaS)
- one or more applications available via the Internet (i.e., word processor)
Platform as a Service (PaaS)
- software stack ready for application use via the Internet (i.e., a database server)
Infrastructure as a Service (IaaS)
- servers or storage available over Internet (i.e., storage available for backup use)

Kernel Data Structures

Chapter 2: Operating-System Service

System Calls

Programming interface to the services provided by the OS
Typically written in a high-level language (C or C++)
Mostly accessed by programs via a high-level Application Programming Interface (API) rather than direct system call
System Call Parameter Passing
- pushed, onto the stack by the program and popped off the stack by the OS

Types of System Calls

Process control
- create process, terminate process
- end, abort
- load, execute
- get process attributes, set process attributes
- wait for time
- wait event, signal event
- allocate and free memory
- Dump memory if error
- Debugger for determining bugs, single step execution
- Locks for managing access to shared data between
File management
- create file, delete file
- open, close file
- read, write, reposition
- get and set file attributes
Device management
- request device, release device
- read, write, reposition
- get device attributes, set device attributes
- logically attach or detach devices processes
Information maintenance
- get time or date, set time or date
- get system data, set system data
- get and set process, file, or device attributes
Communications
- create, delete communication connection
- send, receive messages if message passing model to host name or process name
  - From client to server
- Shared-memory model create and gain access to memory regions
- transfer status information
- attach and detach remote devices

program stack

Linker and Loader

Source code compiled into object files designed to be loaded into any physical memory location – relocatable object file
Linker combines these into single binary executable file
- Also brings in libraries
Modern general purpose systems don’t link libraries into executables
- Rather, dynamically linked libraries (in Windows, DLLs) are loaded as needed, shared by all that use the same version of that same library (loaded once

Operating System Structure

Simple structure
Monolithic Structure More
Microkernel
Layered
Hybrid

Traditional UNIX System Structure

UNIX:
- limited by hardware functionality, the original UNIX OS had limited structuring
- Consists of everything below the system-call interface and above the physical hardware
- Provides the file system, CPU scheduling, memory management, and other OS functions; a large number of functions for one level

Linux System Structure

Monolithic plus modular design

Microkernels

Moves as much from the kernel into user space
Mach is an example of microkernel
- Mac OS X kernel (Darwin) partly based on Mach
Benefits:
- Easier to extend a microkernel
- Easier to port the OS to new architectures
- More reliable (less code is running in kernel mode)
- More secure
Detriments:
- Performance overhead of user space to kernel space communication

Layered Approach

The OS is divided into a number of layers (levels), each built on top of lower layers
- The bottom layer (layer 0), is the hardware
- the highest (layer N) is the user interface
With modularity, layers are selected such that each uses functions (operations) and services of only lower- level layers

hybrid systems

Apple Mac OS X hybrid, layered, Aqua UI plus Cocoa programming environment

macOS iOS	darwin	android

System Boot

When power initialized on system, execution starts at a fixed memory location
Small piece of code
- bootstrap loader, BIOS, stored in ROM or EEPROM locates the kernel, loads it into memory, and starts it
Modern systems replace BIOS with Unified Extensible Firmware Interface (UEFI)
Common bootstrap loader, GRUB

tracing

strace – trace system calls invoked by a process
gdb – source-level debugger
perf – collection of Linux performance tools
tcpdump – collects network packets

Chapter 3: Processes

The program code, also called text section
Current activity including program counter, processor registers
Stack containing temporary data
- Function parameters, return addresses, local variables
Data section containing global variables
Heap containing memory dynamically allocated during run time

process state

new
running
waiting
ready:the process is waiting to be assigned to a processor
terminated

Process Scheduling

Process Control Block (PCB) or task control block)

scheduling

Goal – Maximize CPU use, quickly switch
processes onto CPU core
- Maintains scheduling queues of processes
- ready queue
- wait queue

context switch

context-switch time is pure overhead; the system does no useful work while switching
- The more complex the OS and the PCB  the longer the context switch
Time dependent on hardware support
- Some hardware provides multiple sets of registers per CPU  multiple contexts loaded at once

Operations on Processes

Inter Process Communication(IPC)

shared memory
message passing

IPC in Shared-Memory Systems

An area of memory shared among the processes that wish to communicate
The communication is under the control of the user processes not the OS

IPC in Message-Passing Systems

Blocking is considered synchronous
Non-blocking is considered asynchronous

Ordinary pipes

unidirectional(single direction)
cannot be accessed from outside the process that created it.
- Typically, a parent process creates a pipe and uses it to communicate with a child process that it created

named pipes

Communication is bidirectional
No parent-child relationship is necessary between the communicating processes

Client-Server Systems

sockets	Remote Procedure Calls (RPC)

Chapter 4: Threads & Concurrency

Concurrency vs. Parallelism

Multicore Programming

Data parallelism
- different data, same operation on each data
Task parallelism
- different operation, same data

Amdahl’s Law

$P = parallel portion speed up = \frac{1}{( 1 - P ) + \frac{P}{N}}$

Multithreading Models

Many-to-One
- One thread blocking causes all to block
- example
  - solaris green threads
  - GUN portable threads
One-to-One
- More concurrency than many-to-one
- example
  - windows
  - linux
Many-to-Many
- Windows with the ThreadFiber package
two-level model
- mix Many-to-Many and One-To-One

Many-to-One	ono-to-one	Many-to-Many	two-level model

Implicit threading

Thread Pools
- Create a number of threads in a pool where they await work
Fork-Join Parallelism
OpenMP
Grand Central Dispatch
- dispatch queues
- macOS,iOS

Chapter 5: CPU Scheduling

CPU scheduler

CPU utilization
- keep the CPU as busy as possible
Throughput
- of processes that complete their execution per time unit
Turnaround time
- amount of time to execute a particular process
- turnaround time = completion time – arrival time
Waiting time
- amount of time a process has been waiting in the ready queue
- waiting time = turnaround time – burst time
Response time
- amount of time it takes from when a request was submitted until the first response is produce
- response time = start time – arrival time

CPU scheduling decisions may take place when a process:

Switches from running to waiting state
Switches from running to ready state
Switches from waiting to ready
Terminates

Preemptive

preemptive
- can result in race conditions
- linux,windows,MacOS
nonpreemptive
- only under circumstances 1 and 4

Dispatcher

witching context
Switching to user mode
Jumping to the proper location in the user program to restart that program

Dispatch latency =time it take to stop one process and start another running

Scheduling Algorithm

Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time

Determining Length of Next CPU Burst

exponential averaging $t_{n} = CPU burst time τ_{n} = predict CPU burst time τ_{0} τ_{n + 1} = t_{0} = α t_{n} + (1 - α) τ_{n}$

First- Come, First-Served(FCFS) Scheduling

$Waiting time P_{1} = 0, P_{2} = 24, P_{3} = 27 Average waiting time = (0 + 24 + 27) /3 = 17$

Convoy effect short process behind long process
- Consider one CPU-bound and many I/O-bound processes

Shortest-Job-First(SJF) Scheduling

minimum average waiting time for a given set of processes

shortest-remaining-time-first(Preemptive SJF)

process	arrival time	burst time
$P_{1}$	0	8
$P_{2}$	1	4
$P_{3}$	2	9
$P_{4}$	3	5

$Average waiting time = \frac{( 10 - 1 ) + ( 1 - 1 ) + ( 17 - 2 ) + ( 5 - 3 )}{4} = 6.5$

Round Robin (RR)

Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds
- After this time has elapsed, the process is preempted and added to the end of the ready queue
Typically, higher average turnaround than SJF, but better response

process	burst time
$P_{1}$	8
$P_{2}$	4
$P_{3}$	9

$Time Quantum = 4$

Priority Scheduling

The CPU is allocated to the process with the highest priority
SJF is priority scheduling where priority is the inverse of predicted next CPU burst time

process	burst time	priority
$P_{1}$	10	3
$P_{2}$	1	1
$P_{3}$	2	4
$P_{4}$	1	5
$P_{5}$	5	2

$Average waiting time = 8.2$

Priority Scheduling + Round-Robin

Run the process with the highest priority
Processes with the same priority run round-robin

process	burst time	priority
$P_{4}$	7	1
$P_{2}$	5	2
$P_{3}$	8	2
$P_{1}$	4	3
$P_{5}$	3	3

Multilevel Queue

Multiple-Processor Scheduling

Multicore CPUs
Multithreaded cores
NUMA(non-uniform memory access) systems
Heterogeneous multiprocessing

SMP

Symmetric multiprocessing (SMP) is where each processor is self-scheduling
- (a) All threads may be in a common ready queue
- (b) Each processor may have its own private queue of threads
keep all CPUs loaded for efficiency
- Load balancing
  - attempts to keep workload evenly distributed
- push migration
  - pushes task from overloaded CPU to other CPUs
- pull migration
  - idle processors pulls waiting task from busy processor
processor affinity
- Soft affinity
  - the OS attempts to keep a thread running on the same processor, but no guarantees
- Hard affinity
  - allows a process to specify a set of processors it may run on

hyperthreading

real-time scheduling

Real-Time system
- soft real-time system
  - but no guarantee as to when tasks will be scheduled
- hard real-time system
  - task must be serviced by its deadline
latency
- Interrupt latency
  - time of stop process to another process
- Dispatch latency
  - take current process off CPU and switch to another CPU

Earliest Deadline First Scheduling (EDF)

Priorities are assigned according to deadlines:
- the earlier the deadline, the higher the priority
- the later the deadline, the lower the priority

Operating System Examples

linux scheduling

Completely Fair Scheduler (CFS)
- CFS scheduler maintains per task virtual run time in variable vruntime
- To decide next task to run, scheduler picks task with lowest virtual run time
Linux supports load balancing, but is also NUMA-aware

solaris scheduling

priority-based scheduling
Six classes available
- Time sharing (default) (TS)
- Interactive (IA)
- Real time (RT)
- System (SYS)
- Fair Share (FSS)
- Fixed priority (FP)

Chapter 6: Synchronization Tools

Race condition

critical section segment of code
- Process may be changing common variables, updating table, writing file, etc
- When one process in critical section, no other may be in its critical section

Critical-Section Problem

Mutual Exclusion
- If process is executing in its critical section, then no other processes can be executing in their critical sections
Progress
- if not process in critical section and have process want to enter critical section then have to let the process
Bounded Waiting
- the time process wait to enter critical section have to limit(cant wait forever)

software solution

cant avoid shared variable be override value by another process
Entry section: disable interrupts
Exit section: enable interrupts

part of Solution

Assume that the load and store machine-language instructions are atomic
- Which cannot be interrupted
turn indicates whose turn it is to enter the critical section
two process have enter critical section in turn

Peterson’s Solution

Assume that the load and store machine-language instructions are atomic
- Which cannot be interrupted
turn indicates whose turn it is to enter the critical section
flag array is used to indicate if a process is ready to enter the critical section
solve critical section problem
- Mutual exclusion
- progress
- bounded-waiting

Memory Barrier

Memory models may be either:
- Strongly ordered – where a memory modification of one processor is immediately visible to all other processors
- Weakly ordered – where a memory modification of one processor may not be immediately visible to all other processors

Mutex Locks

First acquire() a lock
Then release() the lock
busy waiting
- the process will be block and continuous check is lock
- spinlock when is lock free will automatic let the waiting process know

semaphore

wait()
signal()
Counting semaphore
- integer value can range over an unrestricted domain
Binary semaphore
- integer value can range only between 0 and 1
- Same as a mutex lock
Must guarantee that no two processes can execute the wait() and signal() on the same semaphore at the same time

Semaphore Implementation with no Busy waiting

block()
- place the process invoking the operation on the appropriate waiting queue
wakeup()
- remove one of processes in the waiting queue and place it in the ready queue

Synchronization Hardware

Hardware instruction
- Atomic Swap()
- Test and Set()
Atomic variables

Hardware instruction

Atomic variables

atomic variable that provides atomic (uninterruptible) updates on basic data types such as integers and booleans

deadlock

deadlock
- two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
- Starvation
  - indefinite blocking
  - A process may never be removed from the semaphore queue in which it is suspended
- Priority Inversion
  - Scheduling problem when lower-priority process holds a lock needed by higher-priority process
  - Solved via priority-inheritance protocol

Chapter 7: Synchronization Examples

Problems of Synchronization

Most of the synchronization problems do not exist in functional languages

Bounded-Buffer Problem (Producer-consumer problem)
Readers and Writers Problem
Dining-Philosophers Problem

OS

windows
- spinlocks
- dispatcher object
linux
- Atomic integers
- Mutex locks
- Spinlocks, Semaphores
- Reader-writer versions of both
POSIX
- mutex locks
- semaphores
  - named
    - can be used by unrelated processes
  - unnamed
    - can be used only by threads in the same process
- condition variable

Chapter 8: Deadlocks

Deadlock Characterization

Mutual exclusion
- only one process at a time can use a resource
Hold and wait
- a process holding at least one resource is waiting to acquire additional resources held by other processes
No preemption
- a resource can be released only voluntarily by the process holding it, after that process has completed its task
Circular wait
- there exists a set {P0, P1, …, Pn} of waiting processes such that:

Deadlocks Prevention

mutual exclusion
- not required for sharable resources (e.g., read-only files); must hold for non-sharable resource
hold and wait
- must guarantee that whenever a process requests a resource, it does not hold any other resources
No Preemption
- If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
Circular Wai
- check is have circular wait or not

Deadlock Avoidance

Cant do Preventon，have to check in run time
The goal for deadlock avoidance is to the system must not enter an unsafe state.
each process declares the maximum number of resources of each type that it may need
deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition

safe state

safe state
- no deadlock
unsafe state
- possibility of deadlock
Avoidance Algorithms
- Single instance of a resource type
  - resource-allocation graph
- Multiple instances of a resource type
  - Banker’s Algorithm

Resource-Allocation Graph

graph contains no cycles
- no deadlock
graph contains a cycle
- only one instance per resource type, then deadlock
- several instances per resource type, possibility of deadlock

Banker’s Algorithm

Max: request resource count to finish task
Allocation: currently occupy resource count
Need: Max-Allocation resource count
Available: free count of resource type

Resource-Request Algorithm

example

total available A (10 instances), B (5 instances), and C (7 instances)
safe sequence: $P_{1}, P_{3}, P_{4}, P_{0}, P_{2}$
unsafe sequence: $P_{1}, P_{2}, P_{4}, P_{0}, P_{3}$

task	allocation	max	need	available	order
	A,B,C	A,B,C	A,B,C	A,B,C
$P_{0}$	0,1,0	7,5,3	7,4,3	7,4,5=( (7,4,3) + (0,0,2) )	3
$P_{1}$	2,0,0	3,2,2	1,2,2	3,3,2=( (10,5,7) - (7,2,5) )	0
$P_{2}$	3,0,2	9,0,2	6,0,2	7,5,5=( (7,4,5) + (0,1,0) )	4
$P_{3}$	2,1,1	2,2,2	0,1,1	5,3,2=( (3,3,2) + (2,0,0) )	1
$P_{4}$	0,0,2	4,3,3	4,3,1	7,4,3=( (5,3,2) + (2,1,1) )	2

Deadlock Detection

Single instance

Multiple instances:

Total instances: A:7, B:2, C:6
Available instances: A:0, B:0, C:0

task	allocation	request/need
	A,B,C	A,B,C
$P_{0}$	0,1,0	0,0,0
$P_{1}$	2,0,0	2,0,2
$P_{2}$	3,0,3	0,0,0
$P_{3}$	2,1,1	1,0,0
$P_{4}$	0,0,2	0,0,2

Deadlock Recovery

Process termination
- Abort all deadlocked processes
- Abort one process at a time until the deadlock cycle is eliminated
- In which order should we choose to abort?
  - Priority of the process
  - How long process has computed
  - Resources the process has used
Resource preemption
- Selecting a victim
  - minimize cost
- Rollback
  - return to some safe state, restart process for that state
- Starvation
  - same process may always be picked as victim, so we should include number of rollbacks in cost factor

Chapter 9: Main Memory

The only storage CPU can access directly
- Register access is done in one CPU clock (or less)
- Main memory can take many cycles, causing a stall
- Cache sits between main memory and CPU registers

Protection

need to ensure that a process can only access those addresses in its address space
we can provide this protection by using a pair of base and limit registers defining the logical address space of a process
CPU must check every memory access generated in user mode to be sure it is between base and limit for that user

Logical vs. Physical Address

Logical address/virtual address
- generated by the CPU
Physical address
- address seen by the memory unit
Logical and physical addresses are the same in compile- time and load-time address-binding schemes; they differ in execution-time address-binding scheme

Memory-Management Unit

How to refer memory in a program – Address Binding

compile time
load time
execution time

How to load a program into memory – static/dynamic loading and linking

Dynamic Loading
- load function instruct when need to use
- better memory space
Static Linking
- duplicate same function instruct to memory in compile time
Dynamic Linking
- runtime link function address
- DLL(Dynamic link library) in window

Dynamic Loading	Static Linking	Dynamic Linking

Contiguous Memory Allocation

Variable-partition

Dynamic Storage Allocation Problem

First-fit: Allocate the first hole that is big enough
Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
Produces the smallest leftover hole
Worst-fit: Allocate the largest hole; must also search entire list
Produces the largest leftover hole

Fragmentation

External fragmentation
- problem of variable-allocation
- free memory space enough to size but is not contiguous
- compaction
Internal fragmentation
- problem of fix-partition-allocation
- memory not use by process

Non-Contiguous Memory Allocation

Paging

Divide physical memory into fixed-sized blocks called frame
- size is power of 2, between 512 bytes and 16M bytes
Divide logical memory into blocks of same size called pages
To run a program of size N pages, need to find N free frames and load program
benefit
- process of physical-address space can be non-contiguous
- avoid external fragmentation

Page table

Page table only contain the page own by process
process cant access memory that is not in
Page table is kept in main memory
- Page-table base register (PTBR)
  - points to the page table
- Page-table length register (PTLR)
  - indicates size of the page table

Translation Look-aside Buffer (TLB)

The two-memory access problem can be solved by the use of a special fast-lookup hardware cache called translation look-aside buffers (TLBs) (also called associative memory)
In this scheme every data/instruction access requires two memory accesses

address translation scheme

Page number(p)
- each process can have $2^{n}$ page (32-bit computer one process can use 4GB memory)
Page offset(d)
- combined with base address to define the physical memory address that is sent to the memory unit

給定一個 32-bits 的 logical address，36 bits 的 physical address 以及 4KB 的 page size，這代表？
- page table size = $2^{32}$ / $2^{12}$ = $2^{20}$ 個 entries
- Max program memory: $2^{32}$ = 4GB
- Total physical memory size = $2^{36}$ = 64GB
- Number of bits for page number = $2^{32}$ / $2^{12}$ = $2^{20}$ pages -> 20 bits
- Number of bits for frame number = $2^{36}$ / $2^{12}$ = $2^{24}$ frames -> 24 bits
- Number of bits for page offset = 4KB page size = $2^{12}$ bytes -> 12 bits

Shared Pages

Shared code
- One copy of read-only (reentrant) code shared among processes

Chapter 10: Virtual Memory

Code needs to be in memory to execute, but entire program rarely used
Program no longer constrained by limits of physical memory
Consider ability to execute partially-loaded program

virtual memory

Only part of the program needs to be in memory for execution
Logical address space can therefore be much larger than physical address space
Allows address spaces to be shared by several processes
Allows for more efficient process creation
More programs running concurrently
Less I/O needed to load or swap processes
Virtual memory can be implemented via:
- Demand paging
- Demand segmentation

Demand Paging

Page is needed
Lazy swapper
- never swaps a page into memory unless page will be needed
- store in swap(disk)

valid-invalid bit

During MMU address translation, if valid–invalid bit in page table entry is i => page fault

page fault

page table that request are not in memory

free-frame list

when page fault occurs, the OS must bring the desired page from secondary storage into main memory
Most OS maintain a free-frame list – a pool of free frames for satisfying such requests
zero-fill-on-demand
- the content of the frames zeroed-out before being allocated

Performance of Demand Paging

Memory access time = 200 nanoseconds
Average page-fault service time = 8000 nanoseconds
p = page fault probability
Effective Access Time = (1 – p) x 200 + p (8000)

Demand Paging Optimizations

Swap space I/O faster than file system I/O even if on the same device
Swap allocated in larger chunks, less management needed than file system

Copy-on-Write

allows both parent and child processes to initially share the same pages in memory
- If either process modifies a shared page, only then is the page copied
vfork() variation on fork()system call has parent suspend and child using copy-on-write address space of parent
- Designed to have child call exec()
- Very efficient

origin	Process 1 Modifies Page C

Page Replacement

if There is no Free Frame
use a page replacement algorithm to select a victim frame
Write victim frame to disk if dirty
Bring the desired page into the (newly) free frame; update the page and frame tables
Continue the process by restarting the instruction that caused the trap

FIFO Algorithm

first in first out

Optimal Algorithm

Replace page that will not be used for longest period of time
stack algorithms

Least Recently Used (LRU) Algorithm

Replace page that has not been used in the most amount of time
stack algorithms

Second-chance Algorithm

If page to be replaced has
- Reference bit = 0 -> replace it
- reference bit = 1 then:
  - set reference bit 0, leave page in memory
  - replace next page, subject to same rules

Counting Algorithms

Least Frequently Used (LFU) Algorithm
Most Frequently Used (LFU) Algorithm

page buffering algorithm

Keep a pool of free frames, always
possibly, keep list of modified pages
Possibly, keep free frame contents intact and note what is in them

allocation of frames

fixed allocation
priority allocation

Non-Uniform Memory Access

allocating memory “close to” the CPU on which the thread is scheduled

thrashing

Page-Fault Frequency

A process is busy swapping pages in and out
If a process does not have “enough” pages, the page-fault rate is very high
- Page fault to get page
- Replace existing frame
- But quickly need replaced frame back
If actual rate too low, process loses frame
If actual rate too high, process gains frame

Buddy System

Allocates memory from fixed-size segment consisting of physically-contiguous pages

Slab Allocator

use by solaris and linux
Slab can be in three possible states
1. Full – all used
2. Empty – all free
3. Partial – mix of free and used
Upon request, slab allocator
1. Uses free struct in partial slab
2. If none, takes one from empty slab
3. If no empty slab, create new empty

Priority Allocation

If process Pi generates a page fault,
- select for replacement one of its frames
- select for replacement a frame from a process with lower priority number

Chapter 11: Mass-Storage Systems

HDD(hard disk drives)

Positioning time (random-access time)
- seek time
  - calculated based on 1/3 of tracks
  - 3ms to 12ms
- rotational latency
  - latency = 1 / (RPM / 60) =60/RPM
  - average latency = $\frac{1}{2}$ latency
Transfer Rate
- Effective Transfer Rate (real): 1Gb/sec
Access Latency
- Access Latency=average seek time + average latency
Average I/O time
- Average I/O time = average access time + (amount to transfer / transfer rate) + controller overhead

Nonvolatile Memory Devices

type
- solid-state disks (SSDs)
- usb
drive writes per day (DWPD)
- A 1TB NAND drive with rating of 5DWPD is expected to have 5TB per day written within warrantee period without failing

Volatile Memory

RAM drives
RAM drives under user control

Disk Attachment

STAT
SAS
USB
FC
NVMe

Disk Scheduling

OS maintains queue of requests, per disk or device
Minimize seek time
Linux implements deadline scheduler
- Maintains separate read and write queues, gives read priority
- Because processes more likely to block on read than write

FCFS

SCAN algorithm

The disk arm starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the other end of the disk, where the head movement is reversed and servicing continues

C-SCAN

SCAN but when it reaches the other end, however, it immediately returns to the beginning of the disk, without servicing any requests on the return trip

NVM Scheduling

NVM best at random I/O, HDD at sequential
write amplification
- one write, causing garbage collection and many read/writes

Error Detection and Correction

CRC (checksum)
ECC

Swap-Space Management

Used for moving entire processes (swapping), or pages (paging), from DRAM to secondary storage when DRAM not large enough for all processes

RAID Structure

Mirroring
Striped mirrors (RAID 1+0) or mirrored stripes (RAID 0+1) provides high performance and high reliability
Block interleaved parity (RAID 4, 5, 6) uses much less redundancy

Chapter 13: File-System Interface

file attributes

Name – only information kept in human-readable form

Identifier
- unique tag (number) identifies file within file system
Type
- needed for systems that support different types
Location
- pointer to file location on device
Size
- current file size
Protection
- controls who can do reading, writing, executing
Time, date, and user identification
- data for protection, security, and usage monitoring
Information about files are kept in the directory structure, which is maintained on the disk
Many variations, including extended file attributes such as file checksum

file operations

create
write
read
seek
delete
truncate

file locking

Shared lock
Exclusive lock
Mandatory
- access is denied depending on locks held and requested
Advisory
- processes can find status of locks and decide what to do

File Structure

simple record structure
- Lines
- Fixed length
- Variable length
Complex Structures
- Formatted document
- Relocatable load file

types of File Systems

tmpfs
- memory-based volatile FS for fast, temporary I/O
objfs
- interface into kernel memory to get kernel symbols for debugging
ctfs
- contract file system for managing daemons
lofs
- loopback file system allows one FS to be accessed in place of another
procfs
- kernel interface to process structures
ufs, zfs
- general purpose file systems

Directory structure

Naming problem
- convenient to users
- Two users can have the same name for different files
- The same file can have several different names
Grouping problem
- logical grouping of files by properties,
Efficient
- locating a file quickly

Two-Level Director

Tree-Structured Directories /Acyclic-Graph Directories

guarantee no cycles?
- Garbage collection
- Every time a new link is added use a cycle detection algorithm to determine whether it is OK

User IDs
- identify users, allowing permissions and protections to be per-user
Group IDs
- allow users to be in groups, permitting group access rights

something