Operating Systems CMPSC 473
IO Virtualization: Basics; Magnetic disk drives; File systems
Lectures 26: April 22 2021 Instructor: Bhuvan Urgaonkar
• Project 3 grading
Administrative matters
– 20% “grace” points to everyone, scores normalized to maximum (i.e., min – 20/140, max – 140/140)
– TAs ended up going through all your code, so no need for interviews
– Expect to see your grade by Tuesday, April 27
• Samplefinalexamtocomeoutearlynextweek:
– Final will be OPEN-BOOK/NOTES/SLIDES but CLOSED-INTERNET
– Noreadymadesolutionsorsolutionsonpiazza/canvasbyteachingstaff
– If you need help, come to our OHs
Administrative matters
• Project 2 and 3 AI violations
– Someofyouwillreceiveemails
– We will interview you to determine next steps
• Changestomyofficehours:
– Fridays2:30-4:30fortherestofthesemester
Quiz 26.1: Multiplex
We saw that the following provides mutual exclusion
Semaphore S = 1; // initialized to 1 wait (S);
Critical Section signal (S);
What guarantee do you think the following provides?
Semaphore S = N; // initialized to N > 1 wait (S);
Critical Section signal (S);
A Canonical Computer
On your own, if interested
• Find out data transfer rates for the various busses and devices in the previous diagram
Recall: Process view of IO devices
• ProcessesmakeuseofIOdevicesviathesystemcallinterface
• Very commonly, a unified file abstraction is offered even across disparate IO devices
– Made popular by UNIX
• /proc/devices
• /dev
– Major and minor numbers
• Majornumberidentifiesthedriverforthedevice
• Minor number used by the driver to distinguish multiple devices it may be managing
– Character vs. block devices
• Characterdevicesexchangedataatabytegranularity,nobuffering,norequestreordering
• Character vs. block
Remarks on device diversity
• Regularfilesvs.device(special)files
• Pseudo-devices
– e.g., /dev/null, /dev/zero
• AusefulclassificationofIOstyles(implicationsforeaseof programming vs efficiency):
– Synchronous or blocking – we will be concerned with this, e.g., file system operations
– Asynchronousornon-blocking–e.g.,certainformsofnetworkingsuchasselect()
A Canonical Device
• Internal structure
– Complex devices have a simple CPU, memory, other chips • Software running within the device called “firmware”
• Hardwareinterface
– E.g., STATUS, COMMAND, DATA registers that the (main) CPU can read/write
Methods of Device Interaction
• Programmed IO
– CPU uses special IO instructions
– Recall: privileged, so issued by OS
– E.g., in and out for the x86 ISA
• Memory-mapped IO
– Hardwaremakesdeviceregistersavailableasiftheywerememorylocations
– Loads and stores to these memory locations are routed by hardware to these devices instead of main memory
The Canonical Protocol
• Programmed IO, based on “polling”
– CPUresponsibleforcheckingdevicestatus
• Two main approaches (possibly used together) to lower overheads: – Eventnotification(intheformofinterrupts)
– Direct Memory Access (DMA) engine
Interrupts
• E.g., read some data from a device (1 and 2: processes; p: polling)
Interrupts
• E.g., read some data from a device (1 and 2: processes; p: polling)
Interrupts
• E.g., read some data from a device (1 and 2: processes; p: polling)
• Improved overlap between IO and CPU => better CPU utilization
• Sometimespollingismoreefficient – Extremelyfastdevices
– See more discussion in OSTEP 36.4
– Analogize with polling vs. yielding in locks
Direct Memory Access
• E.g., writing some data to the disk
Direct Memory Access
• E.g., writing some data to the disk
• “… is essentially a very specific device within a system that can orchestrate transfers between devices and main memory without much CPU intervention.”
• Instead of doing programmed IO, the CPU can
– Program the DMA engine by telling it where the data lives in memory, how much data to copy, and which device to send it to
– At that point, the OS is done with the transfer and can proceed with other work
– When the DMA is complete, the DMA controller raises an interrupt, and the OS thus knows the transfer is complete
• Single DMA in older systems, per-device DMA these days
• Historical note: both interrupts and DMA can be traced back to the mid 50’s!
Direct Memory Access (2)
• Explore on your own if interested (not on syllabus)
• Generally, DMA engines work with physical addresses
– Device drivers have to be careful to ensure that physical pages being used are: • Contiguous
• May not swapped be out during the transfer
• More recently: IOMMU
• Programmed IO
– CPU uses special IO instructions
– Recall: privileged, so issued by OS
– e.g., in and out for the x86 ISA
Methods of Device Interaction
• Memory-mapped IO
– Hardwaremakesdeviceregistersavailableasiftheywerememorylocations
• Analogizewithmemorymappingfiles
– Quiz 26.2: Where in the address space would these memory locations be?
– Loads and stores to these memory locations are routed by hardware to these devices instead of main memory
• “There is not some great advantage to one approach or the other. The memory- mapped approach is nice in that no new instructions are needed to support it, but both approaches are still in use today.”
How to make OS device-neutral?
• Solved by separating out hardware-independent and hardware-dependent portions
– Devicedriversarehardware-specificpiecesoftheOSthatexposedevice-independentabstractions to other parts of the OS
• Quiz26.3:Offerexamplesofsimilarseparationwehaveseenfor
– CPU management
– Memory management
The Device Driver
• A device driver is a part of the OS that creates an abstract (and generally easier to use) interface via which the rest of the OS interacts with the device
• Pro: restricts device-specific details to only this piece of code making programming the rest of OS easier and “steady” in the face of device evolution
• Con: Some special functionality offered by the device may not be exploited well
• Generally, represent the bulk of OS code; also a dominant source of OS bugs
CPU/Memo Sub-system
Disk interface to OS
• Thediskconsistsofalargenumberofsectors – Sector size: 512B
– Numbered 0 to n-1 on a disk with n sectors
– Read or written atomically
– Multi-sector operations need to be made atomic by OS
• Filesystemstypicallyread/writeinunitsofblocks;eachblock consists of multiple sectors
• “Tornwrite”:onlyaportionofamulti-sectorwritefinishesdueto an intervening failure (e.g., power loss)
Magnetic storage medium
• Platters made of a hard material such as aluminum, coated with thin layer of ferromagnetic material
• Data stored by magnetizing this material, direction of magnetization interpreted as 0 or 1
• Persistent medium – data remains even when powered off
• A really cool video on the basics:
– https://www.youtube.com/watch?v=AfmTaOJMoUk