OS Exam 2

Prof. Dude

Static relocation

Before hardware support, a loader would rewrite a program’s addresses to the desired offset as it loaded the program into memory.

No protection + difficult to move address space later

Base & Bounds/Limit registers

Also called dynamic relocation.

CPU uses a base and a bound register.

Base register is set to wherever the OS decides to place the program in memory

physical address = virtual address + base value

Bound register helps provide protection: memory reference must be within bounds

Assisted by MMU (memory mgmt unit) part of CPU

Swapping

Moving some memory pages to disk

Memory compaction

Rearrange unused memory into contiguous blocks

Pages

A fixed-size unit of virtual memory. Stored in page frames

Paging

Chopping virtual memory into fixed-size pieces

Provides flexibility and simplicity

Page table

per-process structure that stores address translations

Virtual address

the address the program sees (and is translated to the physical address by hardware)

address space

abstraction for physical memory that contains the state of a running program

MMU

part of CPU that helps with address translation

Page frames

Viewing physical memory as an array of fixed-size slots called ___ ______

Page table

Per-process data structure that stores virtual-to-physical address translations

Page table entry and its typical pieces

• Valid bit - unused space marked invalid

• Protection bits (Read/Write/Execute)

• Present bit- indicates if in physical memory or disk

• Dirty bit- flags if modified

• Referenced/Accessed bit- track if been accessed

How virtual addresses are converted to physical addresses

Virtual address is comprised of virtual page number + offset.

Virtual page number is used to index page table and find the physical frame number, and then the offset is applied to that.

Translation Lookaside Buffer

Part of the MMU; it’s a hardware cache of popular virtual-to-physical translations.

Fast because doesn’t use the page table.

Page faults

Attempting to access a page that’s not loaded into physical memory (present bit would be 0)

Page fault handler

Process is blocked, page fault handler locates page on disk, OS updates page table w/ correct number, TLB is updated, and desired data can be retrieved

Linear page table

Just an array

Multilevel page table

Tree-like structure- top level is page directory

Requires more loads during a TLB miss + extra complexity

inverted page tables

One system-wide page table with an entry for every physical page frame.

Used by most 64-bit OSs

Optimal

Ideal replacement policy- fewest misses overall. Requires future knowledge by removing the page that will be accessed furthest in the future

FIFO

First In, First Out. Removes the page on the tail of the queue. Simple to implement.

Clock

Approximates least-recently-used (but not as expensive). Kicks out page that hasn’t been used in a certain amount of time.

LRU

Removes least-recently-used.

LFU

Kicks out least frequently used page

Belady’s Anomaly

Situation where adding page frames doesn’t actually decrease the number of faults (may increase them).

Working Set

Pages currently in use

Thrashing

Memory demand exceeds available physical memory = constantly paging.

demand paging

loading pages into memory only when accessed

Spatial locality

For addresses close together, only the first access of the page results in a TLB miss.

temporal locality

quick re-referencing of memory in time

How many bits to represent the offset for a 4KB page

12; (because 2^12)

Canonical device

Has an interface (interacts with the computer) and an internal structure

Device controllers

Like a tiny computer; often has hundreds of thousands of lines of firmware

Interrupts

Improves I/O efficiency; instead of pulling, put calling process to sleep; then context switch. Wait until hardware interrupt to finish the request and wake waiting process.

Programmed I/O

CPU involved in data movement

Interrupt-driven I/O

Less taxing on CPU, uses interrupts instead of polling

Precise interrupt

Leaves machine in a well-defined state

Imprecise interrupt

Does not leave machine in a well-defined state- slow recovery

DMA I/O

Uses a Direct Memory Access device that can orchestrate transfers between devices and main memory without much CPU intervention; slower than CPU

Memory-mapped I/O

Hardware makes device registers available as if they were memory locations. OS routes to the device.

Device driver

Tells OS how the device works. Most of an OS kernel is device driver code.

Device driver role

^

I/O Software Layers

Interrupt handlers

When I/O request finished, CPU jumps into the OS at a predetermined interrput handler/interrupt service routine

Platter

Circular hard surface of an HDD on which data is stored (on 2 surfaces)

Track

One of many concentric circles on a platter.

Sector

512-byte block of data

Head

Reads/changes magentic patterns on the disk

Arm

Moves across disk to position the head over the desired track

Logical block addressing

Each block is numbered 0 to n-1 on an n-sector drive

RAID 0

Striping (no redundancy)

RAID 1

Mirroring

RAID 4

Saving space with parity (single disk with parity data)

RAID 5

Rotating Parity

RAID 6

Double rotating parity (can lose any 2 disks)

Disk formatting

Before a disk can be used, must receive a low-level format.

Creates disk partition

Then high-level format creates boot block, root dir, and empty files system

FCFS

First come first served disk scheduling

SSF

Shortest seek time first; picks nearest track first. Can lead to starvation

Elevator

Also called SCAN; Arm moves back and forth and services requests as it goes

C-SCAN

Elevator/scan but only in one direction to not favor the middle tracks

Error handing – bad sectors

Try rereading. If repeatedly fail, controller can either:

1. Remap bad sector to a spare

2. Shift all sectors (keep contiguous)

Three essential requirements of long-term information storage

1. Must store a large amount of information

2. Info must survive the termination of the process using it.

3. Multiple processes must be able to access the info at once.

File

An abstraction for an array of bytes. Has a low-level name, usually an inode number

file naming

File has a name as well as an inode number

file structure

OS doesn’t care about structure of any particular file.

However, the overall file system structure is maintained through directories.

file extension/type

a convention that indicates how the file is used

file access

Processes receive a file descriptor (points to an entry in the open file table)

attributes

Metadata (stored in inodes)

Root directory

The very base of the file system / start of file hierarchy. / on Unix.

Absolute path name

full file path starting at root directory /

relative path name

In reference to the working directory

working/current directory

.

Master Boot Record

Sector 0 of a disk. Contains boot code and partition table

boot block

First sector of a partition

Superblock

First block of the filesystem. Contains key info about said filesystem, number of inodes and data blocks, start of inode table, etc.

Contiguous allocation

Blocks

linked-list allocation

First word in each block points to the next block

linked-list with in-memory table (FAT),

Entire file block usable for data; all file link info is in memory; easy random access

Inodes

Short for index node; points to location of the file on disk; also stores file metadata.

Directory implementation

A directory is just a file.
Contains list of name-inode number pairs as well as “.” (itself) and “..” (the parent directory)

Soft link

Actually a file itself; holds pathname of linked-to file. (can become a dangling reference)

Hard link

Creates another way to refer to a file (not copied, just a reference)

Journaling file systems

Logging intended actions before doing them; can be used to correct actions that weren’t completed due to crash.

Virtual File Systems (VFS)

Abstracts application programmer interactions away from the specifics of any file system.

Management of Disk-Space

Allocation structures needed to track free and allocated blocks

Free lists or bitmaps can be used to manage the blocks

Block size

Usually 512 or a multiple of it

Free blocks

Unused block, usually listed somewhere

Backups

Handle 2 potential problems:

1. Recover from disaster

2. Recover from stupidity

Consistency

File system data must persist beyond power loss or system crash; must not be left in an inconsistent state.

Old systems used a file system checker (verify correct info). Newer ones use journaling.

2 Types of backups

1. Physical dumps- raw data copy, easier

2. Logical dumps- copy of structure, slower

MS-DOS

Fixed-size 32 byte directory entries

64K entry FAT

Time only accurate ±2 secs

UNIX file system

14-char filenames, 64K file limit

Single, double, triple indirect blocks for addressing

CD-ROM file system

• One contiguous spiral of data

• sectors of 2352 bytes- payload 2048

• Position in minutes and seconds (1 sec = 75 blocks)

• Variable-number of variable-length directory entries

Fragmented

Files stored non-contiguously = slower access

Headcrash

747 with 100000 people @ 60mph 1/100 of an inch