Structure of the I/O Subsystem

The I/O subsystem is the complex part of an operating system that manages every input and output operation. This chapter details the layered structure of the I/O subsystem, how each layer is implemented, how the interfaces are designed, and how the whole thing is put together.

Basic Concepts of the I/O Subsystem

1. Definition of the I/O Subsystem

The I/O subsystem is the system module that is specifically responsible for managing the various input and output devices, providing a uniform I/O interface, and coordinating the exchange of data between the CPU and external devices.

2. Role of the I/O Subsystem

• Device abstraction: hides hardware differences and offers a uniform interface
• Resource management: manages I/O devices and the resources around them
• Performance optimization: improves I/O performance through buffering, scheduling, and similar techniques
• Error handling: deals with errors and abnormal conditions during I/O operations

3. Characteristics of the I/O Subsystem

• Layered design: a layered architecture in which each layer is responsible for a specific function
• Modular implementation: the modules are relatively independent, which makes the system easier to maintain and extend
• Uniform interface: offers applications a single, consistent way to perform I/O
• Efficient management: raises I/O efficiency through a combination of techniques

Layered Structure of the I/O Subsystem

1. Overall Architecture

Four layers stack up from the hardware upwards: the user-level interface, the device-independent layer, the device driver layer, and the hardware control layer. Each one only talks to its neighbours, which is what makes the whole subsystem replaceable one layer at a time.

// Layered structure of the I/O subsystem
typedef struct {
    // User-level interface
    user_io_interface_t user_layer;

    // Device-independent layer
    device_independent_layer_t device_independent;

    // Device driver layer
    device_driver_layer_t driver_layer;

    // Hardware control layer
    hardware_control_layer_t hardware_layer;
} io_subsystem_t;

// User-level interface
typedef struct {
    // Standard I/O functions
    int (*open)(const char *path, int flags);
    int (*close)(int fd);
    int (*read)(int fd, void *buffer, int size);
    int (*write)(int fd, void *buffer, int size);
    int (*seek)(int fd, long offset, int whence);
    int (*ioctl)(int fd, int cmd, void *arg);

    // Advanced I/O functions
    int (*select)(int nfds, fd_set *readfds, fd_set *writefds,
                  fd_set *exceptfds, struct timeval *timeout);
    int (*poll)(struct pollfd *fds, int nfds, int timeout);
} user_io_interface_t;

2. User-Level Interface

Basic Function

The user-level interface gives applications a standardized set of I/O operations and hides the complexity underneath. A program calls open, read, or write and works with a small integer handle; it never needs to know which layer actually performs the transfer.

Implementation Example

// User-level I/O implementation
typedef struct {
    int fd;                  // File descriptor
    char *path;              // File path
    int flags;               // Open flags
    int mode;                // Access mode
    off_t offset;            // Current offset
    int ref_count;           // Reference count
} file_descriptor_t;

// File descriptor table
typedef struct {
    file_descriptor_t *fds;  // File descriptor array
    int max_fds;             // Maximum number of file descriptors
    int used_fds;            // Number of file descriptors in use
    mutex_t fd_mutex;        // File descriptor table mutex
} file_descriptor_table_t;

// Open a file
int user_open(const char *path, int flags) {
    file_descriptor_table_t *fd_table = get_fd_table();

    // Allocate a file descriptor
    int fd = allocate_file_descriptor(fd_table);
    if (fd == -1) {
        return -1; // No file descriptor could be allocated
    }

    // Call the device-independent layer to open the file
    int result = device_independent_open(path, flags, &fd_table->fds[fd]);
    if (result != 0) {
        free_file_descriptor(fd_table, fd);
        return -1;
    }

    return fd;
}

// Read a file
int user_read(int fd, void *buffer, int size) {
    file_descriptor_table_t *fd_table = get_fd_table();

    // Check that the file descriptor is valid
    if (fd < 0 || fd >= fd_table->max_fds || !fd_table->fds[fd].path) {
        return -1; // Invalid file descriptor
    }

    // Call the device-independent layer to read the file
    return device_independent_read(fd, buffer, size);
}

// Write a file
int user_write(int fd, void *buffer, int size) {
    file_descriptor_table_t *fd_table = get_fd_table();

    // Check that the file descriptor is valid
    if (fd < 0 || fd >= fd_table->max_fds || !fd_table->fds[fd].path) {
        return -1; // Invalid file descriptor
    }

    // Call the device-independent layer to write the file
    return device_independent_write(fd, buffer, size);
}

3. Device-Independent Layer

Basic Function

The device-independent layer implements the I/O operations that do not depend on any particular device and provides a uniform way of accessing devices. Buffering, scheduling, and permission checks live here, so that a new driver does not have to reimplement them.

Implementation Example

// Device-independent layer interface
typedef struct {
    // Device operation interface
    int (*device_open)(const char *path, int flags);
    int (*device_close)(int device_id);
    int (*device_read)(int device_id, void *buffer, int size);
    int (*device_write)(int device_id, void *buffer, int size);
    int (*device_seek)(int device_id, long offset, int whence);
    int (*device_ioctl)(int device_id, int cmd, void *arg);

    // Buffer management
    buffer_manager_t buffer_manager;

    // Device scheduling
    device_scheduler_t device_scheduler;

    // Error handling
    error_handler_t error_handler;
} device_independent_layer_t;

// Device-independent layer open operation
int device_independent_open(const char *path, int flags, file_descriptor_t *fd) {
    // Parse the path and determine the device type
    device_type_t device_type = parse_device_type(path);

    // Pick the matching driver for this device type
    device_driver_t *driver = get_device_driver(device_type);
    if (!driver) {
        return -1; // No matching driver was found
    }

    // Ask the driver to open the device
    int device_id = driver->open(path, flags);
    if (device_id == -1) {
        return -1; // The device could not be opened
    }

    // Initialize the file descriptor
    fd->fd = device_id;
    fd->path = strdup(path);
    fd->flags = flags;
    fd->offset = 0;
    fd->ref_count = 1;

    return 0;
}

// Device-independent layer read operation
int device_independent_read(int fd, void *buffer, int size) {
    file_descriptor_t *file_desc = get_file_descriptor(fd);
    device_driver_t *driver = get_device_driver_by_fd(fd);

    // Check the access permissions
    if (!(file_desc->flags & O_RDONLY) && !(file_desc->flags & O_RDWR)) {
        return -1; // No read permission
    }

    // Use the buffer manager
    buffer_manager_t *bm = get_buffer_manager();
    return buffer_manager_read(bm, fd, buffer, size);
}

// Device-independent layer write operation
int device_independent_write(int fd, void *buffer, int size) {
    file_descriptor_t *file_desc = get_file_descriptor(fd);
    device_driver_t *driver = get_device_driver_by_fd(fd);

    // Check the access permissions
    if (!(file_desc->flags & O_WRONLY) && !(file_desc->flags & O_RDWR)) {
        return -1; // No write permission
    }

    // Use the buffer manager
    buffer_manager_t *bm = get_buffer_manager();
    return buffer_manager_write(bm, fd, buffer, size);
}

4. Device Driver Layer

Basic Function

The device driver layer implements the communication with concrete hardware devices and provides the device-specific operations. A driver is the only place that has to know how the hardware really behaves.

Implementation Example

// Device driver layer interface
typedef struct {
    // Driver registry
    driver_registry_t driver_registry;

    // Device management
    device_manager_t device_manager;

    // Interrupt handling
    interrupt_handler_t interrupt_handler;

    // DMA management
    dma_manager_t dma_manager;
} device_driver_layer_t;

// Driver registry
typedef struct {
    device_driver_t *drivers[MAX_DRIVERS];  // Driver array
    int driver_count;                       // Number of drivers
    mutex_t registry_mutex;                 // Registry mutex
} driver_registry_t;

// Register a device driver
int register_device_driver(device_driver_t *driver) {
    driver_registry_t *registry = get_driver_registry();

    lock_mutex(&registry->registry_mutex);

    if (registry->driver_count >= MAX_DRIVERS) {
        unlock_mutex(&registry->registry_mutex);
        return -1; // The driver table is full
    }

    // Add it to the driver table
    registry->drivers[registry->driver_count] = driver;
    registry->driver_count++;

    unlock_mutex(&registry->registry_mutex);
    return 0;
}

// Look up a driver
device_driver_t *find_device_driver(device_type_t device_type) {
    driver_registry_t *registry = get_driver_registry();

    lock_mutex(&registry->registry_mutex);

    for (int i = 0; i < registry->driver_count; i++) {
        if (registry->drivers[i]->device_type == device_type) {
            unlock_mutex(&registry->registry_mutex);
            return registry->drivers[i];
        }
    }

    unlock_mutex(&registry->registry_mutex);
    return NULL; // No matching driver was found
}

5. Hardware Control Layer

Basic Function

The hardware control layer interacts with the hardware devices directly and implements the low-level control operations, down to port I/O and memory-mapped registers.

Implementation Example

// Hardware control layer interface
typedef struct {
    // Hardware abstraction layer
    hardware_abstraction_layer_t hal;

    // Interrupt controller
    interrupt_controller_t interrupt_controller;

    // DMA controller
    dma_controller_t dma_controller;

    // Bus management
    bus_manager_t bus_manager;
} hardware_control_layer_t;

// Hardware abstraction layer
typedef struct {
    // Port I/O operations
    int (*port_read)(int port);
    void (*port_write)(int port, int value);

    // Memory-mapped I/O operations
    int (*mmio_read)(void *address);
    void (*mmio_write)(void *address, int value);

    // Interrupt operations
    void (*enable_interrupt)(int irq);
    void (*disable_interrupt)(int irq);
    void (*ack_interrupt)(int irq);
} hardware_abstraction_layer_t;

// Port I/O read operation
int hal_port_read(int port) {
    // Implement the concrete port read for each architecture
    #ifdef X86_ARCHITECTURE
        return inb(port);
    #elif defined(ARM_ARCHITECTURE)
        return arm_port_read(port);
    #else
        return generic_port_read(port);
    #endif
}

// Port I/O write operation
void hal_port_write(int port, int value) {
    // Implement the concrete port write for each architecture
    #ifdef X86_ARCHITECTURE
        outb(port, value);
    #elif defined(ARM_ARCHITECTURE)
        arm_port_write(port, value);
    #else
        generic_port_write(port, value);
    #endif
}

Core Components of the I/O Subsystem

1. Buffer Management System

Buffer Manager

The buffer manager owns the pool of buffers, the strategy used to fill them, the scheduling of buffer operations, and the monitoring that reports on their behavior.

// Buffer manager
typedef struct {
    // Buffer pool
    buffer_pool_t buffer_pool;

    // Buffer strategy
    buffer_strategy_t buffer_strategy;

    // Buffer scheduling
    buffer_scheduler_t buffer_scheduler;

    // Performance monitoring
    buffer_monitor_t buffer_monitor;
} buffer_manager_t;

// Buffer pool
typedef struct {
    buffer_t *buffers;       // Buffer array
    int buffer_count;        // Number of buffers
    int free_buffers;        // Number of free buffers
    mutex_t pool_mutex;      // Pool mutex
    semaphore_t free_sem;    // Free-buffer semaphore
} buffer_pool_t;

// Allocate a buffer
buffer_t *allocate_buffer(buffer_pool_t *pool) {
    wait_semaphore(&pool->free_sem);
    lock_mutex(&pool->pool_mutex);

    // Look for a free buffer
    for (int i = 0; i < pool->buffer_count; i++) {
        if (pool->buffers[i].status == BUFFER_FREE) {
            pool->buffers[i].status = BUFFER_IN_USE;
            pool->free_buffers--;
            unlock_mutex(&pool->pool_mutex);
            return &pool->buffers[i];
        }
    }

    unlock_mutex(&pool->pool_mutex);
    return NULL; // No free buffer is available
}

// Release a buffer
void free_buffer(buffer_pool_t *pool, buffer_t *buffer) {
    lock_mutex(&pool->pool_mutex);

    buffer->status = BUFFER_FREE;
    pool->free_buffers++;

    unlock_mutex(&pool->pool_mutex);
    signal_semaphore(&pool->free_sem);
}

2. Device Scheduling System

Device Scheduler

The scheduler keeps one request queue per device, chooses an algorithm for ordering the requests, and records statistics and control state for the queue.

// Device scheduler
typedef struct {
    // Scheduling queues
    device_queue_t *queues[MAX_DEVICES];

    // Scheduling algorithm
    scheduling_algorithm_t algorithm;

    // Scheduling statistics
    scheduling_stats_t stats;

    // Scheduling control
    scheduling_control_t control;
} device_scheduler_t;

// Device queue
typedef struct {
    io_request_t *requests;  // Request queue
    int head;                // Head of the queue
    int tail;                // Tail of the queue
    int count;               // Queue length
    int max_size;            // Maximum length
    mutex_t queue_mutex;     // Queue mutex
} device_queue_t;

// Add an I/O request
int add_io_request(device_queue_t *queue, io_request_t *request) {
    lock_mutex(&queue->queue_mutex);

    if (queue->count >= queue->max_size) {
        unlock_mutex(&queue->queue_mutex);
        return -1; // The queue is full
    }

    queue->requests[queue->tail] = *request;
    queue->tail = (queue->tail + 1) % queue->max_size;
    queue->count++;

    unlock_mutex(&queue->queue_mutex);
    return 0;
}

// Fetch the next I/O request
io_request_t *get_next_io_request(device_queue_t *queue) {
    lock_mutex(&queue->queue_mutex);

    if (queue->count == 0) {
        unlock_mutex(&queue->queue_mutex);
        return NULL; // The queue is empty
    }

    io_request_t *request = &queue->requests[queue->head];
    queue->head = (queue->head + 1) % queue->max_size;
    queue->count--;

    unlock_mutex(&queue->queue_mutex);
    return request;
}

3. Error Handling System

Error Handler

The error handler keeps the catalog of error types, the function associated with each type, the statistics that count what happened, and the recovery machinery.

// Error handler
typedef struct {
    // Error type definitions
    error_type_t error_types[MAX_ERROR_TYPES];

    // Error handling functions
    error_handler_t error_handlers[MAX_ERROR_TYPES];

    // Error statistics
    error_stats_t error_stats;

    // Error recovery
    error_recovery_t error_recovery;
} error_handler_t;

// Error handling function
void handle_io_error(int device_id, error_type_t error_type, int error_code) {
    error_handler_t *handler = get_error_handler();

    // Update the error statistics
    handler->error_stats.total_errors++;
    handler->error_stats.error_counts[error_type]++;

    // Invoke the matching error handling function
    if (handler->error_handlers[error_type]) {
        handler->error_handlers[error_type](device_id, error_code);
    }

    // Try to recover from the error
    if (handler->error_recovery.recovery_enabled) {
        attempt_error_recovery(device_id, error_type);
    }
}

Performance Optimization of the I/O Subsystem

1. Asynchronous I/O

Asynchronous I/O Implementation

With asynchronous I/O the caller submits a request and returns immediately; a background thread performs the transfer and records the completion. The program is therefore not tied to the speed of the device.

// Asynchronous I/O structure
typedef struct {
    // Asynchronous I/O requests
    async_io_request_t *requests;
    int request_count;
    int max_requests;

    // Asynchronous I/O completion queue
    async_io_completion_t *completions;
    int completion_count;

    // Asynchronous I/O thread
    pthread_t async_thread;
    int thread_running;

    // Synchronization primitives
    mutex_t request_mutex;
    semaphore_t request_sem;
    mutex_t completion_mutex;
} async_io_manager_t;

// Submit an asynchronous I/O request
int submit_async_io_request(async_io_request_t *request) {
    async_io_manager_t *manager = get_async_io_manager();

    lock_mutex(&manager->request_mutex);

    if (manager->request_count >= manager->max_requests) {
        unlock_mutex(&manager->request_mutex);
        return -1; // The request queue is full
    }

    // Append the request to the queue
    manager->requests[manager->request_count] = *request;
    manager->request_count++;

    unlock_mutex(&manager->request_mutex);
    signal_semaphore(&manager->request_sem);

    return 0;
}

// Asynchronous I/O worker thread
void *async_io_thread(void *arg) {
    async_io_manager_t *manager = (async_io_manager_t*)arg;

    while (manager->thread_running) {
        // Wait for an I/O request
        wait_semaphore(&manager->request_sem);

        lock_mutex(&manager->request_mutex);

        // Process all pending requests
        for (int i = 0; i < manager->request_count; i++) {
            async_io_request_t *request = &manager->requests[i];

            // Perform the I/O operation
            int result = execute_io_operation(request);

            // Build the completion event
            async_io_completion_t completion;
            completion.request_id = request->request_id;
            completion.result = result;
            completion.error_code = (result < 0) ? errno : 0;

            // Add it to the completion queue
            add_completion_event(manager, &completion);
        }

        manager->request_count = 0;
        unlock_mutex(&manager->request_mutex);
    }

    return NULL;
}

2. I/O Multiplexing

Multiplexing Implementation

Multiplexing lets one thread wait on many descriptors at once. select blocks until one of the registered descriptors becomes ready, and the layer then dispatches the event to the handler registered for that descriptor.

// I/O multiplexer manager
typedef struct {
    // File descriptor sets
    fd_set read_fds;
    fd_set write_fds;
    fd_set except_fds;

    // Maximum file descriptor
    int max_fd;

    // Timeout setting
    struct timeval timeout;

    // Event handling
    event_handler_t event_handlers[MAX_FDS];
} io_multiplexer_t;

// Multiplexing wait
int io_multiplex_wait(io_multiplexer_t *multiplexer) {
    fd_set read_fds = multiplexer->read_fds;
    fd_set write_fds = multiplexer->write_fds;
    fd_set except_fds = multiplexer->except_fds;

    // Call the select system call
    int result = select(multiplexer->max_fd + 1,
                       &read_fds, &write_fds, &except_fds,
                       &multiplexer->timeout);

    if (result > 0) {
        // Handle the file descriptors that are ready
        for (int fd = 0; fd <= multiplexer->max_fd; fd++) {
            if (FD_ISSET(fd, &read_fds)) {
                handle_read_event(multiplexer, fd);
            }
            if (FD_ISSET(fd, &write_fds)) {
                handle_write_event(multiplexer, fd);
            }
            if (FD_ISSET(fd, &except_fds)) {
                handle_except_event(multiplexer, fd);
            }
        }
    }

    return result;
}

---

Glossary