Transcript CENG334 Introduction to Operating Systems

CENG334
Introduction to Operating Systems
I/O systems
Topics:
Erol Sahin
Dept of Computer Eng.
Middle East Technical University
Ankara, TURKEY
URL: http://kovan.ceng.metu.edu.tr/~erol/Courses/CENG334
I/O systems




The two main jobs of a computer are I/O and
processing.
A computer without I/O support is more like a
turkey who is claimed to think but not speak..
Hence, I/O is an essential part of an operating
system.
In many cases, the main job is I/O and the
processing is merely incidental.


browse a web page or
edit a file
2
I/O devices




Widely vary in in their types and
characteristics, hence their interfacing
within the OS.
I/O-device technology exhibits two
conflicting trends.
 increasing standardization of software
and hardware interfaces.
 increasingly broad variety of I/O
devices.
Hardware
 Ports
 Buses
 Device controllers
Software
 Device drivers present a uniform
device-access interface to the I/O
subsystem,
 Similar to system calls providing a
standard interface between the
application and the operating
system.
3
Modern I/O Systems
Slide from Kubiatowichz
4
I/O Hardware
General Categories





storage devices (disks, tapes),
transmission devices (network cards,
modems),
human-interface devices (screen,
keyboard, mouse),
Specialized devices
5
I/O Devices: Hardware interfacing


Interfacing medium
 Wired
 wireless
Interfacing Components
 Port: one device can be
connected (e.g. serial port)
 Bus: More than one device
 Device controller
6
Memory-Mapped I/O (1)


How can the processor give commands and data to a controller to accomplish an I/O
transfer?
 controller has one or more registers for data and control signals.
 processor communicates with the controller by reading and writing bit patterns in these
registers
How to write and read these registers
 Specialized I/O instructions
 Memory-mapped I/O
 Pros and cons?
 Hybrid
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
7
Memory-Mapped I/O (2)
(a) A single-bus architecture. (b) A dual-bus memory architecture.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
8
Device I/O port locations on PC
9
I/O ports

An I/O port typically consists of four registers,
 status register contains bits that can be read
by the host.
 These bits indicate states such as
whether the current command has
completed, whether a byte is available
to be read from the data-in register, and
whether there has been a device error.
 control register can be written by the host
 to start a command or
 to change the mode of a device.
 data-in register is read by the host to get
input.
 data-out register is written by the host to
send output.
status
control
data-in
data-out
10
I/O interfacing in SW: Polling
A typical interaction loop
1. The host repeatedly reads the busy bit until that bit
becomes clear
2. The host sets the write bit in the command register
and writes a byte into the data-out register.
3. The host sets the command-ready bit.
4. When the controller notices that the command-ready
bit is set, it sets the busy bit.
5. The controller reads the command register and sees
the write command. It reads the data-out register to
get the byte, and does the I/O to the device.
6. The controller clears the command-ready bit, clears
the error bit in the status register to indicate that the
device I/O succeeded, and clears the busy bit to
indicate that it is finished.
status
control
data-in
data-out
11
I/O interfacing in SW: Polling
Polling typically requires three CPU-instruction
cycles



read a device register,
logical–and to extract a status bit, and
branch if not zero.
status
control
data-in
data-out
12
I/O interfacing in SW: Polling
A typical interaction loop
1. The host repeatedly reads the busy bit until that bit
becomes clear
2. The host sets the write bit in the command register
and writes a byte into the data-out register.
3. The host sets the command-ready bit.
4. When the controller notices that the command-ready
bit is set, it sets the busy bit.
5. The controller reads the command register and sees
the write command. It reads the data-out register to
get the byte, and does the I/O to the device.
6. The controller clears the command-ready bit, clears
the error bit in the status register to indicate that the
device I/O succeeded, and clears the busy bit to
indicate that it is finished.
status
control
data-in
data-out
13
Programmed I/O (1)
Steps in printing a string.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
14
Programmed I/O (2)
Writing a string to the printer using programmed I/O.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
15
Interrupts Revisited
How an interrupt happens. The connections between the devices and the
interrupt controller actually use interrupt lines on the bus rather than
dedicated wires.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
16
Interrupt servicing
Interrupt mechanism needs

Address: to select a specific interrupt handling routine


Typically an offset in a table called interrupt vector
which contains addresses of interrupt handlers
17
I/O interfacing: Interrupts


CPU hardware has a wire called the
interrupt-request line that the CPU
senses after executing every
instruction.
Upon interrupt, the CPU saves
 a small amount of state, such
as the current value of the
instruction pointer, and
 jumps to the interrupt-handler
routine at a fixed address in
memory.
 interrupt handler determines
the cause of the interrupt,
performs the necessary
processing, and
 executes a return from interrupt
instruction to return the CPU to
the execution state prior to the
interrupt.
18
Interrupt Handlers (1)
Save registers not already been saved by interrupt
hardware.
Set up a context for the interrupt service procedure.
Set up a stack for the interrupt service procedure.
Acknowledge the interrupt controller. If there is no
centralized interrupt controller, reenable interrupts.
Copy the registers from where they were saved to the
process table.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
19
Interrupt Handlers (2)
Run the interrupt service procedure.
Choose which process to run next.
Set up the MMU context for the process to run next.
Load the new process’ registers, including its PSW.
Start running the new process.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
20
Interrupt-Driven I/O
Writing a string to the printer using interrupt-driven I/O. (a) Code
executed at the time the print system call is made. (b) Interrupt
service procedure for the printer.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
21
Interrupts (other good uses than I/O)
Virtual memory paging



A page fault is an exception that raises an interrupt.
The interrupt suspends the current process and jumps to the
page-fault handler in the kernel.
This handler
 saves the state of the process,
 moves the process to the wait queue,
 performs page-cache management,
 schedules an I/O operation to fetch the page,
 schedules another process to resume execution,
 and then returns from the interrupt
22
Interrupts (other good uses than I/O)
System Call (low-priority interrupt)





checks the arguments given by the application,
builds a data structure to convey the arguments to the kernel, and
then executes a special instruction called a software interrupt (or a trap).
This instruction has an operand that identifies the desired kernel service.
When the system call executes the trap instruction, the interrupt hardware
saves the state of the user code, switches to supervisor mode, and dispatches
to the kernel routine that implements the requested service.
23
Interrupt servicing: Advanced
Modern interrupt controllers provide



The ability to defer interrupt handling during critical processing
Efficient way to dispatch the proper interrupt handle w/o polling
all the devices
Multi-level interrupts, to distinguish low and high priority
interrupts
Most CPU’s have two interrupt request lines

Nonmaskable


Reserved for unrecoverable errors
Maskable


Used by device controllers
Can be turned off before the execution of critical instruction
sequences
24
Interrupt servicing: Advanced (cont)
Interrupt mechanism needs

Address: to select a specific interrupt handling routine



What if there are more devices than the interrupt vector size?


Typically an offset in a table called interrupt vector
which contains addresses of interrupt handlers
Interrupt chaining
Interrupt priority levels


defer the handling of low-priority interrupts without masking off all interrupts,
and makes it possible for a high-priority interrupt to pre-empt the execution of a
low-priority interrupt.
25
Direct Memory Access
For a device that does large transfers, such as a disk drive, it seems wasteful to use
an expensive general-purpose processor to watch status bits and to feed data into a
controller register 1 byte at a time—a process termed programmed I/O
Avoid burdening the main CPU with PIO by offloading some of this work to a specialpurpose processor called a direct-memory-access (DMA) controller.



To initiate a DMA transfer, the host writes a DMA command block into memory.
 a pointer to the source of a transfer,
 a pointer to the destination of the transfer, and
 a count of the number of bytes to be transferred.
The CPU writes the address of this command block to the DMA controller, then goes on
with other work.
The DMA controller proceeds to operate the memory bus directly,
 placing addresses on the bus to perform transfers without the help of the main
CPU. A simple DMA controller is a standard component in PCs, and bus-mastering
I/O boards for the PC usually contain their own high-speed DMA hardware
26
Operation of DMA
27
I/O Using DMA
Printing a string using DMA. (a) Code executed when the print system
call is made. (b) Interrupt service procedure.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
28
Application I/O interface
The Goal is to


abstract away the detailed differences in I/O devices by identifying a few general kinds.
Each general kind is accessed through a standardized set of functions—an interface
29
Characteristics of I/O devices

Character-stream or block


Sequential or random-access


A sharable device can be used concurrently by several processes or threads; a dedicated
device cannot.
Speed of operation


A synchronous device is one that performs data transfers with predictable response times. An
asynchronous device exhibits irregular or unpredictable response times.
Sharable or dedicated


A sequential device transfers data in a fixed order determined by the device, whereas the
user of a random-access device can instruct the device to seek to any of the available data
storage locations.
Synchronous or asynchronous


A character-stream device transfers bytes one by one, whereas a block device transfers a
block of bytes as a unit.
Device speeds range from a few bytes per second to a few gigabytes per second.•
Read–write, read only, or write only

Some devices perform both input and output, but others support only one data direction
30
Application I/O interfacing



For the purpose of application access, many of these differences are hidden by the
operating system, and the devices are grouped into a few conventional types.
The resulting styles of device access have been found to be useful and broadly
applicable. Although the exact system calls may differ across operating systems,
the device categories are fairly standard. The major access conventions include
Device categories






block I/O,
character-stream I/O,
memory-mapped file access, and
network sockets.
Operating systems also provide special system calls to access a few additional
devices, such as a time-of-day clock and a timer. Some operating systems provide
a set of system calls for graphical display, video, and audio devices.
escape (or back door) that transparently passes arbitrary commands from an
application to a device driver. In UNIX, this system call is ioctl() (for I/O control).
31
Block and character devices
The block-device interface captures all the aspects necessary for
accessing disk drives and other block-oriented devices.

read() and write() , and, if it is a random-access device, it has a seek() command
to specify which block to transfer next.
Applications normally access such a device through a file-system
interface. The operating system itself, and special applications such
as database-management systems, may prefer to access a block
device as a simple linear array of blocks. This mode of access is
sometimes called raw I/O.
32
Block and character devices
A keyboard is an example of a device that is accessed through a
character-stream interface.



get() or put() one character.
On top of this interface, libraries can be built that offer line-at-a-time
access, with buffering and editing services (for example, when a user
types a backspace, the preceding character is removed from the
input stream).
Example devices:

Keyboard, modem, mouse
33
Network Devices: The socket interface
the performance and addressing characteristics of network I/O differ
significantly from those of disk I/O, most operating systems provide a
network I/O interface that is different from the read() –write() –seek()
interface used for disks.
the system calls in the socket interface enable an application to create
a socket, to connect a local socket to a remote address (which plugs
this application into a socket created by another application), to listen
for any remote application to plug into the local socket, and to send
and receive packets over the connection.
To support the implementation of servers, the socket interface also
provides a function called select() that manages a set of sockets. A
call to select() returns information about which sockets have a packet
waiting to be received, and which sockets have room to accept a
packet to be sent.
34
Clocks and Timers
clocks and timers that provide three basic functions:



Give the current time
Give the elapsed time
Set a timer to trigger operation X at time t
The hardware to measure elapsed time and to trigger operations is
called a programmable interval timer.




scheduler uses this mechanism to generate an interrupt that will preempt a process
disk I/O subsystem uses it to invoke the flushing of dirty cache buffers to disk
periodically
the network subsystem uses it to cancel operations that are proceeding too slowly
because of network congestion or failures.
operating system may also provide an interface for user processes to use timers
35
Clock Hardware
A programmable clock.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
36
Clock Software (2
Three ways to maintain the time of day.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
38
Simulating multiple timers with a single clock
The operating system can support more timer requests than the
number of timer hardware channels by simulating virtual clocks.
To do so, the kernel (or the timer device driver) maintains a list of
interrupts wanted by its own routines and by user requests, sorted
in earliest-time-first order. It sets the timer for the earliest time.
When the timer interrupts, the kernel signals the requester, and
reloads the timer with the next earliest time.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
39
Blocking and Nonblocking I/O
When an application issues a blocking system call, the execution of
the application is suspended.


The application is moved from the operating system's run queue to a wait queue.
After the system call completes, the application is moved back to the run queue,
where it is eligible to resume execution, at which time it will receive the values
returned by the system call.
Easy to understand
A nonblocking call does not halt the execution of the application for an
extended time. Instead, it returns quickly, with a return value that
indicates how many bytes were transferred.

One example is a user interface that receives keyboard and mouse input while
processing and displaying data on the screen.
An asynchronous call returns immediately, without waiting for the I/O to
complete.

The application continues to execute its code. The completion of the I/O at some
future time is communicated to the application, either through the setting of some
variable in the address space of the application, or through the triggering of a signal
or software interrupt or a call-back routine that is executed outside the linear control
flow of the application.
40
Kernel I/O System
Kernels provide many services related to I/O:






scheduling,
buffering,
caching,
pooling,
device reservation, and
error handling
built on the hardware and device-driver infrastructure.
41
I/O scheduling
To schedule a set of I/O requests means to determine a good order in
which to execute them.



Operating-system developers implement scheduling by maintaining a queue of requests
for each device.
When an application issues a blocking I/O system call, the request is placed on the
queue for that device.
The I/O scheduler rearranges the order of the queue to improve the overall system
efficiency and the average response time experienced by applications.
42
Buffering
A buffer is a memory area that stores data while they are transferred
between two devices or between a device and an application.
Buffering is done for three reasons.



to cope with a speed mismatch between the producer and consumer of a data stream.
 a file is being received via modem for storage on the hard disk
to adapt between devices that have different data-transfer sizes.
 networking: messages are typically framented during sending and receiving
to support copy semantics for application I/O.
 application has a buffer of data that it wishes to write to disk. It calls the write()
system call, providing a pointer to the buffer and an integer specifying the number
of bytes to write.
 After the system call returns, what happens if the application changes the contents
of the buffer?
 When processing write() system call, OS copy the application data into a kernel
buffer before returning control to the application.
 The disk write is performed from the kernel buffer, so that subsequent changes to
the application buffer have no effect.
43
Buffering (1)
(a) Unbuffered input. (b) Buffering in user space.
(c) Buffering in the kernel followed by copying to user space.(d)
Double buffering in the kernel.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
44
Buffering (2)
Figure 5-16. Networking may involve many copies of a packet.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
45
Caching
Caching is done at the I/O level to improve the I/O efficiency.
The difference between a buffer and a cache is that a buffer may hold
the only existing copy of a data item, whereas a cache, by definition,
just holds a copy on faster storage of an item that resides elsewhere.
Caching and buffering are distinct functions, but sometimes a region of
memory can be used for both purposes. For instance, to preserve
copy semantics and to enable efficient scheduling of disk I/O, the
operating system uses buffers in main memory to hold disk data.
46
Spooling
A spool is a buffer that holds output for a device,
such as a printer, that cannot accept
interleaved data streams.






Although a printer can serve only one job at a time,
several applications may wish to print their output
concurrently, without having their output mixed together.
The operating system solves this problem by intercepting
all output to the printer.
Each application's output is spooled to a separate disk file.
When an application finishes printing, the spooling system
queues the corresponding spool file for output to the
printer.
The spooling system copies the queued spool files to the
printer one at a time.
In some operating systems, spooling is managed by a
system daemon process.
47
Error handling
An operating system that uses protected
memory can guard against many kinds of
hardware and application errors, so that a
complete system failure is not the usual result
of each minor mechanical glitch.


Devices and I/O transfers can fail in many ways, either
for transient reasons, such as a network becoming
overloaded, or for “permanent” reasons, such as a disk
controller becoming defective.
Operating systems can often compensate effectively for
transient failures.
 For instance, a disk read() failure results in a
read() retry, and a network send() error results in
a resend() , if the protocol so specifies.
 Unfortunately, if an important component
experiences a permanent failure, the operating
system is unlikely to recover.
48
I/O protection
Users should not be allowed to issue illegal I/O instructions.
All I/O instructions should be priviliged to provide a proper protection.
Note that the kernel cannot simply deny all user access.

Most graphics games and video editing/playback software need direct access to
memory-mapped graphics controller memory to speed access.
 The kernel may provide a locking mechanism to allow a section of graphics
memory to be allocated to a process at a time.
49
I/O Software Layers
I/O software is typically organized in four layers.
Each layer has a well-defined interface.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
50
Interrupt handlers
The driver can start an I/O operation and then block until the I/O is
completed and the interrupt occurs


The driver can block itself by doing a down on a semaphore or a wait on a condition
variable.
When the interrupt happns, the interrupt routine does whatever it has to do to handle the
interrupt and then unblock the driver that started it, by up'ping on the semaphore or
notifying the condition variable.
 the net effect of the driver is to unblock the driver.
51
Device drivers
Each I/O device attached to a computer needs some device-specific
code for controlling it.


written by device manufacturer
each OS needs its own device drivers
Each device driver supports a specific type or class of I/O devices.

A mouse driver can support different types of mice but cannot be used for a webcam.
The OS defines what a driver does and how it interacts with the rest of
the OS.
A device driver has several functions

to accept abstract read and write requests from device-independent software above it
and make sure that they are carried out, +
 initialization of the device
 manage is power requirements and log events
52
Device driver structure






check whether input parameters are valid
translation from abstract to concrete terms
 for a disk driver, converting a block id into head, track, sector and cylinder numbers
for the disk's geometry
check if the device is currently in use by checking its status register
 if not, insert the request into queue
 if the device is not on, turn it on
issue the sequence of commands
 after issuing each command, check whether the device is ready to accept the next
one
 [in most cases] the driver blocks itself until an interrupt comes
 [in fewer cases] the driver waits for the completion of the command
the driver is awakened up by the driver to continue its operation
the data and the error information is passed to the device-independent OS I/O software
53
Device drivers - issues



Note that
 an I/O device may complete while the device driver is running and create an
interrupt
 the interrupt may cause the current driver to run
device drivers must be reentrant, a running driver has to expect that it will be called a
second time before the first call has completed.
Drivers cannnot make system calls but are allowed to call some kernel procedures for
interaction.
54
Device Drivers
Figure 5-12. Logical
positioning of device
drivers. In reality all
communication
between drivers and
device controllers
goes over the bus.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
55
Device-Independent I/O Software
Figure 5-13. Functions of the device-independent I/O software.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
56
Uniform Interfacing for Device Drivers
Figure 5-14. (a) Without a standard driver interface.
(b) With a standard driver interface.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
57
User-Space I/O Software
Layers of the I/O system and the main functions of each layer.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
58