New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Operating Systems

by: Donnell Kertzmann

Operating Systems CSE 410

Donnell Kertzmann
GPA 3.97


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Computer Science and Engineering

This 69 page Class Notes was uploaded by Donnell Kertzmann on Saturday September 19, 2015. The Class Notes belongs to CSE 410 at Michigan State University taught by Staff in Fall. Since its upload, it has received 39 views. For similar materials see /class/207418/cse-410-michigan-state-university in Computer Science and Engineering at Michigan State University.

Similar to CSE 410 at MSU


Reviews for Operating Systems


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15
Operating Systems CSE 410 Spring 2004 File Management Stephen Wagner Michigan State University File Management a File management system has traditionally been considered part of the operating system Applications are stored as files Input for application is stored in files Output from application is stored in files a File management has become increasingly distributed and removed from the operating system Objectives for a File Management System a Guarantee that the data in the file are valid Optimize performance Provide IO support for a variety of storage device types Minimize or eliminate the potential for lost or destroyed data 0 Provide a standardized set of IO interface routines 0 Provide IO support for multiple users Security User Program I A Pile Sequential Sal Indexed I Hashed Logical IO Basic IO Supervisor Basic File System Disk Device Driver Tape Device Driver Figure 121 File System Software Architecture GROS86 Device Drivers 0 Lowest level a Communicates directly with peripheral devices a Responsible for starting lO operations on a device a Processes the completion of an lO request Basic File System 0 Physical IO 0 Deals with exchanging blocks a Concerned with the placement of blocks a Concerned with buffering blocks in main memory Physical blocks Physical blocks in secondary in main memory Records File buffers storage disk Structure Directory Access management method E DiSk Blocking scheduling User amp program E 1 comands Operation File IO Free storage File name manipulation E management functions File E allocation User access control File management concerns 39 M Operating system concerns Figure 122 Elements of File Management File Organization a Character Files 0 Piles o Sequential Files 0 Indexed Sequential Files 0 Indexed File a Direct or Hashed File Charact r Files 0 File is organized as a sequence 0 characters 0 Basic Operations Seek gtllt Each character has a position in the file gtllt Seek may allow random access or be more restricted Read gtllt User is allowed to read any number of bytes gtllt At lower level blocks are read Overwrite Append Truncate a Very common file organization File Organization with Records a A more sophisticated way is to organize files as records a A record consists of a fixed set of fields a structure Each field has a data type and length All records do not necessarily have the same fields a Character Files can be viewed as a file composed of very simples Records Piles a Data are collected in the order they arrive a Purpose is to accumulate a mass of data and save it 0 Records may have different fields This requires records to be self describing At the very least the length of each record needs to be stored a Record access is by exhaustive search Sequential Files 0 Fixed format used for records 0 All records are identical Same length same fields in same order a Field names and lengths are attributes of the file 0 Can support random access 0 One field is the key field Uniquely identifies the record Records often stored in key sequence alF es Sequen H Sequential Files 0 If files are stored in key sequence adding a record becomes expensive Requires moving records in the file a To reduce the cost records are not immediately added to the file New records are placed in a log file or transaction file Batch update is performed to merge the log file with the master file A special case needs to be made to search the log file Indexed Sequential File 0 Index provides provides a lookup capability to quickly search the file by key 0 Index contains a key field and a pointer to the main file Not every single entry need be indexed 0 Index is used to get close to desired record a Sequential search is used to find desired record Indexed Sequential File Indexed Sequential File a New records are stored in overflow file a Overflow file is periodically merged with main file a Main file includes pointers to entries in overflow file Advantage of Index 0 Example 3 file contains 1 million records a On average 500000 accesses are required to find a record in a sequential file a If an index contains 1000 entries it will take 500 accesses on average to find nearest key in index followed by 500 accesses on average in the main file a A binary search can be used to find the nearest key in index with 10 accesses followed by 500 accesses to main file Indexed F e 0 Uses multiple indices for different key fields a May contain an exhaustive index that contains one entry for every record in the main file a May also contain a partial index Indexed F e Direct File 0 Similar to a sequential file but records are not ordered 0 Records are accessed directly by key 0 Similar to an STL map a Implemented using a hash table Hash function is used to find location of record in file Some sort of chaining is used to handle collisions Implementation of Different File Types 0 Most OS s do not provide direct support for the above file organizations a All of the above organizations can be built on top of character files Piles can be used for web logs Relational databases can be built out of indexed sequential files UNIX dmb files are direct files File Directories 0 Files have several attributes Name Access Privileges Location a To make locating files easy files are organized into directories o The Directory is a file 0 Provides a mapping between file names and files a A Directory is a sequential file sorted by the file name key Hierarchical Directories Directories can contain files an other directories o The directories form a tree 0 Their is some master director The root directory in UNIX 0 Logical Organization Allows users to organize files and directories 0 Physical Organization Allows system to quickly access traverse hierarchy Master Directory Subirectory Subirectory Subirectory Subirectory Subirectory File File File File Master Directory Directory quotUser Cquot Directory quotUser Aquot quotUser Bquot quotWordquot Directory quotDrawquot Directory quotUnit Aquot ABC File quotABCquot File quotABCquot Pathname User BVVordUnitAABC Naming Conventions 0 Files are located by following a path from root directory 0 Several files can have the same file name as long they have unique path names 0 Files can be referenced relative to the current directory File Sharing a In multiuser system files may be shared among users a Two issues Access rights Management of simultaneous access Access Rights 0 None User may not know of the existence of the file User is not allowed to read the user directory that includes the file a Knowledge User can only determine that the file exists and who its owner is Access Rights 0 Execution The user can load and execute a program but not copy it 0 Reading The user can read the file for any purpose including copying and execution o Appending The user can add data to the file but cannot modify or delete any of the file s contents Access Rights 0 Updating The user can modify delete and add data a Changing Protection User can change access rights granted to other users a Deletion User can delete file Access Rights 0 Files have an owner 0 Owner has all rights previously listed 0 Owner may grant rights to others users Specific users User groups Everybody Simultaneous Access 0 System may provide ability to lock a file locks may be at the file level user may be able to lock individual records a Mutual exclusion and deadlock are issues for shared access Record Blocking Records must be organized as blocks for l to be performed Records are the logical unit of access of a file Blocks are the unit of lO with secondary storage 0 Two issues Should blocks be fixed or variable length What should be relative size of a block compared to the average record size 0 Tradeoffs Smaller block more lO operations needed Larger block more records in one lO operation Fixed Blocking xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx D Data g Waste due to record fit to block size lj Ivaps due to hardware 3sign l g Waste due t block size colistraint a frnm YPd 1 hard Qi7P T Waste 1119 m hlnr k t m frank Qi7P Q 7 i i Variable Blocking Spanned Wile D Data Waste due to record fit to block size lj aps due to Waste due to b1 ck size constrw frnm YPd rpr nri Qi7P 7 Waste due to block fit to track size Niii V D Data Waste due to record fit to block size l I rm hardware 3sign Variable Blocking Unspanned i N Niii V D Data Waste due to record fit to block s1ze Gaps due to hardware design Q Waste due to block size constraint from fixed record size 7 Waste due to block fit to track size Secondary Storage Management 0 Space must be allocated to files 0 Must keep track of the space available for allocation Preallocation VS Dynamic Allocation o Preallocation Need maximum size for the file at creation time Difficult to reliably estimate the maximum potential size of the file Tend to overestimate file size so we do not run out of space 0 Dynamic Allocation Allocate space to a file in portions as needed Portion Size a Portion Size the size of the portion allocated to a file 0 Variable large contiguous Advantages better performance avoids waste file allocation tables are small Disadvantage space is hard to reuse 0 Blocks Advantages greater flexibility Disadvantage requires large tables or complex structures for their allocation Free Space Fragmentation 0 Similar problem as allocating dynamic partitions 0 First Fit 0 Best Fit 0 Nearest Fit Choose the unused group of sufficient size that is closest to the previous allocation for the file to increase locality Methods of File Allocation o Contiguous allocation Single set of blocks is allocated to a file at the time of creation Only a single entry in the file allocation table starting block and length of file 0 External fragmentation will occur compaction is needed 0 Need to declare the size ofthe file at the time of creation File Allocation Table File A File Name Start Block Lengh 0 1 2 3 4 FileA 2 3 File B 9 5 5I 6I 7I 8I 9I 18 8 File B File D 30 2 10E III 12 13D 14l 26 3 15 16 17 18 19 2o 21 22F 23 24 25 26D 27 28 29 sogg s i 32 33 34 V Figure 127 Contiguous File Allocation File Allocation Table File A File Name Start Block Lengh 0 1 2 3 4E FileA o 3 File B File B 3 5 leI 6I 7 s 9 gage 189 3 File C 1 e 10 11 7A 12 13 14 me E 16 3 File D 15 16 171 18D 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Figure 128 Contiguous File Allocation After Compaction Methods of File Allocation o Chained allocation Allocation on basis of individual block Each block contains a pointer to the next block in the chain Only single entry in the file allocation table starting block and length of file a No external fragmentation 0 Best for sequential files a Does not take advantage of locality 25 26 27 28 29 30 31 32 33 34 V File Allocation Table File Name Start Block Lengh File B 1 5 Figure 129 Chained Allocation File Allocation Table File B File Name Start Block Lengh 0 1 2 3 4 u 5l 6 7 8 9l 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 File B 0 5 Figure 1210 Chained Allocation After Consolidation Methods of File Allocation 0 Indexed allocation File allocation table contains a separate on Ievel index for each file The index has one entry for each portion to the file The file allocation table contains block number for the index t File Allocation Table File Name Index Block File B 24 25 26 27 28 30 31 32 33 34 V Figure 1211 Indexed Allocation with Block Portions File Allocation Table File Name Index Block 0 1 File B 24 5I 6I 7I 8I 9I 10 11 12 13 14 15E MEI Start Block Length zol21222324 39 1 3 28 4 25 26I 27 28 30 31 32 33 34 V Figure 1212 Indexed Allocation with VariableLength Portions Free Space Management a Bit Tables 0 Chained Free Portions o Indexing a Free Block List U N IX File Management 0 Types of files Ordinary Directory Special Named oI nodes A control structure that contains the key information needed by the OS for a particular file Direct0 Directll Direct2 Direct3 Direct4 Direct5 Direct6 Direct Direct8 Direct9 single indirect ouble indirect triple indirect Inode address fields Blocks on disk Operating Systems CSE 410 Spring 2004 lO Management and Disk Scheduling Stephen Wagner Michigan State University Categories of I O Devices 0 Human readable 0 Machine readable 0 Communications Human Readable lO Devices 0 Used to communicate with the user 0 Printers 0 Video Terminal 0 Keyboard a Mouse 0 Speakers Machine Readable lO Devices 0 Used to communicate with electronic devices 0 Disk and tape drives a Sensors o Controllers Communication lO Devices 0 Networks a Digital Line Drivers 0 Modems Differences in lO Devices 0 Data Rate 0 Application 0 Complexity of Control Data Rate Differences a Different IO devices will have different data rates c There may be several orders of magnitude difference between the data rates a The data rate affects how the OS communicates with the IO Gigabit Ethernet Graphics display Hard disk Ethernet Optical disk Scanner Laser printer Floppy disk Modem Mouse Keyboard 101 102 103 104 105 106 107 Data Rate bps Figure 111 Tvnieal IO Device Data Rates 108 109 Application Differences 0 Disk used to store files requires file management software 0 Disk used to store virtual pages needs special hardware and software a A Terminal used by an administrator may be given higher priority Complexity Differences 0 Unit of Transfer Data may be transferred as a stream of bytes for a terminal or in larger blocks for a disk 0 Data representation 0 Error conditions Techniques for Performing lO o Programmed IO Processor busy waits for the IO to complete Even the fastest IO devices are slow compared to the processor 0 Interru pt d river IO IO command is issued Processor continues executing another process IO module sends an interrupt when it is done Direct Memory Access DMA 0 DMA module controls exchange of data between main memory and lO device 0 Processor interrupted only after entire block has been transferred 0 Processor does not have to be involved in moving every piece of data Evolution of lO 0 Processor directly controls a peripheral device 0 Controller or lO module added Programmed lO used Processor does not need to handle the details of external devices Evolution of lO o Interrupt Driven lO used Processor does not have to spend time waiting for an lO operation to be performed Processor is still busy moving data a Direct Memory Access Blocks of data are moved in and out of memory without involving the processor Processor is only involved at beginning and end


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.