Understanding Disk Scheduling in Multiprogramming Systems

 
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
Platter
Tracks
Track
Sectors
 
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.
 
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.
 
Solid State Drive (SSD)
 
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 Memory Organization: Page
 
 
NAND Memory Organization: Block
 
 
 
SSD Device Architecture
 
 
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
 
Wire Leveling Algorithm
 
 
SSD vs. HDD
 
 
 
 
 
 
 
 
 
 
 
 
From N. Memon’s Slides
Slide Note
Embed
Share

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.


Uploaded on Aug 31, 2024 | 1 Views


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


  1. 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.

  2. Platters Tracks Platter Sectors Track

  3. 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

  4. 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

  5. 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.

  6. 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.

  7. 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.

  8. 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

  9. 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.

  10. 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.

  11. C-LOOK Based on C-SCAN, C-LOOK involves the drive head sweeping across the disk satisfying requests in one direction only.

  12. 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.

  13. Single Layer Cell vs. Multi Layer Cell From Micron

  14. 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)

  15. NAND Memory Organization: Page

  16. NAND Memory Organization: Block

  17. SSD Device Architecture

  18. 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.

  19. 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

  20. Wire Leveling Algorithm

  21. SSD vs. HDD

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#