Introdctn to Operating Systems
Introdctn to Operating Systems EECS 678
Popular in Course
Popular in Elect Engr & Computer Science
This 40 page Class Notes was uploaded by Melissa Metz on Monday September 7, 2015. The Class Notes belongs to EECS 678 at Kansas taught by Prasad Kulkarni in Fall. Since its upload, it has received 56 views. For similar materials see /class/182479/eecs-678-kansas in Elect Engr & Computer Science at Kansas.
Reviews for Introdctn to 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/07/15
15 Chapter 10 Outline l File concept I Accessing file data I Directory structure I Protection of information on disk EECS 678 Introduction to Operating Systems 7 Sp ng 2009 15 File System Abstraction Blockoriented Byteoriented Physical sectors Named files No protection Users protected from one another Data might be corrupted if Robust to machine failures machine crashes EECS 678 Introduction to Operating Systems 7 Sp ng 2009 2 9 Characteristics of a File l Provides a mode of permanent storage of information I Information in a file is related in some way I Files can hold any kind of information 0 text binary applicationdefines structures etc I Files have several attributes 0 name identifier type location size protection and accounting information I File operations 0 basic operations create read write seek delete truncate 0 other operations copy rename list file attributes l Operating system structures 0 systemwide openfile table I processspecific openfile table EECS 678 Introduction to Operating Systems 7 Sp ng 2009 19 File Types I Can indicate the internal structure of a file 0 file extensions can be used to indicate file type I Should OS recognize specific file structures 0 should at least recognize structure of an executable file 0 may require 08 to handle all such structures increasing size 0 may disallow custom userdefined file structures l Unix attempts no interpretation of files 0 application provides code to interpret file structures l Magic number at start of file may recognize file structure 0 inserted by the application creating the file EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 File Types Name Extension file type usual extension function executable exe com bin readytorun machine one language program object obj o compiled machine language not linked source code c cc java pas source code in various languages batch bat sh commands to the command interpreter text txt doc textual data documents word processor wp tex rtf various wordprocessor d formats library lib a so dll libraries of routines for programmers print or view ps pdf jpg ASCII or binaryfile in a format for printing or viewing archive arc zip tar related files grouped into one file sometimes com pressed for archiving or storage multimedia mpeg mov rm binary file containing mp3 avi audio or AV information EECS 678 Introduction to Opemting Systems 7 Spring 2009 15 Accessing Information in a File l Sequential access 0 bytes are accessed in order 0 operations readnexz writenexz rewind skip n records I Random direct access 0 bytes are accessed in any order 0 each access uses a relative address from the start of the file 0 request for record N of length L gt request for L bytes starting at location L N from file start I Indexbased access 0 construct an index for the file 0 user specifies index of the record to retrieve 0 search for index in the indexfile which points to the record on disk EECS 678 Introduction to Operating Systems 7 Sp ng 2009 6 a Accessing Information in a File 2 I Sequential access current position beginning end rewind 1 read or write I I Indexed access logical record last name number Adams Arthur Asher smith john socialsecurity age O 0 O Smith index file relative file EECS 678 Introduction to Operating Systems Spring 2009 File System Organization Disk can be subdivided into partitions O raw partition without a le system formatted partition with a le system Partition containing file system known as a volume Computer systems may have multiple types of file systems 0 general purpose virtual network partition A 0 disk 1 partition B EECS 678 Introduction to Operating Systems 7 Spring 2009 partition C lt directory fi les gt disk 2 gt disk 3 19 Directories l Structure to hold information about the files in a system 0 partition containing a file system is called a volume 0 records name location size type etc of all files in a volume I Directory operations 0 search file create file delete file rename file list directory traverse the file system I Logical organization of a directory for o efficiency locating a file quickly 0 naming convenient to users gt two users can have same name for different files gt the same file can have several different names 0 grouping logical grouping of files by properties eg all Java programs all games I Study several different directory structures EECS 678 Introduction to Operating Systems 7 Sp ng 2009 g SingleLevel Directory l A single directory for all users l Advantages 0 simple structure easy and efficient to support I Disadvantages 0 name collisions multiple usersfiles may have the same name 0 not scalable for large systems 0 cannot group related files together EECS 678 Introduction to Operating Systems 7 Spring 2009 10 TwoLevel Directory I Separate directory for each user 0 OS only searches user directory for les master file directory user file directory cat bo a teslH a dataH a iteslH X data a twill l Disadvantages 0 still not very scalable user cannot name two les the same 0 users may not be allowed to share or group les 0 system les and libraries need to be shared EECS 678 Introduction to Operating Systems 7 Spring 2009 11 at TreeStructured Directories l Generalization of twolevel structure 0 oneroot directory 0 unique path for every le in the directory structure root apeI bin pmgmms 5m marl i ms i i find leounil hex iuomri i p i s mail l l 1 1 GO reorder list li39nd a Ems m In nmcunnln opmung SynanerpnngZOOQ 15 TreeStructured Directories 2 l Advantages o conceptual model maps well into human model of organizing things 0 scalable the probability of name collisions decreases 0 spatial locality store all files under a directory within a cylinder to avoid disk seeks 0 simple searching based on absolute or relative paths 0 grouping capability l Disadvantages 0 not all files fit into the hierarchical model gt some files may need to be listed under multiple directories gt shared files 0 accessing a file may involve many levels of directory lookups gt inefficient EECS 678 Introduction to Operating Systems 7 Sp ng 2009 13 E GUIgt00 Absolute Path Resolution Read the file header for the root directory 0 stored at a fixed location on disk Read the first data block for the root directory lookup directory entry for pets Read the file header for pets Read data block for pet directory lookup entry for catij Read the header file for catij Read the data block for catij r EECS 678 Introduction to Operating Systems 7 Spring 2009 14 5 Absolute Path Resolution 2 l Performance optimizations 0 cache top level directories in memory 0 a user inside a directory eg pets can use relative path names eg catjpg to refer to files within the current directory EECS 678 Introduction to Operating Systems 7 Sp ng 2009 15 5 AcyclicGraph Directories l Allows sharing of files or subdirectories 0 same file appears under multiple directory listings words EECS 678 Introduction to Operating Systems 7 Spring 2009 16 19 AcyclicGraph Directories 2 l Links to implement file sharing 0 pointer to another file or subdirectory 0 directory entry of link points includes the name of the real file 0 OS resolves link using the embedded path name to find the real file I Problem of aliasing 0 shared structures may be traversed more than once 0 do not follow links during directory traversal I If user deletes the shared file 0 symbolic links become dangling pointers 0 search for all links and remove them 0 leave the links but fail to resolve when used 0 what is file is deleted and later file with same name is created before link is used EECS 678 Introduction to Operating Systems 7 Sp ng 2009 17 9 Reliability and Protection l Reliability file system must be safe from physical damage 0 provide duplication using backups on tertiary storage 0 RAID systems I Protection prevent file system from improper access 0 file creatorowner decides who may access the files and 0 how files may be accessed by each user or group EECS 678 Introduction to Operating Systems 7 Spn39ng 2009 18 19 Protection l Types of access 0 read write execute append delete list 0 provide lowlevel protection with read write and execute privilege o higherlevel functions for append list delete rename copy implemented with lowlevel checks l Access control 0 assign different access types to every file directory for each user 0 Access control lists ACL gt associate user name type of access with every file entry gt inefficient variable and large sized directory entry tedious to create AOL for each file 0 Unix provides owner group and universe level permissions gt combine access control list with ownerusergroup form of permissions gt ACLs checked before ownerusergroup permissions EECS 678 Introduction to Operating Systems 7 Sp ng 2009 19 w Access Lists and Groups Mode of access read write execute Three classes of users RWX a owner access 7 1 1 1 RWX b group access 6 1 1 0 RWX c public access 1 gt 0 0 1 Ask manager to create a group unique name say G and add some users to the group For a particular file say game or subdirectory define an appropriate access owanrclmiylic chmod 761 game G game Attach a group to a file chgrp EECS 678 Introduction to Operating Systems 7 Sp ng 2009 19 Windows XP Accesscontrol List Management 10 m Pmpelne 9 Geneval Sacumy Summary Gmup Druggrnamgs zAdmxmslralm PEG LAPTOP vAdmmIsIraImE PEth AF39T pbg CTpbg ZEUsevs PEG LAPTDMUSEVSJ Pevmwssmhs m Guest Aunw Deny FuH Cumml D Mndwfy B Read amp Execme D Ead D Wme D Spema Perrmssmns Fm spam pavmwsslnns mm advanned semnqs chck Advanced EECS 67E Introducnonto Op mung System57 Spnng 2009 a 139w 1 w r chwx drwxrwxr x Cll WXl WX 1 w 1 1 1 wx1 x1 x d1 wx x x drwx d1wx1wx1wx 1 pbg 5 pbg 2 pbg 2 pbg 1 pbg 1 pbg 4 pbg 3 pbg 3 pbg staff 3 1200 staff 5 l 2 staff 5 12 student 5 12 staff 9423 staff 2047 1 faculty 5 12 staff 1024 staff 5 12 Sep 3 0830 Jul 8 0933 Jul 8 0935 Aug 3 1413 Feb 24 2003 Feb 24 2003 Jul 31 1031 Aug 29 0652 Jul 8 0935 EECS 678 Intraducnan m Opantlng Sy ans r Spnng 2009 Permissions in a Unix System int1 0ps private doc student proj programc program lib mail test 3 Chapter 13 Outline I Terms and definitions I Basic concepts EECS 678 Introduction to Operating Systems 7 Sp ng 2009 t Definitions l lO subsystem 0 component of the OS that implements the application lO device interface I Port 0 connection point for an lO device with the computer 0 consists of datain dataout status and control registers l Bus 0 set of wires with protocol for what can be transferred on the bus 0 PCI PClX PCle SCSI HyperTransport etc I Controller 0 circuit to operate a port a bus or a device 0 each device controller provides registers for the CPU to send data and controls signals to that device EECS 678 Introduction to Operating Systems 7 Sp ng 2009 A Typical PC Bus Structure SCSI bus monitor processor l l cache l bridgememory controller graphics controller SCSI controller IDE disk controller keyboard parallel serial port port EECS 678 Introduction to Operating Systems 7 Spring 2009 interface expansion bus I 9 IIO Mechanisms l Polling 0 during lO the computer does nothing but constantly monitor the status register 0 no other way to determine device status 0 inefficient wastes CPU resources I Interrupts 0 device asynchronously notifies the CPU on status changes O HO devices produce hardware interrupt software interrupt is a synchronous event in software 0 save current execution state context switch and begin execution of an interrupt service routine interrupt handler 0 CPU typically provides 12 pins for indicating interrupts o interrupts have priorities may be maskable O efficient EECS 678 Introduction to Operating Systems 7 Sp ng 2009 InterruptDriven IIO Cycle CPU lO controller device driver initiates IO initiates IO CPU executing checks for interrupts between instructions input ready output mplete or error generates interrupt signal CPU receiving interrupt transfers control to interrupt handler interrupt handler processes data returns from interrupt CPU resumes processing of interrupted task EECS 678 Introduction to Operating Systems 7 Spring 2009 t IIO Mechanisms 2 l Direct Memory Access 0 used to avoid programmed IIO for large data movement 0 DMA controller allows direct data transfers between memory and devices disk controllers graphics controllers network cards etc 0 CPU initiates the DMA transfer 0 bypasses CPU to transfer data directly between lO device and memory 0 CPU free to do other tasks EECS 678 Introduction to Operating Systems 7 Sp ng 2009 19 Steps to Perform DMA Transfer 1 device driver is told to transfer disk data to buffer at address X 5 DMA controller 2 device driver tells transfers bytes to disk controller to buffer X increasing transfer C bytes memory address from disk to butter and decreasing C at address X until C 0 6 when C 0 DMA interrupts CPU to signal transfer completion DMAbus interrupt controller PCI bus l 3 disk controller initiates lDE disk DMA transfer controuer 4 disk controller sends each byte to DMA controller EECS 678 Introduction to Operating Systems 7 SpIing 2009 sf IIO Device Categories l Block device 0 stores information in fixed sized blocks 0 each block has its own address 0 generally use buffered input and output routines o eg disks l Character device 0 delivers or accepts a stream of characters 0 individual characters are not addressable 0 often use unbuffered input and output routines o eg keyboards printers network cards EECS 678 Introduction to Operating Systems 7 Sp ng 2009 t IIO Device Addressing l Memorymapped HO 0 same CPU instructions to access both memory and devices 0 same address bus to address both memory and devices 0 reduces memory addressing space 0 reduces CPU logic and complexity l Portmapped HO 0 dedicated CPU instructions to access lO devices 0 separate lO bus or extra lO pin to allow lO addressing 0 full address space can be used for memory 0 easier to distinguish memory and lO operations in assembly programs EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 Virtual Memory Outline I Background l Demand Paging l CopyonWrite l Page Replacement l Allocation of Frames l Thrashing l MemoryMapped Files I Allocating Kernel Memory l Other Considerations l OperatingSystem Examples EECS 678 Introduction to Operating Systems 7 Sp ng 2009 15 Background l Virtual memory separation of user logical memory from physical memory 0 only part of the program needs to be in memory for execution o logical address space can therefore be much larger than physical address space 0 allows address spaces to be shared by several processes 0 allows for more efficient process creation I Benefits of not requiring the entire program in memory before execution 0 programs can be larger than the physical address space 0 more programs can be resident in memory at the same time o faster program startup EECS 678 Introduction to Operating Systems 7 Sp ng 2009 If I Space between heap and stack is not used unless the heap or stack grows l Shared memory Virtualaddress Space stack virtual memory does not require physical pages for such holes pages can be easily shared by virtual memory shared libraries can be mapped readonly into address space of heap each process data shared memory IPC can be implemented easily code parent pages can be shared with 0 child during fork EECS 678 Introduction to Operating Systems 7 Spring 2009 Shared Library Using Virtual Memory stack stack 1 shared shared library pages shared library heap heap data data code code EECS 678 Introduction to Operating Systems 7 Spring 2009 5 Demand Paging l Bring a page into memory only when it is needed 0 less lO needed 0 less memory needed 0 faster response 0 more applications simultaneously resident in memory I Page is needed gt reference to it 0 invalid reference gt abort O notinmemory gt bring to memory I Lazy swapper never swaps a page into memory unless page will be needed 0 Swapper that deals with pages is a pager EECS 678 Introduction to Operating Systems 7 Sp ng 2009 9 Demand Paging System program A program B HHHHWH main memorv swap out swapin 16D17 18 19 0D1D 2E SE 4 5 e 7 8D 9I1011I 12D13E114D15D 20 D21 D22 ljzslj EECS 678 Introduction to Operating Systems 7 Spring 2009 g5 ValidInvalid Bit l Each page table entry associated with a valid invalid bit 0 v gt inmemory i gt notinmemory 0 Initially set to Invalid for all page table entries Frame validinvand bit I Example of a page table snapshot v V V page I Valid invalid bit in page table set to i during address translation causes a page fault EECS 678 Introduction to Operating Systems 7 Sp ng 2009 7 5 Page Table When Some Pages Are Not in Main Memory valid nvalid Dm mmALoNKO page table logical memory 7 nhvsical memon EECS 678 huroduction to Opemiing Systems 7 111ng 2009
Are you sure you want to buy this material for
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'