COMP 3430 Operating Systems – Chapter 39 and 40 reading notes
Winter 2022
About these reading notes
Chapter 39: Interlude: files and directories
Copyright By PowCoder代写 加微信 powcoder
39.1filesanddirectories ……………………………. 2 39.2Thefilesysteminterface …………………………. 3 39.3Creatingfiles……………………………….. 3 39.4Readingandwritingfiles …………………………. 3 39.5Readingandwriting,butnotsequentially…………………. 4 39.6Sharedfiletableentries………………………….. 4 39.7Writingimmediatelywithfsync()……………………. 4 39.8Renamingfiles………………………………. 5 39.9Gettinginformationaboutfiles………………………. 5 39.10Removingfiles ……………………………… 5 39.11Makingdirectories ……………………………. 5 39.12Readingdirectories……………………………. 5 39.13Deletingdirectories. …………………………… 6 39.14Hardlinks………………………………… 6 39.15Symboliclinks ……………………………… 6 39.16Permissionbitsandaccesscontrollists………………….. 6 39.17Makingandmountingafilesystem ……………………. 6
Chapter 40: File System Implementation
40.1Thewaytothink . . . . . . .
40.2 Overall organization . . . . .
40.3 File organization: the inode .
40.4Directoryorganization ………………………….. 8 40.5Freespacemanagement …………………………. 8 40.6Accesspaths:readingandwriting …………………….. 8 40.7Cachingandbuffering…………………………… 9
……………………….. 7 ……………………….. 7 ……………………….. 7
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
About these reading notes
These are my own personal reading notes that I took (me, Franklin) as I read the textbook. I’m pro- viding these to you as an additional resource for you to use while you’re reading chapters from the textbook. These notes do not stand alone on their own — you might be able to get the idea of a chap- ter while reading these, but you’re definitely not going to get the chapter by reading these alone.
These notes are inconsistently all of the following:
• Mesummarizingpartsofthetext.
• Mecommentingonpartsofthetext.
• Measkingquestionstomyselfaboutthetext.
– …andsometimesansweringthosequestions.
The way that I would expect you to read or use these notes is to effectively permit me to be your in- ner monologue while you’re reading the textbook. As you’re reading chapters and sections within chapters, you can take a look at what I’ve written here to get an idea of how I’m thinking about this content.
Chapter 39: Interlude: files and directories
• Note: we haven’t really looked at address spaces yet beyond how they fit into processes and threads. Virtual memory is coming up real soon.
• Note:Thischapterisprimarilyabouttheclientsideofthefilemanagementinterface,andsome stuff about its implementation.
• ThischapterisdescribingaUNIXfilesystem.Asyou’reworkingthroughthischapter,trytothink about how the ideas are similar to a Windows-based operating system. Some ideas are literally the same (e.g., files and folders), others are not exactly the same (e.g., links and permissions).
39.1 files and directories
• Makesureyouagreewiththeauthor’sdescriptionoftheabstractideaofafile:alineararrayof bytes that you can read or write.
• As the authors say: just accept that “inode number” is a thing, that a file has it, and that it is unique, you don’t need to know what it is (yet) beyond “it’s also part of the file”.
• Notice how the authors are describing the structure for a directory: the directory “thing” itself contains the names of the files that are underneath it, paired up with inode numbers. Note specifically that this means that file “things” do not have a name embedded within them, but
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
instead only have this unique inode number. The name is attached to its relationship with the directory that it’s contained within.
– This both sounds and feels really weird, so convince yourself about this relationship be- tween files, inode numbers, their names, and directories.
• How does this concept of a “root” entry differ from Windows? Both macOS and Linux (and all UNIXes) share this idea of a root entry.
39.2 The file system interface
• Keep this unlink function in mind. Keep it in mind in the context of above (how directories have inode references + names to refer to a file), and keep it in mind in the context of figure 39.1 (which is a tree).
39.3 Creating files
• Weirdly, you create a file by using the open system call. Is this consistent with higher-level languages like Python and Java?
• NotetwothingsabouttheAPIforopenhere:
1. Whatkindsofoptionsyoucanpass(permissionsandfilemodificationoptions),and
2. Howyoupassthoseoptions(withsomebinaryarithmetic).
We’re going to see this binary arithmetic again real soon, specifically in the context of permis-
• Hey look! File descriptors! Neat!
– The authors show the xv6 PCB; the Linux kernel does something similar, there’s a reference to a files_struct in the struct task_struct PCB, which leads you to fdtable.h
– Wait, so a file descriptor is a number, the PCB has an array of pointers. What is the file descriptor in this context?
39.4 Reading and writing files
• Theauthorsaren’tjokingaboutstrace,it’sanincrediblyusefultooltoseewhatsystemcalls
a program makes when it’s running.
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
• “eachrunningprocessalreadyhasthreefilesopen,standardoutput…,standardinput…,and standard error”
– Iffiledescriptorsareanarrayofpointers,doyouthinkthatthe“standardoutput”pointer for each process in a single shell is the same? Do all processes share the same standard output pointer?
• TRYrunningthecodesnippetatthebottomofpg5yourself!
39.5 Reading and writing, but not sequentially
• This is pretty neat, if you need to write to a specific and known part of a file, you can just go directly to that part of the file with the lseek system call.
– Check and see: the commands head and tail let you print out the beginning of or the end of a file respectively. Do these programs use lseek? What would it mean for these files to use lseek on something like standard output?
• The authors again show some code from xv6 that relates to the PCB for that OS, you can also take a look at the corresponding code from the Linux kernel
– Canyoufindthe“offset”or“position”thatthey’rereferringtoinxv6intheLinuxkernel?
• What’s the difference between the open file table and the array of file descriptors that was de- scribed earlier? (hint: think about the level where these two structures are located, there’s only one open file table, but there are many file descriptor arrays).
39.6 Shared file table entries
• Tryrunningthecodeinfigure39.2yourself,andconfirmthatyoucanseehowthefiledescriptors and the open file table are related here in terms of the parent and child process.
39.7 Writing immediately with fsync()
• “Thefilesystem,forperformancereasons,willbuffersuchwritesinmemoryforsometime”– this was actually described before in the I/O scheduling policies section. What is the OS trying to accomplish by buffering writes like this?
– Whatkindsofthingsdoyouthinkcouldgowrongif,forexample,thesystemsuddenlylost power when it’s only buffered (in memory) the write you issued?
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
• “this sequence does not guarantee everything that you might expect; in some cases you also need to fsync() the directory that contains the file foo.” – why do you think you would need to do this? What’s the relationship between a file and a directory? Does the directory itself have changes that would need to be persisted to the disk?
39.8 Renaming files
• Rename is an atomic operation: thinking about the relationship between files and directories (specifically about where and how a name of a file is kept), how do you think this works?
• Convince yourself that the steps the authors are describing here about how an editor might overwrite a file makes more sense than just overwriting the file (using a temp file, then renaming the temp file).
39.9 Getting information about files
• Actuallytryrunningthecodesnippetbeneathfigure39.5yourself,whatdoesyouroutputlook like compared to the author’s? What’s different, and what’s the same?
• Notenowthatwe’retalkingaboutaninode,whichisdistinctfromaninodenumber.Theyare related (an inode has an inode number), but they are not the same thing.
39.10 Removing files
• OK cool, here’s that unlink again. Why do you think unlink takes the name of a file rather than a file descriptor?
39.11 Making directories
• “Noteyoucanneverwritetoadirectorydirectly.”–whynot?Whydoesn’titmakesensetowrite to a directory?
39.12 Reading directories
• Note that there are different system calls for working with directories. Is this consistent with how you work with directories in other higher level languages like Java or Python?
• Howdoesstructdirentdifferfromthecorrespondingstructthatrepresentsfiles?
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
39.13 Deleting directories.
• Whydoyouthinkwedon’tuseunlinktodeleteadirectory? 39.14 Hard links
• OK,theauthorsareabouttorevealthemagicoflinkandunlink!Hooray!
• Try running the code that the authors show here to confirm what what they’re doing actually
works on your own systems.
39.15 Symbolic links
• What’sthedifferencebetweenasymboliclinkandahardlink?Whywouldyouuseoneoverthe other?
39.16 Permission bits and access control lists
• Here’swhereweneedtolookwaywaybackattheopensystemcall,intermsofthewaythat permissions are passed to it for creating a new file.
• Makesureyouseetherelationshipherebetweentheoctalvalues(theyarebase8)andtheread (r), write (w), and execute (x) bits for each class of users (owner, group, world).
39.17 Making and mounting a file system
• Notethatwhatfollowsisnotsomethingyoucandoonaviary.Youcanrunmkfsonanempty
file, but you cannot run it on a device like /dev/sdX.
– You can, of course, do this on the VM you’ve been using for labs. Just make sure you take
a snapshot before you do anything like this, just in case you clobber your system!
Chapter 40: File System Implementation
• Haha.AFStoZFS.Getit?
• As you’re working through this chapter, try to keep the organization that was described in the
previous chapter in mind, specifically this idea of inodes, inode numbers, and the relationship between files, their names, and directories.
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
40.1 The way to think
• Data structures: Trees. Trees everywhere.
– Though this file system (and FAT and exFAT) are more array/linked structure based than trees.
40.2 Overall organization
• “simplefilesystemsusejustoneblocksize”;ablocksizeishowmanybytesthereareinablock.
• They’recallingbacktoaninode,youmaywanttoremindyourselfaboutwhataninodemight
look like by referring back to chapter 39.
• We’regoingtothinkaboutthislater,buthowdoyouthinktheauthorsarechoosingthenumber
of blocks to represent an inode? The number of blocks seems like an arbitrary choice, too.
• NotethatabitmapisnotsomethingthatyoumakeinMicrosoftPaint(itis,butnotinthiscon- text). In this context, the authors are describing a sequence of bits, where the ith bit being set
(it’s a 1) means that the corresponding ith inode (in that inode region) is used. If the jth bit is unset
(it’s a 0), then that means that the jth inode is free (we can put a new file there).
• Beabletoexplainthedifferencebetweenthesuperblockandaninodebydescribingtheinfor-
mation contained within each, and by describing the level that each applies to. 40.3 File organization: the inode
• The general approach to figuring out where an inode is in an entire block is straightforward; there are many parts to include, but it’s arithmetic underneath it all.
• Thesimplifiedext2filenodeisreallygoodhere,it’sgivingyouanideaofthekindsofthingsthat should be in an inode, and approximately how many bytes each one of those takes.
– They’reabouttogettothisrightaway,but:ifyouhaveatotalof15diskpointersinanext2 inode, how big of a file could you ultimately represent?
The multi-level index
• Soyeah,directpointersarenotveryscalable(asyoujustfiguredout).
• Thinkingaboutprogramming,howmightyoudistinguishbetweendirectpointersandindirect
pointers? How would you need to change the struct that would be represented by the sim- plified ext2 inode in figure 40.1?
COMP 3430 Operating Systems – Chapter 39 and 40 reading notes Winter 2022
• Thenwegettodoubleandtripleindirectpointers.Whynotquadruple?Usingthenumbersthat the authors have here, how big of a file could you represent if you logically follow what they’re describing to having 4 levels of indirection?
• “Onesuchfindingisthatmostfilesaresmall”.Doyouthinkthisistrueonyourownsystem? 40.4 Directory organization
• “Such a delete is one reason the record length is used: a new entry may reuse an old, bigger entry and thus have extra space within.” ← this seems like a good idea that’s going to come back and bite us.
• Theasideonpg9isdescribinghowthisrelatestoFAT/exFAT.Payspecialattentiontothisidea, FAT/exFAT and what’s being described in this chapter are similar to each other.
• RememberhowfilesanddirectoriesweretreateddifferentlyattheAPIlevel?Howarefilesand directories different at the implementation level? Are they both represented by inodes? Do they have similar or the same metadata?
40.5 Free space management
• Inshort:youhavetoknowwhat’scurrentlynotusedsoyoucanfindaplacetowritestuff.
• Whywouldext2orext3pre-allocateblocks?Whywouldthefilesystemcareifblocksinonefile
are contiguous with one another? (hint: This is deeply related to how disks work)
40.6 Access paths: reading and writing Reading a file from disk
• Whydoesreadingafilerequirereadingdirectories?
• Whydoyouthinktherootinodenumberis2onmostUNIXfilesystems?Whynot0?
• Be able to convince yourself about what’s happening as a file is being read by both looking at
figure 40.3, but also about what’s happening near the bottom of pg 11, where the authors are
describing how the data pointers are being used from the inode itself.
• On closing a file “No disk I/Os take place.” <– this is a lie, a terrible lie, but... it’s OK to assume
that this is true.
• The authors claim that a directory with lots of files in it will be slow to access. Based on what
you know about files now, and their relationship with a parent directory, can you confirm to yourself that this is true?
COMP 3430 Operating Systems - Chapter 39 and 40 reading notes Winter 2022
Writing a file to disk
• ...isawfullysimilartoreadingafilefromdisk(atfirst).
• Why does writing require so much reading? Why do we need to read and write inodes when
we’re writing data to a file? Think back to what inodes are, think back to how inodes keep track of data, and think back to the structure way back at the beginning of this chapter showing how the disk is separated into blocks.
40.7 Caching and buffering
• We’reactuallygoingtocomebacktothisideawhenwetalkaboutvirtualmemory;theauthors hint at this when they talk about a “unified page cache”.
• LRU is least recently used (this is explicitly not the same as the oldest). A file might be around for a long time in a cache, but referred to constantly, where a newer file might have only ever been referenced once.
• Thisideaofbufferingwritesagaincomesup.Trytothinkaboutthisfromadesignperspective: how might an OS know that the same block has been written to twice?
• “Someapplications(suchasdatabases)”;relationaldatabasemanagementsystems,thespecial snowflakes that they are, effectively re-implement a huge amount of stuff that’s otherwise the responsibility of an operating system (like file systems).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com