CS 350 Topics 5-8

Device

How a computer receives input from, and produces output for, the outside world. Also known as peripheral.

Bus

A communication pathway between various components of a computer.

Internal Bus

Also known as memory bus, it’s for communication between the processor and main memory. It is fast and close to the processor(s).

Peripheral Bus

Also known as expansion bus, it allows devices in the computer to communicate.

Port-Mapped I/O, Memory-Mapped I/O

A processor communicate with a device via two ways:

1. ____ (PMIO)

2. ____ (MMIO)

Port-Mapped I/O

A processor communicates with a device using special I/O instructions (in, out) and a separate port-based address space.

assembly, I/O, port, memory

With a Port-Mapped I/O (PMIO), the processor uses special ____ language ____ instructions. Device registers are assigned ____ numbers, which correspond to regions of ____ in separate, smaller address space.

Memory-Mapped I/O

A processor communicates with a device using normal load/store instructions and memory-mapped addresses.

physical, processors, main

With Memory-Mapped I/O (MMIO), each device register has a ____ memory address. ____ can read from, or write to, these device registers using normal load and store instructions, as though accessing ____ memory.

Device Registers

Memory-mapped I/O for devices is carried out through these.

status, command, data

There are three primary types of device registers:

1. ____

2. ____

3. ____

status

Primary device register that tells you something about the current state of the device. Typically, this register is read.

command

Primary device register used to control the device by writing specific values.

data

Primary device register used to transfer data between the processor and the device.

Status and Command

A combined register that is read to discover the the current state of the device and written to issue the device a command.

Data Buffer

A combined register that is sometimes separated into data_in and data_out buffers.

Undefined Behaviour

When the system’s outcome is unpredictable and not specified (for example, writing to a device while a write is already in progress).

IRQ

Short for interrupt request.

Device Driver

A part of the kernel that interacts with a device, for example write a character to a serial output device.

Communication

____ happens by reading from, or writing to, the command, status and data registers.

Polling, Interrupts

Two methods for interacting with devices are:

1. ____

2. ____

Polling

A method for interacting with devices where the kernel driver repeatedly checks the device’s status, which uses processor time.

Interrupts

A method for interacting with devices where the kernel does not wait for the device to complete the command. Instead, request completion is taken care of by the interrupt handler.

status, signals

In polling, the CPU busy waits by repeatedly reading the ______ register, whereas in interrupts, the CPU does not wait and the device ______ completion.

Program-Controlled I/O, Direct Memory Access

There are two strategies for transferring data to or from devices:

1. ____ (PIO)

2. ____ (DMA)

Program-Controlled I/O

Strategy for transferring data to/from devices where the device driver moves the data between main memory and a buffer on the device.

Direct Memory Access

Strategy for transferring data to/from devices where the device itself is responsible for moving data to and from memory.

processor, PMIO, MMIO, small

In Program-Controlled I/O or Programmed I/O (PIO), the device driver uses the ____ to transfer the data with either ____ or ____. PIO is suitable for transferring a ____ amount of data.

processor, block, large

In Direct Memory Access (DMA), the ____ is not used to transfer the data and is free to do something else. DMA is used for ____ data transfers between devices (e.g., between a disk controller and main memory). DMA is suitable for transferring ____ amounts of data.

data, DMA, starting, RAM, amount

Large Data Transfer to/from Devices Step 1:

The processor initiates the ____ transfer (i.e. issues a ____ request to the disk controller), giving it the ____ address of the destination in ____ and the ____ of data to transfer.

controller, main

Large Data Transfer to/from Devices Step 2:

The ____ (not the processor) writes to ____ memory.

transfer, controller, interrupt

Large Data Transfer to/from Devices Step 3:

When the ____ is complete, the ____ generates an ____ to let the kernel know it is complete.

platters, actuator arm

A hard drive (a.k.a. hard disk drive) consists of two major parts. A stack of ____ (a.k.a. disks) that spin around and the ____ ____ (a.k.a. disk arm assembly).

Platter

A rotating disk coated with magnetic material used to store data. Part of a hard drive.

Actuator Arm

A mechanical arm that positions the read/write head over different tracks. Part of a hard drive.

Spindle

A central motor that spins the platters in a hard drive at a constant speed.

surfaces, spindle, 5400, 7200, 100, 200

Regarding the stack of platters, each platter has two ____, which can be used to store data. The platters rotate together on a central ____ at a fixed speed, typically either ____ or ____ rotations per minute (rpm). The drive speed drifts slowly over time, so the exact rotational position cannot be predicted after ____ – ____ revolutions.

pivot, together, shocks, read, write, surfaces

Regarding the actuator arm, it rotates around a ____. All parts of the arms move ____. The pivot offers some resistance to linear ____. The arm contains ____/____ heads — one for each recording surface. The heads read data from, and write data to, the disk ____.

tracks, cylinders

Surfaces are broken up into a series concentric circles called ____ and ____.

Track

A single concentric circle on a single surface.

Cylinder

The collection of all the tracks (one for each surface) that are in the same relative location. The actuator arm moves all read/write heads to the same of this.

Read/Write Heads

These sense and record data along one cylinder at a time.

CHS

Addressing scheme for locating data on a disk which specifies a block’s location using the track, surface and sector.

cylinder, head, sector

CHS stands for ____ (track), ____ (surface), and ____.

cylinders, sectors, controller

In CHS, even though the outer ____ have a larger circumference, they have the same number of ____ and store the same amount of data. It was done this way because it is easy for the ____ to find the location based on those three parameters.

Logical Block Addressing

An addressing scheme that assigns sequential numbers to disk blocks, abstracting away their physical location.

disk positioning system

The ____ ____ ____ moves the arm to a specific cylinder and keeps it there. It resists physical shocks, imperfect tracks, etc.

Seek Time

The time it takes to move the arm to the correct cylinder.

speedup, coast, slowdown, settle

A seek consists of up to four phases:

1. ____ – accelerate the arm to the maximum speed or until the half way point

2. ____ – at max speed (for long seeks)

3. ____ – stops arm near destination

4. ____ – adjusts head to actual desired track

head, seek

____ switch times comparable to short ____ times.

catch error, overwrite

Writes require longer settle time than reads because:

• reads can ____ ____ and retry

• writes may ____ other tracks

1/3

Average seek time ≈ ____ of max seek time

Thermal Recalibration

Periodic adjustment of the disk’s actuator control parameters to compensate for temperature-induced changes and maintain accurate head positioning.

interface, blocks

The disk ____ typically presents the disk as a linear array of ____ called logical block addressing (LBA) rather than the older cylinder, head, sector (CHS) method

zoning, track skewing, sparing

The disk controller maps logical locations to physical locations.

• ____ – puts about 2.7x more blocks on larger (i.e. outside) cylinders.

• ____ ____ – sector 0 position varies by cylinder to improve sequential access times.

• ____ – flawed blocks (not properly storing data) are remapped to new locations

logical-to-physical, seek, non-linear, rotational, table

The kernel does not know the ____ mapping. Larger logical number differences generally imply larger ____ times, but the relationship is highly ____ and depends on the cylinder. The kernel also lacks ____ position information, but can empirically build a ____ to estimate access times.

seek, rotational latency, transfer

The time it takes to move data to or from a disk involves:

1. ____ time

2. ____ ____

3. ____ time

Seek Time

The time to move the disk arm to the target cylinder. It depends on the distance (in cylinders) between requests and ranges from 0 up to the maximum seek time.

Rotational Latency

The time for the desired block to rotate under the read/write head. It depends on disk speed and ranges from 0 to one full rotation time.

Transfer Time

The time for the desired block(s) to pass under the read/write head and be transferred. It depends on disk rotational speed and the number of blocks transferred.

Request Service Time

Seek Time + Rotational Latency + Transfer Time

disk controller

The ____ ____ controls the hardware and mediates access.

command queuing, read-ahead, write caching

Possible disk/interface features:

• ____ ____: allows multiple requests; enables scheduling based on head position and rotation.

• ____ (disk cache): prefetches sequential blocks to avoid full-rotation delays.

• ____ ____: delays writes for efficiency, but data may be lost on crash.

placement, ordering, faster, slower, crash

____ and ____ of I/O requests are critical: sequential access is much ____ than random, and long seeks are much ____ than short ones. Ordering must also consider ____ safety (e.g., soft updates).

seek, pending

Order requests to minimize ____ time: this requires multiple ____ requests (I/O concurrency), which the kernel uses to reorder, and is maximized by high-performance applications.

First Come First Served

A disk scheduling algorithm which processes the disk requests in the order they are received.

simple, fair, locality, latency, throughput

First Come First Served (FCFS) advantages: ____ to implement and ____ (requests served in arrival order). Disadvantages: cannot exploit ____ to minimize seek time, leading to higher average ____ and lower ____ compared to other methods.

Shortest Positioning Time First

A disk scheduling algorithm that selects the request requiring the least positioning time (seek time + rotational latency), minimizing access delay.

locality, starvation, mispredict, effective

Shortest Positioning Time First (SPTF) advantages: exploits ____ (nearby requests) to reduce seek time and increase throughput. Disadvantages: can cause ____ of distant requests and may ____ fastest request due to disk speed drift. Improvement (Aged SPTF): increases priority of older requests using ____ seek time (T_eff = T_pos - w * T_wait).

Elevator Scheduling

A disk scheduling algorithm which sweeps across the disk, servicing requests in order along one direction. Similar to SPTF but only selects requests in the current direction, reversing only when no further requests remain.

locality, bounded waiting, middle, SPTF

Elevator Scheduling (SCAN) advantages: exploits ____ of nearby requests and provides ____ ____ (avoids starvation). Disadvantages: ____ tracks receive better service (served in both directions) and may miss locality that ____ could exploit.

C-SCAN

A disk scheduling algorithm which sweeps in one direction only, then returns to the beginning (circular). Avoids favouring middle tracks, but the return sweep moves across the full disk without servicing requests.

Flash Drives

Storage devices that use electronic circuits (flash memory) instead of spinning disks, with no mechanical parts.

Flash Memory

A type of non-volatile storage that uses electronic circuits to store data, retaining information without power and requiring no mechanical parts.

blocks, pages

Flash memory is divided into ____, which are in turn subdivided into ____.

32KB, 4MB, 2, 4, 8

Flash memory organization: divided into blocks (____–____), each containing pages (____/____/____KB). Pages are the unit of read/write; blocks are the unit of erase.

page, 1, 1, 0, block, 0, 1, voltage

For flash memory, reads and writes occur at the smaller ____ level. Pages are initially set to all ____, and writing changes bits from ____ → ____ at the page level. However, overwriting or deleting requires operations at the larger ____ level. Changing bits from ____ → ____ requires high ____, which can only be applied to an entire block.

reads, erases, RAM, invalid, write, table, garbage

Writing/deleting in flash memory: naive approach ____ the whole block, ____ it (reset to 1s), updates in ____, and writes it back (slow). Instead, SSD controllers mark pages as ____, ____ to a new unused page, and update a translation ____; this requires ____ collection to reclaim invalid pages.

write, wear leveling

SSD limitations: each block supports a limited number of ____ cycles before becoming read-only (≈1,000 for consumer SSDs, ≈1,000,000 for enterprise). SSD controllers use ____ ____ to distribute writes evenly across blocks, balancing wear.

Wear Leveling

A technique used by SSD controllers to distribute writes evenly across memory blocks, ensuring they wear out at a similar rate.

single, multi, triple, quad

Currently there are four types of flash memory that are in use:

1. ____-level cells have 2 levels, which store 1 bit

2. ____-level cells have 4 levels, which store 2 bits

3. ____-level cells have 8 levels, which store 3 bits (typical in consumer products)

4. ____-level cells have 16 levels, which store 4 bits

As more levels are used, the cost per GB is cheaper, but it is slower to access data, and it wears out sooner.

Files

Persistent, named data objects.

persistent

When you edit a file, the change is not ____ until you save it.

Persistent Storage

Storage where data remains saved over time (e.g., after saving a file) and persists until explicitly deleted, even across system restarts.

Secondary Storage

The first state info we’ve seen that does not disappear at shutdown. It is persistent storage. Therefore, it is where all important state ultimately resides

named data objects, intermediate result

In the expression “c = (a+b)*2”

- a, b and c are ____ ____ ____ but

- (a+b) is not a named object. It is an ____ ____.

bytes

The data in a file consists of a sequence of numbered ____.

capacity, access

An upside to secondary storage is that it has a larger ____ (100 – 1,000x) than main memory. Downside, it’s slower to ____ (microseconds) compared to main memory (nanoseconds).

File Systems

The data structures and algorithms used to store, retrieve, and access files.

logical, virtual, physical

A file system can be separated out into three different layers (although sometimes the first two are combined into one layer):

1. ____ file system

2. ____ file system

3. ____ file system

Logical File System

Layer of file system that is the high-level API which a programmer sees (e.g. fopen, fscanf, fprintf, fclose). It manages file system information, e.g. which files are open for reading and writing, which are read-only.

Virtual File System

Layer of file system which is an abstraction of lower level file systems, presents multiple different underlying file systems (HDD, SDD, DVD, network drive) to the user as one, e.g. the user interface for macOS and Windows.

Physical File System

Layer of file system which represents how files are actually stored on physical media (e.g. track, sector, magnetic orientation).

File Descriptor

An integer handle used by a process to refer to an open file or I/O resource.

open

File system call which returns a file descriptor (or identifier or handle). Other file operations (e.g., read, write, lseek, close) for that process require this file descriptor as a parameter in order to identify this file from all the others.

close

File system call which invalidates a valid file descriptor for a process. The kernel tracks which file descriptors are currently valid for each process.

read

File system call which copies data from a file into a virtual address space.

write

File system call which copies data from a virtual address space into a file.

lseek

File system call which enables non-sequential reading and writing.

fstat

File system call which retrieves (gets) file metadata.