Class Notes (838,994)
Canada (511,159)
CMPT 225 (60)
John Edgar (28)

CMPT 225 Week 12 Lecture 3

3 Pages
Unlock Document

Computing Science
CMPT 225
John Edgar

Disk Scheduling and External Sorting Hard Drive: consists of number of disks, aligned with each other, sit on spindle Disk head array - series of heads which sit on top of the disks Disk head reads from one side of one disk at a time Raid: composed of multiple disk drives, can be read in parallel, depending on RAID type Data in blocks - possible example, 2048 bytes To read this block, must move disk head to appropriate track Seek Time: in region of 2 to 20 milliseconds - time to move to track you want to read Disk is rotating. Really fast, ~100rps To read data from hard drive: 1. Move disk head to correct track (concentric circles on the disk) 2. Wait for the block that you're trying to read to rotate to the disk head (called rotational latency or delay [but latency sounds cooler] - 4-11 milliseconds) 3. Transfer data as it passes underneath disk head (0.1ms) Reading 1 block from a disk: order of 10ms Suggests that how you organize things on the disk is very important! Can also call blocks pages, pages are abstractions of blocks, can refer to pages on disk and pages in main memory - same size. Reading one page in RAM is in region of 50ns ms = 10^-3s ns = 10^-9s Disk: 10,000,000ns RAM: 50ns Accessing a page in a disk is about 200,000 times slower than accessing page in RAM! Suggests: we would like to minimize the number of times we access hard drives. Also want to minimize as much as possible seek time and rotational latency If want to write algorithm that accesses blocks on a disk, using a simple queue for a disk access algorithm is a bad idea. Algorithms for DiskAccess: Fair algorithms are usually bad (ex using a queue) Elevator algorithm is commonly used for disk access - algorithm that is used by -pause for dramatic effect- elevators. Stops at closest first, regardless of order of buttons pushed. Does not deal with requests in order they are made. Use this to schedule disk requests. External Sorting: Problem: we want to sort a large file currently residing on a disk and the file is too large to fit in main memory Cost Metric: Most concerned with reducing the number of times that the disk is accessed. (read or written) Not as concerned with the number of main memory operations This cost is different than what we were looking at before Goal:An algorithm that
More Less

Related notes for CMPT 225

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.