Lecture 11
External Memory (Continued) and I/O Modules
• Magnetic Disk
Copyright By PowCoder代写 加微信 powcoder
– The most important external memory device on almost all computer systems
– Working mechanism
• The Organization of Multiple Disks
– RAID family
Magnetic Disk
Store bits
Allow the platter to spin
Magnetic Disk
How bits are read/written?
(1) Head moves to the “right position” (2) Platter spins
There could be multiple Platters and Heads
How are the Bits stored on Platter? • Platter
– Nonmagnetic material covered with magnetic “coats”
– On the magnetic surface, there are many magnetized spots –
each spot stores one bit
– More specifically, each magnetized spot has two polarities: S and N
– The orientations (S-N or N-S) are represented as 0 or 1
– Example: 120Gb hard disk drive contains over 120 billion spots!
How are the Bits Read/Written
• The interaction between Head and Platter
– The essence is the electromagnetic fields – the change of current will cause the change the magnetic fields, and vice versa
– Head is covered with magnetic fields and electronic wires
Illustration of Read/Write Head
How are the Bits Read/Written
• The interaction between Head and Platter
– Read and write essentially have the same mechanism: the direction of the current in the Head corresponds to the orientation of the magnetized spot
– Two states of the directions of current = two states of the orientations (S-N or N-S)
– Read: magnetic (Platter) → current (Head)
– Write: current (Head) → magnetic (Platter)
How are the Bits Organized on Platter • Tracks and Sectors on Platter
– The patter contains a set of concentric rings, called tracks – Each track contains a number of sectors
– Sector = a number of magnetized spots ( a block of data) – The size of a sector may vary
How are the Bits Organized on Platter
The size of the Head is the same as the width of the track (the head will read/write the tracks)
Intersector gap and intertrack gap: separate the sectors, to minimize the errors due to misalignment of the head or simply reduce the interference of magnetic fields
One issue with this Organization
• There could be different date rates for different tracks
– The head is fixed while the platter is spinning
– Inner and Outer tracks have different speed relatively to the head – this result in different data rates when reading/writing bits
stored in inner and outer tracks
Arrangement 1: Constant Angular Velocity (CAV)
• Ideal: rotate the platter at a constant speed,
but the densities of spots (bits) on different
tracks are different
– Platter is divided into a number of pie-shaped sectors – advantage: blocks of data can be addressed by tracks and sectors
– Disadvantage: amount of data can be stored on long outer tracks is only the same as what can be stored on short inner tracks (waste of space)
Arrangement 2: Multiple Zone Recording • Platter are organized into zones
– Each zone has multiple tracks
– Outer track has more sectors
– The densities of the sectors are the same – increased capacity
– Various data transfer rate (for some disk designs, the rotation speed may change to achieve constant transfer rate)
Zone in the same color
Components of Disk Drive • Data organization on Disk
– Disk – Platters – Tracks – Sectors
– Head has the same width as that of tracks (or
– Read/Write by sectors (one sector usually contain 512 bytes
– question: how to locate the desired sectors within a track?
How to Locate Sector Positions within Track • Use extra control data as Marks
– Extra control data – used only by disk drive, not accessible by users
– Format of Disk (the organization of user data and control data)
– Example: Format: each track has 30 sectors, each sector has 600 bytes (512 for data storage)
How to Locate Sector Positions within Track
The Format of One Track
One Sector
ID field: uniquely identify a sector
Synch byte: the beginning
Head number: because there are multiple platters and heads CRC: error correction code
Data field
The Timing of Disk I/O Transfer
• An important performance measurement
– The time does not just depend on how fast the disk can read/write bits – many other considerations
– There are various queuing delays: wait for device and wait for channel
– Wait for device: when process (task) issues an I/O request, it must first wait in a queue for the device to be available
– Wait for channel: multiple I/O devices may share the channel between Processor and devices – need to wait for the channel to be available
The Timing of Disk I/O Transfer • Access time
– The time for the Head to get to the right position
– It consists of two parts: seek time and rotational delay
– Seek time: the Head moves to the right track
– Rotational delay: the desired sector rotates to the Head
– Factors: how compact is the platter (size of platter), rotation speed
– Common example: average seek time ~ 10 ms; average rotational delay ~ 1.5 ms
The Timing of Disk I/O Transfer • Data transfer
– The actual time to read/write data as platter moves under head – Factor: the rotation speed and the number of sectors
– Typical rotation speed: 3600 – 20,000 rpm (revolutions per min)
Access time
Internal Memory
Large Capacity
Low Speed (limited by mechanical components) Relatively high error probability (frequent and fast movement of mechanical components)
The next question: how to stack disks to achieve better performance?
External Memory
• Magnetic Disk
– The most important external memory device on almost all
computer systems
– Working mechanism
• The Organization of Multiple Disks – RAID family
Redundant Array of Independent Disks (RAID)
Operating System
A logic disk
RAID: physically a set of disk drives
Logically, one huge disk
Redundant Array of Independent Disks (RAID) • Overview
– There are 7 levels: RAID 0 to RAID 6
– These levels are NOT hierarchical, they are different designs (disks) – Different levels have different characteristics
• Common Characteristics
– A logic disk drive to the operating system
– Data striping: divide logically sequential data (file) into segments (strips) and distribute them to different physical devices
– Redundant: will store some redundant data (except for RAID 0)
Redundant Array of Independent Disks (RAID)
• RAID wants to address two main issues of single disk
– I/O speed: parallel the I/O operations across many disks – Reliability: introduce redundancy
RAID 0 – Data Distribution (NO Redundancy) • Data are segmented into strips and distributed:
Note the organization of the strips
View of the OS
• Data are stripped across all disks
– Round Robin stripping • Increased speed
– A set of data is likely to be stripped across multiple disks
– Disks seek in parallel
– Failure of one disk may cause the loss of multiple files
Two files A and B (each occupying 4 strips) are distributed across 3 disks
• Duplicated data (mirrored data)
RAID 2 and RAID 3: Redundancy through Error Correction Code
• Parallel Access Technique
– The spindles of disk drives are synchronized so that each disk head
is in the same position on each disk at any given time
– Read the bits in the same position in parallel
– The size of each strip is very small (e.g., a single byte or word)
• RAID 2 and RAID 3 differ in error correction code used
• RAID 2 typically uses Hamming Code
Data disks Parity disks
Example: (7-4) Hamming Code, the bits in the same position on each data disks are encoded, the resulting parity bits are then stored in the same position on the parity disks
• Data bits and parity bits are read/write simultaneously
– Codes are calculated “on-the-fly”
– Correct error in real time
– Good for low quality disks which has frequent errors
• Still, lots of redundancy (although better and RAID 1) • Expensive, not commonly used
• RAID 3 uses a single parity bit
Data disks Parity disks
Add a single parity bit for the data bits (b0 – b3) in the same position (bit- interleaved parity)
• Only one redundant disk, no matter how large the array
– Efficient than RAID 2
• It can handle hardware failure
– Suppose one disk fails, can fully recover the data
– Not good for soft failures (bit level errors), since it can only detect one error
• Compared to RAID 3
– Disks are accessed independently (not in parallel)
– Strips have much larger size (block-level), good for high I/O read
request rate (since one request can handled by one disk)
– Also compute a single bit parity for corresponding data bits (the distribution of parity bits are different in RAID 4, 5, 6
Bottleneck for data update (there is a write penalty): suppose we want to update one file in block 0, we need to read multiple blocks to also update the parity information)
• Almost the same as RAID 4
– Difference: round robin allocation for parity strips, so that parity information is striped across all disks
– Can avoid the bottleneck at parity disk in RAID 4
• Almost the same as RAID 5
– Difference: two parity calculation schemes (P and Q)
– Increased data availability at the cost of higher write penalty
• Chapter 6
– Section 6.1: HDD
– Section 6.2: RAID
– Section 6.3: other external memory types, optical memory, magnetic tapes (optional)
Lecture 11 I/O Modules
Previously …
Internal Memory
System Bus
Address/Data/Control
The above simple architecture highlights the basic operations of a computer system:
CPU fetches data and instructions from main memory, process, and store results back into main memory
Problems: where do the data/instructions from? Where to present the results? Where to store the results permanently? — We need some external devices to communicate with the external world
We need all kinds of External Devices
Internal Memory
System Bus
Address/Data/Control
External devices:
I/O Modules – the Communication Bridge
Internal Memory
System Bus
Address/Data/Control
How to communicate?
All Kinds of External Devices
Generic Model of an I/O Module
To Processor or Internal memory
A computer system has many I/O modules, each of which may connect to one or multiple external devices
One or More External Devices
Overview of Today’s Lecture • Three questions:
– Why do we need I/O modules?
– What functions are supported by I/O modules?
– How to implement the functions of I/O modules (what techniques are used)?
The Need for I/O Modules
• Why don’t directly connect external devices using system bus?
– Two considerations: data transfer rate and “logic”
– System bus has high data transfer rate
– External devices are much slower
– Also, there are a wide variety of devices with various transfer rates
– Hard to match – inefficiency
The Need for I/O Modules
• Why don’t directly connect external devices using system bus?
– We need something more than a “a connector”
– We need a “logic” to control and translate the data formats of
the various external devices
– If we use system bus, it is impractical to integrate all the logic for all devices into CPU
The Need for I/O Modules
• An I/O module is more than a “connector”, it is like a tiny processor with two major functions
– Interface to the processor and memory via the system bus or some central switch
– Interface to one or more external devices by some data links
External (Peripheral) Devices or Peripherals
Controls device’s operations in response to direction from the I/O module
Block diagram of an external device
Three types of signals
Buffer: temporarily hold data being transferred between I/O module and outside environment
Transducer: conversion between electrical energy (bits) and other forms of energy (it is device-specific)
Examples: speech data, keystroke, …
Keyboard Input as An Example
• The basic unit of exchange is Character – human- understandable
– Two types of characters: printable and control
– Each character is encoded as a code (typically 7 or 8 bits)
– User depress a key (input from outside world) → generate electronic signal and translated into bit pattern, which is one code (done by transducer) → Buffer → transmitted to I/O module → memory/processor
Major Roles of I/O Modules
I/O Board contains multiple I/O modules, each is in charge of one or multiple external devices, including MagSafe power, USB, audio ports
Major Roles of An I/O Module
• The major functions or requirements for an I/O module fall into the following categories:
– Control and timing
– Processor communication – Device communication
– Data buffering
– Error detection
Control and Timing
• Why? – need to coordinate the flow of traffic
between internal resources and external devices
– Processor may communicate with multiple external devices at
any time and it’s often unpredictable
– The communication relies on internal resources (main memory and system bus), which are shared by external devices
– An I/O module is like a driver in a car (data flow) – coordinate when to transfer the data
Control and Timing
• The typical scenario of data transfer
– Processor asks the I/O module to check the status of device
– I/O module returns the device status
– If device is ready, processor sends a command to request data – I/O module obtains units of data from external device
– Data is transferred from I/O module to processor
Processor Communication and Device Communication
• Processor Communication – three types of information: command, data, status
– Processor sends commands to I/O module through control bus and data bus; for example: READ SECTOR for disk drive
– Exchange data between processor and I/O module
– Status: I/O module reports status of the external device since it is usually very slow; example: status could be BUSY and READY
Processor Communication and Device Communication
• Device communication: similar but with different codes
– Particular important is the address of a device
– Each device is associated with unique addresses and the I/O module needs to recognize the addresses for the devices it controls – in the eye of processor, each I/O has a unique address or a set of unique addresses
Data Buffering and Error Detection
• Data from processor and devices are temporarily buffered in I/O module
– Cope with the different data transfer rates • Error Detection
– Detect mechanical and electrical malfunctions (e.g., paper jam for a printer)
– Detect soft errors using error detection code (parity bits)
Structure of I/O Module
I/O module allows the processor to view a wide range of devices in a simple-minded way. (I/O module hides the details of timing, data formats, and other specifications to the processor, which simply issues read/write commands)
There are a variety of I/O modules with various functions.
Depending on the different functionalities, they are referred to as I/O channel, I/O processor or simply I/O controller or device controller
The Big Picture
Previously, we introduced the functions of I/O modules, now the next question is how those functions are implemented (techniques).
Goal of I/O: usually, get data from I/O and store data in memory (input); get data from memory and send data to I/O (output)
Key: the interaction between CPU, Memory, I/O modules over the system bus
I/O Techniques
• Two General Categories
– First, Processor serves as the intermediate party between I/O and Memory: Programmed I/O and Interrupt-driven I/O
– Second, Memory and I/O interact directly without CPU: Direct Memory Access
Programmed I/O
• Processor issues I/O Commands to I/O modules and
directly control the I/O process
• Key feature: Processor will wait for the completion of the I/O command
– Processor sends the command to I/O module
– I/O module will do the job and set the I/O status register after
finishing the job – I/O module will not alert processor
– Processor needs to periodically check the status to see it the job has been completed
Programmed I/O Example
Example of reading a block of data from external memory device
Processor needs to periodically check the status – a waste of CPU cycles
Another Important Issue – Addressing
• Processor needs to know which I/O device it is interacting
– Each device is associated with unique identifiers (addresses)
– As a result, each I/O is associated with a set of addresses
– When Processor issues a device address, each I/O module needs to recognize the address and determine if the address is for itself
– What’s this address? – two modes of addressing
Addressing Scheme I: Memory Mapped I/O
• Memory and devices share the same address space
– Intuition: devices contain different registers, and processor actually wants to access these registers (check status, data,…) – these registers are “part of memory”
– Example: 10 address lines, first 512 locations for Memory, latter 512 locations for devices
– In the view of processor, devices are similar to memory – processor use instructions (containing address) to access device
Addressing Scheme I: Memory Mapped I/O • Example: Keyboard
Addresses assigned to device
Processor use instructions to access devices (via I/O module): basically, process wants to load the content in status register and input data register to AC, and continuous check the status of the device
Addressing Scheme II: Isolated I/O
• Separated address space for Memory and Device
– Use I/O or memory select lines (to differentiate the addresses transmitted over the address bus)
– System will have separate instructions for I/O operations where the identifier of the device is hard-coded into the instructions
Identifier 5 is assigned to the Keyboard
Summary of Programmed I/O
• Processor issues commands, and periodically check whether I/O is ready to transfer data
• Disadvantages:
– Processor needs to wait for I/O
– Waste of CPU cycles – it is slowed down to the speed of external devices (Programmed I/O is the oldest form of I/O handling)
• Advantages:
– Simple, very easy hardware/software
Interrupt-Driven I/O • General Procedure
– Processor issues I/O commands to I/O module
– Processor continues its other tasks while the module performs
I/O operations
– The module singles the processor when I/O operations are
finished, meaning that it’s ready to transfer data, via Interrupt
– Processor responds by interrupt handler, e.g., by executing an interrupt service routine
Interrupt-Driven I/O
Programmed I/O vs. Interrupt-driven I/O
The key difference is the “inner loop” which periodically checks the status of the I/O
Interrupt-driven I/O can save a lot of CPU time
Handling Interrupt
Combination of Hardware and Software resources to handle interrupt
Recall the CPU cycle: fetch instruction, execute, check interrupt
Need extra hardware resources to store the state (PC, contents of CPU registers, etc) of the current program. The state is stored in stack, which is a special type of memory
C value = software (program) to handle interrupt
Handling Interrupt
Software: designated programs to handle I/O devices (different for various I/O devices)
Designated programs: interrupt-service routine and device-service routine
Design Issues for Interrupt-driven I/O • Cause:
– There are various devices, causing interrupts at any time • Two Issues:
– How to identify which device has issued the interrupt? (someone is knocking on the door, but who?)
– How to decide which one to proceed if multiple interrupts occur (I know Alice, Bob, Eve are knocking on the door, whom should I answer first – priority)?
Solutions (Brief)
• Hardware solution: separate interrupt lines (different doors)
– Still, there could be multiple devices using the same interrupt line for sending the signal
– Use extra software solutions combined with hardware solution • Software solution: Polling mechanism
– Combine interrupt-service routine and device-service routine
Software Poll
• Interrupt-service routine
– Goal: find which device causes the interrupt
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com