Understanding Disk Scheduling in Multiprogramming Systems
In a multiprogramming system, several processes may contend for disk resources. Disk scheduling aims to efficiently share the disk drive's resources among processes, maximizing I/O request satisfaction while minimizing head movement. Various disk scheduling policies like FCFS, SSTF, and SCAN aim to balance throughput and response time. A practice scenario illustrates how these algorithms work in servicing requests. Images and descriptions further elucidate the concepts and goals of disk scheduling.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Disk scheduling In multiprogramming systems several different processes may want to use the system's resources simultaneously. The disk drive needs some mechanism to resolve this contention, sharing the resource between the processes fairly and efficiently.
Platters Tracks Platter Sectors Track
Disk scheduling goals In order to satisfy an I/O request the disk controller must first move the head to the correct track and sector. maximize the number of I/O requests minimize the movement of the head
Disk scheduling goals trade-off between throughput (the average number of requests satisfied in unit time) and response time (the average time between a request arriving and it being satisfied) => Disk scheduling policies
FCFS The disk controller processes the I/O requests in the order in which they arrive. This policy aims to minimize response time with little regard for throughput. the head may move almost randomly across the surface of the disk.
Practice Assume that a disk has 100 cylinders labeled 0-99. The read head is positioned over the cylinder 50 moving toward the cylinder 99. Accessing data requires 5 time unit, moving from one cylinder to the next require 1 time unit. The incoming requests arrive as follows: Arrive time: 0 15 32 40 55 63 123 Cylinder : 10 35 78 92 60 75 40 What is the order of the requests which will be serviced by FCFS disk scheduling algorithm? Each request is labeled by the cylinder it accesses.
Shortest Seek Time First (SSTF) Each time an I/O request has been completed the disk controller selects the waiting request whose sector location is closest to the current position of the head. time spent in movement is minimized but a request may be delayed for a long period if many closely located requests arrive just after it.
SCAN The drive head sweeps across the entire surface of the disk visiting the outermost cylinders before changing direction and sweeping back to the innermost cylinders It selects the next waiting requests whose location it will reach on its path backwards and forwards across the disk. movement time should be less than FCFS the policy is clearly fairer than SSTF
LOOK Similarly to SCAN, the drive sweeps across the surface of the disk, satisfying requests, in alternating directions. a sweep out towards the outer edge of the disk will be reversed when there are no waiting requests for locations beyond the current cylinder.
Circular SCAN (C-SCAN) C-SCAN is similar to SCAN but I/O requests are only satisfied when the drive head is traveling in one direction across the surface of the disk. Go from the innermost cylinder to the outermost cylinder satisfying the waiting requests When it reaches the outermost cylinder it sweeps back to the innermost cylinder without satisfying any requests.
C-LOOK Based on C-SCAN, C-LOOK involves the drive head sweeping across the disk satisfying requests in one direction only.
Solid State Drive (SSD) Flash Memory based on NAND Cell: Simplest Structure, Array When a charge is applied, the electrons tunnel into the cell through the dielectric barrier. When the charge is stopped the electrons are trapped in the cell. The resulting positive or negative charge can then be measured.
Single Layer Cell vs. Multi Layer Cell From Micron
SSD Layout Example: 4GB MLC Flash Cell - 2 bits Page 4KB (8,192 cells) Block - 256KB (64 pages) Plane 524MB (2048 blocks) Chip/Die 2GB (4 planes) Drive 4GB (2 chips/dies)
NAND Flash Page Series of floating gates and cells all connected. A write occurs starting from the source, and writing down the entire page. A read requires a measurement of the sink, which totals up the values of the floating gates.
NAND Operations Block Erasure Memory Wire: Finite number of program-erase cycles, 100,000 P/E cycles ---- Wire Leveling (spread write operations between sectors) Read Disturb: Read NAND flash memory can cause other cells near the cell being read to change over time if the surrounding cells of the block are not rewritten Delete-before-write (Garbage collection, Overprovisioning, TRIM) Flash deletes in blocks of 128KB. Expensive operation Write amplification
