1
Q
file system components
A
interface
implementation
mass-storage structure: lowest level of the fs, the secondary and tertriary storage structures
2
Q
block devices
A
hard disks, SSDs
store information in fixed-sized blocks
transfers are in units of entire blocks
I/O occurs with random access (by block ID)
3
Q
character devices
A
printers, network interfaces
no blocks, only stream of characters/bytes
not addressable, doesn’t have any seek operation
I/O occurs with sequential access
4
Q
device controller
A
- Located between actual device and computer
- Offers electronic interface in form of I/O registers
- R/W those registers to ask the controller to perform actions
- e.g. parallel port, usb
5
Q
port-mapped I/O
A
two address spaces: main memory + ports
I/O Registers are accessed via dedicated port numbers and special instructions
6
Q
memory-mapped I/O
A
one address space
I/O Registers are mapped into addresses of main memory and accessed like memory
7
Q
hybrid I/O
A
two address spaces
Both implementation can coexist on a given architecture
8
Q
I/O requests
A
Most devices offer status bits in their registers to signal that a request has been finished (and the error code)
OS can poll this status bit (polling)
9
Q
polling / busy waiting
A
after outputting a character, the CPU continuously polls the device to see if it is ready to accept another one
10
Q
interrupts
A
Device controller can trigger interrupts to signal that an I/O request is complete
=> For the device, this means simply changing the voltage on an electrical interrupt line
- Each controller has interrupt vector assigned
- CPU runs vector-specific handler when int occurs
11
Q
trap
A
deliberate action from a program, software interrupt
12
Q
fault (exception)
A
usually not deliberate, typically caused by programs
13
Q
hardware interrupt
A
device such as printer or network sends a signal to the CPU
14
Q
precise <-> imprecise interrupts
A
precise: state is consistent- everything before the interrupt is executed and after isn’t
imprecise: doesn’t have the same guarantee
15
Q
Data Exchange Between Device and CPU
A
- Program disk controller reads a sector
- Wait for interrupt
- Read sizeof(sector) bytes from I/O registers
- Repeat for next sector
16
Q
DMA
A
hardware does the data transfer
17
Q
DMA steps
A
- CPU programs the DMA controller
- DMA requests transfer to memory from disk controller
- data transferred to/from main memory
- ack sent to DMA controller
- interrupt sent to the CPU when done
18
Q
DMA controller
A
- On ISA systems there was a dedicated DMA controller (third-party DMA)
- On PCI (and PCIe) systems each PCI device may become “Bus Master” and perform DMA (first-party DMA)
- Device and DMA controller are combined
- problem: You have to trust your Hw
- Embedded systems still have a dedicated DMA controller
- Disk controller still uses own buffers
19
Q
issues in I/O software
A
- Device independence
- Uniform naming
- Error handling
- Buffering
- Synchronous vs asynchronous
20
Q
device independence
A
- I/O software provides abstraction over actual hardware
- Programs should not have to care about device particularities
21
Q
uniform naming
A
- We don’t want to type ST6NM04 to address the first hard disk
- /dev/sda is better
- /mnt/movies even better
22
Q
error handling
A
errors should be handled closest to their source
23
Q
buffers
A
networking: incoming packets have to be buffered
audio: buffering to avoid clicks
24
Q
synchronous vs asynchronous
A
- Programs don’t want to deal with interrupts → OS turns async operations into blocking operations
- Lower levels have to deal with interrupts, DMA, etc.
25
I/O software layers + their functions
1. user processes: make i/o call, format i/o, spooling
2. device-independent software: naming, protection, blocking, buffering, allocation
3. device drivers: set up device registers, check status
4. interrupt handlers: wake up driver when i/o completed
5. hardware: perform i/o operation
26
i/o storage devices
SSD
HDD
27
SSD vs HDD
28
DRAM
or NOR/NAND flash memory
no mechanical parts (only controller + memory)
can be used as part of SSHDs
29
NAND flash memory
organised in cells, pages, blocks
controller can read/program at page granularity
controller can erase at block granularity
RND/SEQ access latency comparable
reads more efficient than writes
wear levelling to improve write endurance
garbage collection to implement write operations
30
HDD
hard disk drive
multiple platters and cylinders in a single disk with as many tracks as their heads
each track has N sectors
31
HDD addressing modes
CHS (cylinder-head-sector): virtual/physical
LBA (logical block addressing): virtual
32
HDD block read/write time factors
seek time: the time to move the arm to the proper cylinder
rotational delay: the time for the sector to come under the head
data transfer time: the time to transfer a single block
33
Disk Arm Scheduling algorithms aspects
- we want: fast access time and large disk bandwidth
- access time: seek time + rotational latency
- seek time: time for the disk arm to move the heads to the cylinder with the desired sector
- disk bandwidth: total number of bytes transferred / total time between the first request for service and the completion of the last transfer
- total head movement: sum of differences between sectors between which the moves happpened
34
FCFS disk
- the requests are addressed in the order they arrive in the disk queue
- fair algorithm
- no starvation: every request gets its turn
35
shortest seek first
can cause starvation: incoming requests can cause a previous one to not get its turn (we are at 15 and 99 waits, but we get 13 then 2, 7 etc.)
36
elevator algorithm
- scan from one end to the other
- no starvation
- a request that arrives just behind the head it will have to wait for the head to change direction even though it is right next to it
37
Hard Disk Errors
programming errors: request for nonexistent sector
transient errors: cause by dust on the head
permanent errors: disk block physically damaged
seek errors: the arm was sent to cylinder 6 but i went to 7
controller errors: controller refuses to accept commands
38
HD bad sector remapping
1. A disk track with a bad sector
2. Substituting a spare for the bad sector
3. Shifting all the sectors to
bypass the bad one
39
clock hardware types
- Simple clocks deliver hardware interrupts for each voltage cycle of the power supply (i.e., every 20 or 16.7 ms)
- Advanced programmable clocks that have own crystal oscillator that decrements a counter in a register. If counter hits zero → HW interrupt
40
duties for a clock driver
1. Maintaining the time of day
- System boot time (backup clock) + uptime (ticks)
2. Preventing processes from running longer than allowed
- Decrement current process' quantum at each tick
3. Accounting for CPU usage
- Increment current process’ cpu time at each tick
4. Handling alarm system call from user processes
- Decrement alarm counter at each tick
5. Providing watchdog timers for parts of system itself
- Generate sys notifications for synchronous alarms
6. Profiling, monitoring, statistics gathering
- Increment specific counters at each tick
41
magnetic disk physical geometry
Displays the actual structure of a disk with two zones, showing concentric circles representing tracks and numbered sectors on each track
42
magnetic disk virtual geometry
Represents the simplified view presented to the operating system, where the disk is organized into a different
43
magnetic disk
- provides the bulk of secondary storage for modern computer systems
- the surfaces are covered with a magnetic material → we store information by recording it magnetically on the platters
- read-write head
- reads and writes are equally fast, which makes them suitable as secondary memory (paging, file systems, etc.)
- Organized into cylinders, tracks, and sectors; modern disks have multiple heads (1 to 16).
- Older disks depended on the controller; modern SATA disks have integrated microcontrollers for optimized performance.
- Features like overlapped seeks and simultaneous operations on multiple drives reduce access times.
44
disk structure
- large one-dimensional arrays of logical blocks
- logical blocks: the smallest unit of transfer, usually 512 bytes
- the array is mapped onto the sectors of the disk sequentially
- Hard disks consist of stacked platters (3.5-inch or 2.5-inch).
- Initially, disks have no data.
45
disk formatting
1. low-level formatting
2. logical formatting
46
low-level formatting
before a disk can store data, it must be divided into sectors that the disk controller can read and write
47
disk sector layout
1. preamble: starts with a certain bit pattern that allows the hardware to recognize the start of the sector
2. data
3. ECC: error-correcting code
48
disk sector
- Requires software to format each platter into concentric tracks with sectors and gaps.
- Sector format includes a preamble, cylinder and sector numbers, a data portion, and an error correction code (ECC)
- Common sector(data) size is 512 bytes
- Spare sectors are reserved for replacing defective ones
49
logical formatting
1. partition the disk into one or more groups of cylinders
2. logical formatting: the os stores the ds data structures onto the disk
50
disk capacity
- Formatted capacity is usually about 20% lower than unformatted capacity due to formatting overhead and spare sectors.
- Confusion exists between advertised (unformatted) and actual (formatted) capacities.
- Different interpretations of terabytes (TB) vs. tebibytes (TiB) add to the confusion.
51
disk partitioning
- After formatting, disks are partitioned to allow multiple operating systems.
- MBR (Master Boot Record) and GPT (GUID Partition Table) support different disk sizes and partitioning methods.
- The partition table outlines starting sectors and sizes of partitions.
52
high-level formatting
- Each partition undergoes high-level formatting to establish a file system.
- This includes creating a boot block, free storage administration, and differentiating file systems.
- The system can then boot using the appropriate partition marked as active.
53
boot process
BIOS reads GPT upon power-on to locate the bootloader for the operating system.
54
boot block
- the bootstrap program: initialises all aspects of the system = starts the computer
- boot disk or system disk
- most computers store the bootstrap program in the ROM → the bootstrap can’t be changed → put to disk so we can alter it if needed
55
bootstrap loader program
in ROM, brings full bootstrap program from the disk
56
bad disk sectors
blocks that are damaged and can't be used
57
bad sector handling
manual
sector sparing or forwarding
sector slipping
58
manual bad sector handling
format finds a bad block → write a special value in the corresponding FAT entry
59
sector slipping
- the controller maintains a list of bad blocks on the disk
- initialised at low-level formatting
- set aside a spare sector not visible to os
60
sector sparing or forwarding
- also has spares
- logical block n is defective and first available spare is at m
- remaps all sectors from n to m moving them down one spot: m is copied to the spare, then m-1 into m, and so on until n + 1 is copied into n + 2
- this frees n + 1 so that we **keep sequential order**
61
RAID
redundant arrays of independent disks
- a way of storing the same data in different places on multiple hard disks or SSDs to protect data in the case of failure
- higher data transfer rate and higher reliability
- working
- it places data on mutliple disks and allows I/O operations to overlap in a balanced way, thus improving performance
- increases mean time between failures
- disk mirroring: copying identical data to more than one drive
→ expensive
- disk stripping: spread data over multiple disk drives
- improvement of reliability over redundancy
62
RAID level 0
no mirroring
blocks are split between disks
63
RAID level 1
mirroring
data is duplicated
improves reading rate
fault tolerance
64
RAID level 2
stripping not mirroring
disks with data + disks wit parity for each block
parity data used for error detection and correction
65
RAID level 3
bits are stripped + single parity bit
66
RAID level 4
block-level stripping + parity per block
67
RAID level 5
parity after each block ( a1, a2, a3, a_parity, b1, b2, b3, b3, b_parity…)
68
RAID level 6
like 5 but we use multiple parities → guarding against multiple disk failures
69
stable storage
- data is never lost
- replicate data on multiple storage devices with independent failure modes
- partial failure: during the write some data is not damaged some is
- total failure: before the write started
- for each logical block must maintain two physical blocks
- when changing them first complete the write to the first one before changing the second one
- during recovery both blocks are examined
- if one is corrupted then replace it with the contents of the other one
- if neither has an error but the contents differ, replace the content of the first block with that of the second
70
Operating Systems
flashcards
Decks in class (8)
# Cards
