Operating system architectures

Goals

Control and coordinate system resources.

Hardware abstraction layer (HAL)

Disk access, memory management, task scheduling, user interfacing.

Monolithic kernel

Virtual interface to hardware

System calls provided by modules

Pros

Very fast, if done correctly

Dynamic extention on runtime by loading modules

Cons

Difficult to do correctly

Bug in 1 module can crash the whole system

Examples

Classic UNIX (BSD)

Linux

Micro kernel

Tiny kernel, with features split into system and user programs

Provides minimal process/memory management, and communications (IPC).

Pros

Easy to extend

More secure and reliable, due to fewer kernel processes

Cons

Slower, due to more system calls

Examples

QNX

AIX

Minix (Linux's basis)

Virtual Machine

Each VM functions as a whole computer

Hardware is either passed through, or emulated.

Sharing data through virtual disks and/or virtual network

Pros

Isolation dimisses needs for protection

Good for researching/testing new operating systems

Examples

Mac OS 68k on Mac OS PPC

x86 on PPC

Very slowly PPC on x86 (registers)

Transmeta CPUs

Java VM, Parrot VM

Exokernel

Undergoing further research

Processes and threads

Processes

Process State

New, Running, Waiting, Ready, Suspended, Terminated

Only #CPUs can be Running at any one time

Process Control Block (PCB)

Process state

Program counter (next instruction)

CPU registers

CPU scheduling information (priority)

Memory management information

Accounting information (time used, other statistics)

I/O status information (open files, etc)

Parent-Child processes

Child can use New or Parent resources (exec, fork)

Parent can wait for children, or continue

Parent can take down children with it, or allow them to continue

Independent or Cooperating

Data sharing

Task splitting (SMP)

Modularity

Convenience

Threads

Seperate stack, registers. Shared code, data, files.

Pros

Responsiveness (one load, one display, one blocked)

Resource sharing

Time economy (creation, context switching)

Utilization of multiprocessor architectures (SMP)

Types

Kernel threads

User threads

Many-to-one (Solaris, GNU Pthreads)

Pro: Efficient

Con: One thread can block whole process

Con: No SMP

One-to-one (Linux, Win32)

Pro: Concurrency (no blocking)

Pro: SMP

Con: Overhead of creating kernel threads

Con: Overall thread limit

Many-to-many (IRIX, Tru64 UNIX)

Pro: Concurrency (no blocking)

Pro: SMP

No cons

Two-level model (many-to-many + one-to-one)

Examples

Apache HTTPd

Scheduling

CPU

Non-preemptive (cooperative: Win16, MacOS 9-)

Process has to release the CPU itself

Pro: Simple, stable.

Con: Bad multitasking

Preemptive (Win32, MacOS X)

CPU is passed around via a timer

Pro: Concurrency

Con: Complex, potentially unstable.

First-Come, First-Serve (FCFS, FIFO)

Non-preemptive

Con: Average wait time not minimal

Con: Average wait time varies a lot

Shortest-Job-First Scheduling (SJF)

Provably optimal

Long-term: Program has to say how long it will need

Short-term: Exponential average (averaged over time)

Non-preemptive mode: Will allow current process to finish time-slice

Preemptive mode: Will break off current process in favour of smaller one

Priority scheduling (the above SJF is a PS)

Non-preempt mode: Put in front of ready queue

Preempt mode: Cuts current process off in favour of high priority ones.

Con: Indefinite blocking/starvation

Solution: Age increases priority

Round-Robin scheduling

FIFO queue where each entry gets a time-slice to do its work.

Multilevel Queue scheduling

Foreground vs Background queues

Inter-queue scheduling

Multilevel Feedback-Queue scheduling

Processes can be moved between queues based on various feedback

Multi-Processor scheduling (asymmetric master/slave, symmetric individuals)

Real-time (hard RT with special hardware, soft RT on normal hardware)

Quality measurement: Maximize CPU utilization (but max 1 sec response), max throughput so average turnaround time is proportional to execution time.

Disk

First-Come, First-Serve (FCFS, FIFO): Fair, but possibly slow.

Shortest seek time first (SSTF): Like SJF, so can cause starvation/long waits.

SCAN: Goes back and forth, servicing requests along the path.

C-SCAN: Goes forth like SCAN, but does nothing on the way back.

LOOK: Moves to the last request in a given direction, then reverses.

Quality measurement: Difficult, since rotational latency cannot be accounted for.

Page-replacement (Belady's anomaly: more frames != less faults)

FIFO, shuffles out the frame at the head of the queue, suffers from BA

Optimal, which requires knowledge of the future (used for comparison; similar to SJF; no BA)

Least Recently Used (LRU), shuffles out the page used longest time ago, no BA, stack algorithm (n is subset of n+1).

Additional Reference Bit, which shifts the reference bit onto a byte every Xms (e.g. 100ms). Lowest number = LRU page.

Second-Chance, like FIFO but skips and clear a page if its reference bit is set.

Enchanced Second-Chance, looks at both reference and modify bit; if modified it won't be victim.

Least frequently used/most frequently used; Shuffles out the page with the lowest/higest usage count.

Quality measurement: Compare to optimal.

Synchronization and communication

Synchronization (we wish to avoid race conditions)

Critical Sections

Mutual-exclusion (only 1 in a critical section at any time)

Progress (who gets to enter its CS)

Bounded waiting (prevent infitine wait/starvation)

Two threads need 3 variables to correctly satisfy these requirements.

Hardware synchronization: Get-and-Set instruction, Swap instruction

Semaphores

Two methods: acquire (wait, decrement), release (increment)

Binary semaphore: Mutually exclusive (mutex) locks

Counting semaphore: Access to a given number of a resource

Spinlock (busy-wait) semaphores: Bad on single-CPU systems (but 2 CPU: 1 spin, 1 work).

Introduce wakeup call, and a waiting process list.

Single-CPU: Just stop interrupts. Multi-CPU: Use solution from CS (3 vars).

Deadlock

Definition: A set of processes are waiting for an event that can only be caused by a process in the set.

Indefinite blocking/starvation: A process that never gets a resource due to using LIFO buffers.

Reader-Writer problem: Many readers, single writer.

Dining philosophers problem: 5 thinkers, round table, chopsticks.

Solution is to code correctly. Weak solution is to forcibly kill or restart processes that are deadlocked.

Livelock: Like deadlock, only where a process fails at something repeadetly.

Communication

IPC

Useful in distributed computing (clusters, internet)

Message-Passing System

Direct communication

Must know the process to send to/receive from

Con: Hard-coding names is bad.

Indirect communication

Uses a mailbox to send/receive messages.

Owner can receive, users can send.

Process-owned mailbox: No confusion about ownership, but must notify when exiting.

OS-owned mailbox: Creator is owner, and can assign new receivers (owners).

Synchronous (blocking) communication & Asynchronous (non-blocking) communication

Combination of non-blocking send/receive, and blocking send/receive. If both block, it's a rendezvous.

Automatic buffering & Explicit buffering

Zero capacity: Exactly 1 message at the time (very likely causes blocking)

Bounded capacity: At most N messages (may cause blocking)

Unbounded capacity: Unlimited messages (sender never blocks)

Shared Memory

Multiple processes share a single address space

Memory management

Address Binding (relative to absolute addresses)

Compile time: Relative address is known at compile time (very unlikely today) = Absolute code

Load time: Relative address is known at load time, and doesn't change = Relocatable code.

Execution time: Relative address change between execution slices = Current prevailing model

Logical address (virtual address) map to physical addresses via a Memory Management Unit

Dynamic loading

DLLs, shared libraries. Update shared code without recompile.

Memory Allocation

First-fit: First hole large enough to accomodate the program. Fastest.

Best-fit: Smallest hole. Equally good as first-fit.

Worst-fit: Largest hole. Worst.

All lead to external fragmentation (small chunks of unallocated space)

Virtual memory (swap)

Page based

Page number P + Page offset D. P goes into the page table, and outputs an address F, so that F+D is the physical address to be accessed. This happens behind the scenes (coder sees 1 address).

Leads to internal fragmentation (unused allocated space) of average ½ page per process.

Process only sees its memory as a continuous block, but OS sees it scattered all over.

Hardware support:

Dedicated page register: Very fast, but cannot contain many pages.

Page-table base register (PTBR): Page table in main memory, which is slow (by x2).

Translation look-aside buffer (TLB): Fast parallel search, expensive hardware. Some entries can be wired down (permanent), such as kernel pages.

Address-space identifiers (ASIDs): Keys the entry to the process. If no ASID, TLB must be flushed before use to prevent corruption.

Structure

Hierarchical Paging: Splitting P+D into P1+P2+P3+D or more. Bad for 64bit.

Hashed Page Table: Using a hash table to find where to search.

Inverted Page Table: PID+P+D. Smaller to store, but slower (TLB helps).

Shared pages – processes can share common pure code.

Segment based

Supports the users' view of the code. Addresses are passed as <segment-id, offset>. Coders usually don't have to bother with it, though, since compiler handles the segmentation.

Hardware: Segment table with a segment base and a segment limit. Segment S + Offset D, where D must be < limit.

Protection & Sharing

Segments can be defined read-only or execute-only.

Processes can share segments of code, but self-references are an issue (use: relative offsets).

Fragmentation

Segments are variable length, so have to use first/best-fit

External fragmentation. Solved by paging...

Demand Paging

Pager, that only reads in pages we need.

Valid/invalid bit: Valid = Legal & loaded; invalid = illegal or not loaded

Example:

x86 uses segments that are paged.

File systems

Bad Block management: Keep spare sectors available, and dynamically remap. Data lost.

Files

Allocation

Contiguous allocation: Causes external fragmentation, but file access is non-fragmented.

Linked allocation: Blocks are allocated in a linked list. Causes major file-fragmentation, but uses the disk space optimally. Can be made safer/faster with a cached FAT.

Indexed allocation: A few blocks contain the index of data blocks.

Free-space management

Bit vector

Linked list

Grouping: Indexed allocation, but for free space.

Counting: A disk address, and a count of free blocks at that address.

Efficiency

META-data (access time, creation time, etc)

File structures, types

Access control (chmod, chown)

Performance: Cache

Encryption, compression

Recovery (Journaling)

Directory structure

Linear list: Simple, but slow. B-tree helps a lot.

Hash table: Much faster; avoids hash collisions with linked lists.

Single-Level directory: Everything in /

Two-Level directory: chroot to user's own single-level directory.

Tree-structure directory: Absolute paths, relative paths.

Whether a directory can also function as a fil (usually no)

Acyclic-graph structure: Allows for links

General-graph structure: Allows for cyclic links

File references (symbolic links, hard links)

Links are not resolved when doing backups

Virtual File Systems (VFS)

Provides an abstraction layer to the various types of local file systems. Can traverse networks.

IO and disk management

Device Driver

Provides an abstraction layer with a stable API to a piece of hardware, whose API may vary.

Can be loaded and unloaded dynamically based on demand (USB/FireWire devices)

Accessing a device

Polling/busy-waiting: Inefficient.

Interrupts

Non-maskable: Can happen at any time

Maskable: Can be turned off during critical sections.

Direct Memory Access (DMA): For large read/write, let the device bypass the CPU.

Appliction I/O Interface (abstraction layer)

Character stream or blocks: Byte by byte, or blocks of bytes.

Sequential or random access: Device-dependent, or seekable.

Synchronous or asynchronous: Predictable, or unpredictable response time.

Sharable or dedicated: Multi-process, or not.

Speed of operation: b/s to GiB/s

Read/Write/Both: Access modes

Kernel I/O sub-systems

I/O scheduling: Requests are queued up, then re-ordered to be executed in an efficient manner.

Buffering

Double-buffers (1 for download, 1 for writing to disk)

Data transfer size disparity (network packet sizes)

Clean semantics (copying files)

Caching: A copy of existing data, for faster access

Spooling: Creates the data on disk, and then sends it to the device one at the time (printer)

Device reservation: Enables locking a device to only one process at the time.

Error-handling: Retries failed operations, or makes sure a permanent error does not crash us.

Disk management

Disk scheduling

Disk formatting

Partitioning (not really, there is a standard)

Boot blocks

Bad blocks

Swap management (partition, or inline in file system)

RAID (better in hardware)

Networking

Definition: A communication path between two or more systems.

Types:

Client-Server

Peer-to-Peer (access via a central coordinater, or through broadcast)

Distributed (SETI, distributed.net, GRID)

Clusters (redundancy, load balancing)

Protocols

LAN: IPX, TCP/IP, UDP (also /IP)

WAN: TCP/IP, UDP, Border Gateway Protocol (BGP, routing)

Communication

Sockets

Remote Procedure Call (RPC)

Remote Method Invocation (RMI, Java)

Distributed file systems

Transparency (usually through VFS)

Issue: Consistency

Issue: Stateless vs stateful

Network Files System (NFS)

Heterogeneous (can work on all machines, OSs, network archs)

Mount Protocol

User-mode server process

Export list (root-only editing)

Returns a file handle

RPCs: Mount, unmount, view list.

NFS Protocol

RPCs: Search dir, read dir, alter dir/links, alter attributes, read/write files.

Stateless design: No open/close calls. No locking.

Path-name translation: One call for every path component (slow, but can be cached).

Remote Operations

Concept: Remote-service paradigm (meaning no buffer/cache)

Practically: Buffering and caching are used for performance.

Slow; no concurrency/synchronization between clients.

Andrew File System (AFS)

Scalable (5000+ workstations)

Local name space (client, Virtue) vs. Shared name space (server, Vice)

Client has small storage to cache what they are currently working on (temp, etc).

Split into clusters of a few clients and a server, that in turn connect to the other clusters.

Pros

Client Mobility: Client can log in anywhere

Security: Everything executed on client, so server is secured via authentication/encryption.

Protection: Access lists enables fine-tuning permissions (both allow and deny lists).

Heterogeneity: Some files are links to system-specific binaries.

Shared name space

Volumes (which are not whole disks or partitions)

FID: Volume number, vnode number (inode on volume), uniquifier (multiple-access).

Volume-location database. Volumes can be moved atomically.

Only 1 master read-write of a volume, and several read-only slave volumes.

Operations and Consistency

Whole files are cached on clients, and are only updated on close, or on a callback from Vice. Venus manages this. Same goes for symbolic links. This greatly reduces RPCs since it's passive (vs active where it'd ask all the time).

Protection

OS

Access control, Reliability/Stability

Policy: What to enforce (may change over time; best if seperates from mechanisms )

Mechanism: How to enforce policies (general mechanisms are better)'

Domain of Protection

Objects (hardware & software), have specific operations.

Processes: need-to-know only current variables and rights (minimally)

Domain Structure: Split out access rights to domains, which can overlap

User domain

Process domain

Procedure domain

UNIX: User domains, setuid

MULTICS: Ring domains, doesn't satisfy need-to-know

Access matrices (chmod)

Read, write, execute, copy*, owner

Confinement problem (unsolvable, information wants to be free)

Implementation

Global table: Too large, bad management.

Access lists (objects): Specific rights, and a default list.

Capability lists (domains): List of objects and their capabilities with that domain. Secure.

Lock-Key mechanism: Cross between Access and Capability. Objects has locks, domains have keys to those locks.

Access Revocation

Immediate vs Delayed: How to know when, if delayed?

Selective vs General: Who it affects, all or some.

Partial vs Total: What it revokes, all or some.

Temporary vs Permanent

Access lists are immediate, any, any, any.

Capabilities need schemes:

Reacquisition: Capabilites are deleted over time, but can be reacquired if not revoked.

Back-pointers: Slow, but general and partial.

Indirection: 2 tables, one with capabilites and one with objects.

Keys:

Network issues

Security

Types of vulnerabilities

Buffer-overflow (int vs unsigned)

Definitions

Virus: A process that will inject its own code into other programs, thus altering them. A virus is by definition passive, meaning a user has to initiate the first infection (usually not on purpose).

Worm: A process that will actively seek out exploitable vulnerabilities in a system, usually though the network. Then infect them, and use them for spreading itself.

Trojan-horse (trojan): A virus or worm that asides from spreading itself also provides a backdoor to access the system remotely.

Prevention

NX-bit

Tino Didriksen

2004-06-06T15:39:31