DOC PREVIEW
U of I CS 241 - Lecture notes

This preview shows page 1-2-3-23-24-25-26-46-47-48 out of 48 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

FilesQuizAllocation of Disk SpaceContiguous AllocationContiguous Allocation IssuesSlide 6External Fragmentation Solution: Linked allocationLinked AllocationLinked List AllocationSlide 10Linked List Allocation IssuesSlide 12#3. Indexed AllocationIndexed AllocationSlide 15Linked Indexed FilesMultilevel Indexed FileSingle File Access ConceptsDisk SchedulingDetailed View of a DiskSlide 21Slide 22Disk Performance Factor: SeekingDisk Performance: Other FactorsDisk Examples (Summarized Specs)Disk BehaviorsQuestionSlide 28Disk Scheduling - FIFOFIFO (FCFS) orderScheduling – Shortest Seek Time FirstSlide 32SSTF (Shortest Seek Time First)Scheduling - ScanElevator (SCAN)Scheduling – C-ScanC-SCAN (Circular SCAN)Disk LayoutFile System Implementation -PartitionsDOS File Allocation (Linked List)UNIX i-Nodes (Indexed)Free Space ManagementAlternativeMore Complex Free Space ManagementSlide 45Network File System (NFS)Examples of remote mounted file systemsLogical view: Mounted File SystemCopyright ©: Nahrstedt, Angrave, Abdelzaher 1FilesCopyright ©: Nahrstedt, Angrave, Abdelzaher2QuizA UNIX file system has 512B blocks and 4B block address pointers. What’s the max file size in bytes given what you know of the i-node structure?Copyright ©: Nahrstedt, Angrave, Abdelzaher3Allocation of Disk SpaceLow level access methods depend upon the disk allocation scheme used to store file data ContiguousLinked listBlock or indexedCopyright ©: Nahrstedt, Angrave, Abdelzaher4Contiguous AllocationCopyright ©: Nahrstedt, Angrave, Abdelzaher5Contiguous Allocation IssuesAccess method suits sequential and direct accessDirectory table maps files into starting physical address and lengthEasy to recover in event of system crashFast, often requires no head movement and when it does, head only moves one trackCopyright ©: Nahrstedt, Angrave, Abdelzaher6Contiguous Allocation IssuesFile is allocated large contiguous chunksExpanding the file requires copyingDynamic storage allocation - first fit, best fitExternal fragmentation occurs on diskCopyright ©: Nahrstedt, Angrave, Abdelzaher7External FragmentationSolution: Linked allocationCopyright ©: Nahrstedt, Angrave, Abdelzaher8Linked AllocationCopyright ©: Nahrstedt, Angrave, Abdelzaher9Linked List AllocationEach file is a linked list of chunksPointers in list are not accessible to userDirectory table maps files into head of list for a fileA node in the list can be a fixed size physical block or a contiguous collection of blocksEasy to use - no estimation of size necessaryCopyright ©: Nahrstedt, Angrave, Abdelzaher10Linked List AllocationCan grow in middle and at endsSpace efficient, little fragmentationSlow - defies the principle of locality. Need to read through linked list nodes sequentially to find record of interest blocksSuited for sequential access but not direct accessCopyright ©: Nahrstedt, Angrave, Abdelzaher11Linked List Allocation IssuesDisk space must be used to store pointers (if disk block is 512 bytes, and disk address requires 4 bytes, then the user sees blocks of 508 bytes)Not very reliable. System crashes can scramble files being updatedImportant variation on linked allocation method: `file-allocation table' (FAT) - OS/2 and MS-DOSCopyright ©: Nahrstedt, Angrave, Abdelzaher12Linked List Allocation IssuesSummary: linked allocation solves the external fragmentation and size-declaration problems of contiguous allocation,However, it can't support efficient direct accessCopyright ©: Nahrstedt, Angrave, Abdelzaher13#3. Indexed AllocationCopyright ©: Nahrstedt, Angrave, Abdelzaher14Indexed AllocationSolves external fragmentationSupports sequential, direct and indexed accessAccess requires at most one access to index block first. This can be cached in main memoryCopyright ©: Nahrstedt, Angrave, Abdelzaher15Indexed AllocationFile can be extended by rewriting a few blocks and index blockRequires extra space for index block, possible wasted spaceExtension to big files issuesCopyright ©: Nahrstedt, Angrave, Abdelzaher16Linked Indexed FilesLink full index blocks together using last entry.Copyright ©: Nahrstedt, Angrave, Abdelzaher17Multilevel Indexed File Multiple levels of index blocksCopyright ©: Nahrstedt, Angrave, Abdelzaher18Single File Access ConceptsLog Sequential Direct or HashedCopyright ©: Nahrstedt, Angrave, Abdelzaher19Disk SchedulingCopyright ©: Nahrstedt, Angrave, Abdelzaher20Detailed View of a DiskCopyright ©: Nahrstedt, Angrave, Abdelzaher21Disk SchedulingSeek timeRotation timeTransfer timeCopyright ©: Nahrstedt, Angrave, Abdelzaher22Disk SchedulingSeek timeAvg rotation time = ½ revolution timeTransfer time = (transfer speed)/(size)Copyright ©: Nahrstedt, Angrave, Abdelzaher23Disk Performance Factor: SeekingSeeking: position the head to the desired cylinderRoughly takes 2-5msSeeking speed depends on:The power available for the pivot motorhalving the seek time requires quadrupling the power)The arm’s stiffness. Accelerations of 30-40g are required to achieve good seek times, and too flexible an arm can twist and bring the head into contact with the platter surface. A seek is composed ofA speedup, a coast , a slowdown, a settleFor very short seeks, the settle time dominates (1-3ms)Copyright ©: Nahrstedt, Angrave, Abdelzaher24Disk Performance: Other FactorsRotational delayWait for a sector to rotate underneath the headsTypically 8.3  6.0 ms (7,200 – 10,000RPM) or ½ rotation takes 4.15-3msTransfer bytes Average transfer bandwidth (15-37 Mbytes/sec)Performance of transfer 1 KbytesSeek (5.3 ms) + half rotational delay (3ms) + transfer (0.04 ms)Total time is 8.34ms or 120 Kbytes/sec!What block size can get 90% of the disk transfer bandwidth?Copyright ©: Nahrstedt, Angrave, Abdelzaher25Disk Examples (Summarized Specs)Seagate BarracudaIBM Ultrastar 72ZXCapacity, Interface & ConfigurationFormatted Gbytes 28 73.4Interface Ultra ATA/66 Ultra160 SCSIPlatters / Heads 4 / 8 11/22Bytes per sector 512 512-528PerformanceMax Internal transfer rate (Mbytes/sec) 40 53Max external transfer rate (Mbytes/sec) 66.6 160Avg Transfer rate( Mbytes/sec) > 15 22.1-37.4Multisegmented cache (Kbytes) 512 16,384Average seek, read/write (msec) 8 5.3Average rotational latency (msec) 4.16 2.99Spindle speed (RPM) 7,200 10,000Copyright ©: Nahrstedt, Angrave, Abdelzaher26Disk BehaviorsThere


View Full Document

U of I CS 241 - Lecture notes

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?