Transcript 1.01

COT 4600 Operating Systems Spring 2011
Dan C. Marinescu
Office: HEC 304
Office hours: Tu-Th 6:00 – 7:15 PM
Lecture 6 – Thursday, January 27, 2011



Last time:
 Complexity of Computer Systems
 Bandwidth and Latency
 Iteration
 Names and The Basic Abstractions
Today:
 Discussion of “Hints for Computer Systems Design” by Butler Lampson.
 Memory.
 Interpreters.
 Communication links.
Next time
 Communication links
Lecture 6
2
Names and fundamental abstractions

The fundamental abstractions
1.
2.
3.

Storage  mem, disk, data struct, File Systems, disk arrays
Interpreters  cpu, programming language e.g. java VM
Communication wire, Ethernet
rely on names.
Naming:


Flat
Hierarchical
Lecture 6
3
Names and the three basic abstractions

Memory  stores named objects



Interpreters  manipulates named objects



write(name, value)
value  READ(name)
file system: /dcm/classes/Fall09/Lectures/Lecture5.ppt
machine instructions ADD R1,R2
modules  Variables call sort(table)
Communication Links connect named objects

HTTP protocol used by the Web and file systems
Host: boticelli.cs.ucf.edu
put /dcm/classes/Fall09/Lectures/Lecture5.ppt
get /dcm/classes/Fall09/Lectures/Lecture5.ppt
Lecture 6
4
Latency and Bandwidth



Important concepts for physical characterization.
Applies to all three abstractions.
Informal



Bandwidth  number of operations per second!
Latency  to get there
The bandwidth of the CPU, Memory, and I/O sbsystems
must be balanced.
Lecture 6
5
Sender
Receiver
Program
t1
Storage
device
Latency
t1
t2
Latency
t3
t2
t3
Bandwidth
t4
t5
t4
t5
Bandwidth
t6
t6
Time
Time
Communication latency- time it takes
the first bit sent to reach the receiver
Operation latency- time it takes the
command to read the device
Bandwidth- number of bits/bytes
transmitted per unit of time
Bandwidth- number of bits/bytes
transmitted per unit of time
Lecture 6
6
Memory

Hardware memory:

Devices






RAM (Random Access Memory) chip
Flash memory  non-volatile memory that can be erased and
reprogrammed
Magnetic tape
Magnetic Disk
CD and DVD
Systems



RAID
File systems
DBMS (Data Base management Systems)
Lecture 6
7
Attributes of the storage medium/system



Durability  the time it remembers
Stability  whether or not the data is changed during the
storage
Persistence  property of data storage system, it keeps
trying to preserve the data
Lecture 6
8
Critical properties of a storage medium/system


Read/Write Coherence  the result of a READ of a
memory cell should be the same as the most recent
WRITE to that cell.
Before-or-after atomicity the result of every READ or
WRITE is as if that READ or WRITE occurred either
completely before or completely after any other READ or
WRITE
Lecture 6
9
A
A
WRITE item A in cell M
READ from cell M
A
A
M
time
M
Read/Write Coherence  the result of a READ of
a memory cell should be the same as the most
recent WRITE to that cell.
Previous
READ/WRITE
Current
READ/WRITE
Next
READ/WRITE
Before-or-after atomicity  the result of every
READ or WRITE is as if that READ or WRITE
occurred either completely before or completely
after any other READ or WRITE
Lecture 6
10
Why it is hard to guarantee the critical properties?





Concurrency  multiple threads could READ/WRITE to
the same cell
Remote storage  The delay to reach the physical
storage may not guarantee FIFO operation
Optimizations  data may be buffered to increase I/O
efficiency
Cell size may be different than data size  data may be
written to multiple cells.
Replicated storage  difficult to maintain consistency.
Lecture 6
11
Access type; access time

Sequential access



Tapes
CD/DVD
Random access devices

Disk




Seek
Search time
Read/Write time
RAM
Lecture 6
12
Physical memory organization



RAM  two dimensional array. To select a flip-flop
provide the x and y coordinates.
Tapes  blocks of a given length and gaps (special
combination of bits.
Disk:




Multiple platters
Cylinders correspond to a particular position of the moving arm
Track  circular pattern of bits on a given platter and cylinder
Record  multiple records on a track
Lecture 6
13
Names and physical addresses


Location addressed memory  the hardware maps the
physical coordinates to consecutive integers, addresses
Associative memory  unrestricted mapping; the hardware
does not impose any constraints in mapping the physical
coordinates
Figure 2.2 from textrbook
Lecture 6
14
RAID – Redundant Array of Inexpensive Disks




The abstraction put to work to increase performance and
durability.
Raid 0  allows concurrent reading and writing.
Increases performance but does not improve reliability.
Raid 1  increases durability by replication the block of
data on multiple disks (mirroring)
Raid 2  Disks are synchronized and striped in very
small stripes, often in single bytes/words.

Error correction calculated across corresponding bits on disks,
and is stored on multiple parity disks (Hamming codes).
Lecture 6
15
Lecture 6
16
RAID (cont’d)


Raid 3 Striped set with dedicated parity or bit
interleaved parity or byte level parity.
Raid 4  improves reliability, it adds error correction
Lecture 6
17
RAID (cont’d)

Raid 5  striped disks with parity combines three or
more disks to protect data against loss of any one disk.


The storage capacity of the array is reduced by one disk
Raid 6  striped disks with dual parity combines four or
more disks to protect against loss of any two disks.


Makes larger RAID groups more practical.
Large-capacity drives lengthen the time needed to recover from
the failure of a single drive. Single parity RAID levels are
vulnerable to data loss until the failed drive is rebuilt: the larger
the drive, the longer the rebuild will take. Dual parity gives time
to rebuild the array without the data being at risk if a (single)
additional drive fails before the rebuild is complete.
Lecture 6
18
Figure 2.3 from textbook
Lecture 6
19
Interpreters


The active elements of a computer system
Diverse


Hardware  Processor, Disk Controller, Display controller
Software 




script language: Javascropt, Pearl, Python
text processing systems: Latex, Tex, Word
browser : Safari, Google Chrome,Thunderbird
All share three major abstractions/components:



Instruction reference  tells the system where to find the next
instruction
Repertoire  the set of actions (instructions) the interpreter is
able to perform
Environment reference  tells the interpreter where to find the
its environment, the state in which it should be to execute the
next instruction
Lecture 6
20
An abstract interpreter



The three elements allow us to describe the functioning
of an interpreter regardless of its physical realization.
Interrupt  mechanism allowing an interpreter to deal
with the transfer of control. Once an instruction is
executed the control is passed to an interrupt handler
which may change the environment for the next
instruction.
More than a single interpreter may be present.
Lecture 6
21
Figure 2.5 from the textbook
Lecture 6
22
Processors


Can execute instructions from a specific instruction set
Architecture


PC, IR, SP, GPR, ALU, FPR, FPU
State is saved on a stack by the interrupt handler to transfer
control to a different virtual processor, thread.
Lecture 6
23
Interpreters are organized in layers


Each layer issues instructions/requests for the next.
A lower layer generally carries out multiple instruction for
each request from the upper layer.
Lecture 6
24
Figure 2.6 from the textbook
Lecture 6
25
Example – a calendar management program

Top layer a Java program with the following components:




Next layer  JVM which interprets the program




The instruction reference  get the information provided by the
keyboard and mouse and interpret them
The repertoire  add an event, delete an event, etc.
The environment  the files holding the current calendar
The instruction reference: next bytecode instruction
JVM instructions
The environment: IR, PC, etc
Bottom layer  the computer the JVM is running on
Lecture 6
26
Figure 2.7 from the textbook
Lecture 6
27
Communication Links

Two operations




SEND (link_name, outgoing_message_Buffer)
RECEIVE (link_name, incoming_message_Buffer)
Message  an array of bits
Physical implementation in hardware


Wires
Networks



Ethernet
Internet
The phone system
Lecture 6
28
The Internet – an extreme example of what hides
behind the communication link abstraction




Hourglass communication model
Protocol stack
Internet Core and Edge
The hardware


Router
Network adaptor
Lecture 6
29
Internet Core and Edge
Server
Satellite
Ethernet
Database
Ethernet
Disk array
Edge Router
Satellite dish
Edge Router
Local ISP
Local ISP
Border Router
Local ISP
Regional ISP
Internet core
National Service Provider
NAP
NAP
National Service Provider
NAP
National Service Provider
Regional ISP
Local ISP
Border Router
Local ISP
Edge Router
Edge Router
Radio tower
Dialup System
Lecture 6
PDA
Modem
30
Hourglass communication model
Teleconferencing
Videoconferencing
Application Layer
RealAudio
Telnet
WWW
Email
Transport Layer
FTP
TCP
UDP
Network Layer
IP
ATM
Physical and Data Link Layers
Dial-up
Modems
LANs
Wireless
Direct Cable
Broadcast
Frame
Sateliite
Relay
Lecture 6
31
Transport and Network Services
Transport Layer
Network Layer
Reliable
ConnectionOriented
Service
Unreliable
Connectionless
Service
Datagram
(a)
Reliable
ConnectionOriented
Service
Virtual Circuit
(b)
Lecture 6
32
Multiplexing and Demultiplexing
P1
P2
P3
P1
P4
P2
P3
P4
Sending side
Receiving side
Lecture 6
33
Application Layer
HTTP
FTP
TELNET
NFS RPC
DNS
SNTP
Transport Layer
TCP
UDP
Network Layer
IP
Data Link Layer
Satellite
Ethernet
Lecture 6
Wireless
34
Application, Transport, Network, and Data Link Layer
Protocols
Application Layer
HTTP
FTP
TELNET
NFS RPC
DNS
SNTP
Transport Layer
TCP
UDP
Network Layer
IP
Data Link Layer
Satellite
Ethernet
Lecture 6
Wireless
35
It's a long way to Tipperary it's a long way to go!!
Host
Host
Application Layer
(Message)
Application Layer
(Message)
Network
Transport Layer
(Segment)
Network Layer
(Packet)
Data Link Layer
(Frame)
Physical
Layer
Router
Network Layer
Data Link Layer
Physical Layer
Lecture 6
Router
Transport Layer
(Segment)
Network Layer
Network Layer
(Packet)
Data Link Layer
Data Link Layer
(Frame)
Physical
Layer
Physical
Layer
36
From Local Area to Wide Area Networks
Wide Area Network
Router
Router
Network Layer
Network Layer
Data Link
Layer
Physical
Layer
Data Link
Layer
Physical
Layer
Host
Host
Application
Layer
Application
Layer
Transport
Layer
Transport
Layer
Network
Layer
Local Area Network
Bridge
Data Link
Layer
Hub
Physical
Layer
Physical
Layer
Data Link
Layer
Physical
Physical
Layer
Layer
Local Area Network
Bridge
Data Link
Layer
Physical
Layer
Lecture 6
Network
Layer
Hub
Data Link
Layer
Physical
Layer
Physical
Layer
37
Message delivery to processes
Router
Network
interface
Port
Process
Host
Network
Network
IP address = (NetworkId, HostId)
Lecture 6
38
Sockets and Ports
Process
Socket
Output message queue
Port
Internet
Input message queue
Host
Lecture 6
39
Router
Input Port
LT - Line
Termination
Input Port
Data Link
Protocol
Output Port
Lookup
Forwarding
Queuing
Queuing
Switching
Fabric
Data Link
Protocol
LT
Output Port
Output Port
Input Port
Routing
Processor
Lecture 6
40
Router supporting QoS (Quality of Service)
Shaper
Dispatcher
and Buffer
Acceptance
Classifier
Input
flows
Output
link
Policer
Lecture 6
41
The network adaptor
Communication
Link
Host I/O Bus
Out Buffers
Host
I/O Bus
Interface
In Buffers
Communication
Link
Interface
Network Adaptor
LAN
Host
Lecture 6
42