Operating Systems – CSCI 402
Simple I/O Architecture
Bus
Controller Controller Controller Controller
Memory
memory-mapped I/O
Disk
all controllers listen on the bus to determine if a request
is for itself or not
memory controller behaves differently from other controllers, i.e., it passes the bus request to primary memory
others “process” the bus request
and respond to relatively few addresses if no one responds, you get a “bus error”
memory is not really a “device”
321 0
25
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Bus
Controller Controller Controller Controller
Memory
memory-mapped I/O
two categories of devices
Disk
PIO (programmed I/O)
perform I/O operations by reading or writing data in the controller registers one byte or word at a time over the bus
26
321 0
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
I/O read
Bus
Memory
memory-mapped I/O
two categories of devices
Disk
PIO (programmed I/O)
perform I/O operations by reading or writing data in the controller registers one byte or word at a time over the bus
27
321 0
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
write
Bus
Memory
memory-mapped I/O
two categories of devices
Disk
PIO (programmed I/O)
perform I/O operations by reading or writing data in the controller registers one byte or word at a time over the bus
28
321 0
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
read
Bus
Memory
memory-mapped I/O
two categories of devices
Disk
PIO (programmed I/O)
perform I/O operations by reading or writing data in the controller registers one byte or word at a time over the bus
29
321 0
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
I/O write
Bus
Memory
memory-mapped I/O
two categories of devices
Disk
PIO (programmed I/O)
perform I/O operations by reading or writing data in the controller registers one byte or word at a time over the bus
30
321 0
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Bus
Controller Controller Controller Controller
Memory
memory-mapped I/O
two categories of devices
PIO (programmed I/O)
DMA (direct memory access)
Disk
the controller performs the I/O itself
the processor writes to the controller to tell it where to transfer the results to
the controller takes over and transfers data between itself and primary memory
321 0
31
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
I/O write (to setup memory/device locations)
Memory
memory-mapped I/O
two categories of devices
PIO (programmed I/O)
DMA (direct memory access)
Disk
the controller performs the I/O itself
the processor writes to the controller to tell it where to transfer the results to
the controller takes over and transfers data between itself and primary memory
321 0
32
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
direct memory data transfer
Memory
memory-mapped I/O
two categories of devices
PIO (programmed I/O)
DMA (direct memory access)
Disk
the controller performs the I/O itself
the processor writes to the controller to tell it where to transfer the results to
the controller takes over and transfers data between itself and primary memory
321 0
33
Copyright ý . Systems – CSCI 402
Simple I/O Architecture
Controller Controller Controller Controller
interrupt (I¡¯m done)
Memory
memory-mapped I/O
two categories of devices
PIO (programmed I/O)
DMA (direct memory access)
Disk
the controller performs the I/O itself
the processor writes to the controller to tell it where to transfer the results to
the controller takes over and transfers data between itself and primary memory
321 0
34
Copyright ý . IO Registers
This is the abstraction of a PIO device
a “register” is just a memory-mapped I/O address on the bus
Control register (1 byte) Status register (1 byte) Read register (1 byte) Write register (1 byte)
Go read (start a read operation)
Operating Systems – CSCI 402
GoR
GoW
IER
IEW
RdyR
RdyW
Legend: GoR
GoW Go write (start a write operation) IER Enable read-completion interrupts IEW Enable write-completion interrupts RdyR Ready to read
RdyW Ready to write
35
321 0
Copyright ý . Systems – CSCI 402
Programmed I/O
E.g.: Terminal controller
Procedure (write)
write a byte into the write register
set the GoW bit (and optionally the IEW bit if you¡¯d like to be notified via an interrupt) in the control register
poll and wait for RdyW bit (in status register) to be set (if interrupts have been enabled, an interrupt occurs when this happens)
36
321 0
Copyright ý . MA Registers
This is the abstraction of a DMA device
a “register” is just a memory-mapped I/O address on the bus
Operating Systems – CSCI 402
Go
IE
Op Code
Rdy
Control register (1 byte) Status register (1 byte)
Memory address register (4 bytes)
Device address register (4 bytes)
Legend:
Go
Op Code IE
Rdy
Start an operation
Operation code (identifies the operation) Enable interrupts
Controller is ready
37
321 0
Copyright ý . Systems – CSCI 402
Direct Memory Access
E.g.: Disk controller
Procedure
set the disk address in the device address register (only relevant for a seek request)
set the buffer address in the memory address register
set the op code (SEEK, READ or WRITE), the Go bit and, if desired, the IE bit in the control register
wait for interrupt or for Rdy bit to be set
38
321 0
Copyright ý . Systems – CSCI 402
Device Drivers
Who knows how to use memory-mapped I/O to talk to devices?
not the kernel developers
device manufacturers do
it¡¯s desirable if kernel is device-independent
but how?
39
321 0
Copyright ý . Systems – CSCI 402
Device Drivers
Who knows how to use memory-mapped I/O to talk to devices?
not the kernel developers
device manufacturers do
it¡¯s desirable if kernel is device-independent
but how?
Device manufacturers package their knowledge into device drivers
OS
Disk Driver
NIC Driver
Keyboard Driver
memory mapped I/O
Disk 1
Disk 2
NIC
Keyboard
40
321 0
Copyright ý . evice Drivers
Operating Systems – CSCI 402
Common Data
read write interrupt
Device Driver
Device drivers provide a standard interface to the rest of the OS code in device drivers knows how to talk to devices (the rest of the OS really doesn¡¯t know the details)
OS can treat I/O in a device-indepdendent manner by calling functions in the standard interface
“interface” = array of function pointers Copyright ý . Cheng
321 0
41
C++ polymorphism achieved using virtual base class or interface each type of disk driver is a subclass of the disk class and has its own implementation of these functions
each disk driver looks like a generic disk to the OS
this gets compiled into an array of function pointers (which is what C++ code gets compiled into)
in reality, there are no object classes and no polymorphism the CPU doesn¡¯t even know about data structures
the CPU only knows about memory addresses and
how to execute machine instructions
321 0
Operating Systems – CSCI 402
C++ Interface = Array of Function Pointers
class disk {
public:
virtual status_t read(request_t) = 0;
virtual status_t write(request_t) = 0;
virtual status_t interrupt( ) = 0;
};
42
Copyright ý . Cheng
struct disk {
void **disk_ops;
…
}
(void *)wd123_disk_ops[] = {
read_handler_t wd123_read;
write_handler_t wd123_write;
intr_handler_t wd123_intr;
…
}
(void *)sg76_disk_ops[] = {
read_handler_t sg76_read;
write_handler_t sg76_write;
intr_handler_t sg76_intr;
…
}
struct disk *d = …;
d->disk_ops = wd123_disk_ops; /* known as “binding” */
/* or d->disk_ops = sg76_disk_ops; */
to read from any disk, call the first function indirectly
(*((read_handler_t)d->disk_ops[0]))(…); Copyright ý . Cheng
321 0
43
Operating Systems – CSCI 402
C Impmlementation of C++ Polymorphism
class disk {
public:
virtual status_t read(request_t) = 0;
virtual status_t write(request_t) = 0;
virtual status_t interrupt( ) = 0;
};
… in C++
This is a synchronous interface
a user thread would call read/write() system call
these functions are called in the kernel which starts the device the device driver¡¯s interrupt method is called in the interrupt context
if I/O is completed, the thread is unblocked and return from the read/write() system call
Operating Systems – CSCI 402
44
321 0
Copyright ý . Cheng
class disk {
public:
A Bit More Realistic
virtual handle_t start_read(request_t) = 0;
virtual handle_t start_write(request_t) = 0;
virtual status_t wait(handle_t) = 0;
virtual status_t interrupt( ) = 0;
};
Even in Sixth-Edition Unix, the internal driver interface is often
asynchronous
start_read/start_write() returns a handle identifying the operation that has started
a thread can call the wait() method to synchronously wait for I/O completion
Operating Systems – CSCI 402
45
321 0
Copyright ý . /O Processors: Channels
Channel
Channel
Channel
when I/O costs dominate computation costs
Controller
Controller
Controller
Operating Systems – CSCI 402
Memory
use I/O processors (a.k.a. channels) to handle much of the I/O work
important in large data-processing applications
can even download program into a channel processor
321 0
46
Copyright ý . Systems – CSCI 402
3.3 Dynamic Storage Allocation
Best-fit & First-fit Algorithms
Buddy System Slab Allocation
47
321 0
Copyright ý . Systems – CSCI 402
Dynamic Storage Allocation
Where in the kernel do you need to do memory allocation?
stack space
malloc()
fork()
various OS data structures
process control block thread control block mutex (it¡¯s a queue)
etc.
Memory allocator
computer science people like to personify things
just like we say that a variable “lives” in an address space
a “memory allocator” is simply a collection of functions
it¡¯s not a thread it¡¯s not a process
48
321 0
Copyright ý . ynamic Storage Allocation
Goal: allow dynamic creation and destruction of data structures
use “memory allocator” to manage a large block of memory (i.e., a collection of contiguous memory addresses)
contract with application:
application will not touch anything owned by the memory allocator (memory allocator can do anything with them) application will only touch “allocated memory blocks” (memory allocator promises not to touch these)
very bad things can happen if contract is violated assuming that there are no bugs in a memory allocator
Concerns:
efficient use of storage efficient use of processor time
Example:
first-fit vs. best-fit allocation Copyright ý . Cheng
321 0
49
Operating Systems – CSCI 402
Allocate 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
Allocation Example
1300 bytes free (first) 1200 bytes free (last)
Operating Systems – CSCI 402
50
321 0
Copyright ý . Systems – CSCI 402
Allocation Example
1300 bytes free (first) 1200 bytes free (last)
Allocate 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
300 1200
51
321 0
Copyright ý . Example
1300 bytes free (first) 1200 bytes free (last)
300 1200
300 100
Operating Systems – CSCI 402
Allocate 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
52
321 0
Copyright ý . 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
1300 bytes free (first) 1200 bytes free (last)
Operating Systems – CSCI 402
Allocation Example
300 1200
300 100
50 100
321 0
53
Copyright ý . Systems – CSCI 402
Allocation Example
1300 bytes free (first) 1200 bytes free (last)
Allocate 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
300 1200
300 100
50 100
1300 200
321 0
54
Copyright ý . 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
Allocation Example
1300 bytes free (first) 1200 bytes free (last)
300 1200
300 100
50 100
1300 200
200 200
Operating Systems – CSCI 402
55
321 0
Copyright ý . 1000 bytes:
Allocate 1100 bytes:
Allocate 250 bytes:
First Fit
Allocation Example
1300 bytes free (first) 1200 bytes free (last)
300 1200
300 100
50 100
1300 200
200 200
200 200
321 0
Operating Systems – CSCI 402
Stuck!
56
Copyright ý . Systems – CSCI 402
Fragmentation
First-fit vs. best-fit allocation
studies have shown that first-fit works better
best-fit tends to leave behind a large number of regions of memory that are too small to be useful
best-fit tends to create smallest left-over blocks!
this is the general problem of fragmentation
internal fragmentation: unusable memory is contained within an allocated region (e.g., buddy system)
external fragmentation: unusable memory is separated into small blocks and is interspersed by allocated memory (e.g., best-fit)
57
321 0
Copyright ý . Cheng