I/O subsystem, buffering and spooling

Why it exists

Programs need the keyboard, the disk, the network and the screen, but devices differ wildly (a keyboard delivers a byte now and then, a disk a block at a time, a network card thousands of packets a second), they are slow next to the CPU, and a program must not be allowed to use them as it likes. The I/O subsystem is the part of the operating system that hides the differences behind a small set of calls, shares the devices safely, overlaps the slow device with useful computation, and protects them. GATE asks what happens in which order when a device interrupts, how I/O is protected, what buffering, caching and spooling are and what they gain, how I/O requests interact with scheduling (a process that does I/O leaves the CPU and later returns to the ready queue), and how much a given buffering scheme saves.

Prerequisites

The hardware side (device registers, polling, interrupts and DMA) is on the I/O interface, interrupts and DMA pages; this page is about what the operating system does with it.

Precise definitions

Hardware parts. A device controller (or adapter) is the electronics that operates a device and has registers (status, command, data) that the CPU reads and writes. A device driver is the kernel module that knows one kind of controller and gives the kernel a uniform interface to it. An interrupt handler (interrupt service routine) is the kernel code that runs when the device signals completion.

How the CPU reaches the registers.

• Isolated (port-mapped) I/O: the registers have their own address space and special instructions (IN, OUT). These instructions are privileged, so a user program that tries them traps: that is the protection.
• Memory-mapped I/O: the registers appear at ordinary memory addresses, read and written with ordinary load and store instructions; no special I/O instruction exists to make privileged. Protection is then done by the operating system with the memory protection hardware: the pages that hold device registers are mapped only into the kernel's address space (a user program that touches them takes a protection fault), unless the OS deliberately maps them for one trusted process.

Three ways to move data.

What happens at an interrupt, in order: (1) the device raises the interrupt line; (2) the CPU finishes the current instruction; (3) it saves the state of the running process (program counter and status word) on the control stack; (4) it loads the new program counter from the interrupt vector for that device; (5) the interrupt service routine runs; (6) the saved state is restored and the interrupted process resumes (or another is chosen). The state is saved before the new program counter is loaded and the old one is restored last.

An I/O request through the layers. A process calls read (a system call); the kernel checks the arguments and whether the data is already in a buffer or cache; if not, it passes the request to the driver, which starts the device and the process is put to wait (moved from running to the device's wait queue); when the device finishes it interrupts, the handler completes the request and moves the process back to the ready queue: a process that does I/O enters the ready queue once more for every I/O that finishes.

Kinds of device and I/O call. Block devices (disks) transfer fixed-size blocks and allow random access; character devices (keyboard, serial line) deliver a stream of bytes; network devices have their own interface (sockets). A call can be:

• blocking: the process is suspended until the I/O completes;
• non-blocking: the call returns at once with whatever can be done now (possibly nothing, as an error such as "would block");
• asynchronous: the call returns at once and the whole transfer happens later; the process is told when it is complete (a flag, signal or callback).

Services of the kernel I/O subsystem. I/O scheduling (ordering the requests of each device, as in disk scheduling); buffering; caching; spooling and device reservation; error handling (retry, report); protection (users reach devices only through system calls).

Buffering. A buffer is a memory area that holds data while it moves between two parties. It is used (1) to match speeds (a fast producer and a slow consumer), (2) to match transfer sizes (a network message in packets, a file read in blocks), (3) to keep copy semantics (what is written is the data at the time of the call, even if the program changes its own copy before the device has taken it). Suppose each block takes $T$ to read from the device into a system buffer, $M$ to move from the system buffer to the process's area, and $C$ for the process to work on. The time per block in the steady state is

• no buffering (read, then compute): $T + C$;
• single buffer (the next read overlaps the processing, but the buffer must be emptied first): $\max(T, C) + M$;
• double buffer (the device fills one buffer while the process uses the other): $\max(T,\; C + M)$.

A circular buffer is a ring of more than two buffers, which smooths out bursts. Adding buffers cannot make the whole faster than the slower of the device and the process.

Caching, buffering and spooling. A cache holds a copy of data that also exists elsewhere, kept for speed (the original is still on disk). A buffer may hold the only copy of data in transit. Spooling (simultaneous peripheral operations on-line) stores the output for a device that cannot be shared, typically a printer, in a file on disk: each process writes its output to its own spool file, and a daemon sends the files to the printer one at a time. Several processes then appear to use the printer at once, nobody holds the printer while doing other work, and one source of deadlock disappears.

CPU utilisation and the degree of multiprogramming. If each of $n$ processes in memory waits for I/O a fraction $p$ of its time, independently of the others, the CPU is idle only when all $n$ are waiting: $\text{utilisation} = 1 - p^n$.

How it works

Interrupt sequence. The processor-level view: the device interrupts, the current instruction completes, the state is saved, the handler runs, the state is restored.

DMA. The CPU sets up the controller and goes on; the controller moves the block and interrupts once at the end.

What each method costs the CPU. A 4096-byte block from a slow device and from a fast one. A fast device cannot be served by an interrupt per byte at all: the CPU is overloaded.

What buffering buys. Ten blocks, three combinations of times. One buffer saves the overlap of reading and computing; a second buffer also hides the move; when the process is the bottleneck, nothing helps.

Why the operating system keeps several processes. While one process waits for its I/O, another can use the CPU.

Worked examples

#include <stdio.h>
 
#define MAXN 64
 
static int max(int a, int b) { return a > b ? a : b; }
 
/* time at which block n has been processed; buffers = 0 (read straight into the program's area), 1 or 2 */
static int total(int n, int T, int C, int M, int buffers) {
    if (buffers == 0) return n * (T + C);
    int read_end[MAXN] = {0}, move_end[MAXN] = {0}, comp_end[MAXN] = {0};
    for (int i = 1; i <= n; i++) {
        int start;
        if (buffers == 1) start = move_end[i - 1];                                  /* the buffer is free once the previous block has been copied out */
        else start = max(read_end[i - 1], i >= 2 ? move_end[i - 2] : 0);            /* the device fills the buffer that is free, one block at a time */
        read_end[i] = start + T;
        move_end[i] = max(read_end[i], comp_end[i - 1]) + M;                        /* the program is ready and the block has arrived */
        comp_end[i] = move_end[i] + C;
    }
    return comp_end[n];
}
 
int main(void) {
    int cases[2][3] = {{10, 5, 1}, {4, 10, 1}};                                      /* T, C, M */
    for (int k = 0; k < 2; k++) {
        int T = cases[k][0], C = cases[k][1], M = cases[k][2];
        printf("T=%d C=%d M=%d, 10 blocks: no buffer %d, single %d, double %d; per block %d, %d, %d\n", T, C, M,
               total(10, T, C, M, 0), total(10, T, C, M, 1), total(10, T, C, M, 2),
               total(11, T, C, M, 0) - total(10, T, C, M, 0), total(11, T, C, M, 1) - total(10, T, C, M, 1), total(11, T, C, M, 2) - total(10, T, C, M, 2));
    }
    return 0;
}

T=10 C=5 M=1, 10 blocks: no buffer 150, single 115, double 106; per block 15, 11, 10
T=4 C=10 M=1, 10 blocks: no buffer 140, single 114, double 114; per block 14, 11, 11

#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
 
static long calls_for(int fd, size_t total, size_t chunk) {
    static char buf[65536];
    long calls = 0;
    while (total > 0) {
        size_t k = total < chunk ? total : chunk;
        ssize_t w = write(fd, buf, k);
        if (w < 0) return -1;
        total -= (size_t)w;
        calls++;
    }
    return calls;
}
 
int main(void) {
    int p[2];
    if (pipe(p) != 0) return 1;
    if (fcntl(p[0], F_SETFL, fcntl(p[0], F_GETFL) | O_NONBLOCK) != 0) return 1;
    char buf[16];
    ssize_t n = read(p[0], buf, sizeof buf);
    printf("empty pipe, non-blocking read: returned %zd, error is 'would block': %s\n", n, (n < 0 && (errno == EAGAIN || errno == EWOULDBLOCK)) ? "yes" : "no");
    if (write(p[1], "hello", 5) != 5) return 1;
    n = read(p[0], buf, sizeof buf);
    printf("after writing 5 bytes, the same read returned %zd\n", n);
 
    int fd = open("/dev/null", O_WRONLY);
    if (fd < 0) return 1;
    size_t chunk[4] = {1, 512, 4096, 65536};
    for (int i = 0; i < 4; i++) printf("sending 65536 bytes in chunks of %5zu bytes: %ld write calls\n", chunk[i], calls_for(fd, 65536, chunk[i]));
    close(fd);
    return 0;
}

empty pipe, non-blocking read: returned -1, error is 'would block': yes
after writing 5 bytes, the same read returned 5
sending 65536 bytes in chunks of     1 bytes: 65536 write calls
sending 65536 bytes in chunks of   512 bytes: 128 write calls
sending 65536 bytes in chunks of  4096 bytes: 16 write calls
sending 65536 bytes in chunks of 65536 bytes: 1 write calls

Cheat box

Traps and GATE patterns

Connections

The interrupt and the DMA transfer are hardware mechanisms (interrupts, DMA); here the operating system builds buffering, caching and spooling on top of them. The request enters the kernel through a system call; the process waits and later returns to the ready queue as in the process state diagram. The disk is the device with the longest delays and has its own request ordering in disk scheduling. Spooling removes the "no sharing" condition for printers and so is one of the answers to deadlock.

PYQs

Three processes A, B and C each execute a loop of
100 iterations. In each iteration of the loop, a
process performs a single computation that requires
tc CPU milliseconds and then initiates a single I/O
operation that lasts for tio milliseconds. It is
assumed that the computer where the processes
execute has sufficient number of I/O devices and
the OS of the computer assigns different I/O
devices to each process. Also, the scheduling
overhead of the OS is negligible. The processes
have the following characteristics:

Process id
TC
Tio
A
100 ms
500 ms
B
350 ms
500 ms
C
200 ms
500 ms

The processes A, B, and C are started at times 0, 5
and 10 milliseconds respectively, in a pure time
sharing system (round robin scheduling) that uses a
time slice of 50 milliseconds. The time in
milliseconds at which process C would complete its
first
I/O
operation
is
___________.

Consider three processes, all arriving at time zero,
with total execution time of 10, 20, and 30 units,
respectively. Each process spends the first 20% of
execution time doing I/O, the next 70% of time doing
computation, and the last 10% of time doing I/O
again.

The operating system uses a shortest remaining
compute time first scheduling algorithm and
schedules a new process either when the running
process gets blocked on I/O or when the running
process finishes its compute burst. Assume that all
I/O operations can be overlapped as much as possible.

For what percentage of time does the CPU remain
idle?

Suppose in a multiprogramming environment, the
following C program segment is executed. A process
goes into I/O queue whenever an I/O related
operation is performed. Assume that there will always
be a context switch whenever a process requests for
an I/O, and also whenever the process returns from an
I/O. The number of times the process will enter the
ready queue during its lifetime (not counting the time
the process enters the ready queue when it is run
initially) is ______

Int main()
{

int x = 0, i = 0;

 scanf("%d", &x);

 for(i = 0; i < 20; i++)

 {

x = x + 20;

printf("%d\n", x);

 }

return 0;
}

OPERATING SYSTEMS

The following are some events that occur after a
device controller issues an interrupt while process L
is under execution:

P. The processor pushes the process status of L onto
the control stack
Q. The processor finishes the execution of the
current instruction
R. The processor executes the interrupt service routine
S. The processor pops the process status of L from
the control stack
T. The processor loads the new PC value based on
the interrupt

Which of the following is the correct order in which
the events above occur?

Normally user programs are prevented from
handling I/O directly by I/O instructions in them.
For CPUs having explicit I/O instructions, such I/O
protection is ensured by having the I/O instruction
privileged. In a CPU with memory mapped I/O,
there is no explicit I/O instruction. Which one of the
following is true for a CPU with memory mapped
I/O?

Self-check

Revision card

References