CPSC 351

I/O Management

A major component of OS design that handles device diversity, performance management, and provides uniform device-access interface

Port

Connection point for an I/O device to interface with the computer

Bus

Communication pathway that can be daisy chain or shared direct access; PCI and PCIe are common examples

Controller (Host Adapter)

Electronics that operate port, bus, and device; contains processor, microcode, private memory, and bus controller

Memory-Mapped I/O

Device data and command registers mapped to processor address space, especially useful for large address spaces like graphics

Direct I/O Instructions

Method where devices have addresses used by specific I/O instructions

Polling

Busy-wait cycle where host reads status register until ready; reasonable if device is fast but inefficient if device is slow

Interrupt-Request Line

CPU line triggered by I/O device and checked after each instruction to handle I/O completion

Interrupt Handler

Receives and processes interrupts based on priority; performs context switch at start and end

Interrupt Vector

Dispatch mechanism to route interrupt to correct handler

Maskable Interrupts

Interrupts that can be ignored or delayed; some interrupts are nonmaskable

Direct Memory Access (DMA)

Technique to avoid programmed I/O by bypassing CPU to transfer data directly between I/O device and memory

DMA Controller

Device that handles bus mastering to grab bus from CPU and perform cycle stealing for efficient data transfer

DVMA

DMA version aware of virtual addresses; more efficient than standard DMA

Device Driver

Software layer that encapsulates device details and hides differences among I/O controllers from kernel

Block Devices

Devices like disk drives with commands including read, write, seek; support raw I/O, direct I/O, or file-system access

Character Devices

Devices like keyboards, mice, serial ports with commands including get() and put()

Nonblocking I/O

I/O call returns as much as available immediately; returns quickly with count of bytes read or written

Asynchronous I/O

Process runs while I/O executes; I/O subsystem signals process when I/O completed

Blocking I/O

Process suspended until I/O completed; easy to use but insufficient for some needs

Vectored I/O

Allows one system call to perform multiple I/O operations; scatter-gather method better than multiple individual calls

Buffering

Storing data in memory while transferring between devices to cope with speed/size mismatches and maintain copy semantics

Double Buffering

Two copies of data: kernel and user, or full/being processed and not-full/being used

Caching

Faster device holding copy of data; key to performance, sometimes combined with buffering

Spooling

Hold output for a device that can serve only one request at a time (e.g., printing)

Device Reservation

Provides exclusive access to a device through system calls for allocation and deallocation

Programmed I/O

Moving data one byte at a time; inefficient for large data movement

STREAMS

Full-duplex communication channel between user-level process and device in Unix; consists of stream head, driver end, and zero or more modules

I/O Performance Factors

CPU execution of device driver/kernel code, context switches due to interrupts, data copying, and network traffic

Improving I/O Performance Methods

Reduce context switches, reduce data copying, reduce interrupts with large transfers/smart controllers, use DMA, use smarter hardware, balance CPU/memory/bus/I/O performance

Fetch file attributes and disk addresses

Fetch file attributes and disk addresses into RAM for speedy access

Close Operation

Free memory allocated to keep track of file state

Memory Mapped Files

Store file contents in process virtual memory; reading/writing file is like reading/writing local memory

Hierarchical Directory System

Directories containing subdirectories containing subdirectories; used by modern systems like Windows, Linux, macOS

Absolute Path

Path from root to file (e.g., /usr/ast/mailbox)

Relative Path

Path from current working directory to file

Partition

Division of disk; can be active (bootable OS) or inactive

Partition Table

Stores information about all present partitions (sizes and starting addresses)

Master Boot Record (MBR)

Stores boot program; BIOS executes MBR to find active partition and execute boot block

Boot Block

Contains program that boots OS on partition

Superblock

Contains magic number (identifies partition type), number of blocks, and administrative information

Free Space Management

Stores information about free blocks on disk

inodes

Array of data structures, one per file, containing file information and block addresses

Contiguous File Allocation

Store each file as contiguous run of disk blocks; easy but causes external/internal fragmentation

External Fragmentation

No hole big enough to store file in contiguous allocation

Internal Fragmentation

Unused space within blocks is wasted

Linked List Allocation

Store file blocks in linked list with first word of each block containing pointer to next

File Allocation Table (FAT)

Linked list allocation with table in memory; entire block used for data, list traversed without disk references

I-node (Index Node)

Data structure containing file attributes and list of file block addresses; only in memory when file is open

Directory Entry

Maps file name to information needed to locate data; stores or references attributes

Soft Link (Symlink)

File which references path of another file

Hard Link

Alias of file; associates name with file; pointer to file's i-node

Journaling

Create list of changes (journal) and save to disk before modifying file system; protects from inconsistencies after crashes

Virtual File System (VFS)

Provides object-oriented way of implementing file systems; allows same system call interface for different file system types

Page Cache

Caches information from disk in RAM to speed up disk accesses

Linked-List Free Space Management

Linked list of blocks where each block stores list of free block numbers

Bitmap Free Space Management

Reserve blocks that store bitmap where bit n=1 means block n is free, bit n=0 means used

Security

System is secure if resources used and accessed as intended under all circumstances (unachievable in practice)

Threat

Potential security violation

Attack

Attempt to breach security; can be accidental or malicious

Intruders (Crackers)

Those who attempt to breach security

Breach of Confidentiality

Unauthorized reading of data

Breach of Integrity

Unauthorized modification of data

Breach of Availability

Unauthorized destruction of data

Theft of Service

Unauthorized use of resources

Denial of Service (DOS)

Prevention of legitimate use

Masquerading

Pretending to be authorized user to escalate privileges; breach of authentication

Replay Attack

Resending captured message as-is or with modification

Man-in-the-Middle Attack

Intruder sits in data flow, masquerading as sender to receiver and vice versa

Session Hijacking

Intercept already-established session to bypass authentication

Four Levels of Security

Physical (data centers, servers), Human (avoid social engineering), Operating System (protection mechanisms), Network (prevent interception/interruption)

Trojan Horse

Code segment that misuses its environment; exploits trust mechanisms

Trap Door

Specific user identifier or password that circumvents normal security procedures

Logic Bomb

Program that initiates security incident under certain circumstances

Stack and Buffer Overflow

Exploits bug by writing past arguments on stack into return address; enables privilege escalation

Virus

Code fragment embedded in legitimate program; self-replicating, designed to infect other computers

Virus Dropper

Inserts virus onto system

Boot/Memory Virus

Infects boot sector or memory

Macro Virus

Written in macro language; example: Visual Basic macro

Polymorphic Virus

Changes to avoid having virus signature

Worm

Standalone program using spawn mechanism; can spread across networks

Port Scanning

Automated attempt to connect to range of ports to detect services, OS, and vulnerabilities

Distributed Denial-of-Service (DDOS)

DOS attacks coming from multiple sites simultaneously

Cryptography

Means to constrain potential senders/receivers of messages based on secrets (keys)

Encryption

Constrains set of possible receivers of a message using keys and algorithms

Symmetric Encryption

Same key used to encrypt and decrypt; key must be kept secret; examples: DES, Triple-DES, AES, RC4

DES (Data Encryption Standard)

Block-encryption algorithm; keys now too short, considered insecure

AES (Advanced Encryption Standard)

NIST-adopted block cipher; keys of 128, 192, or 256 bits; works on 128-bit blocks

Asymmetric Encryption (Public-Key)

Each user has public key (published) and private key (secret); RSA is most common

RSA

Block cipher based on difficulty of finding prime factors; public key encrypts, private key decrypts

Authentication

Constraining set of potential senders of message; proves message unmodified

Hash Function

Creates small, fixed-size message digest from message; must be collision resistant

Message Digest

Small, fixed-size block of data (hash value) created from message

Collision Resistant

Infeasible to find different message with same hash value

MD5

Message-digest function producing 128-bit hash

SHA-1

Message-digest function producing 160-bit hash

Message Authentication Code (MAC)

Symmetric encryption used for authentication; cryptographic checksum generated from message using secret key

Digital Signature

Based on asymmetric keys; anyone can verify authenticity; private key signs, public key verifies

Certificate Authority

Trusted party that certifies public key belongs to entity; their public keys included with web browsers

Digital Certificate

Proof of who/what owns public key; public key digitally signed by trusted party