COMP 3430 Operating systems – Chapter 36 and 37 reading notes
Winter 2022
About these reading notes
Chapter 36: I/O Devices
Copyright By PowCoder代写 加微信 powcoder
36.1Systemarchitecture ………………………………. 2 36.2Acanonicaldevice……………………………….. 3 36.3Thecanonicalprotocol …………………………….. 3 36.4LoweringCPUoverheadwithinterrupts …………………….. 4 36.5MoreefficientdatamovementwithDMA…………………….. 4 36.6Methodsofdeviceinteraction …………………………. 5 36.7FittingintotheOS:thedevicedriver ………………………. 5 36.8Casestudy:AsimpleIDEdiskdriver ………………………. 6 36.9Historicalnotes ………………………………… 6 36.10Summary…………………………………… 6
Chapter 37: Hard disk drives 7 37.1Theinterface………………………………….. 7 37.2Basicgeometry ………………………………… 7 37.3Asimplediskdrive……………………………….. 7
Single-tracklatency:Therotationaldelay……………………. 8 Multipletracks:seektime …………………………… 8 Someotherdetails………………………………. 8
37.4I/Otime:Doingthemath ……………………………. 8 37.5Diskscheduling ………………………………… 9 SSTF:Shortestseektimefirst …………………………. 9 Elevator(akaSCANorC-SCAN)…………………………. 9 SPTF:Shortestpositioningtimefirst ……………………… 10 Otherschedulingissues ……………………………. 10
COMP 3430 Operating systems – Chapter 36 and 37 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 36: I/O Devices
Hard drives are cool and stuff, but it’s probably a good idea to look at the generalization or abstraction of input and output devices before we look at a specific example of I/O devices.
Everything that’s attached to our computer (pretty much) is some kind of I/O device. Keyboards, mice, screens, stuff that you attach with USB, WiFi.
Before you get into this chapter:
• Howdoyou(asaprogrammer)currentlyinteractwithI/Odevices?
• Howdoyou(asauser)interactwithI/Odevices?
• BasedonwhatyousawinCOMP2280(oranappropriaterelatedcourseinadifferentprogram,
COMP 2280 is introduction to computer systems: assembly languages, architecture, etc), how do you think an OS actually interacts with hardware devices? It can’t just make system calls like open, can it?
36.1 System architecture
• Whoa,holdonasecondhere.IthoughtCOMP3370wascomputerarchitecture,what’sthedeal?
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
• We’re really just starting to get comfortable with terms and acronyms (so many acronyms). We’re also starting to get comfortable with the physical relationship between devices (e.g., where they are located physically relative to each other, who’s connected to what).
– “memorybus”:beepbeep.
• This architecture stuff is about “physics, and cost”. What does an operating system care about
this stuff?
• While the detailed description on pg 2 is interesting, it’s not really that relevant beyond “here are the definitions of acronyms, and where these are physically related to each other”.
– Arethereanyacronymsherethatyoudon’trecognize? 36.2 A canonical device
• Alright,sothisisactuallymorelikewhatanoperatingsystemneedstocareabout(doesitneed to care about physical location of devices relative to others?)
• “From Figure 36.3 (page 4), we can see that a device has two important components. … inter- face … internal structure …”
– Wait, what? Isn’t that what we’re looking at in COMP 3350? Are software and hardware design related to each other somehow?
• “more complex devices will include a simple CPU, some general purpose memory, and other device-specific chips to get their job done.”, this feels very much like the kind of device that Xzibit would like.
– Does that mean that there’s a computer inside my computer? Does that mean that there are multiple operating systems running on my machine?
36.3 The canonical protocol
• Protocol: we’ve seen this word before in the context of pipes and client/server architectures. Protocols are really more of a distributed computing thing, but(!), given what we just learned above, is this a distributed computing situation?
• “Byreadingandwritingtheseregisters,theoperatingsystemcancontroldevicebehaviour”,OK, this is our first hint about how an OS actually communicates with hardware devices.
• Given just the pseudocode just below the start of this section: what might happen if multiple threads tried to interact with this device?
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
• Haveyoueverseentheterm“polling”before?(outsideofthecontextofpoliticsandoutsideof the context of surveying people)
• The description of what this pseudocode is doing (poll, write, poll): what does this look like to you? Does it remind you of anything we’ve seen before?
– Whatkindsofproblemswiththatthingdidweeventuallytrytoovercome?HINT:wegotto use new system calls that are only available on ancient operating systems (Solaris): park and unpark.
36.4 Lowering CPU overhead with interrupts
• OK,cool.WeputtheprocesstosleepandlettheI/Odevicetelluswhenit’sfinishedratherthan
constantly asking it “Are you done yet?”.
• Yay!OurCPUismoreefficientlyutilizednow!
• WhywouldreallyfastI/Orequestsmakethesystemslower?CananOSactuallyrecognizethis? Do operating systems need to know about how fast a device is?
• This term livelock was used previously when discussing solutions to deadlock. Does it mean the same thing here?
• IscoalescingthesamethingthattheOSisdoinginthehybridapproach?Maybe.Coalescingis something we’ll see in the next chapter in terms of scheduling writes to disk.
36.5 More efficient data movement with DMA
• OK, so while maybe we improved resource utilization (we’re not just constantly asking the I/O device if it’s finished, we can do meaningful work!), performance still has room for improve- ment!
• Themainproblemthat’sleftisthattheCPU(andthustheOS)stillisresponsiblefortransferring the data somewhere once the I/O device indicates that it’s finished. The OS actually has to give those bytes to the process that did the read system call.
• Wait:didn’twesayearlierthatthere’sbasicallyatinycomputerinsidethatI/Odevice?Instead of us (the OS and the CPU) pushing data at the device from memory, why don’t we let the device pull the data directly from memory? Yay! This is DMA!
– TheOStellsthedevicewhereandhowmuchdatatocopyfrom/tomemory,thenthedevice does the rest of the work itself.
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
36.6 Methods of device interaction
• Wait a minute. We didn’t say how the OS communicates with the device? I thought we said that the OS communicates by reading and writing registers? How does it read and write those registers? Does x86 assembly have specific notation for writing to drives?
• Uh,IguessreallyoldmachineshadI/Oinstructions.
– Whoa, x86 does have special instructions for this, in and out. The instruction lets you
specify which device should be communicated with using a port.
• “Such instructions are usually privileged.” – why would this instruction be privileged? Why wouldn’t you want a user program to be able to directly issue reads and writes to a disk, for example?
– What does it even mean for an instruction to be privileged? Think way way back to direct execution in chapter 6!
• Memory-mappedI/O:steal/hideatinybitofmemoryfromthesystemandusethoseaddresses to communicate with a device. You may have done something like this in COMP 2280.
36.7 Fitting into the OS: the device driver
• Based on what’s being described here, try to think about where this device driver fits; the file system is a pretty integral part of an operating system. If you were to imagine you sitting in a chair at your keyboard and the disk, where the file system, the operating system, and a device driver are “in between” you, how would you actually order these things?
• OK, awesome. Abstraction. That was something we learned about… well, everywhere in CS I guess.
– Thinking about something like a hard drive, what kinds of abstract operations might an operating system or a file system need to do?
– Thinking about something like a web cam, what kinds of abstract operations might an operating system need to do?
• Youmightnotpickuponthis,butaninterestingthingaboutwhat’sbeingdescribedhere:
it simply issues block read and write requests to the generic block layer, which routes to them to the appropriate device driver, which handles the details of issuing the specific re- quest.
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
is that this means that the “generic block layer” could service an I/O request that spans across multiple physical drives. Think about that: a file spread across multiple physical hard drives! Neat!
• Whywouldsomethinglikeafile-systemcheckerneed“raw”support?
• “Notethattheencapsulationseenabovecanhaveitsdownsideaswell.”,what’sdescribedhere is also a downside of the entire idea of OO: yeah, we get it, a dog barks to speak and cat meows and they’re both animals, but, uh. Wait, what was this about? Right. OO. Can you think of any ways that you might approach changing this relationship (device drivers, OO, encapsulation) so that, for example, the “rich error reporting” from SCSI would be available?
• “Studies of the Linux kernel reveal that over 70% of OS code is found in device drivers;” — the Linux kernel is millions of lines of source code. Millions and millions. We’ve looked at an in- finitesimally small fraction of the Linux source code in class.
36.8 Case study: A simple IDE disk driver
• ACK.Figure36.5is…notasightforsoreeyes.It’sasightthatmaybemakessoreeyes.
• Really,thisisjustshowingalloftheaddresseswhereyouwouldwritetoinwiththeinandout instructions to communicate with an IDE drive. We’re not going to write x86 assembly, so we don’t really have to care very much about these specific addresses.
• Theprotocolhereisdescribinghowyouwouldinteractwiththedevice,usingtheseaddresses, and you can see some actual code in figure 36.6 on pg 12 that’s implementing this protocol.
36.9 Historical notes
• “Interruptsareanancientidea”,yeah,alotofthings(asurprisingnumberofthings)inmodern operating systems are ancient ideas.
• DMAwasavailable70yearsago(asanidea,anyway). 36.10 Summary
• Make CPU get used for good stuff more, let the I/O device do more of the work, abstraction makes supporting many kinds of things easier.
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
Chapter 37: Hard disk drives
• Now we’re talking about I/O, cool. You can consider looking at chapter 36, it describes a gener- alization of input and output devices where this chapter focuses specifically on hard drives as I/O devices, and the related I/O scheduling topics.
• Thischapterfocusesheavilyonspinningplatterharddrives(“spinningrust”).Bythetimeyou’re at the end of this chapter, try to decide whether or not a lot of the issues that you looked at here apply to solid state drives (SSDs), where there are no platters, and access times are effectively uniform.
37.1 The interface
• Sectors. If you’re also in COMP 3370 right now, this is another word to describe “chunks” of memory (on top of frames, slots, blocks, words, pages).
• We’reeventuallygoingtogettofilesystems(howsoftwareorganizesdataphysicallyonadisk), but try to think about this now: how might software that organizes data physically on a disk use this atomicity guarantee that a 512-byte sector is either fully written or not written at all?
• Theauthorsmakeastatementthatsequentialreadsorwriteswillbefasterthanrandomreads or writes. Can you convince yourself that this is true based on figure 37.1?
37.2 Basic geometry
• Thissectionlistsalotoffactsaboutcirclesandstuff.Literallygeometry.Howdoes𝜋fitintothis picture?
– Seriously, can you, for example, calculate the time that a single rotation takes of a disk platter given what the authors have provided here? What additional information do you need if you can’t calculate it?
37.3 A simple disk drive
• As you are reading through this section, try to think about how software that organizes data physically on a disk (a file system) can use the information that the authors are describing to inform itself about how and where to physically put bytes on the disk.
COMP 3430 Operating systems – Chapter 36 and 37 reading notes
Winter 2022
Single-track latency: The rotational delay
• Convinceyourselfthat
is the average delay time here.
• Ifaccessingsector5istheworstcase,what’sthebestcase?
Multiple tracks: seek time
• Acceleration? Coasting? Deceleration? What is this, physics? The Fast and the Furious? 2Fast4Disks.
• Theimportanttakeawayfromthisshouldbethateachofthesedifferent“phases”takeacertain amount of time, and that amount of time very quickly adds up to milliseconds of access time. Think about this for a second: I/O is a “blocking” operation, the OS and the scheduler will do things like stop scheduling jobs that are waiting for I/O to finish. Milliseconds doesn’t seem like a very long time. How much work can a process do in milliseconds?
Some other details
• WetalkaboutcachingextensivelyinCOMP3370,theconceptsarealleffectivelythesamehere (if you’ve taken or are taking COMP 3370).
– COMP3370question:writebackvswritethroughintermsofcache→memoryreallyonly considered performance, but now write back vs write through has real side effects, like something happening during a power loss. In terms of a between CPU and main memory cache do we need to consider things like power loss?
37.4 I/O time: Doing the math
• Asyou’restartingtolookatthesemeasurements,trytothinkabouthowthisisrelatedtowhat we thought about in terms of scheduling (e.g., with scheduling we considered turnaround time, arrival, start time, finish time, etc).
– Rememberhowwehadthoseunrealisticsimplificationsforscheduling?Oneofthemwas that we knew how long a job would take to complete. In terms of I/O: do we know how long a job will take to complete?
• A1TBdriveisadrive“builtforcapacity”.LOL.
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
• Based on the numbers and formulas that you see here, what has a bigger effect: average seek time or RPM?
• The RPM change (and seek time change) from the Cheetah to the Barracuda are both approxi- mately 2x, but the sequential rate of transfer reported on pg 8 is nowhere near 2x. What’s the deal with that?
• Onpg9:Ohno.It’scalculus….orwait,isthisphysics?Ohno.
37.5 Disk scheduling
• Whatisthis,processes?
• Think about this for a second: Logically, it would seem to make sense that I/O be serviced on
a first-come-first-serve basis (e.g., process 1 makes a request before process 2, therefore pro- cess 1’s I/O job should be completed before process 2’s I/O job). But does it? Think back to the geometry of a disk. Think back to the unrealistic limitations that we put onto processes. Are the limitations that we put on processes still unrealistic when we think about them in terms of servicing I/O jobs?
• The authors don’t state this explicitly, but where do you think the disk scheduler lives? In the OS or in hardware? You might want to look back at chapter 36 briefly to see how an OS asks an I/O device for information, specifically section 36.3 on pg 4 in chapter 36.
SSTF: Shortest seek time first
• Whichprocessschedulingpolicydoesthismostcloselyresemble?DoesthisI/Oschedulingpol- icy suffer any of the same problems that the process scheduling policy suffered? Consider this for both SSTF and NBF.
• Starvation!
Elevator (aka SCAN or C-SCAN)
• Thesectionistitled“Elevator”whereSCANandC-SCANare“aka”,butonlylaterdotheauthors actually use the word “elevator”.
– Really convince yourself about what’s happening here. Like literally visualize an elevator going up and down in a building.
• Doesthisresembleanyoftheschedulingpoliciesthatwe’veseen?
• How exactly does this solve the issue of starvation and fairness? Think back to how starvation
and fairness were addressed in terms of scheduling algorithms, and think back to how they were addressed in terms of locks. Is the same solution used here (even transitively or implicitly)?
COMP 3430 Operating systems – Chapter 36 and 37 reading notes Winter 2022
SPTF: Shortest positioning time first
• Whichprocessschedulingpolicydoesthismostcloselyresemble?DoesthisI/Oschedulingpol- icy suffer any of the same problems that the process scheduling policy suffered?
• Intermsofthinkingaboutthislikeaprocessschedulingpolicy,whatexactlywould“positioning time” or “access time” be in terms of a process? Is there a relationship here?
Other scheduling issues
• Ohwait,theauthorsdotalkaboutwherediskschedulinghappens.Neat. – DoyouthinkthataharddrivehasanOSonit?
• Thisisrelatedtothetopic,butbeyondthescopeofourcourse:canyouconvinceyourselfthat waiting for more I/O is a better choice than immediately issuing I/O requests when you receive them?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com