Transcript CSE22MAL

ELE22MIC Lecture 19
• Microprocessor Storage Hierarchy
– MAIN MEMORY
– MASS STORAGE
• MEDIA, DISK FILE SYSTEMS
• Memory Management Unit
• Memory Protection and Privilege Levels
• 68HC11 Gray Code - Encoder Software
Demonstration
• Refer: http://thor.ee.latrobe.edu.au/~paulm
Mass Storage
• It is necessary to be able to store large quantities of
information (programs and data) for long periods of
time and during periods of no power.
• Old forms of storage:
– paper tape, punched cards, magnetic tape - small
capacity, very slow, hard to use.
• Modern forms of storage:
– hard disks
– floppy disks
– optical disks
– magnetic tape - huge capacities, very fast, very
versatile, easy to use.
Storage Hierarchy
Typical Memory Heirarchy:
Speed,
Capacity,
Memory type
<1ns,
<1KB,
Register
2ns,
1MB,
Cache
<10ns,
64M-1GB,
Main memory
1s,
<2MB
Floppy Disk
10ms,
5-300GB,
Hard Disk
1s/10min, 650MB-4.7GB CDROM/RW/DVD
100s,
100MB-4TB
Tape
Storage Hierarchy
• Consider the following issues
–
–
–
–
Speed
Cost
Volatility
Protection
Storage systems are organized in hierarchy
as follows:
Register, Cache, Main memory, Disk,
CDRW/Tape
Cache
• Main Memory Caching
– copys data into faster storage systems to
improving the system performance.
• Modern PC systems currently don’t use memory
cache as the overhead is greater than the benefit.
• Cache use in hardware - its use ebbs & flows
with the technology capacity - it is used when
performance improvement can be gained. Used
in Intel 386 through Pentium.
Cache Memory
• Higher Speed than main memory
• When CPU accesses memory for code & data
that is held in a cache, a cache “hit” can occur
and the information is directly accessed from
the cache.
• If the cache is filled, the MMU (may) determine
the least recently used cache memory, and
replace it with the newly accessed one.
• In most computers the cache hit ratio is > 85%
Main Memory
• Main Memory - Currently with PC333 and
faster memory systems - R/W acces times are
<3ns.
• Based on capacitive storage elements
• When using SDRAM, and later technology,
DRAM refresh is managed on the memory
controller without system intervention.
• SRAM - as used in HCCOM
– 85ns cycle time.
Secondary Storage- Floppy Disks
• A floppy (flexible) disk is a flexible Mylar disk
which has been uniformly coated with a ferromagnetic compound.
• Each side is organised in concentric circles
called Tracks.
• Each track is organised in divided into
segments called sectors.
• Historically Disks have been available in 8
inch, 5 1/4”, 3 1/2” dimensions.
Magnetic Surface Recording
Mass Storage - Floppy Disks (1)
Mass Storage - Floppy Disks (2)
• A 5 1/4” floppy disk can contain:
–
–
–
–
two sides,
80 tracks,
9 sectors per track,
512 bytes per sector.
• The 5 1/4” floppy disk can contain:
– 2 x 80 x 9 x 512 bytes = 640k bytes
Mass Storage - Floppy Disks (3)
• Using similar formatting arrangements the
3 1/2” floppy disk can contain 2MB, but after
formatting for IBM format only 1.44 MB. The
File Allocation Table occupies this space.
Media Descriptor Byte
Media Descriptor Byte values:
Byte(hex)Medium
#sides
fe
8" 1
fe
5 1/4"
1
fc
5 1/4"
1
fe
8" 1
fe
8" 1
ff
5 1/4"
2
fa
3 1/2 "
1
fa
5 1/4"
1
fd
5 1/4"
2
fb
3 1/2 "
2
fb
5 1/4"
2
f9
3 1/2 "
2
f9
5 1/4"
2
f0
3 1/2 "
2
fd
8"
2
f8
hard disk
SPT
2
8
9
6
8
8
8
8
9
8
8
9
15
18
26
# tracks
77
40
40
77
77
40
80
80
40
80
80
80
80
80
77
Capacity
77 KB
160 KB
180 KB
231 KB
308 KB
320 KB
320 KB
320 KB
360 KB
640 KB
640 KB
720 KB
1200 KB
1440 KB
1960 KB
5 MB+
DOS Ver.
1.00
1.00
2.00
1.00
1.00
1.10
1.00
1.00
2.00
1.00
1.00
3.20
3.00
3.20
1.00
2.00
Mass Storage - Hard Disks (1)
• Original hard disk interface ST506 was a very
popular standard between disk vendors.
• Originally developed by Seagate Technology
• Data is read & written serially onto the disk
surface in a similar manner to floppy disks.
• 5mbit/sec data transfer rate
• Separate controller & disk.
Mass Storage - Hard Disks (2)
•
•
•
•
In 1983 ESDI was developed. 15mbit/sec.
Higher density - 20 to 50 Sectors per track.
The defect map is stored in the drive.
The number of Cylinders, Heads & Sectors
stored in ROM on the hard-disk.
Mass Storage - Hard Disks (3)
Mass Storage - Hard Disks (4)
•
•
•
•
Circa 1985 IDE was developed.
Transfer rate of 16M byte/sec.
Integrated hard-disk controller.
Enhanced IDE (EIDE) transfer rates:
– UDMA - 33 MB/s; ATA 66, - 66MB/s
– ATA 100 - 100MB/s
• SCSI-Ultra320 SCSI 320MB/s, 2-4ms seek
time
• Serial ATA - SATA 1.5Gbit/s, 250GB capacity
File System Layout (1)
• File Systems are stored on disks.
• Most disks are divided up into one or more
partitions
Partition
Tables
File System Layout (2)
• Sector 0 of the disk is called the Master
Boot Record (MBR) and is used to boot
the computer (or run a boot loader to select the desired
Operating System. eg: LILO, partition commander, etc).
Partition
Tables
File System Layout (3)
• After the Master Boot Record comes the
partition tables - information such as Start
& Ending Addresses, File System type, etc.
Partition
Tables
File System Layout (4)
• Each Partition contains a root directory, user
files & directories - structure is dependent of
file-system type. This example here shows a unix style file
system.
Partition
Tables
File System Layout (5)
• BOOT SECTOR - Occupies first sector of floppy disk/partition. Contains:
jump to start of boot loader code, OEM name, bytes per sector, sectors per
allocation unit (Cluster), number of FATs, number of root directory entries,
number of logical sectors, medium descriptor byte, sectors per FAT,
sectors per track, number of heads, number of hidden sectors, program to
boot the Operating system
Partition
Tables
File System Layout (6)
• MSDOS FAT - File Allocation Table:
– The root directory points to the starting cluster of each file.
– The entry in the FAT corresponding to that cluster points to the next cluster
used for that file.
– The entry -1 is used to signify end of file cluster chain.
– The location of boot files IO.SYS, MSDOS.SYS & COMMAND.COM is
fixed
Partition
Tables
Format (1)
• Disks can have a logical structure imposed
upon them called a format.
• The format or file-system type is identified by
numeric values in the partition table.
• The format tells the operating system what to
expect where
– Where to find the root directory
– Where is each file extent can be found
– How to locate the operating system at boot time.
Format (2)
• There is a huge list of different format types
including:
–
–
–
–
–
–
–
–
FAT 12 - still used on IBM format floppy disks
FAT 16 - Used on hard disks < 2 GB
FAT 32 - Used on hard disks > 2GB
ISO9660 - Used on CDROMs (MS Jolliet)
NTFS - Newer NTFS allows for encrypted data.
Ext3fs - Used on newer unixes (allows journalling)
Minix, QNX, SCO,….etc
See fdisk under Linux for more info.
Root Directory
• The root directory contains a list or table
describing file attributes such as: names, sizes,
dates & times, and where each file commences
on the physical disk.
• Where each file extent is found is specified
using a File Allocation Table (in MSDOS) or
an I-Node (under most Unixes).
• Warning various fdisk programs number partitions
differently. Even the one OS may use different
labelling conventions. Be exceptionally cautious deleting
File Allocation Table
• MSDOS File Allocation Table
– FAT 16 -> 2^16 table entries -> 65536 clusters
– FAT 32 -> 2^32 table entries -> 4177918 clusters
– A cluster is a group of sectors allocated by one FAT
entry - determined at format time - vary from 1
sector (512 bytes) to 128 sectors (64k) per cluster
– Each FAT entry forms a link in a linked list
pointing to the next cluster entry. A terminal value
indicates end of cluster chain.
– The Directory Entry includes a pointer to the first
cluster and the file size.
Files
• Each file is an abstraction
– It is a block of bytes managed by the operating
system.
– Identified by complete path-name or file-name
• Path refers to [device:] [directory/folder..] filename . ext
– Operating systems services such as open, close,
read, write and seek hide the underlying
mechanisms and formats - Sectors, Tracks,
controllers, CRCs / checksums, speed of rotation,
head position, etc
Hardware Protection
To ensure proper system operation
protection is required for any shared
resource.
•
•
•
•
Dual-Mode Privileged operation
I/O protection
Memory protection
CPU protection
Dual-Mode Privileged operation (1)
• Ensure that by sharing system resources an
incorrect program can not cause other
programs to execute incorrectly
• Provide hardware support to differentiate at
least two modes of operation
• A Mode bit is used in the hardware to
indicate the current mode
• Mode=0 for system mode
• Mode=1 for user mode
Dual-Mode operation (cont) (2)
• In User Mode: Direct execution of privileged
operations are prevented.
• Instead privileged operations are done on
behalf of a user.
• In user mode, privileged instructions such as
I/O, set clock, etc. are not allowed.
• A user calls the operating system through a
call-gate to perform any privileged
operation. The call gate prevents direct
damage to operating system structures/stack.
Dual-Mode operation (cont) (3)
• When an interrupt or error occurs, HW
switches to monitor mode
• Privileged instructions can be issued only in
monitor mode
– Monitor mode (Supervisor/system/
privileged mode): Hardware only allows
privileged instructions (i.e. machine
instructions which can cause harm) to be
executed in monitor mode such
instructions can be requested and are
provided by system calls of the OS.
Dual-Mode operation (cont) (4)
– Monitor mode (cont’d)
• That is, a user may make a system call to the
service provided by the OS. In doing this, a
user is required to place the necessary
parameters for each call in well defined
registers (locations).
• The execution of such specialized function
(system) calls within a users program causes
the users program to execute a special trap
instruction, thereby switching from user mode
to monitor mode and transfers control to the
OS.
Dual-Mode operation (cont)
I/O Protection
• All I/O instructions are privileged
instructions
• Must ensure that a user program could
never gain control of the computer in
monitor (supervisor) mode.
Memory Management Unit
• The MMU hardware acts basically a
sophisticated look-up table, configurable by
the processor.
• The MMU provides the translation from
logical to physical addresses.
• A word is defined as the basic addressable
unit of a processor.
• In a 16 bit processor, a word is 16 bits, in a
32 bit processor a word is 32 bits.
Memory Management Unit
Logical
Address
Bus
Physical
Address
Bus
Memory Management Unit
• In systems using memory management,
words of memory are grouped together to
form pages.
• An address can be considered to consist of a
page number and a word number within that
page.
• The MMU translates the page number to a
new page number, but leaves the word
number unmodified.
Memory Management Unit
Logical
Address
Bus
Physical
Address
Bus
Memory Management Unit
Logical Address :
Physical Page Number:Word -> Physical Address
Memory Protection
• Some registers within the MMU are used to
distinguish the address of one program from
another, e.g.
– Base register – holds the smallest legal
physical memory address
– Limit register – contains the size of the
range available to the program
• Memory outside the defined range is
protected - Accessing memory outside the
selected range causes a GP Fault.
MMU : Logical Mem < Physical (1)
• The simplest form
of memory
management is
when the logical
space is smaller
than the physical
memory present.
MMU : Logical Mem < Physical (2)
Physical Page Number:Word Number -> Physical Address
MMU : Logical < Physical (3)
• In this instance, the processor's logical
address becomes the word number within a
page and the MMU supplies the page
number. The processor selects which page
in physical memory its logical address
corresponds to.
• The physical page number and the word
number together form the physical address
for memory.
MMU : Logical < Physical (4)
MMU : Logical >= Physical (1)
• For processor's with address spaces
equal to or larger than the physical
space, the memory management
scheme becomes:
– The MMU contains a translation table.
– The translation table is accessible and
configurable by the processor.
MMU : Logical >= Physical (2)
• F
Protection Hardware (1)
• Some processors, like the 8086 and 68020,
have a special interface for a MMU (68851
in the case of the '020).
• Other processors, like the Intel 80386,
Motorola 68030 and 68040, have MMUs
built-in.
• If the processor was not designed to use an
MMU, it will have no special support.
Protection Hardware (2)
• The MMU must therefore be treated as a
peripheral (I/O) device by the processor.
• Thus the MMU must appear in the
processor's address space.
• The MMU must appear in the logical space
of the processor and not the physical space
of the system, otherwise the MMU may be
'lost’ (mapped out of addressable memory).
Protection Hardware (3)
• However, since the MMU is in the logical
space, it is no longer protected from
tampering or corruption by a crashing
program.
• To solve this, some processors have two (or
more) states of operation.
– Supervisor mode
• AKA Kernel / system / monitor mode
– User mode
Protection Hardware (4)
• When executing in monitor mode, the
operating system has unrestricted access
to both monitor and users’ memory
• The load instruction for the base and limit
registers are privileged instructions
Performing Privileged I/O
•
How does a user program perform I/O, if I/O
instructions are privileged?
• System calls – request OS to do I/Os
– Trap to a specific location using an interrupt
vector
– Interrupt service routine sets the mode to system
– Then the routine verifies the parameters are
correct before executing the request
– Set the mode to user before returning control to
the next instruction following the system call
Protection Rings on 386+
Operating System Services
• OS services can include:
• Program Management
– Load, Execution, Removal
•
•
•
•
I/O operations
File-system manipulation
Communication
Error detection & handling
– ….
Operating System Services (cont’d)
• Resource management
– Allocating/De-allocating resources to the
processes
• Account keeping – Recording the usage
of resources for various purposes (e.g.
billing, statistics, etc.)
• Protection – Ensuring that all access to
system resources is controlled
System Calls
• System calls provide the interface between a
running program and the Operating system
• Three normal methods are used to pass
parameters between a running program and
the Operating system
– Through the stack
– Through registers
– Through a table, the table address is in a
register
Example: Gray Code Input
Pseudo-code description:
Start Loop
Using polling - Get input from port A
Mask out all bits except bit 0 and bit 1 to get Gray code.
If Gray code value has changed from previous Gray value
then process the change in Gray code value, else loop
again.
Map Gray code to binary value
Work out difference to previous value +1 or -1.
Process the +/- 1 difference add it to the value to be changed.
Save the current value as the previous value
Loop to start
Gray Code Conversion Software (1)
RAM EQU $2000
org RAM
jmp start
; 68HC11 Equates
REGBAS EQU $1000
Starting address for register block
PORTA EQU $00
; Port A INPUT:PA0..2, OUTPUT:PA3..6, & I/O PA7
; Buffalo Equates:
OUTLHF EQU $FFB2 ; Print left half
OUTRHF EQU $FFB5 ; Print right half
CRLF EQU
$FFC4 ; Print CRLF
Gray Code Conversion Software (2)
PrevGrayCode RMB 1
CurrBinCode RMB 1
PrevBinCode RMB 1
COUNTER
RMB 1
start:
LDAA #0
STAA COUNTER
; The Previous Gray Code
; Gray Code converted to binary
; Previous Binary Code
; Number to increment/decrement
LDX #PORTA+REGBAS
LDAB 0, X
ANDB #%00000011 ; Mask all but bottom 2 bits
STAB PrevGrayCode ; Previous gray value - initialisation
Gray Code Conversion Software (3)
Initialisations:
BSR
Gray2Bin
STAB CurrBinCode
STAB PrevBinCode
; Convert Gray -> Binary code
; Binary equivalent of gray value
; Previous Value of binary value
LoopStart:
LDX #PORTA+REGBAS
LDAB 0, X
ANDB #%00000011 ; Mask all but bottom 2 bits
CMPB PrevGrayCode ; Has the reading changed?
BEQ
LoopStart
; No, so read again
STAB PrevGrayCode ; else Gray Code has changed
Gray Code Conversion Software (4)
; Convert Gray code to Binary
BSR Gray2Bin
* Convert Gray 2 Binary - uses Acc. B
STAB CurrBinCode
SUBB PrevBinCode * subtract previous
* Valid differences are -1 or +3 = down 1, or -3 = up 1
CMPB #1
BEQ Up1
CMPB #-1
BEQ Dn1
CMPB #-3
BEQ Up1
CMPB #3
BEQ Dn1
*
JSR BigStepError * If we get here we have stepped by +/-2
BRA Continue
Gray Code Conversion Software (5)
Up1: ; Subroutine Up1 Knob has been turned clockwise
; Increment - but limit up to 255 - No wrapping back to 0
LDAA COUNTER
CMPA #$FF
; are we already at the maximum?
BEQ ALREADY_MAX ; Branch if already maximum.
INCA
; else increment
STAA COUNTER
; and save result
ALREADY_MAX:
BRA Continue
Gray Code Conversion Software (6)
; Subroutine Dn1 - Knob has been turned anti-clockwise
Dn1:
; Decrement - limit downto 0 - no wrapping to -1
LDAA COUNTER
CMPA #0
; Are we already at the minimum?
BEQ ALREADY_ZERO ; Branch if zero
DECA
; Else Decrement
STAA COUNTER ; and save result
ALREADY_ZERO:
Gray Code Conversion Software (7)
Continue:
* Save new binary value in PrevCode
LDAB CurrBinCode ; Get new binary code
STAB PrevBinCode ; make it previous code also
* Output the hex value to the terminal
LDAA COUNTER
JSR OutHexByte
JSR CRLF
; output carriage return - line feed
BRA
LoopStart
Gray Code Conversion Software (8)
*************************************************
* Convert Gray code in Accumulator B to Binary
*************************************************
Gray2Bin:
CMPB #2
; Is Bit 1 set?
BHS XorBit1 ; Branch if 2 or 3 to XorBit1
RTS
; Do nothing
XorBit1:
EORB #1
; This inverts Bit 0
RTS
; We return with Acc.B = Binary code
Gray Code Conversion Software (9)
OutHexByte:
* Outputs to console the Hexadecimal byte passed in Acc A
PSHB
; Save Acc. B on stack
PSHA
; Save Acc. A twice.
PSHA
;
JSR OUTLHF ; OUTput Left HalF - high nybble
PULA
; Recover Acc.A - byte to display
JSR OUTRHF ; OUTput Right HalF - low nybble
PULA
PULB
RTS
; Restore Acc.A
; Restore Acc.B
; ReTurn from Subroutine
Acknowledgments
• Next Lecture : Swapping & Virtual Memory
• Motorola M68HC11 Reference Manual
• The Indispensable PC Hardware Handbook,
Hans-Peter Messmer, ISBN 0-201-87697-3
• Floppy Disk images from IEEE Electronics
Engineers Handbook, 4th Edition, Donald
Christiansen, ISBN 0-07-021862-5.
• Seng Goh’s original lecture notes on Memory
Management