my name is dr. Mike Murphy I'm anassistant professor of computer scienceand information systems at CoastalCarolina University in this lecture I'mgoing to introduce the fundamentals ofoperating systems what they are whatthey do and why they're important nowwhat's an operating system well it's alayer of software that provides twoimportant services to a computer systemit provides abstraction and arbitrationabstraction means hiding the details ofdifferent hardware configurations sothat each application doesn't have to betailored for each possible device thatmight be present on the systemarbitration means that the operatingsystem manages access to shared hardwareresources so that multiple applicationscan run on the same hardware at the sametime without interfering with oneanother now these Hardware resourcesthat need to be managed include the CPUthe hierarchy of memory all theinput/output devices on the system andto some degree the power and systemmanagement features in the system manyof these features are handled directlyby the hardware but the operating systemis involved particularly in energyconservationnow the abstraction features of theoperating system allow hardware devicesmanufactured by different manufacturersto have a same interface within softwarefor applications to use these hardwaredevices all have different low-levelinstruction sets they all haveparticularly particular capabilitiesfeatures and details that are unique toeach hardware device if we didn't have acommon interface into these hardwaredevices first of all our variety ofhardware might be limited but worseevery application on the system wouldhave to be programmed to use everysingle devicesystem an example back in the 1990scomputer games often required internalprogramming for specific video cards andspecific sound cards it was oftennecessary to go into the settings foreach game and tell the game what type ofvideo card you had what type of soundcard you had for the purpose ofconfiguring the game to use thatparticular hardware imagine if that hadto be done for every single applicationon the system including say a calculatoror a web browser that would be a veryuntenable situation in terms of beingable to make use of computers the way weuse them today also what if we couldonly run one program at a time on acomputer system years and years ago thatwas the case however a modern system isrunning multiple applicationssimultaneously and it's up to theoperating system to ensure that allthese applications can access yourresources so each CPU is divided amongthe different programs each program getsaccess to memory input output as well asdisk and in an ideal world the operatingsystem also enforces policies thatisolate applications from each other sothat a crash in one application doesn'ttake down the entire system or otherapplications now of these examples do wehave a situation where we haveabstraction or arbitrationwell first examples supporting bothIntel and AMD processors this is anexample of abstraction we don't have towrite separate software for an Intelprocessor relative to an AMD processorat least for 99.99% of applicationssimply write the application once itwill run on either processor switchingbetween applications is an example ofarbitrating hardware resources among thedifferent applications on the systemseparating memory allocated to differentapplications is also an arbitrationactivity it keeps one application fromoverwriting the contents of memory thatbeing used by another applicationenabling video conferencing software touse different camera devices this wouldbe an example of abstraction the videoconferencing program just has to knowhow to use a camera interface that theoperating system provides and thendifferent cameras from differentmanufacturers can be used without havingto write the application the videoconferencing program to be able to talkto each individual camera similarlyaccessing two different hard disks fortwo different manufacturers anyunderlying detail differences betweenthose drives can be handled by using theoperating system to abstract away thedetails sending and receiving messagesover a network is both abstraction andarbitration on the one hand we'reabstracting away the details of eachparticular network card to be able tosend and receive the message on theother hand we're sharing that networkcard among all the differentapplications on the system now we canthink of the system in terms of layersat the bottom of the layer cake we havethe hardware this is what executes thesoftware top three layers the operatingsystem is the middleman so to speakbetween the applications and thelibraries and utilities upon which theapplications depend and the underlyinghardware specifically the core of theoperating system or the kernel so namedafter say a kernel of corn is theminimum piece of software that's neededto share the hardware between thedifferent applications whatever livesoutside the kernel that as software issaid to be in user space that means itsapplication code or sometimes even partsof the operating system that are notstrictly necessary to share the hardwareor abstract away its details nowoperating systems implement a commonmechanism for allowing applications toaccess the hardware which is abstractionand the applications make requests fromthe operating system to go and accessthe hardware or other features by makingsystem calls down into the operatingsystem this is called entering theoperating system or enter ating enteringthe kernel from the top half operatingsystems are also able to alertapplications that hardware has changedperhaps a network packet has come inperhaps the user has pressed the key onthe keyboard these alerts are deliveredvia system called interrupts andreferred to entering the kernel from thebottom half from the hardware side ofthe operating system we should also notethat operating systems can manage andterminate applications by sendingsignals to those applications now thereare a wide variety of operating systemsout there they basically fall into twocategories Microsoft Windows which isnot Unixand everything else which is UnixMicrosoft Windows systems non UNIXsystems are the most popular desktopoperating systems at the moment howeverthey're rapidly being eclipsed by tabletdevices most of which are running UNIXstyle systems Windows is typicallypre-installed by PC manufacturers whichaccounts for a good portion of itspresent popularity UNIX systems on theother hand are installed by the end-userexcept for commercial UNIX systems andMac OS 10 Mac OS 10 is probably thebest-selling UNIX system of date andLinux which includes the Androidplatform is probably secondnow there are some mainframe systems outthere also some of which are UNIX likesome use custom operating systems thereare a variety of players in the embeddedsystems market however that's presentlydominated by Android with Apple's iOSwhich is based on Mac OS 10 in closesecondothers Symbian blackberry OS tiny OS areconfined to smaller markets now the ideabehind the UNIX systems began withinthis time sharing system started in 1964called multics and the idea behindmultics was to make computing into aremote service that could be accessed byterminals using telephone lines itwasn't terribly successful becausedial-up connections of the time at about9600 baud were rather slow howevercanada actually did have a multix systemdeployed and used it as part of theirnational defense network until the year2000 multics is remembered howeverprimarily for its influence as amulti-user shared system and today withcloud computing there's some significantparallels between some of the cloudcomputing models that we use and some ofthe ideas that were pioneered back inthe multics system now UNIX was actuallya play on the term multix it wasdeveloped by Bell Labs in 1969 it'sactually a trademarked term so someauthors use Star NEX to refer to thefamily of systems and use the word UNIXonly for the commercial distributionsthe original UNIX systems werecommercial distributions with freevariants BSD and Linuxcoming along late 80s and early 90s nowUNIX systems are time sharing systems inthat they support multiple users at thesame time but they're designed to be runon local computer resources instead ofremote resources the Berkeley systemdistribution which is based on a T'scommercial distribution was one of thefirstopensource BS with one of the firstopen-source UNIX systems to emerge itwas based on the commercial distributionso AT&T sued UC Berkeley but an eventualsettlement allowed Berkeley todistribute BSD freely in both source andbinary form today's descendants of BSDinclude FreeBSD OpenBSDand Mac OS 10 which is based on the UNIXbsd system Linux however was analternate approach to getting aunix-like kernel running on a computersystem this was started by Lina'sTorvalds as an undergrad at theUniversity of Helsinki released insource code for him in 1991 and oftencombined with a set of user spaceutilities and libraries created by thecanoe project thus the resultingcombination is sometimes called canoeslash Linux it has been commerciallysuccessful for many device classesincluding web servers network andembedded devices and mobile phones somepeople including myself use Linux as adesktop platform and it does have thebenefit of having the one kernel that'sscalable from embedded devices all theway up to supercomputers valuable toolfor us in terms of learning aboutoperating systems now what is Linux wellgenerically the term Linux is a refersto a class of operating systems that usea common kernel now distributions ofLinux are operating environments asthey're sometimes called are cobbledtogether by taking the Linux kernel andadding various different user spacetools to itmany of these core tools originated inthe ganoub project which originallystarted MIT and thus systems aresometimes called canoe slash Linuxinstead of just Linux I typicallyhowever say just Linux we're referringto either the kernel itself or to theoperating system distributions that arebased upon that kernelthe Linux kernel was originally startedas a hobby by an undergraduate at theUniversity of Helsinki a gentleman bythe name of Lina's Torvalds he stillheads the carnal development project nowLinux is what's called a mite amonolithic kernel and that means thatthe device drivers are built into thekernel however it's not a truemonolithic kernel because the devicedrivers can be built as modules andloaded and unloaded from the kernel atruntime the latest stable version was2.6 point 37 On January 5th of 2011 thathas since been updated to version 3.0 3I believe was the latest version thatI've seen as of now which is late August2011 the latest version can also bechecked by going to WWll org here is anexample of some of the main componentsof Linux operating system at the lowestlayer we have the computer hardware andon top of that Hardware we have theLinux kernel Linux kernel contains anumber of built-in subsystems thatenable access to the computer hardwarethese include drivers memory managementprocess management file systemsnetworking including sockets andprotocols and other utilities that thekernel provides on top of the kernel wehave the goosy library upon which mostother libraries are based since C istypically the lowest level systemlanguage to which all other software iseventually compiled on top of that wehave our compiler GCC some importantutilities called coreutils also part ofthe canoe project and the born-againshell or bash which provides acommand-line interface into the systemall we need in order to run a Linuxsystem and do useful things with it iseverything below this line where I'mmoving the mouse right here all thesoftware above this line is add-onsoftware it's not strictly needed inorder to run a Linux system what makesLinux systems more convenient or doother things so for example we can addnetwork tools such as secure shellserver and generate a generic servicesserver called I net D that can launchall kinds of different services we canalso run a lamp stack that stands forLinux Apache MySQL PHP if we're in adesktop scenario we can also run agraphic user interface this includes x11specifically the x.org distribution andone of a number of differentenvironments that can be run inside x11popular ones include gnome KDE and Xfcewhich isn't on this particular graphicnow a large number of people have comeup with different distributions of Linuxthese distributions contain differentsets of software but they all share theLinux kernel in common we typicallyclassify distributions by which packagemanager they use unlike Linux and Macsystem unlike I'm sorry Windows and Macsystems where we install individualapplications and then have to manuallyupdate each application by runningseparate installers Linux distributionstypically use package managers whichdownload and install extra software andupdate existing software with a singlecommand these package managers includethe Red Hat package manager or RPM whichis used in red hat enterprise linuxfedora and reeva openSUSE and a numberof other distributionsa competing package format is theadvanced package tool this is usedprimarily by Debian and derivatives ofDebian such as Ubuntu there are otherbinary formats however in use Slackwareuses a tgz format with its own packagemanagement commands Arch Linux has acustom written package manager calledpac-man and there are some others outthere there are also source formatsGentoo is able to build everything fromsource using a builds Linux from scratchisn't so much a distribution as it is abook that tells you how to put togetheryour own Linux system by compilingsources for each particular applicationthis is of course time-consuming andthere are other source formats out thereas wellnow in industry Red Hat Enterprise Linuxis quite popular it's a Linuxdistribution from Red Hat incorporatedwhich is based in Research Triangle ParkNorth Carolina that's in the Durham areait is an open source distribution butthe official product is sold with anupdate subscription accessed via perinstallation serial numbers therefore inorder to get the update subscription andthe installation media it's necessary topurchase a subscription from Red Hatthey do use the RPM package format infact they invented it RPM stands for redhat packaged format sent OS is a freerebuild of Red Hat Enterprise Linuxthat's widely used in academia industryon many high-performance computingsystems and for many other applicationsthis of course uses the RPM packageformat and is available at zero costFedora core is a community distributionthat's sponsored by Red Hat that grewout of an old product that Red Hat usedto produce which was called Red HatLinux without the enterprise part andFedora is used to develop and testpackages and infrastructure that arelater incorporated into the EnterpriseLinuxproducts Debian is a fully open sourcedistribution which avoids proprietarysoftware and has an emphasis on securityand stability the stable version ofDebian is extremely stable because thepackages are extremely well tested theflipside is is that those packages tendto be rather dated and thus an unstableversion is available if morebleeding-edge packages are needed debianuses something called the advancedpackage tool or apt in order to manageits software Ubuntu is actually based onDebian it's sponsored by a companycalled canonical Limited which is basedin South Africa it's designed to be easyto use and friendly to new usersswitching from competing platformsthere's a new release every six monthsand it's often necessary to completelyreinstall the operating system at eachnew release there is a functionalitythat's built into the advanced packagingtool called dist upgrade which seemslike a great idea on paper but inpractice often doesn't work right andleaves the system unstable Debian Ubuntualso has a package pinning policy thusonce a package is released it's onlyupdated for security updates if newfeatures are added one has to wait tillthe next version of Ubuntu comes outbefore getting the newly updated packagenow Arch Linux which is what Ipersonally run is a minimalist frameworkfor creating a custom system it's not somuch as a distribution as it is a set oftools that enables each individual tocreate his or her own installationcustomized to his or her own desiresit's a different philosophy fromtraditional distributions it is acompletely written from scratchdistribution it's not based on any otherand it is what's called a rollingdistribution there are not discreteversions of Arch Linux every time yourun a system update on Arch Linux youget the latest version of the operatingsystemalong with the latest version of allapplication packages and all the latestbugs and the pac-man package manager'which was written from scratch for art'slinux is used to manage the software sothese are just a few examples ofdifferent Linux systems different Linuxdistributions that can be used with thehighly scalable Linux kernel a hard diskdrive for access by multiple programs inparticular we'll talk about diskattachment talk about some of theproperties of magnetic disks discussdisk addressing discuss partitioning andintroduce solid-state drives now beginwith disk attachment disks are attachedto the motherboard via some kind ofcable and the exact type of cabledepends upon the bus in use on thesystem there are several different typesof bus which are implemented bydifferent chips attached to themotherboard on the different computersystems one common bus that was widelyin use until the early 2000s on consumergrade Hardware was the integrated Driveelectronics or IDE bus this has beensince backronym parallel ata or pata weconsisted of 40 to 80 ribbon cableconnecting to a 40 pin connector toprovide 40 simultaneous parallelchannels of communication between themotherboard and the hard driveenterprise level systems of that timeperiod typically used scuzzy or smallcomputer system interface buses whichconsisted of cabling of 50 to 80 pinconnectors between the hard disk and themotherboard scuzzy also defined astandard set of commands a standardprotocol for interfacing with disks CDsand other types of storage devices thisprotocol was useful for recordable CDmedia and DVD ROM media and wasimplemented on the ata bus using thescuzzy protocolin a system known as a tapi or a TApacket interface now in modern timesserial interfaces between themotherboard and the disk have replacedfor the most part the parallelinterfaces 488 style disks we haveserial ata or SATA which replaces the 40pin connector with a 7 pin connectorstill uses the same protocol either a TAor tapi protocol and serial Attachedscuzzy or SAS which uses the scuzzyprotocol over a narrower channelconsisting of 26 to 32 pins both ofthese new serial attachment mechanismssupport higher bus transfer speedsenabling theoretically faster devices tobe attached to the motherboard does notnecessarily mean however that the diskshave gotten that much faster now westill store large amounts of informationusing magnetic disks these are metallicor glass platters that are coated in amagnetic surface and a stack of theseplatters is rotated at high speed by anelectric motor a stack of heads movesback and forth across the plattersaltering the magnetic fields in order toread and write data moving the headsback and forth results in seek time andwaiting for the platter to rotate aroundto the correct position results inrotational delay historically magneticmedia were addressed by geometry thesmallest addressable unit of space on ahard disk is called a sector and this istypically 512 bytes at least on olderdiscs though other sizes have been usedand newer drives go up to 4 kilobytestracks our circular paths at a constantradius from the center of the disk andeach track is divided into sectors onehead reads from a single track on asingle side of each platter when youstack multiple heads up while usingmultiple tracks on the various sides ofseveral different platters the result iswhat's called a cylinderand historically accessing discsrequired accessing the particular datalocations using cylinder heads sector orCHS geometry addressing as disks grewlarger and faster however this type ofaddressing scheme became limited and sological block addressing was put intouse and it's now the standard todaylogical block addressing or LBA giveseach block on a disk its own logicaladdress and leaves it up to the diskfirmware to convert the logicaladdresses into physical locations on thedisk current standards with logicalblock addressing on ata will allowenough space for disks up to 128petabytes operating systems normallyimplement these 48 bit addresses using64-bit data structures thus operatingsystems that support 64-bit diskaddressing can generally support harddisks up to 8 ZB bytes of data assumingwe're using 512 byte sector sizes nowregardless of the size of the disk it isconvenient to partition the disk intomultiple sections so that we can isolatedata from each other we can isolate themain partition of the operating systemfrom a partition we would use forswapping out pages of virtual memory forexample and we can isolate that fromuser data also with early hard drives itwas convenient to isolate partitions soas to minimize seek time by making itsuch that the head didn't have to moveas far in order to access data now thereare two types of partition table or datastructure that resides on the disk toindicate where on the disk the differentpartitions lie a common partition tabletype that's in widespread use today isthe master boot record basedpartitioning scheme and the way thisworks is that the BIOS on the system thebasic input/output system actually loadsthe first 512 byte sector from the bootfive at boot time and code stored inthat 512-byte sector loads the rest ofthe system also within that sector isstored the partition table which iscalled a DA style partition table andthe dos partition table still useslegacy cylinder head sector addressingsupports a maximum of four primarypartitions one of which can be anextended partition with logical drivesin it and supports maximum partitionsizes and maximum partition startingaddresses at 2 TB bytes this is thedefault partitioning scheme forMicrosoft Windows and most Linuxdistributionshowever as hard drives become larger andgrow past 2 terabytes the goooodpartition table or GPT starts to be usedthis is a larger partition table thatcan support disks or partitions up to 8ZB bytes in size for compatibility withold partitioning tools and prevent oldtools from overwriting sections of thedisk and seeing in this free space aprotective or dummy Master Boot Recordis retained at the beginning of the diskGPT is the default partitioning schemeand Mac OS 10 is an optionalpartitioning scheme in Linux and issupported in 64-bit versions of Windows7 Windows Vista and Windows Server 2008provided that the system uses theextensible firmware interface or efiinstead of the legacy BIOS interface forLinux the grub to boot loader can use alegacy BIOS interface but requires adedicated small partition on the harddrive in which to store the rest of thebootloader now hard drives and magneticmedia are used for large quantities ofspace because of their relative low costwhen high performance is required weprefer to use solid-state drives or SSDsthese drives have no moving parts whichmakes them generally faster and lesssubject to physical damagemechanical hard disks most of these SSDsuse NAND flash memory to store data andthis is a storage mechanism that's basedon injecting or removing an electronfrom a flash cell injecting an electroninto a flash cell changes its state fromone to zero so this is backwards fromwhat one would expect an empty flashcell actually has a state of 1 insteadof 0 the membranes through which thiseject this electron is injected andremoved eventually wear out typicallyafter anywhere from a hundred thousandto a million cycles furthermore theelectrons tend to leak out over longtime periods periods of many yearscausing flash to lose data which makesflash based memory systems unsuitablefor long term backups in this diagram wecan see how a flashed or how asolid-state drive using flash memoryworks blank flash memory stores thevalue 1 1 1 1 1 1 1 1 11 11 0 if I wantto write the value 1 0 0 1 0 1 0 0 Ihave to pop electrons into the secondthird fifth seventh and eighth flashlocations the 8-bit those bit locationsI'm pretending we only have a byte hereif later I wish to change that storedvalue to 1 0 1 0 0 0 1 1 I must firsterase that block of flash memory beforeI can program the new data valuegenerally I must erase flash memory inthe size of an array stip eclis 4kilobytes waiting for this block eraseyour procedure causes something calledwrite amplification where successivewrites to an SSD become progressivelyslower to avoid this problem typicallyerase the SSD ahead of time wheneverspacehas been freed on it and there's an atacommand called trim that facilitatesthis process one other issue that has tobe dealt with with SSDs is the fact thateach cell can only be written to andread from generally written to erasedand written to a fixed number of timesthis is typically between a hundredthousand and a million so to spread outthe writes across the entire SSD the SSDmoves data around the drive as files areupdated and it also reserves a certainamount of free space unusedso that that free space can be swappedin and out with space that's in uselater this process called wear levelinghas the advantage of dramaticallyincreasing the useful life of the SSDand reducing write amplificationwhenever clean blocks are made availablehowever in order for the writeamplification reduction to be effectivethe operating system and the underlyingfile system must support the ATA trimcommand and furthermore it's impossibleto ensure that the disk is secureagainst forensic data recovery becauseit may not be possible to overwrite andproperly erase the reserved cells ofmemory that have been taken out ofservicethus a used solid-state drive should bephysically destroyed instead ofattempting to resell it which can be anissue because a solid-state drive has ahigher upfront costso in summary disks are attached to thesystem via some kind of bus the newerbus styles are SATA and SAS these moderndisks are addressed using logical blockaddressing they're partitioned eitherwith DOS partition tables or goooodpartition tables GPT use will increaseas the size of disks becomes largerowing to the limits of the dos partitiontable and solid state drives offerhigher performance at a higher initialcost subject to the requirement of wearlevelingand subject to not being able to besafely resold due to the inability toforensically secure the data on thedrivein this lecture I'll bedisc scheduling I'll be introducing thepurpose of disc scheduling talking aboutsome classical and historical toscheduling algorithms talking aboutnative command queuing and discschedulers that are currently in use inthe Linux kernel and then I'll talk alittle bit about how i/o requests can beefficiently scheduled on solid statedrives scheduling serves two purposesdisc scheduling serves two purposesthe first of these is to arbitrate diskaccess among different programs thisensures that competing programs haveaccess to disk resources and that asingle program cannot monopolize thedisk resources in such a way as toprevent other programs from accessingthe disk with mechanical hard drivesscheduling algorithms historically havealso attempted to improve diskperformance by reducing the number ofseeks required moving reducing thenumber of times the drive head needs tobe moved if the drive head has to bemoved too many times a lot of throughputcan be lost from the disk because we'rewaiting on all the seek times to occurthe simplest scheduling algorithm wouldbe the first-come first-serve algorithmwhich is implemented in linux as the noop scheduler this algorithm is extremelystraightforward it simply consists of aFIFO queue into which new requests areadded the requests are removed from thequeue in order one by one and theserequests are sent to the disk forprocessing now there's no reordering ofthe queue this is a first-comefirst-serve ordering so back-to-backrequests for different parts of the diskmay have caused the drive head to moveback and forth across the platterswasting quite a bit of time with seekshistorically several attempts have beenmade to try to improve this behavior oneexample would be the scan algorithm orthe elevator algorithm and in thisalgorithm the drive head only moves inwonderaction it serves all the requests inthat direction before moving back in theother direction this is called theelevator algorithm because it's modeledafter how an elevator works in abuilding the elevator leaves the groundfloor moves to the highest floorstopping along the way to add passengerstraveling up remove passengers atwhichever floor they wish to stop on andthen once the algorithm reaches the oronce the elevator reaches the highestfloor turns around and comes back downsame process here in this example withthe scan algorithm assuming that thehead starts at sector 1 and this requestfor sector 50 comes in while sector 61is being processed the algorithm isgoing to process the requests in order 312 32 40 40 to 60 180 497 and since thatrequest for sector 50 came in while 61was being processed that request forsector 50 s going to have to wait untilthe head changes direction and returnsto sector 50 now there are a fewoptimizations of the simple scanalgorithm the original algorithmproposed that the head would move allthe way from the beginning of the diskto the end of the disk and then all theway back to the beginning the lookalgorithm improves upon this behavior bymoving the head only as far as thehighest numbered request before changingdirections and moving it back down thecircular versions of the algorithm seescan and see look only serve requestsmoving in one direction so for examplewith circular scan the head would startat the first sector move all the way tothe end of the diskservicing requests and then come all theway back down to the first sectorwithout servicing any requests and startthe process over again these arehistorical algorithms in the sense thatwith modern drives we have LBA orlogical block addressing and so we don'tactuallyknow where the disk is placing dataphysically this type of algorithm wasused historically with cylinder headsector addressing where we knew thephysical properties of the disk and theidea here was to reduce average seektime at no time did we know where theplatter was that was up to the disk tofigure out so there was no way to reducerotational delay only minimize seek timeanother algorithm in attempts tominimize seek time is the shortest seektime first algorithm or SST F thisalgorithm actually orders requests bysector location so when the request forsector 50 comes in it's kept in anordered queue a priority queue and thenext request to be served by the diskthese requests are still sent out one ata time is chosen by looking at whateverrequest is closest to the currentdisposition historically this couldresult in starvation because if a bunchof requests come in for one piece of thedisk requests for the remainder of thedisk might not be processed for lengthyperiods of time furthermore once againwith logical block addressing theoperating system doesn't really knowwhere the sectors are laid out on diskand so this algorithm doesn't reallywork with modern hard drives also asolid state drives this algorithmassumes there's a disk head which in thecase of a non-mechanical drive there isnot in the Linux kernel an approximationto shortest seek time first wasimplemented with the anticipatoryscheduler this was the default schedulerfrom 2.6 point 0 through 2 point 6 point17 it was removed in 2.6 point 33because it's obsoletethe idea behind the anticipatoryscheduler was to approximate shortestseek time first by ordering only theread requests into an ordered queue intoa priority queue if the next readrequest was close to the current headposition that request would bedispatched to meotherwise the scheduler would actuallywait a few milliseconds to see ifanother request arrives for nearbylocationand starvation was avoided in itsalgorithm by placing expiration times oneach request and adding preemption sothat if a request was waiting too longit would go ahead and be servicedregardless of its location the idea herewas to reduce overall seeking there wasa separate queue for write requestsbecause write requests could beperformed asynchronously we did not haveto wait on those requests to becompleted before a process couldcontinue doing useful work thisalgorithm was shown with low performancedrives to improve performance on webserver applications however it was shownto have poor performance for databaseloads where there were a lot of randomreads and writes on the disk and withhigh performance disks this algorithmactually breaks down modern hard disksgenerally do qualify as high performancedisks the reason being is that theyimplement something called nativecommand queuing this is a feature ofnewer SATA drives and basically a nativecommand queuing leaves scheduling ofdisk requests up to the disk itself thedisk circuitry and firmware makes thedecision about which requests to handlenext to do this the disk has a built-inpriority queue of about 32 entries andthe disk is able to schedule itsrequests automatically taking intoaccount both the seek time and therotational delay since the disk knowsthe location of the platter this makesmodern disks much more efficient andthis works with logical block addressingthe operating systems role with thistype of hard disk is really morearbitration of the gist resources amongthe different programs running on thesystem one modern Linux scheduler thatcan be used for such arbitration iscalled the deadlines scheduler and inthis scheduler the kernel maintainsseparate request queues for both readrequests and write requests similar tothe anticipatory schedulerreeds are prioritized over rightsbecause process is typically block orstop and wait while waiting to readsomething from the diskthus rights can be done later at somepoint when it's convenient for theoperating system the waiting time ineach queue with the deadline scheduleris used to determine which quest will bescheduled next a 500 millisecond requesttime as the goal for read request thisis the time it would take to start therequest with a 5 second goal to start awrite requests this scheduler mayimprove system from responsivenessduring periods of heavy disk i/o at theexpense of data throughput since eachrequest has a deadline and the longerrequest has been waiting the sooner willbe scheduled this is especially usefulfor data based workloads because thereare many requests for different parts ofthe diskhowever for web servers and otherservices that try to access largequantities of data located in the samelocation on the diskthis particular scheduler can actuallyreduce total through play completelyfair queuing is a somewhat differentidea where instead of actuallyscheduling the i/o requests thecompletely fair queuing model schedulesprocesses or running programs to havetime slice access to each disk andessentially this cfq scheduler giveseach process and i/o time slice and thatprocess can do as much I owe on the diskas it would like within that time slicewhen the time slice expires the CFGscheduler moves on to the next processand gives it access time to the diskthere is a little bit of similarity hereto anticipatory scheduling since aprocess can send another request duringits time slice and try to get thatrequest in without having a lot of seektime however this algorithm can wastetime if a process does not immediatelyturn around and send another requestthus it can reduce the overall discthrough putsince there could be idle times whilewaiting to see if another request willcome in before our time slice expiresthis has been the default scheduler inLinux since 2.6 point 18 now for solidstate disks we have to choose ascheduler that accounts for the factthat there's no seek time to worry abouton the disk the anticipatory schedulerthe elevator algorithms short of seektime first all of these algorithms canactually reduce performance on asolid-state drive because they makeassumptions about minimizing head seektime and we have no heads to move with asolid-state disk completely fair queuingcan also reduce disk performance becauseof idling at the end of a time slicethat's true for any disk so what do wedo to maximize performance for asolid-state drivethere are really two good choices for asolid-state drive there is the no op orFIFO scheduler this works well forgeneral-purpose systems however whenthere are handy i/o workloads and wewant to maintain system responsivenessthe deadline algorithm is useful sinceother processes will have moreopportunities to access the disk insummary operating systems arearbitrating disk access among differentprocesses to prevent one process frommonopolizingthe disk and preventing other processesfrom having access on older discs withcylinder-head sector addressing theoperating system was also attempting toreduced seek time thus improvingaggregate disk performance however newerSATA disks with native command queuingschedule themselves to reduce both seektime and rotational delay thusalgorithms that attempt to minimize seektime are unnecessary furthermore withsolid-state drivesscheduling mechanisms that are based onold mechanical assumptions can actuallyreduce performanceso for SSDs were really only interestedin arbitrationyouin this lecture I'm going to discussfile systems I'll be providing anoverview of the purpose of file systemsdiscussing metadata that they storeexplaining how we create a file systemthrough a process known as formattingtalk about some issues of file systemsincluding fragmentation and journalingbriefly discuss some internal layoutsused by different file systems andfinally talk about mounting andunmounting file systems to make themavailable to users a file system isresponsible for laying out data on apersistent storage device and ensuringthat data can be retrieved reliably thefile system is an abstraction of diskspace it provides routines for queryingopening and closing files and providinghuman readable names for files and somekind of organizational structure forfiles typically through directories orfolders without a file system we wouldhave to access disk by physical locationor by address and each program wouldhave to reserve certain address limitsfor its exclusive use file systems inaddition to performing this abstractionalso arbitrate disk space amongdifferent programs and different usersof a computer system file permissionsallow users to have a certain degree ofprivacy while file quotas ensure thatone user does not monopolize the entiresystem by utilizing that all the diskspace file systems are also responsiblefor storing metadata or informationabout each file this includes a filename file size who owns the file whatgroup that owner belongs to whatpermissions exists for each differentcategory of users on the system toaccess that file as well as to providecertain time stamps on UNIX we have theinode creation time the filemodification timeoptionally the last file access timemetadata records also include internalinformation that is important for thefile system itself such as pointers tothe actual data on disk and a referencecount for how many different names referto the same file system called hardlinks we create a file system by takingan empty partition or a partition thatwe're ready to reuse and formatting itformatting quite simply as the processof making a new file system on anexisting partition formatting typicallydestroys the structure of any filesystem that was previously installed onthe partition thus when you format apartition you lose the access to itscontents at least through standard toolshowever unless that free space unlessthat partition is securely erased thecontents that were formerly on thepartition can still be recovered usingforensic tools the only safe way toswitch between file systems on a singlepartition is to back the data that's onthat partition up to another disk formatthe partition using whatever the newfile system would be and then restoringthe data from the backup there is nosafe way to change a file system type inplace without losing data the filesystems do suffer from a few issues overtime sections of a file in a file systemcan become non contiguous in other wordsa file gets split over different partsof the disk and in the process that alsosplits up the free space so that whennew files need to be allocated they haveto be split up to take advantage ofsmaller blocks of free space this is asituation called fragmentation it'sworse than some file systems than othersfragmented file systems were big problemwith mechanical hard drives simplybecause a fragmented file requires aseek to move from the location of thefirst fragmentthe location of the next fragment andpossibly further seeks if there are morefragments not so much a problem on solidstate drives however since there's noseat time and file systems can getaround this problem either with offlinedefragmentation tools that the systemadministrator can run manually or theycan use fragmentation avoidancestrategies or automatic on-the-flydefragmentation another issue that canoccur with file systems is that a singlehigh-level file system operationtypically requires several low-levelsteps in order to complete if thecomputer should crash or power be lostin the middle of those steps beingperformed the file system could be leftin an inconsistent state a solution tothis problem is called journaling andthe way this works is by recording allthe steps that are to be taken insomething called a journal a specialpart of disk space reserved for thisparticular information records all thesteps that are going to be taken priorto taking the steps thus if the systemshould crash in the middle of a filesystem high level operation all thatneeds to occur is the journal simplyneeds to be replayed next time the filesystem is mounted and the steps can becarried out again and leave the filesystem in a consistent State internallyfile systems may use one of severaldifferent approaches for storing data onthe disk a simple layouts called thefile allocation table which simply has asingle table in each partition to storemetadata and the addresses of datasegments for each file file allocationtable type storage methods are limitedonly in terms of how big the fileallocation table can be and theselimitations specify among other thingsthe maximum size a file can be and howmany files can be on the systemanother approach is to use somethingcalled eye nodes which are datastructures on UNIX systems that containthe metadata for a file includingpointers to the actual data I nodes donot store the file names however theseare stored in a separate structurecalled a directory that map's file namesto inodes the maximum number of files ofa single file system can hold is limitedby the number of I nodes created whenthe file system is formatted this can bea particular problem for file systemsthat wind up storing a really largenumber of very small files there couldbe plenty of space left on the filesystem on the partition however if thenumber of AI nodes is exhausted then nomore files would be able to be createdanother approach to storing files andlaying out data on a file system isthrough the use of extents extentssupport larger maximum file sizesbecause they're designed to allow filesto be composed of several non contiguousblocks of space much like fragmentingthat could occur at the file system thatdoesn't use extents extent informationis stored with the metadata in the fileinode or some other type of datastructure for file systems that supportextents now regardless of how the filesystem lays out its data internally weneed to make the file system availableto users and programs on the computer todo this we perform a process calledmounting mounting is the act of making afile system available to the users ofthe system the opposite process iscalled unmounting which is disconnectinga previously mounted file system UNIXsystems mount file systems at mountpoints which are simply directoriessomewhere within the overall directorystructure of the system so if I plug ina flash drive on a Linux machine forexample that flash drive may be mountedat slash media slash my drive I canmount a large number of different filesystems this wayat the same time and I can make all ofthe different file systems appear to bepart of one directory structure on theother hand Windows systems use Driveletters where the letter C is reservedfor the system partition the one onwhich Windows is installed and a and Bare reserved for floppy drives Windowssupports a maximum of 26 file systems tobe mounted at oncesimply because that's the number ofletters that are available to assigneddrives to its assigned partitionsso in summary file systems organizeddata store metadata provide anabstraction of the underlying storagemedium and arbitrate access to thestorage space we create file systemsthrough a process known as formatting wecan make file systems more robustagainst data loss during a power failurethrough the use of journaling internallyfile systems use various differentmechanisms for laying the data out ondisk but no matter how they workinternally we can make them available toa running system by mounting them inthis lecture I'm going to discussfeatures of the central processing unitor CPU that are useful for supportingmultiple applications sharing a computersystem simultaneously in particular I'llintroduce multi programming and discussthe hardware requirements to supportmulti programming I'll discuss CPUprivilege modes x86 protection ringsmode switches and briefly introducedinterrupts the first concept tointroduce is multi programming and multiprogramming is simply the idea that wecan run multiple processes or multipleinstances of potentially severalprograms at the same time and we can dothis by having the CPU switch quicklyamong the different processes enablingall of them to make forward progress perunit of human perceivable time the CPUwill switch quickly enough to providethe illusion that all the processes arerunning at the same timeeven if we only have one processor corein the vast majority of modern computingsystems with the exception of somespecial-purpose systems our multiprogramming system some of the oldcomputer systems of the day were batchsystems that only ran one sis oneapplication at a time now in order tosupport multi programming we have tohave certain features of our computerhardware first of these is an interruptmechanism for enabling preemption ofrunning processes whenever some kind ofevent occurs we have to have a way ofstopping a process handling an event andthen restarting the process we need tohave a clock so that we know how long aprocess has been running and we need tohave CPU protection levels to restrictaccess to certain instructions toprevent processes from hijacking thesystem or just trying to bypass theoperating system altogether we also needto restrict access to memory in order toprevent reading and writing to memorythat the particular process does not ownbelongs to somebody else- CPU protection levels are sufficient aprotected mode and a privileged modethese modes are also called thesupervisor mode or kernel mode and usermode in kernel mode all instructions onthe CPU are enabled and the kernel canaccess all memory on system in user modethe CPU disables all the privilegedinstructions and restricts most directmemory operations thus a user programmust make a system call to the operatingsystem to request memory or performother resource allocation tasks in thisway the user processes are effectivelysandboxed both from the system and fromeach other on the Intel based systemsx86 and x86 64 systems there areactually four modes available these areimplemented by what are known as x86protection rings which consists of fourprivilege levels numbered 0 through 3ring zero has the greatest number ofprivileges code executing in ring zerocan execute any instruction the CPUprovides and can access all memory rein3 has the fewest privileges all theinstructions are restricted to the setof instructions that are relatively safein practice most operating systemsactually only use ring 0 and 3 os/2 andXen are the notable exceptions that makeuse of ring 1 newer systems withvirtualization extensions either theintel vt-x extensions or the AMD vextensions add an extra privileged levelbelow ring 0 this is colloquiallysometimes referred to as ring negative 1and this mode enables instructions thatallow multiple operating systems toshare the same processor theseinstructions help system support hostingmultiple virtual machines at the sametime now regardless of the number ofmodes available whenever we wish tochange modes for whatever reason we haveto perform something called a modeswitch and that occurs whenever the CPUswitches into user mode kernel mode orhypervisor mode or whenever an x86 CPUchanges which protection ring ispresently effective mode switches havethe potential to be slow operationscompared to other machine instructionsdepending upon the hardware a notableexample was the first generation ofIntel Core 2 series processors in whichthe mode switches into and out ofhypervisor mode were quite slow onesituation in which a mode switch mightoccur is when something called aninterrupt happens and an interrupt issimply a situation in which thecurrently executing code is interruptedso that an event can be handled by theoperating system interrupts can fallinto two categories can have involuntaryinterrupts which are externalto running processes these consist ofthings such as IO interrupts which aregenerated every time you press the keyon the keyboard or perform any other IOtask clock interrupts which are timermechanisms that can be scheduled to gooff in a particular time and page faultswhich have to do with the virtual memorysubsystem interrupts can also bevoluntaryin other words created by a processthat's running system calls andexceptions such as setting fault or / 0actions can result in interrupts as welland the CPU provides hardware mechanismsfor detecting when an interrupt isoccurring and handling the interruptso in summary multi programming systemsallow multiple applications to runsimultaneously implementing multiprogramming reports requires supportfrom the hardware in particular we needCPU privileges we need a clock and weneed some kind of interrupt handlingmechanism the CPUs used in multiprogramming systems need to have atleast two privileged modes Intel x86systems support four or five modesdepending on the processor mode switchescan be expensive in terms of performanceso we don't want to do them more thannecessary and interrupts enable Hardwareevents to be delivered to applicationsand they allow applications to yieldcontrol of the system while waiting forevents are waiting for services lectureI'm going to discuss kernelarchitectures I'll begin by introducingthe functions of the kernel explain theseparation between mechanism and policytalk about some seminal early kernels inthe history of computing and thenintroduce the differences betweenmonolithic kernels and micro kernels nowkernel provides two functions the sametwo functions is in the operating systemit provides abstraction and arbitrationthe kernel provides abstraction in thesense that it provides a mechanism forprograms to access Hardware a way toschedule multiple programs on the systemand it provides some method forinter-process communication or IPC a wayfor programs to send messages to eachother or send messages to hardwaredevices or out to the network kernelsalso provide abstraction mechanisms theyensure that a single process or runningprogram can't take over the entiresystem they enforce any kind of securityrequirements such as access privilegesthat might be in place on the system andthey minimize the risk of a total systemcrash from a buggy application or devicedriver it's important to distinguishbetween mechanism and policy whendiscussing the internal components of anoperating system the mechanism putsimply is the software methods thatenable operations to be carried out anexample of a mechanism would be codethat implemented inside a device driversends a message to a device that causesthat device to blink a light enable acamera or perform some other Hardwarelevel operation policy on the other handis a set of software methods thatenforce permissions access rules orother limits against applications so apolicy for example would be somethingthat said that only users who metcertain criteria could send a messageout to a hardware device to blink alight or enable a camera or perform someother Hardware function it's a generallyaccepted principle of good design thatmechanism and policies should beseparated as much as possiblean early kernel that separated mechanismand policy quite well was the Ragmancentral and RC 4,000 monitor kernel thisCardinal was developed in 1969 primarilyby Perry brand Hansen for the ReaganCentral and RC 4,000 computer systemthis was a computer system that wasdeveloped in Denmark and the centralcomponent of the system was a smallnucleus as brink Hanson called it calledmonitor which allowed programs to sendmessages to each other and allowedprograms to sendreceive buffers which were essentiallytypes of messages for Hardware to andfrom different hardware devices inparticular at that time they had a cardreader our tape reader and a printingstyle output device other kernels withdifferent scheduling mechanisms andother capabilities could be run undermonitor in those days it was not clearthat multi programming was really adesirable feature for computing thussomeone could write a multi programmingcapable kernel and actually run that asa sub kernel under the monitor systemimportantly this was also the firstsystem that allowed sub kernels andsystems level software to be written ina high-level language in this casePascal the system performance wasactually quite awful Frank Hansen statedthat the operating system itself was soslow at performing its IPC tasks thatthere were a number of issues with thesystem completing tasks on time howeverthe system was stable and reliablemaking it successful in computer sciencehistory even if it was not a successfulproduct commercially on the other handthe opposite extreme would be the UNIXkernel this was developed at Bell Labsby a team headed by Ken Thompson andDennis Ritchie also starting in the late1960s the difference between the UNIXkernel and the RC 4000 monitor was thatthe UNIX kernels design implementedperformance thus instead of having avery small kernel that simply providedan IPC mechanism in some basic resourcecollision-avoidance this kernel actuallyprovided all the device drivers all thescheduling all the memory managementincluding support for multi programmingdirectly inside the kernel this kernelwas an early example of what would laterbe called a monolithic kernel amonolithic kernel is a kernel thatcontains the entirebreeding system in kernel-space runs allof the operating system code inprivileged mode or ring zero on an x86system and divides the differentfunctions of the operating system intosubsystems of the kernelall of these subsystems however are runin the same memory space this has theadvantage of higher performance but thedisadvantage is that the kernel becomesless modular more difficult to maintainand the components are not separatedvery well so a crash in one componentcould in fact bring down the entiresystem the opposite of this the RC 4000style kernel is what we now call amicrokernel and a microkernel basicallycontains the bare minimum of code isnecessary in order to implement basicaddressing inter-process communicationsand scheduling this basic amount of coderuns in kernel space and everything elseruns in user space often with lowerprivileges as a general rule of thumbmicro kernels contain less than 10,000lines of code microkernel basedoperating systems tend to be quitemodular because they divide theoperating system functions between thekernel and a set of servers that run inuser space however because many of thecore functions of the operating systemare performed by user space componentswhich have to communicate with eachother via the kernel performance doessuffer thus most kernels that are in usetoday are a hybrid of these two designsI'm going to introduce Murphy's Law ofreality sort of an extension of theMurphy's laws with which you may befamiliar and my definition of Murphy'sLaw of reality is simply that reality isthe hazy space between the extremes ofcompeting academic theories in whicheverything is wrong in some way at leastaccording to the theories this idea of ahybrid kernel architecture is acontroversial one some people do notlikeuse this terminology at all many peopleprefer to keep the binary classificationof monolithic kernel and microkernelhowever if we look at modern kernelstypically the monolithic versions ofmodern kernels are broken into modulesthat can be loaded and unloaded atruntime this helps to increasemaintainability of the kernel and truemicro kernels today would haveunacceptable performance thusmicrokernel based systems typically havesome of the features of monolithickernels such as more device drivers andother code that runs inside the kernelsmemory space some examples of differenttypes of kernels for monolithic kernelsin addition to the system 5 UNIX kernelwhich is a descendant from the originalunits kernel we have the Linux kernelBSD ms-dos and windows 9x kernelsWindows NT XP Vista and 7 if you don'tprefer to use the hybrid terminologywould also qualify as monolithic kernelsand the Mac OS 10 kernel falls into thesame category in terms of micro kernelsthe RC 4000 monitor kernel would havebeen the earliest however there havebeen plenty other examples includingMach L for the MIT exokernel project andthe idea at least behind the Windows NTkernel which was based upon amicrokernel design the same is true ofthe Mac OS 10 kernel since that wasoriginally based on the Mach microkernelhowever those have been heavily modifiedand now have many properties ofmonolithic kernels also so in summarythe kernel is the minimum layer ofsoftware inside the operating systemthat provides the basic foundations forabstracting away details of the hardwareand arbitrating between multipleapplications when the bare absolute bareminimum implementations are used we callthe result a microkernel monolithickernels on the other hand have all theirmajor OS components contained withinthem running everything inside kernelspace to improve performancetwo early influential kernels were theRC 4000 monitor an example of amicrokernel and the original UNIX kernelwhich was an example of a monolithickernel in practice however most modernoperating system kernels are hybrids ofthe two designs and have features ofboth kernel typessystem via the command line in part 1 ofthis lecture I'm going to discusscommand line operation introduced padsin the file system discuss the filesystem hierarchy talk about the contentsof the root directory give an overviewof several top level directories brieflydiscuss configuration files andintroduce the concept of man pages nowin Linux the command line is the oldertype of interface user interface to thesystem it is a text mode interface thatpredates the development of graphicaluser interfaces or gooeys the commandline uses the keyboard exclusively ingeneral there is no use of the mouse andit works by having you type in a commandfollowed by any arguments to thatcommand and then pressing enter thecommand runs and if there are anyresults to be displayed the result ofthe command is displayed below where youentered the command at all times thecommand shell or the program thatprocesses the commands that you'reentering is in something called aworking directory that working directoryis a location on the file system inwhich any file that you create bydefault will be placed and you can openfiles by default without having to giveany kind of path information for themyou can figure out what the currentworking directory is by using the PWD orprint working directory command you canchange directories using the command CDrunning the command CD with no argumentswill take you to your home directory andyou can list the contents of anydirectory with the LS command it'stypical that someone has been usingLinux for some time will compulsivelyissue the LS command every time the CDcommand is used so that you can maintainsome kind of awareness about how thefilesystem is structured paths in thefilesystem can be given in one of twoways they can be given as an absolutepath meaning that they have a leadingslash such as slash @ c slash in it tohaveor /opt slash condors /bin relativepaths on the other hand are relative towhatever current working directory theshell is in thus a relative path my filesee is going to refer to a file named myfile dot C located in the currentworking directory the path tests slashfinal slash P underscore all opps isgoing to refer to a file that is in thefinal subdirectory of a tests directorythat can be found in the current workingdirectory there are also some specialrelative path name components that canbe used a single period a single dotreferences the current working directorytwo periods or two dots references theparent directorythus the path dot dot slash foo slashdot slash bar means go up one directoryfrom the current working directory thengo down into its sub directory foo andaccess a file called AR notice that thesingle dot alone as part of a directorypath generally has no effect because itrefers to the current directory now alldirectories on a UNIX system areorganized according to the filesystemhierarchy and there is a specificationavailable for the filesystem hierarchywhich different distributions follow twodifferent levels and the standards getinterpreted a bit between systems anddistributions in any case however theroot directory of a filesystem islocated at a path consisting of a singleforward slash and you can change to theroot directory by running C D and thenas the argument to C D just a singleforward slash and in this screenshot wecan see we're on a system I've run CDslash and then run LS to look at thecontents of the redirectthere are a number of top-leveldirectories that are fairly standardinside the root directory on a normalLinux systemthese include slash bin which is wherethe minimum set of programs needed towork with the system is located /devwhich contains entries corresponding tohardware devices on the system /xe whichcontains the system level configurationfiles /optwhich contains optional softwaretypically added by the systemadministrator slash USR often pronouncedslash user which contains software hitsships with the Linux distribution slashvar which contains rapidly changingfiles such as log files / Lib whichcontains system libraries used by otherprograms slash media into whichautomatic mounting systems will mountremovable drives and devices /mntoften ran a slash mount which is wherethe system administrator can manuallymount removable devices or networkshares / root not to be confused withthe root directory is actually the homedirectory for the super user or rootuser / S Pen contains super userbinaries or programs that are intendedto be run only by the systemadministrator and slash temp is wheretemporary files are typically stored nowas mentioned a moment ago system-wideconfiguration files generally go inslash Etsy two important examples offiles in slash Etsy include slash Etsyslash init tab which sets the defaultrun level or whether the system is goingto boot into text mode or graphical modeand slash Etsy slash fstab whichcontains the filesystem table indicatingto the kernel where to find differentfile systems that need to be mounted atboot time configuration files in generalon Linux can be edited with a texteditor on a pure command-line systemthis might be the VI tosteady der VI is the one text editorthat is generally expected to be presenton any UNIX system if you need help on acommand or some configuration filewithin the system there is a built-inhelp facility called man pages or manualpages man pages allow you to get help onparticular commands and other featuresof the system simply by typing man aspace and then the command or featureand on which you would like to get helpto navigate through a man page you canuse the up and down arrow keys and thenuse the Q key to exit the manualfacility in the next part of the lectureI'll discuss file permissions and otherbasic issues related to running a Linuxsystemsure I will continue discussing thebasics of utilizing a Linux system inparticular we'll talk about fileownership file permissions listingrunning processes finding libraries usedby a program determining the absolutepath of a program and discuss the roleof the super user on the system firstwe'll start with file ownership andpermissions each file on a Linux systemis going to have an owner a group andaccess permissions this information canall be found by running the LS commandwith a dash lowercase L argument it ispossible to change which user on thesystem is the owner of the file usingthe CH own command or change owner CHowm the change group chgrp commandallows you to change which group a filewill be associated with and permissionsfor a file can be changed with a CHAhmad or CH mo d for change mode commandeach file has three types of permissionsfor each of the three levels of accessaccess controls are set with a bitwiseor of permission bits a value of 1 isused for execute permissions meaningthat the file can be treated like aprogram and executed directly a value of2 is used for write permissions meaningthat someone could change or delete afile and a value of 4 is read permissionbeing able to read the contents of afile individual file permissions aresupported for 3 classes of user theowner of the file members of the groupwith which the file is associated andso-called world permissions or all userson the system changing file permissionscan be done with a CH mo D command andby example a file can be set to be worldreadable and executable but writableonly by its owner using the commandchmod space 755 space the name of thefile a file could be set to be rightprotected in readable only by the ownerand group by running the same chmodcommand only with permissions for 4-0 inthe first example 755 means permission 7which is 4 plus 2 plus 1 meaning read +write + execute for the owner that's thefirst number of the 3 the first 5 thesecond number of the three setspermissions for the group which is 4read + 1 execute makes 5 and the samefor read plus 1 execute for the worldwhich is the third number in the 4 4 0case the 4 means read only for the ownerthe second four means read only for thegroup and zero means no accesswhatsoever by people who are not membersof the group with which the filesassociated permissions on a directoryworks slightly differently if adirectory has execute permissions thecontents of the directory can betraversed allowing access to readablefiles and subdirectories within thedirectory itself read permissions on adirectory are necessary in order for adirectory to be listed but for someoneto obtain a directory listing with LSthey must have both read permissions andexecute permissions for that directoryfiles can be deleted on a Linux systemwith the RM command RM is short forremove entire directories can be deletedusing RM dash RF and then supplying thedirectory name to delete this can be anextremely dangerous command if runincorrectly for example runningRM dash RF / as the root user willdelete every single file on the systemand it will not ask first this willleave the system in a destroyed statethere is also no undelete function onmost UNIX file systems once the RMcommand has been used the file is simplygone and unless that file has beenbacked up it is not easily recoverablewhen working with a Linux system it'soften useful to see what programs orwhat processes are running on the systemthere are two commands that can beutilized in order to find thisinformation the first of these is the PScommand which stands for processes PSspace ax will allow you to see allprocesses currently running on thesystem to find out which user owns eachprocess run PS space ax the top commandis a useful command for getting currentinformation about the state of thesystem including running processesamount of available memory and amount ofCPU that's being utilized this commanddisplays the processes that are usingthe most CPU time and updates itselfevery second or two this command can beexited by hitting the Q key to see whatdynamic libraries are used by a binaryprogram not a script but an actualcompiled binary application one can usethe l DD command so if one were to runthe l DD command on for example slashuser slash bin slash events for systemsthat have the kinome PDF readerinstalled one would find out whichdynamic libraries were needed in orderfor that application to run it's alsopossible to find out the absolute pathname of an installed program to seewhere it actually resides on thefilesystem this is done with the whichcommand for example typing which eventsshould display slash user slash binslideevents on most Linux distributionsprovided of course that software isinstalled finally there is oneadministrative user on the Linux systemcalled the super user it has the accountname root and has privileges to readwrite or delete any file change systemsettings and install software andperform other administrative tasks thatare normally forbidden of ordinary userson some Linux distributions such asUbuntu and on Mac OS 10 the root user isdisabled by default however many otherdistributions including Red HatEnterprise Linux CentOS and Arch Linuxleave the root user account enabled onsystems where the root user account hasbeen disabled or on systems where theadministrator would like to disable theroot account the sudo command allowsauthorized regular users to run acommand as the super user so for examplewe could find the listing of routes homedirectory by typing sudo LS slash rootto switch to the super user temporarilyon one of these systems sudo su dash andentering the users password would allowthe user temporarily to become the rootuser even if the root account isdisabled on systems where the rootaccount is enabled su dash has the sameeffect except that routes password mustbe entered instead of the user'spassword discuss interrupts and deviceinput output when hardware devices on acomputer produce events we need some wayof being able to handle those eventswithin the operating system and deliverthem to applications and hardwaredevices are going to produce events attimes and end patterns that we don'tknow about in advance for example wedon't know which keys the user is goingto press on the keyboard until the useractually presses those keys if a catwalks across the keywe're gonna see a completely differentpattern of keypressesfrom which we would expect to see withthe human user similarly if we haveincoming network packets if we'rerunning a server application or evenjust a workstation and we have messagescoming in from the network we don't knowthe order and timing of those messageswe also don't know when the mouse isgoing to be moved or when any other of awhole bunch of hardware events is goingto occur so how can we get theinformation generated by these eventsand make it available to ourapplications for use well we have twooptions first option is that we can polleach device we can ask each device if ithas any new information and retrievethat information or we can let thedevices send a signal whenever they haveinformation and have the operatingsystem stop whatever it's doing and pickup that information this is called aninterrupt the polling model of inputinvolves the OS periodically pollingeach device for information so every sooften the CPU is going to send a messageto each hardware device in the systemand say hey you have any data for me andmost of the time the device is going tosend back no don't really have any datafor you other times the device is goingto send back some data it's a reallysimple design extremely simple toimplement but there are a number ofproblems with polling first problem isis that most of the time when you'repolling the devices are not going tohave any input data deliver thus pollingis going to waste a whole lot of CPUtime the second issue that occurs ishigh latency if I press a key on thekeyboard that keystroke is not going toget transmitted to the computer untilthe next time the CPU pulls the keyboardto ask which keys have been pressed ifthat time is set to be really short I'llhave good responsiveness but the CPU isnot going to get any useful work done onthe other hand if we set that timelength to be long enough for the CPU toget some workthere's going to be a noticeable lagbetween the time I press a key and thetime a character appears on the screensince the device must wait for a pollinginterval because it can translate inputwe're going to have a high latencysituation and again shortening thatpolling interval to try to reduce thelatency simply wastes a whole lot of CPUtime checking devices that have no inputso a better mechanism is to use a systemcalled interrupts and with interruptsthe hardware devices actually signal theoperating system whenever events occuror more precisely the signal the CPU andthen it's up to the operating system toreceive and handle that signal what theoperating system will do is it willpreempt any running process in otherwords it will switch what we callcontext away from that running processto handle the event basically it willmove the program counter of the CPU tothe code to handle that particularinterrupt this allows for a moreresponsive system than we could everachieve through polling without havingto waste a whole bunch of time askingidle devices for data however this doesrequire a more complex implementationand that implementation complexitybegins at the hardware levelspecifically within the CPU we need tohave a mechanism for checking andresponding to interrupts and thismechanism is implemented as part of theCPUs fetch execute cycle in the processof fetch execute the CPU is going tofetch an instruction from memoryincrement the program counter executethat instruction but instead of simplygoing back to the next fetch the CPUactually has to have additional hardwareto check to see if an interrupt event ispendingif there is an interrupt pending thenthe CPU has to be switched to kernelmode if it's running in user mode so theprivilege level needs to be escalatedsave the program counter by pushing itonto the stack and load a programcounter from a fixed memory locationand that fixed memory location is calledthe interrupt vector table or ivt so weload the program counter from the I VTand then the CPU goes and executes thatnew instruction the next time the fetchexecute cycle resumes so the CPUactually moves from executing programcode to executing code from theinterrupt handler for the particularevent if no interrupt is pending at theend of and executes then we simply goback to the next instruction fetch theinterrupt vector table consists of anarray of addresses of handlers eachelement in this array essentially givesthe program counter location for thehandler for a particular interrupt thishandler is going to be in a subsystem ofthe kernel from on a lithic kernel orthis handler might invoke a call to anexternal server for a microkernel in anycase however the first handler byconvention element 0 of the array isalways the handler for the clock thenhandlers for different devices are inthe array after the clock Handler so theinterrupt vector is always mapped intothe user part of memory it's alwaysavailable at all times so that thekernel can go and look up interruptsinformation whenever is necessary aninterrupt is processed by branching theprogram counter to the interrupt handlerexecuting interrupt handling code andthen at the end of the interrupthandling code there will be aninstruction to return from the interruptin the intel assembly language this isthe IRET instruction which loads theprocessed program counter back frommemory it pops the stack to get theoriginal program counter back and goesahead and changes the CPU back to usermode so it removes the privilegeescalation the interrupt handlingmechanism is thus able to handle eventsfrom hardware devices without having topulldevice individual be discussinginterrupt controllers in particular I'llintroduce the old and new mechanisms fordelivering interrupts from hardwaredevices to the CPU these methods includethe original programmable interruptcontrollers and the new advancedprogrammable interrupt controller withmessage signaled interrupts interruptcontrollers provide an interface forhardware to signal the CPU wheneverdevice needs attention it's important tonote that this signal only includes amessage that essentially says hey I'm adevice I need attention the CPUhistorically then actually does have togo and pull the device to get any datathat the device may have the oldermechanism for performing this operationwas called a programmable interruptcontroller or pick and it actuallyrequired dedicated lines to be added tothe motherboard the eisah or industrystandard architecture bus which datesback all the way to the first pc back in1987 and older versions of the pci orperipheral component interconnect busutilized this mechanism the newmechanism or the advanced programmableinterrupt controller is used on PCIExpress devices and some newer PCIdevices now the old controller or theprogrammable interrupt controlleractually consisted of two programmableinterrupt controller chips that wereattached to each other with one of thechips being attached to the CPU theso-called master chip was the oneattached to the CPU and pin two of thatmaster chip was attached to a slave chipeach pin on each of the two chips allowsfor sixteen interrupts numbers to becreated interrupts 0 through 7 arecorrespond to the pins of the masterchip and interrupts 8 through 15correspond to the pinsof the slave ship now it should be notedthat since pen two of the master chiphandles the slave chip that the masterprogrammable interrupt controller onlysupports an effective seven interruptsso there are only 15 usable interruptsare Dwyer lines for devices and theseare numbered 0 through 15 but we have toskip the number 2 now historically pinnumber 0 which corresponds in softwareterms to what we call interrupt requestline or irq zero was connected to thetimer interrupt request line 1 wasconnected to the keyboard differenteisah and PCI devices could then use theremainder of the master chip byconnecting to irq lines 3 through 7 onthe slave chip pin 0 which correspondsto ir q 8 was connected to the real-timeclock pen 4 corresponding to ir q 12 wasconnected to a ps2 mouse pin 5 or ir q13 connected to the math coprocessorwhich was a separate component from themain cpu in earlier pcs and then pin 6and 7 corresponding to ir q lines 14 and15 connected to the ide controllersthese were used for disk and eventuallyfor optical devices this left pins 1through 3 on the slave controller or IRcues 9 through 11 available for hardwaredevicesnow these interrupt lines on themotherboard were actually circuit tracesthese were conductive paths edged intothe motherboard that allowed interruptsto be received from devices there were15 lines available of the 16 that couldbe used by devices with line 0 and 1reserved for the timer and a ps2keyboard respectively actually evenbefore the ps2 reservation the original80 keyboardeisah and pci add-in devices actuallyhad to share in uruk request lines andthis sharing could lead to Hardwareconflicts that could lock up the systemit was thus up to the system owner tomanage the sharing by setting littlejumpers on the Adhan cards so that thecards were using different irq linesthere were also performance issues whenirq lines were shared because theoperating system actually had to pulleach device sharing an IR cue todetermine which device it was thatraised the interrupt polling was stillnecessary in order to receive any kindof data from the device regardless ofwhether it was sharing an interrupt lineor not on modern systems a completelydifferent interrupt mechanism is usedand this mechanism has a set of memoryregisters on what's called an advancedprogrammable interrupt controller inthis set of memory registers isconnected to a single shared bus thateach device on the system can use toraise an interrupt message by writingthat message into one of the memoryregisters these are called messagesignaled interrupts using the MSI andMSI X specifications essentially eachdevice here I have a timer RTC USB hostcontroller SATA controller is attachedto the bus and indicates its interest inraising and interrupts to the apec bysending a message over that bus now thismessage does not contain any data it'sonly a request for attention if the CPUhas to be involved in the operation ofsending or receiving information thenthe CPU actually has to contact thedevice in other words pull it directlythere is a way around this called directmemory access or DMA transfers which areused extensively on PCI Express devicesthe register on the apec stores therequest for attention until such time asthe operating system handles theinterrupt request and thenmessage is cleared from the APEC this isthe only interrupt mechanism that'savailable on PCI Express buses there areno hardware interrupt lines however anumber of motherboards still haveinterrupt lines physical interrupt linesand have physical pick pens so that theycan support legacy devices there anumber of specialty legacy devices stillin use that need to be supported messagesignaled interrupts do solve a number ofproblems with interrupt request sharingthe original specification allows eachdevice to use any one of 32 IR key linesthe MSI X specification will allow eachdevice to use up to 2048 virtual linesvirtual interrupt requests offersessentially and this allows for lesscontention and reduces the need to shareinterrupt request numbers by device thusreduces the amount of time necessary forthe CPU to determine which device wantedattention so main thing to take awayfrom this is that the interruptcontroller and the interrupt requestmechanism only allows the device toraise a signal that says it wantsattention it's up to the CPU or oncertain buses up the device and thememory controller to get the informationout of that device and into memory andinterrupt handling at the hardware leveland then move on to features provided bythe CPU and finally features of theoperating system for handling interruptsat the hardware level devices areconnected either via traces on themotherboard or via a shared messagingbus to the advanced programmableinterrupt controller the CPU checks forhardware interrupt signals from thiscontroller after each user modeinstruction is processed so after eachinstruction is executed running someparticular program on the system the CPUactually checks to see if there are anyinterrupts that need to be processed ifan interrupt signal is presentthen a colonel routine is called by thecpu in order to handle this interruptthe interrupt dispatch routine if it'snot implemented directly in hardware isactually a compact and fast routine thatcould be implanted in the kernel oftencoded in assembly language it has to bethat fast the specific interrupt handleris always a kernel routine or in thecase of a micro kernel and externalserver routine and this specific handlerdepends upon the type of interruptsreceived these are typically coded in Cso once again the fetch execute cycle wecheck for an interrupt pending aftereach instruction is executed if there isan interrupt pending we escalateprivilege to kernel mode push theprogram counter onto the stack in otherwords save it so we can resume from thatpoint in whatever program wereinterrupting and then go and handle theinterrupts we do this by loading theprogram counter the new program counterthat is from a fixed memory locationprovided to us by the interrupt vectortable the interrupt vector table givesus the address of all the differentinterrupt handlers we need a separatehandler for each type of interrupts theclock requires different logic from thekeyboard for example other devices suchas say a webcam attached to yourcomputer needs different logic in orderto process messages from it so we havedifferent interrupt handlers for each ofthese different devices the table simplystores the addresses of each handler andin our monolithic kernel case thehandlers are actually part of the kerneland are mapped into kernel memory spacethe interrupt vector table consists of alist of each of these addresses forkernel handlers and conceptually ismapped into both kernel memory and usermemory so that it can be accessedquickly and historically they started ataddress 0 however the mappings aredifferent depending on the architectureon intel-based systems we have somethingcalled the interrupt descriptor tableand the IDTprovides special instructions and datastructures that are actually managed bythe CPU itself so the interrupt handlingcan be as fast as possible andprotection rings can be changedautomatically the IDT is simply areserved block of RAM used by the CPU tojump quickly to a specific interrupthandler this IDT is mapped into kernelspace which was originally beginning ataddress 0 but this mapping is actuallyflexible with modern CPUs and can bemapped into other parts of the memoryspace the first 32 entries of the IDTare actually not used for interrupts perse but they're actually used for CPUfault handlers and then the interruptvector table part of the data structurebegins after the cpu fault handler tablewhen we actually go to handle interruptsthe handling occurs in the kernel andthis is done with two levels ofinterrupt handling the fast interrupthandler and the slow interrupt handlerthe fast interrupt handler is the pieceof code that's invoked directly from theinterrupt vector table whenever aninterrupt occurs this is the piece ofcode that the CPU is just going to jumpto when an interrupt occurs fasthandlers execute in real-time andthey're called fast interrupt handlersbecause they need to be fast theexecution of one of these interrupthandlers needs to be short if anylarge-scale data transfer needs to occursay we need to get a lot of data fromthe device all at once this operation ishandled by having the fast interrupthandler in queues something called atask into the operating systems taskqueue whenever all the fast interrupthandlers for all the differentinterrupts are done executing the CPUwill go and check the task queue andexecute any tasks that are present therethe part of interrupt handling that goesinto the task queue is called the slowinterrupt handler and it's called thisbecause it's notyou'd immediately and it can beinterrupted by other devices so whathappens if an interrupt request isreceived while we're still processingand interrupts from a previous requestwell there's no problem if we're in theslow interrupt handler because thisprocessing is done in such a way that wecan stop this processing and handle thenew interrupts if necessary what happensif we are still running a fast interrupthandler well the new interrupt handlercould be executed before the firstinterrupt handler is finished and thiscould cause some major problemsespecially if we get a new interruptfrom a device that's sharing the sameinterrupt line as the one that we'rehandling so what we do is we make fastinterrupt handling atomic that is wemake it uninterruptible on a singlecourse system this is as simple asdisabling interrupts as long as we'rerunning a fast interrupt handler onmulti-core systems there are actualspecial machine instructions tofacilitate atomic operations that arepegged to one CPU core these atomicinterrupt handling operations will runto completion without interruption byany other interrupt or any other requeston the system thus the longer aninterrupt handler takes to run thelonger the system will be unresponsiveto any new interrupts so what happens ifa fast interrupt handler is coded insuch a way that it takes too long otherdevices might be requesting attention atthe same time that this long-runninginterrupt handler is executing worse thesame device that generated the originalinterrupt might now have more data todeliver to the OS before all theprevious data is completely receivedthis could cause hardware failuresbuffer overflows dropped data droppedmessages all kinds of issues thehardware level however inside theoperating system this could lead tosomething called an interrupt stormwhich is really bad an interrupt stormoccurs whenever another interrupt isalways waiting to be processed whenevera fasterhandler finishes its execution thatcould occur either because the fastinterrupt handler is too long and needsto be split into a fast and a slowhandler this can also occur if hardwarehas certain bugs that cause it to raisespurious interrupts if the operatingsystem is perpetually handlinginterrupts it never runs any applicationcodethus it never appears to respond to anyuser inputs the result of the situationis something called a live lock thesystem is still running it's stillprocessing all these interrupts howeverit's not doing any useful work thus tothe user the system appears to be frozenand when an interrupt storm occurs inthis live lock situation results thetypical way out of this problem involvesjudicious use of the power button sointerrupt handling is an importantconcept in order to support multiprogramming systems an interrupthandling when these interrupt messagescome through from our dwyer is dividedinto two types of handler so that wedon't get the interrupt storm the fastinterrupt handler executes atomicallywithout being interrupted by anythingelse but it must be fast must enter thatinterrupt handler do some very shortoperations and immediately exit thathandler if any long-running operationsneed to occur as a result of a deviceinterrupt request we need to handlethose operations inside the slowinterrupt handlerresources and how the system and itsprocesses view random access memory inorder to run any process or instance ofa program on a computer system we needto provide two critical resources accessto the CPU and access to random accessmemory or RAM for storing andmanipulating data RAM is a type ofdedicated Hardware memory that isattached to the motherboard it isseparate from persistent storage or harddisk space Ram is also volatile whichmeans that it loses its contentswhenever power is interrupted to the RAMmodules including whenever the computeris turned off at a low level thecomputer hardware presents memory to theoperating system as one large block ofspace this space is divided into bytesand each byte in memory has a uniqueaddress that can be used to access it a32-bit architecture provides enough ofthese byte addresses to utilize up to 4gigabytes of RAM above that amount thereis not enough space than a 32-bit numberto store the address of any memorylocations in excess of 4 gigabytesthus a 64-bit architecture is requiredfor systems with more than 4 gigabytesof RAM each process or running instanceof a program on a system uses adifferent view of memory process memoryis divided into several pieces the stackthe heap global variables and the textsegment the stack is used to storeautomatic variables or variables thatare local to functions in the Cprogramming language space on the heapis manually allocated and D allocated bythe programmer when writing C code usingthe functions malloc and free free spacefor extra data is located between thestack and the heap and the stack and theheap grow toward one another globalvariables are provided with their ownsection of memory which is allocatedbetween the heap and text segment thetext segment is used to store programcode this segment of memory is read-onlyand cannot bechanged as I mentioned in the previousslide automatic variables are placedonto the stack this placement isperformed by the compiler when theprogram is built placement of data ontothe heap is historically performed bythe programmer although many of theseoperations are now automated in moderndynamic languages in the C and C++languages the programmer must explicitlyrequest and release or allocate anddeallocate heap space in C theseoperations are performed using themalloc and free functions while the newand delete operators are used in C++ inJava the programmer must explicitlyallocate space on the heap using the newkeywordhowever the Java Runtime automaticallydetermines which heap allocations are nolonger in use and frees those locationsautomatically this process is calledgarbage collection Python provides aboveautomatic allocation and garbagecollection whenever a data structurerequires heap space the Pythoninterpreter allocates it automaticallyonce the data structure is no longerused by the program the garbagecollector deallocate sit withoutprogrammer intervention use of heapmemory and processes presents achallenge to the operating systembecause these allocations anddeallocations are not known in advancethe compiler is able to track and reportthe amount of stack space needed sincethe number of local variables in afunction never changes in a languagelike C however the number of heapallocations may vary from programexecution to program execution making itimpossible to know exactly how muchspace should be allocated in advanceworse heap memory allocations tend to besmall and frequent so the process ofallocating memory from this sectionneeds to be fast this speed and dynamicavailability needs to be maintainedwhile the operating system shares thecomputer's RAM among multiple processesat the same time in addition to sharingmemory among processes the kernel hasmemory requirements of its own asidefrom the kernel code and its ownautomatic variables the kernel is filledwith datathat dynamically grow in strength duringthe course of system operation thesedata structures are numerous and includeprocess control blocks the ready listscheduling use device access tables andmany other types of structure unlikesome processes however all memoryallocation and de-allocation in thekernel is performed by the kernelprogrammers in the Linux kernelprogrammers can use one of a number offunctions including K malloc KZ Alec VMmalloc K free and V free the first issuethat must be solved by the kernel issharing memory between itself and a userspace process this sharing isaccomplished first by dividing thememory into two regions kernel memoryand user memory the kernel keeps itsdata structures program code globalvariables and automatic variables andkernel memory isolating these items fromthe running process process memory isplaced in a separate region from thekernel but the kernel is alwaysavailable in memory this mapping isnecessary to maintain performancewhenever an interrupt occurs the processmakes the system call to the kernel orthe process experiences a fault thatmust be handled by the kernel so how dowe go about running multiple processesat the same time well the first way wecan consider which is used in some typesof embedded systems is to divide thememory into fixed sized chunks calledpartitions a memory partition is asingle region of RAM that is provided toa single process both the program codeand data associated with each processmust fit within this pre allocated spaceif a process grows too large it will runout of memory and crash furthermore themaximum number of concurrent processescalled the degree of multi-programmingis limited by the number of partitionsavailable once all memory partitions areused the system cannot start any newprocesses this situation is exacerbatedby the fact that small processes may notbe using their entire partitionsresulting in wasted memorythis lecture I will introduce dynamicmemory allocation at the system levelthis method of memory allocationimproves the degree of multiprogrammingthat a system can provide by allocatingmemory to processes as needed instead ofahead of time and fixed size chunksfixed memory partitioning is fast andefficient in terms of overhead but itwastes space and limits the number ofconcurrent processes to the number ofpartitions that will fit into RAMdynamic memory allocation resolves thisissue by allocating memory to processesas it is neededthis mechanism increases the degree ofmulti-programming that the kernel fitssupported but this improvement comes ata cost of greater complexity in additionthere are trade-offs present in dynamicmemory allocation that directly affectthe performance of the system theseissues include efficiency methods fortracking free space algorithms fordetermining where to make the nextallocation and memory fragmentation theprimary issue with dynamic memoryallocation is fragmentation duringexecution processes allocate and freememory and chunks of varying sizes overtime regions of free space within memorybecome non contiguous with sections ofallocated memory in between sections ofavailable memory this fragmentationcould lead to serious performance issuessince program execution speed will dropdramatically if every data structuremust be implemented as a linked list ofsmall pieces furthermore algorithms thattry to perform on-the-fly memorydefragmentation are extremely complex toimplement and would also severely impactsystem performance since it isimpractical to avoid or fixfragmentation memory fragments aresignificant concern when space isdynamically allocated small fragments ofmemory are useless to programsparticularly C and C++ programs whichrequires structures and objects to beallocated in contiguous memory regionsthese structures are likely to be invarious sizes that are not efficient toutilize for memory management purposesso the systems will allocate a few morebytes and the structures actuallyrequire in order to improve efficiencyof the memory tracking systemsfurthermore structures and objects willbe allocated and freed numerous timesduring program execution furtherfragmenting the RAM overtimefragmentation can waste large portionsof the system memory limiting the degreeof multi programming by making itimpossible for new processes to startthere are two types of fragmentationexternal and internal externalfragmentation occurs when free space andmemory is broken into small pieces overtime as blocks of memory are allocatedand D allocated this type offragmentation tends to become worseexternal fragmentation is so bad withsome allocation algorithms that forevery n blocks of memory that areallocated to a process the system wastesanother half in blocks and fragmentswith these algorithms up to a third ofsystem memory becomes unusable the othertype of fragmentation is called internalfragmentation internal fragmentationoccurs because memory is normallyallocated to processes in some fixedblock size the block size is normally apower of two in order to make the kernelmemory tracking structures moreefficient processes tend to requestpieces of memory and sizes that do notfit neatly into these blocks thus it isoften the case that parts of a block arewasted as a result for small memoryrequests large portions of the block maybe wastedwhen a process requests heap memory thekernel must find a chunk of free spacelarge enough to accommodate the requestthis chunk cannot be smaller than therequested size since the process expectsto use all the space it is requestingsince the memory is divided into blocksfor efficiency the chunk of memoryreturned to the process is normallylarger than the amount requested unlessthe process happens to request a wholenumber multiple of the block size I'mnow going to introduce four classicalalgorithms for dynamic memory allocationbest fit worst fit first fit and nextfitthe first classic algorithm for dynamicmemory allocation is the best fitalgorithm in this algorithm the kernelsearches for the smallest chunk of freespace that is big enough to accommodatethe memory request although best fitminimizes internal fragmentation byavoiding over allocation externalfragmentation is a major problem anattempt to reduce the externalfragmentation and the best fit algorithmis observed in the somewhatcounterintuitive worst fit algorithmusing the worst fit algorithm the kernelfinds and allocates the largestavailable chunk of free space providedit is large enough to accommodate therequest in theory this allocationstrategy leaves larger and thuspotentially more useable chunks of freespace available in practice however thisalgorithm still fragments badly bothinternally and externally aside from thefragmentation both of these algorithmsare impractical in actual kernelimplementations because they mustperform a search of the entire free listto find the smallest or largest chunk ofmemory the need to search the free listis eliminated using the first fit ornext fit algorithm in the first fitalgorithm the kernel simply finds andallocates the first chunk of memory thatis large enough to satisfy the requestthis approach does result in internalfragmentation and it also tends tocreate small fragments of free spacethat accumulate at the start of the freelist reducing performance over time thenext fit algorithm avoids the externalfragment accumulation by starting thesearch for the next chunk of memory fromthe most recent allocation in practiceonly the first fit algorithm is used inthe Linux kernel and then only forembedded devices this algorithm iscalled the slob alligator which standsfor simple list of blocks for nonembedded systems that have thecomputational power for more complexalgorithm slab allocation is usedinstead of any of these simplealgorithms memory allocation I willintroduce the power of two methods withthe buddy system and coalescence forallocating memory toprocesses then I will introduce slaballocation which is used within thekernel to allocate kernel datastructures efficiently in the previouslecture I introduced the classicalgorithms for memory allocation bestfit worst fit first fit and next fit nowI want to introduce algorithms that areactually used within OS kernels toperform memory allocations efficientlythese algorithms are called power of twomethods and they work by maintaininginformation about allocated and freeblocks in a binary tree instead of alist at the top level memory is dividedinto large blocks called super blocks asprocesses request memory these superblocks are divided into smaller subblocks from which the memory isallocated sub blocks can be furtherdivided creating a hierarchy of blocksizes algorithms based on this methodare relatively fast and scaled amultiple parallel CPU cores thesealgorithms also reduce externalfragmentation by coalescing free blocksas I will discuss in a few moments someinternal fragmentation does still occurhowever in this diagram we can see threesuper blocks two of which are partiallyin use each of the first two superblocks has been divided into three subblocks and the third sub block of thefirst super block has been furtherdivided when a process requests memorythe kernel must perform a search of thetree to find an appropriately sizedblock to handle the request inperforming the search the colonel mightsubdivide an existing block into asmaller block to reduce the amount ofinternal fragmentation since this is asearch process a reasonably powerful CPUis required to make this operationefficient another improvement to memorymanagement is to utilize a buddy systemin the power of two strategy in thisallocation system to limits are chosento be powers of two the upper limit Uand the lower limit L the super blocksare the blocks of size U and theseblocks can be subdivided into blocks assmall as L bytes there are trade-offs inpicking the sizeto use 4l a smaller size produces lessinternal fragmentation since the blocksize more closely matches the smallestrequest sizes from the processes howevera smaller size for L means that thereare more total blocks to be trackedwhich increases the size of the binarytree using more ram to store the treeand increasing the search time on theother hand a larger size 4l reduces thesearch time and makes the tree smallerbut the amount of internal fragmentationincreases in addition to the block sizelimits the buddy system also uses atechnique called coalescence whenever aprocess frees a block the kernel checksto see if either neighboring blocks isfree also if one or more neighbors orbuddy blocks are free the block iscoalesced into a larger block reducingexternal fragmentation the coalescencealgorithm is efficient since the maximumnumber of coalescence operations thatmust be performed is equal to the base 2logarithm of U divided by L byproperties of logarithms this value isequivalent to the base to log of U minusthe base J log of L thus for example asystem with a maximum block size U of4096 bytes or 2 to the 12 and a minimumblock size of 512 bytes or 2 to the 9will require at most 3 coalescenceoperations to recreate the super blockreturning a single 512 byte block whoseneighboring 512 byte buddy is free willcause the two blocks to be coalescedinto a single thousand 24 byte block ifthe neighboring thousand 24 byte blockis free the 2024 byte blocks will becoalesced into a 2048 byte block then ifa buddy 2048 byte block is free thethird coalescence will produce the 4096bytes super block the power of twomethods are useful for allocating memoryto processes where some internalfragmentation is acceptable howeverwithin the kernel it is preferable tominimize both internal and extrafragmentation to avoid wasting spacethis conservative approach is neededsince the kernel is always mapped intomain memory an efficient solution forallocating kernel memory is to use aslab allocation algorithm in whichkernel memory is arranged into fixedsize slabs each slab is divided intoregion size for specific types of kernelobjects including file descriptorssemaphores process control structuresand other internal data structuresinitial layout of these slabs isperformed at compile timeat runtime several of each of thedifferent slab layouts are pre allocatedinto caches whenever the kernel requiresa new data structure space for the datastructure is simply taken from the slabcache if the slab cache starts to runout of a certain slab layout itautomatically provisions extrasgraphically slabs can be represented ina manner shown here in this example wehave two pre-allocated copies of thesame slab layout in which each slab canhold a single instance of each of fivedifferent kernel objects some wastedmemory does occur with this arrangementsince there might be a larger number ofone type of object than of another typeof object however this approach isgenerally more efficient in terms ofkernel space utilization slab allocationdoes require more CPU power than does aclassical method such as first fit thusin some embedded environments the slaballigator might be preferable if slaballocation is chosen over the slaballigator the Linux kernel has twochoices of slab alligator the firstchoice is the original slab alligatorwhich was the default alligator untilkernel version 2.6 point 23 thisalligator performed well on sharedmemory systems with few CPU cores butwasted considerable memory space whenused on extremely large shared memorysystems such as those found in graphicsrendering farms to reduce the spacewaste on large-scale SMA systemsChristophe Lemaitre at Silicon Graphicsdeveloped a new alligatorcalled slow which reduces the size ofdata structures needed to trackallocated and free objects the initialimplementation of the slub allocatorcontained a performance bug thataffected the results of certain memorybenchmarking tools initially christophbelieved the bug was of littleimportance since the conditions requiredto trigger it were fairly uncommon inpractice however ninis informedchristoph that either the problem wouldbe fixed or slug would be droppedentirely from the kernel in the end itwas determined that the bug was causedby adding partially used slabs beginningof a linked list instead of to the endof that list the fix was a change to oneline of code and the slub alligator hasbeen the default linux alligator sincetwo point six point 23in this lecture I will introduce pagingand related topics including logicaladdressing address translation and thetranslation lookaside bufferpaging provides a mechanism for sharingmemory among multiple user spaceprocesses at the same time thismechanism improves upon simpleralgorithms such as static partitioningand direct power of two methods byallocating fixed sized pages of memoryto processes the key to effective memoryutilization with paging is that eachprocess it's given its own logicalmemory space in other words each processhas its own view of memory with its ownaddress space the addresses that theprocess sees are called logicaladdresses these logical addresses aredivided into fixed sized pages eachprocess in the system receives its ownprivate set of pages with private memoryaddresses when a process accesses memoryusing one of its logical addresses theCPU translates the logical address intoa physical address physical addressesrefer to locations in system memoryfor performance reasons translation isdone in terms of memory frames or fixedsize regions of RAM the base frame sizeis normally four Kitty bytes althoughthis can vary by hardware device andmost Hardware can support multipledifferent frame sizes operating systemsnormally use logical page sizes thatcorrespond to supported Hardware framesizes again for kitty byte pages are atypical base size on x86 and x86 64systems the Linux kernel can supportso-called huge pages which can be aslarge as one gigabyte when using thenewest AMD and Intel CPUs the keyadvantage to paging is that iteliminates the issue of externalfragmentation since the CPU istranslating logical page based addressesinto physical frame based addressesanyway there is no need for the physicalframes to be contiguous as a result wecan store a data structure and processmemory using pages that are logicallycontiguous however when these logicalpages are mapped to physical frames theframes may be scattered throughout Ramnotice that the distinction between apage and a frame is a matter ofterminology a page refers to a block oflogical memory while a frame refers to ablock of physical memory for now pretendthat there is a one-to-onecorrespondence between logical pages andphysical frames will make things morecomplicated laterthe key to making page translationefficient is that the cpu containsspecial hardware called the memorymanagement unit or MMU which performsthe translation operations in thisdiagram the process accesses memoryusing logical addresses which aredivided into pages when requests aremade using these addresses the memorymanagement unit on the CPU translatesthe logical address into a correspondingphysical address the resulting physicaladdress will be to some point of aphysical memory frame note thatindividual memory addresses within pagesor frames still remain contiguous whichis important because the MMU translatespage numbers to frame numbers leavingthe offset to the memory location withinthe page unchanged as shown in thisdiagram we can divide a logical addressfrom a process into two components thepage number P and the offset D when theMMU is asked to perform a translation itconsults a data structure called a pagetable which provides a mapping betweenpage number and frame numbers using thisinformation the MMU constructs thephysical address by using thecorresponding frame number representedhere about the letter F in place of thepage number once again the offset to theparticular byte within the page or frameis left unchanged a particular byte inRAM is actually addressed using theframe number and offset into the framehowever to the process this memoryaccess appears to occur using a logicalmemory address which is conceptuallydivided into a page number and offsetthe offset component is not changed bythe MMU but the page numbers replaced bythe physical frame numbersin order to perform the translation frompage numbers to frame numbers the MMUmust consult the page table the pagetable is a data structure that is itselfstored in RAM in the kernel memory spacestoring the page table in RAM leads to amajor problem since every MMUtranslation would require a look upsince the lookup requires a memoryaccess each process memory request wouldactually require to physical memoryaccesses this situation is especiallytroublesome because a memory accessoccurs both upon accessing data and uponreading the next instruction to beexecuted without some additionalhardware to resolve this problem systemmemory performance would be effectivelycut in to greatly reducing the overallperformance of the systemthe solution for eliminating the doublememory access issue is to add acomponent to the CPU called thetranslation lookaside buffer or TLBwhich stores some page to frame mappingssome Tobsalso provide room for address spaceidentifiers which aid in implementingmemory protection the TLB is a piece ofassociative memory meaning that it canperform rapid parallel searchesresulting in constant time lookup forpage translation this memory isexceptionally fast meaning that it isalso quite expensive as a result TLBsizes are typically limited from 8 to4096 entriesthe addition of the TOB provides apotential shortcut for performingaddress translation instead ofimmediately searching the page table theMMU first searches the TLB if the pageto frame mapping can be found in the TLBthen it is used to perform thetranslation from page number P to framenumber F this situation is called theTLB hit a TLB miss occurs whenever thepage number is not present in the TLB inthis case the MMU must search the pagetable to locate the appropriate framenumber the CPU and operating systememployed various policies to determinewhen to store a page to frame mapping inthe TLB a simple policy would be to usea first-in first-out policy thatreplaces the earliest entry in the TLBwith the newest entry upon a TLB missother more complex and potentiallybetter policies also exists rules pagetables are data structures that storemappings between logical pages andprocess memory and physical frames inRAM these structures are used andmanaged in different ways on differentsystems often with assistance from thehardware at the end of this lecture Iwill discuss extended page tables whichare useful for allowing Hardware tosupport multiple simultaneous operatingsystems at oncerecall from the previous lecture thatthe page table stores mappings betweenage numbers and frame numbers whenever aTLB miss occurs the page table must besearched to find the appropriate mappingCPUs have differing levels of supportfor managing and searching the pagetables automatically on most modernsystems including x86 64 and arm CPUsthe page tables are managed and searchedby the CPU automatically upon TLB missthis search increases the memory accesstime but no fault or interrupt isgenerated as a result the CPU does nothave to perform a context switch among afew other cpus the MIPS architecturerequires the operating system to manageand search the page table whenever a TLBmiss occurs the CPU triggers a faultwhich is a type of interrupt the CPUmust make a context switch away fromwhatever task is currently beingexecuted in order to execute theinterrupt handler for the fault softwaremanaged page tables are becomingincreasingly uncommon even on embeddedsystems as the popular arm CPU supportsHardware management the MIPS CPU istypically used in lower end consumerdevices such as inexpensive ear eatersand the least expensive tabletsone approach to reducing the page tablesearch time whenever a TLB miss occursis to store the page table as a treeinstead of a list this technique ofhierarchical page tables divides thepage tables into pages each logicaladdress in process memory is dividedinto an outer page table a set ofoffsets into various levels of subtables and a final offset a specificbyte of memory to be accessed thistechnique can be generalized to anynumber of levels in the hierarchy but Iwill present here a simple system thatuses only two levels as illustrated inthis diagram the data structure isarranged so that an outer page tableprovides a mapping between outer pagenumbers and page table pages once theproper page table page is located thetranslation from page number to framenumber can be completed quickly sincethe page of the inner page table isrelatively smallthe address translation mechanism usedwith hierarchical page tables is morecomplex than that used with a simplelinear page table the logical address isdivided into additional components inthis example with two levels in the pagetable the logical address is dividedinto an outer page table entry number Twhich specifies the location in theouter page table in which to find theproper inner page table the nextcomponent of the address P is the offsetinto the inner page table at which themapping can be found in this example wehave a single page to frame mapping ineach inner page table entry so we canobtain the frame number from that entrya real system will be more complex andlikely will require a short linearsearch at some level in the page tableonce the frame number is determined Ramis accessed in exactly the same way asit is in simpler designs with the finaladdress joining a frame number andoffset into the physical address storingthe page table in a tree improves accessperformance however as the total amountof system ram continues to increase withnewer and newer generations of computersthe size of the page table alsoincreasesmoreover the address spaces on 64-bitarchitectures are much larger than theamount of memory that the MMU actuallysupports current 64-bit systems havetrue hardware address sizes in the rangeof 34 to 48 bits if we were to store amapping to handle every logical pagenumber in such a system the mappingwould be large and inefficient since theaddress space is sparse that is notevery 64 bit logical address can map toa physical location in RAM since thephysical addresses are at most 48 bitsas a result many of the possible 64-bitaddresses are unused a solution to thisproblem which both reduces page tablestorage size and increases search speedis to use a hash table or dictionarystructure to store the outer page tablesince several addresses may hashthe same value each entry in the hashtable is an inner linear page tablewhich allows the hash collisions to beresolved through chaining translating alogical address to a physical addresswith a hashed page table begins byhashing the page number P hashing isaccomplished using a hash function whichmay be implemented in hardware for highperformance the hash value returned bythe function gives the location in thehash table where the inner page tablemay be found a linear search of theinner page table is performed to locatethe frame number once the frame number Fis obtained it is joined with the offsetD to give the hardware address somearchitectures notably PowerPC and IntelItanium store their page tablesbackwards that is the system stores adata structure with one entry per frameand the entry stores the correspondingpage number along with the process ID ofthe process owning the page thisapproach called an inverted page tableis efficient in terms of page tablestorage size however inverted pagetables are inefficient in terms ofperformance and these structures are notused on a majority of systemson newer x86 64 systems withvirtualization extensions hardwaresupport exists for extended page tablesor EPT AMD and Intel each brand thistechnique with a different nameAMD uses the term rapid virtualizationindexing for our VI on newer CPUs theyused to call this technique nested pagetables or NPT Intel uses the extendedpage tables terminology EPT adds a levelof paging to the system at the outerlevel each virtual machine or guestrunning on the CPU sees its own set ofmemory frames isolated from anindependent of the actual Hardware theCPU translates page numbers to framenumbers first by translating the pagenumber to a guest frame number the guestframe number is then translated to ahost frame number which is the physicalframe number EPT technology is importantfor virtual machine performance since itallows each guest to manage its ownmemory efficiently moreover guests canaccess memory without having to switchthe CPU in a hypervisor mode which canbe an expensive operation the downsidethe logical address translation withextended page tables is that it becomesconceptually more difficult tounderstand as illustrated by thecomplexity of this diagram a processrunning in a guest operating systemmakes a memory request just as it wouldif no virtualization were present thismemory request is divided into a pagenumber and an offset as usual the CPUthen performs translation of this pagenumber P to a frame number F also asusually furthermore as far as the guestoperating system is concerned thetranslation is complete the guest OSsees the memory region provided by thehost system as if that memory werephysical memory in other words the guestOS has no idea that is running in avirtual machine to the guest OS thevirtual machine looks just like aphysical system however in reality theguests physical memory is actually anillusion provided by theto make the solution work the host musttranslate the frame number F and guestsmemory to an actual physical framenumber G this translation is performedby the CPU without any context or modeswitches using the EPT table once thistranslation is performed the physicalmemory address is generated by combiningG and D where D is the originalunchanged offset into the page it isimportant to note that this entireprocess is performed by the CPU withoutswitching to the host OS or hypervisorin this lecture I will discuss memoryprotection including segmentation andpermission bits on page table entriesremember the operating systems performtwo functions abstraction andarbitration mechanisms for accessingmemory provide abstractions of theunderlying memory hardware howeveroperating systems must also arbitrateaccess Aram by ensuring that one processcannot access memory that does notbelong to it without this arbitration aprocess could change memory belonging toanother process or worse it could crashthe system by changing memory thatbelongs to the kernel on systems thatutilize simple memory management such aspower of two methods memory accessprotections are provided by a mechanismcalled segmentation on the majority ofmodern systems which employ pagingmemory protection is implemented as partof the paging system and memory accesspermissions are stored in the page tableon any system process memory is dividedinto logical pieces or segments atcompile time these segments include thetext segment a region for globalvariables a stack region for automaticvariables and a heap for dynamicallyallocated data structures accesspermissions apply to each segment inparticular the text segment is set to beread only outside a single process theremust be a mechanism to track whichsegments of memory belong to whichprocesses when a process is executingits segments or marked valid so that itcan access the corresponding memorylocations segments of memory belongingto other processes are marked invalidand any attempt to access those segmentsresults in a fault or interrupt call thesegmentation faulttypically a segmentation fault causesthe process to be terminated segmentmemory permissions are implemented onnon paging systems using a segment tablethe segment table has permission bitsthat can be applied to each region ofmemory when memory is accessed usingsegmentation the segment table must beconsulted to determine whether or notthe access is legalin this example a process requestsaccess to memory using a logical addresssince we do not have paging with thesystem this logical address is nottranslated by a page table mechanismhowever this logical address is dividedinto a segment address and an offsetinto the segment in a manner similar topage translation the MMU checks thesegment table to determine if aparticular memory access is valid inthis example the segment table stores upto four permissions and up to three bitsa valid invalid bit a read/write bit andan execute bit in practice most systemsthat support segmentation without pagingnormally only use two bits valid andvalid and read right if the processtries to read from a segment that ismarked valid the memory access ispermitted and occurs normally the samething happens if a process tries towrite to a memory location that ismarked both valid and writable howeverif a process tries to write to a segmentmarked read-only or if a process triesto access an invalid segment the CPUtriggers a segmentation fault and theprocess is terminated for some invalidaccesses on a unix-like system thissegmentation fault may be reported as abus herewith paging systems which comprise themajority of modern systems includingmobile devices memory protection isaccomplished by adding permission bitsto the page table entries in generalpage table entries will have a validinvalid bit and a read/write bit thevalid invalid bit is used in the sameway as it is for segmentation pages thata process is allowed to access our markvalid other pages and any non-existentpages are marked invalid if a processattempts to access an invalid page a CPUfault is raised which functions like aninterrupt to trap into the kernel alinux kernel will send a 6 8 V or sigbus signal to the process depending onthe location memory the process tried toaccess in practice the signal isnormally not caught in the processterminates for historical reasons thisevent is called a segmentation fault orseg fault for shortthe read/write bit used to mark the textsegment of a process can be used toallow pages of memory to be sharedbetween processes pages that arere-entrant or read-only can be accessedby multiple instances of multipleprograms simultaneously this capabilityis useful on modern systems sincemultiple instances of programs aretypically run at the same time in thecase of a web browser for example it isonly necessary to load one copy of thebrowser program code into memory severalcopies of the browser can be run asseveral different processes sharing theprogram code and thus saving memory theopen source chromium browser and itsGoogle Chrome derivative allow each tabto run in a separate process sharedmemory pages allow the code for thebrowser any extensions and any pluginsto be loaded only oncesaving memorythis diagram illustrates how twoprocesses can share a single page andRAM each process sees a handful of validframes one of which is marked read-onlyif this memory frame contains code orother information that can be sharedbetween the processes then the two framenumbers will be identical with in theseparate processes each process may usea different page number to representthis memory location however since eachprocess has its own independent logicalview of memory incidentally this diagramis a conceptual diagram only it does notdirectly map to any particular datastructure in the operating systeminstead the two tables illustrate howeach process might see page donewer AMD and Intel CPUs support anadditional permission bit for settingexecute permissions this bit called theno execute or NX bit is actually aninverted permission it is set to onewhenever execution of data found on amemory page is forbidden originally theNX bit was implemented by AMD on its64-bit capable processors using themarketing name of enhanced virusprotection intel followed suit and addedthis mechanism as the execute disabledor XD bit the concept behind the bit wasto provide a mechanism that could beused to prevent execution of nativemachine instructions from memory spaceused for regular data although theprimary beneficiary of this feature wasa certain virus prone system that is noteven Experion the linux kernel doessupport the NX bit as a guard againstbuffer overflow and similar exploits inthe example presented in thehypothetical page table here only thepage with hex numbers 0 for a4 allowscode execution in the event of anexploit attempts a malicious applicationcould try to load code in another pageperhaps 0 for a1 however since the NXbit is set on that page any attempt toexecute the code loaded by the exploitwill trigger CPU fault and the processwill be terminated this mechanismincreases the security of the systemagainst certain types of attacksin this lecture I will begin discussingvirtual memory due to the complexity ofthe virtual memory subsystem the secondpart of this introduction will be givenas a second lecture we have previouslyseen that each processing system can begiven its own logical memory space thisarrangement allows logical pages to bemapped to physical frames without theneed for physical frames to becontiguous eliminating externalfragmentation and increasing the degreeof multi-programming the de system cansupport we can further increase thedegree of multi programming in thesystem by recognizing that processes donot actually use all the memory in theirlogical address spaces at any given timeparts of the program code includingerror handlers and infrequently calledfunctions are not utilized oftenfurthermore arrays and other datastructures are often oversized and usedin sections instead of all at once if wecan swap unused pages out of memory andonto a backing store such as a hard diskwe can fit more processes into memory atonce increasing our degree ofmultiprogramming furthermore we can giveeach process its own large logicalmemory space which can in fact be largerthan the amount of physical RAM on thesystem when we add a backing store thegeneral address translation processremains the same processes accessmemories and logical addresses which aretranslated into physical addresses bythe MMU the page table is still utilizedto store the page to frame mappingshowever we do add some complexity inthat a frame could be swapped out todisk at the time when it is needed theCPU must provide a mechanism to detectthe situation and generate a fault thatthe operating system can handle to bringthe required page back into physicalmemorythe process of moving pages or frames ofmemory back and forth between RAM andthe backing store is known either asswapping or as paging historically theterm swapping referred to the movementof entire logical address spaces orentire processes between RAM and diskmoving single pages or frames of databetween RAM and the disk was calledpaging in modern practice both terms areused interchangeably and the Linuxkernel component that performs pagemovements is called the swapper a singlemovement of a single page frame into orout of physical memory is called a pageswap historically Linux machines used adedicated hard disk partition to storethe pages that were swapped out to diskmodern versions of Linux are just asefficient using a swap file which is aregular file stored alongside other datain the file system it should be notedthat swapping is an optional feature andit is possible and even quite common torun systems without any backing store orswapping capability most embedded Linuxsystems such as Android devices do notuse a backing store if memory cannot beallocated to a process on such a systemthe process typically crashesnow Paige spots are implemented by theoperating system some assistance fromhardware is required to determine when apage swap needs to be performed whentranslating a page number to a framenumber the MMU checks to see if thecorresponding frame is resident orloaded in RAM if the frame is presentthe memory access proceeds as normal ifthe frame is not present in RAM howeverthe MMU generates a page fault which isa CPU exception that is similar inconcept to an interrupt a specific pagefault handling routine is registeredwith the system either as part of theinterrupt vector table or using aseparate structure for fault handlers apage fault causes this routine known asthe swapper in linux to be invoked it isthen the responsibility of the swapperto locate the missing page on thebacking store and load it into rampossibly moving some other page frame tothe backing store in the process theaddress translation process gains a fewsteps when paging is utilized a processmakes a memory request using a logicaladdress in its private address space asusual the MMU first checks thetranslation lookaside buffer todetermine if the page to frame mappingis present in the case of a TLB miss theMMU must consult the page table to findthe mapping once the mapping from pagenumber to frame number is known the MMUmust next verify that the page isactually loaded in physical RAM if thecorresponding frame is available in RAMthe memory access proceeds as normalhowever if the corresponding frame isnot in memory the MMU generates a pagefault which is essentially a type ofinterrupt if generated the page faultcauses the operating system to switchcontext to the page fault handlingroutine which retrieves thecorresponding memory contents from thebacking store once this process iscomplete the OS changes the CPU contextback to the original processand the memory access proceeds as normalin order for the MMU to be able todetect situations in which a requestedmemory frame is not physically presentin RAM an extra bit must be added to thepage table this bit is set to 1 wheneverthe contents of a logical page arepresent in a memory frame if the presentbit is 0 the page has been swapped outto the backing store for efficiencyreasons the TLB entry corresponding to arow in the page table must also storethe present bit you might have noticedthat the terminology between page andframe is starting to become a bit blurryhere in general we refer to pages ofmemory being swapped out to disk eventhough the swap operation is actuallymoving physical memory frame contentsthis fuzzy terminology is a result ofhistorical evolution of the virtualmemory subsystem now I'd like to take amoment to discuss the nature of backingstores as technology is changing in thisarea historically the backing store wasa mechanical hard disk drive and anumber of design decisions in thevirtual memory subsystem still use thisassumption however many systems nowespecially embedded systems have onlysolid-state storage since each block anda solid-state drive can be erased andwritten only a finite number of timesthere is some question as to whether itis a good idea to use an SSD as abacking store for virtual memory manyembedded devices do not use paging forthis reason another issue with thebacking store is that it is subject toattack via forensic disk analysismethods in the event the device is lostor stolen sensitive information such ascached passwords and other credentialsmight have been swapped out to thebacking store and these pieces ofinformation could be recovered onesolution to this problem which isavailable as an easy to enable option inMac OS 10is to encrypt the contents of virtualmemory the downside to this approach isthe addition of CPU overhead on top ofthe generally slow nature of the backingstore hardware another approach toavoiding the issues of right limits andpost-mortem forensic recovery ofsensitive memory data is to use theLinux compressed caching or comp cachemechanism as a backing store with thisapproach a section of RAM is reservedahead of time to create a compressed ramdisk or z ram disk when a page isswapped out to the C Ram disk it iscompressed on-the-fly to fit into asmaller amount of memory whenever a pageneeds to be swapped in from the backingstore the page is read from the 0m diskand decompressedalthough the compression anddecompression steps do result in CPUoverhead the comp cache system is stillgenerally faster than using a disk orSSD as a backing store furthermore compcache is as secure as ram againstforensic analysis particularly againstrecovering sensitive information from asystem that has been powered off for aperiod of timein this lecture I will continue thediscussion of virtual memory bydiscussing paging performance andintroducing demand paging copy-on-writememory mapped files and shared librariesswapping pages to and from a backingstore is a relatively slow operationcompared to a direct access to ram dueto the fact that most backing storeHardware is several orders of magnitudeslower than Ram whenever a page faultoccurs the memory access that triggersthe page fault will require more timethan a non faulting memory access aslong as the number of pages swapped outto the backing store is relatively smallcompared to the total number of pages ofmemory in the system the performancecost of page swaps is amortized over allmemory accesses as a result the averagememory access time is increased by onlya small amount relative to a system thatdoes not swap out pages however if thefraction of memory accesses resulting inpage faults becomes too high the systembegins swapping or thrashing its memoryon most or all memory accesses thissituation typically occurs when memorybecomes oversubscribed too due to aprogram bug and the result is a systemthat is painfully slow to respond touser input in some cases on some systemsthe OS may need to be rebooted torecover from a swapping situationwith any paging system it is necessaryto decide on a virtual memory fetchpolicy which determines how data areloaded into memory pages for the firsttime typically when a program is starteda lazy implementation of page fetchingis to use demand paging which loads apage from the backing store into RAMonly when it is actually required thisapproach improves the overallresponsiveness of the system andincreases the degree of multiprogrammingat the expense of reducing the initialperformance of newly started processesthe main alternative to demand paging isprefetching which loads some pages intomemory before they are actually neededprefetching may waste some memory byloading data that will not be usedhowever it does improve the startupperformance of many softwareapplications for this reason prefetchingis a fairly common feature of desktopoperating systemswhen memory is limited or electricalpower is severely limited a pure demandpaging approach to fetching may beappropriatepure demand paging does not prefetch anypages including the text segments ofnewly started programs when a newprogram starts a page fault occurs thefirst instruction and the first page ofthe program code is loaded into memorypure demand paging has the greatestpotential to increase the degree ofmultiprogramming particularly insituations where physical RAM isextremely limited in addition the lackof prefetching can save CPU and memoryoperations thus providing up small powersavings when operating from battery assuch pure demand paging could be usefulon smaller embedded systems especiallymonitoring devices and other systemswithout direct human interaction whilethe fetching policy has a high impact onnewly started programs a copy-on-writeapproach improves performance whenever aprocess makes a copy of itself onunix-like systems new processes arecreated when a running process clonesitself with the fork system call cloningall memory at fork time could be a slowoperation since a process might be usinga large number of pages copy-on-writeaddresses this performance issue byhaving the Cologne initially share theoriginal processes memory pages theseshared pages are marked read-onlycausing the MMU default if eitherprocess tries to write to them theoperating system handles this type offault by copying the page and turningoff the read-only bits on both the copyand the original pagethis diagram illustrates thecopy-on-write process in the top half ofthe diagram the original process forks achild process which initially shares theoriginal parents pages the childproceeds to modify page three in thebottom half of the diagram when thismodification is attempted the MMU raisesa fault that traps into the operatingsystem the operating system makes a copyof the corresponding memory frame givesthe copy to the child process andremoves the read-only setting on boththe original and clone page the child'spage is then updated with the modifiedvalue from the memory write and normalprocess execution resumesin addition to increasing the degree ofmultiprogramming by enabling pages ofmemory to be swapped out to a backingstore the virtual memory subsystem canalso be used to improve IO performancefor processes on the system whenprograms request IO from persistentstorage devices these requests generallytake a significant amount of time tofulfill due to the relatively slow speedof the persistent storage device sincemany processes perform frequent readsand writes of small pieces of data theperformance overheads caused by waitingfor device IO to complete can becomesubstantial the virtual memory subsystemcan be made to reduce this overhead bymemory mapping files page sized piecesof a file are loaded into memory wherethey can be read and written efficientlythese pages are periodically writtenback to the persistent storage device asis the case with paging in general thereis no requirement that memory mappedfiles be mapped into contiguous regionsof physical memory logical addressing isused to present an ordered contiguouslogical view of the file to the processhowever the file may be mapped out oforder and non contiguous memory framesalthough the file will be put back inorder when you distort disk the filestill might be non contiguous if thefile system is fragmented to reduce thetotal amount of memory required by aprogram and to make software developmenteasier certain programming routines areimplemented and shared libraries whichcan be used by multiple programs on thesystem when these libraries are used bya program they must be made available toput the program when it runs in thesimple case which defeats the memorysaving potential of shared libraries thecompiler may statically link or copy thelibrary into the program executable atcompile time a more efficient approachis for the loader to link the program tothe shared library at runtime on diskprecompiled shared libraries are storedin binary form as shared objects or dotiso files onthese libraries are called dynamic linklibraries or DLLs on Windows runtimedynamic linking of these sharedlibraries relies on read only sharedpages that can be used by multipleprograms at the same timeshared libraries are made available toprocesses by mapping them into themiddle of the logical address spaces ofeach process between the stack and theheat these shared objects limit themaximum size to which the stack whereheat can grow before running out ofspace a situation in which sharedlibrary mapping becomes a problem iswhen virtual machines are implemented on32-bit hosts the hypervisor process onthese hosts has a maximum logicaladdress space of 4 gigabytes when thehypervisor tries to allocate a largecontiguous block of memory to provideRam to the guest system the allocationcould run into the shared librariesresulting in a failure I have seen thistype of failure occur on a 32-bit hostwhen trying to allocate a continuousblock of just over 1.2 gigabytes on aLinux system with 4 gigabytes ofphysical RAM it is for this reason thata 64-bit operating system is desirableeven for physical systems only 2 to 4gigabytes of RAMHeckscher I will discuss pagereplacement as it is used in the virtualmemory subsystem I will discuss globaland local page replacement page tableentries that support page replacementand a number of classical pagereplacement algorithms whenever there isa demand for memory that is greater thanthe actual amount of physical RAMinstalled on the system the operatingsystem must determine which pages willbe kept in memory and which pages willbe swapped out to disk when memory framecontents are swapped out to disk theoperating system needs to find a page ofmemory that is not currently in usefurthermore in an ideal case theoperating system should also pick a pagethat will not be used for some timeso as to reduce the total number of pageswaps in order for the page swapper tooperate some additional data must bekept about each page including whetheror not the page has been referenced andwhether or not the page has been alteredsince it was last swapped into RAMdecisions regarding page swaps can bemade globally or locally with globalreplacement any page in the system is apotential candidate to be swapped out infavor of another page while simpler toimplement global page replacement doesallow processes to steal memory framesfrom each other on the other hand localreplacement policies allocate a limitednumber of frames to each process when aprocess exceeds its frame allocationonly frames belonging to that processare selected for replacementimplementing a local page replacementalgorithm is more complex than it seemson the surface largely due to Bella D'sanomaly allocating more frames to aprocess does not necessarily reduce thenumber of page faults that occur as aresult of that process in fact with somereplacement algorithms increasing thenumber of available frames actuallyincreases the number of page faults thatoccur at the opposite extreme allocationof too few memory frames to a processalso increases theof page faults without enough physicalmemory processes we'll spend more timepage faulting or swapping than they willspend executing the goal with a localreplacement algorithm is to find anoptimal working set for each processthis working set is the minimum numberof frames that a process actuallyrequires in order to execute to somedesired level of efficiency regardlessof whether global or local replacementpolicies are chosen the operating systemneeds a few pieces of information toimplement page swapping correctly firstthe operating system needs to knowwhether or not a page that is currentlyin memory has been referenced by aprocess pages that are loaded but unusedmight be more ideal candidates to beswapped out to the backing store thesecond piece of information that needsto be stored in the page table is thedirty bit this bit is set to 1 whenevera process writes to a page which letsthe operating system know that the copyof the memory frame contents on thebacking store needs to be updatedwhenever the page is swapped out keep inmind that on systems with hardwaremanaged page tables such as the x86 andx86 64 platforms the MMU updates thesebits automaticallywhenever a page fault occurs theoperating system must locate the desiredpage on the backing store then it mustfind a free frame and ram into which thepage can be loaded if no memory framesare free the operating system mustselect a victim frame to be swapped outto the backing store the algorithm thatis around to determine which frame willbe the victim is called a pagereplacement algorithm page replacementalgorithms ideally should minimize thetotal number of page faults in therunning system in order to maximizesystem performance let's take a look atseveral classic page replacementalgorithms the first classical pagereplacement algorithm we will consideris the random algorithm whenever a pageswap is required this algorithm simplypicks a victim frame at random inpractice this random selection oftenpicks a page that will be needed in thenear future leading to another pagefault in a short time period as such itis not effective for minimizing pagefaults another ineffective algorithm isto select the oldest page or the pagethat has been in memory for the longestperiod of time unfortunately this pagecould be frequently accessed so if ithas swapped out another page fault couldbe triggered in a short period of timeto bring it back into memory somewhatcounter-intuitively selecting the framethat has been accessed the leastfrequently is also ineffective a pagethat is used relatively infrequentlymight still be used regularly whichwould lead to another page fault tobring this frame back into RAM the mostfrequently used algorithm pickswhichever frame is being used the mostand selects that frame to be swapped outto the backing store this is acompletely stupid idea since this pageis likely to be accessed again shortlyafter it is swapped out a good algorithmfor choosing victim frames is the leastrecently used or LRU algorithm thisalgorithm selects the victim frame thathas not been accessed for the longestperiod of timeunfortunately with current hardwarethere is no good way to track the lastmemory access time tracking every accessand software would be a terrible ideasince such a scheme would require aninterrupt on every memory accessthus it is impractical to implement LRUdirectly most implemented pagereplacement algorithms areapproximations of LRU howevertheoretically the optimal algorithm oropt is the best staged replacementalgorithm to use with this algorithm theoperating system picks a frame that willnot be accessed for the longest periodof time as the victim delaying a futurepage fault related to the correspondingpage for as long as possible amathematical proof exists showing thatopt is the best possible pagereplacement algorithmunfortunately opt is also impossible toimplement since it must be able topredict all memory accesses ahead oftime as such we are left with LRUapproximation algorithms such as the notused recently or in you our algorithm nuour tracks frame accesses using acombination of the reference bit dirtybit and/or an age counter this algorithmproduces reasonable performance andactual implementationsin this lecture which is presented intwo parts I will begin discussingprocesses I will introduce the processmodel discuss the type of informationassociated with the process give anoverview of process state and introducethe concept of process forking as isusually the case my presentation isfocused on unix-like systems let's beginby defining what a process is a processis an instance of a computer program inexecution when we ask computer system torun a program the code for that programis loaded from disk into memory andexecuted as a process in the system onsome platforms processes might be calledjobs or tasks on a modern system aprocess consists of one or more threadsof execution in other words a processcan execute one instruction at a time orit can execute several instructions atthe same time on the CPU each process onthe system receives its own privateallocation of resources each processalso has access to its own data and theoperating system maintain statisticsabout each process in order to makeeffective scheduling decisions in memorya process is divided into segmentsprogram code and other read-only dataare placed into the text segment globalvariables in a program have their owndata segment that allows both readingand writing automatic variables forlocal variables and functions areallocated at compile time and placed onthe stack data structures explicitlyallocated at runtime are placed on theheat as memory is used by a process thestack and the heap grow toward eachother if a process makes use of sharedlibraries these libraries are mappedinto process memory between the stackand the heap in order to track processescorrectly and allow multiple processesto share the same system the operatingsystem must track some information thatis associatewith each process this informationincludes the memory that the process isusing as well as the current location inthe process code that is executing knownas the process program counter theoperating system must also track otherresources in use by a process includingwhich files are currently open and anynetwork connections the process is usingin addition to the information generatedby the process itself the operatingsystem must keep scheduling informationand statistics about each process thisinformation includes a unique identifieror process ID it can be used todistinguish processes from each other inorder to arbitrate access to systemresources the operating system must alsostore information about the owner of aprocess so that permissions can beenforced correctly to facilitatescheduling decisions the operatingsystem collects various statistics aboutprocess execution such as the amount ofCPU time consumed and the amount ofmemory used during the lifetime of aprocess the process moves betweenseveral states when a process is firstcreated it is initially in the new stateonce creation is complete and theprocess is ready to run it transitionsto the ready state where it waits to beassigned with CPU core when thescheduler selects a ready process to runthat process is moved to the runningstate and has given CPU resources duringexecution a process might requestexternal resources such as disk i/osince these resources take time toprovide the process is moved out of therunning state and into the waiting stateso that the CPU core can be given toanother process finally when a processis finished it is placed in theterminated state so that the operatingsystem can perform cleanup tasks beforedestroying the process instancecompletely in this diagram we can seehow processes may transition betweenstates at creation time a process isplaced into the new state while theoperating system allocates initialmemory and other resourcesonce creation is complete the process issubmitted to the system and placed inthe ready state whenever a CPU core isavailable to execute a process it isdispatched to the running state where itexecutes execution of a process can beinterrupted for a variety of reasons ifa hardware interrupt occurs theoperating system might have to move theprocess off the CPU core in order toservice the interrupt returning theprocess to the ready state or theprocess might make an i/o request inwhich case the process is moved to thewaiting state while the system waits onthe relatively slow IO device to providethe requested data once IO is completethe process is moved back to the readystate so that it can be scheduled to runagain whenever a CPU core becomes freeupon exiting the process is moved to theterminated State for cleanup themechanism for process creation isplatform dependence I will beintroducing process creation on aunix-like platform such as Linux or MacOS 10 on these platforms all processesdescend from a single parent processthat is created by the kernel at boottime on Linux this first process iscalled a nit which is the common UNIXname for the first created process Appledecided to call this process launch D onMac OS 10 by convention the initialprocess always has a process ID of 1 theinitial process must also remain alivefor the entire time the system is up andrunning otherwise the whole computercrashes with the kernel panic the anitor launch D process is started by thekernel at boot time every other processon the system is a child of this specialprocess child processes on UNIX arecreated by forking a parent process theparent process makes a system call namedfork which makes a copy of the parentprocess this copy which is initially aclone of the parent is called the childprocessit is up to the parent process todetermine what if any resources it willshare with the child process by defaultthe parent process shares any open filedescriptors network connections andother resources apart from the CPU andmemory with the child however theprogram code can close or reassignresources in the child making the childcompletely independent of the parentonce the child process is forked thechild becomes an independent instance ofthe program which can be scheduled torun in parallel with the parent howeverthe parent process can be coded to waiton the child process to finish executingbefore the parent proceeds furthermorethe parent process is able to terminatethe child process at any time on somesystems termination of the parentprocess will terminate all childprocesses automatically on other systemschild processes become orphan processeswhenever the parent terminates unix-likesystems including Linux have the abilityto support both models any processincluding a child process has theability to load a different program intoits memory space this loading isaccomplished via the exec system callwhich replaces the entire program codeof the process with the program codefrom a different program new programs onunix-like systems are started by forkingan existing program then exacting thenew program in the child process whenmultiple processes are executing on thesame system they have the ability toexecute independently or shareinformation between themselves anindependent process is completelyseparate from other processes in thesystem its execution is not affected byother processes and it cannot affectother processes as long as the operatingsystem is designed and implementedcorrectly alternatively processes couldshare information between themselves andthereby affect each other when thisoccurs we say that the processes arecooperating cooperating processes may beused for a variety of reasons includinginformationimplementing high-performance parallelcomputation increasing the modularity ofa program implementation or simply forconvenience when implementing certaindesigns in part 2 of this lecture I willprovide additional detail about processforking and executing new programsin this lecture I will continue thediscussion of processes by introducingthe fork exec and weight system callsI will provide examples of using thesesystem calls in both C and Pythonprocesses are created on unix-likesystems such as Linux by using the forksystem call this call is available as ac function by including the eunice TDHheader file in python access to fork isprovided by importing the OS module inthis c example i fork a child processthat simply prints a message my codebegins by importing the stdio.h and yunaSTD h header files for the printf andfork functions respectively inside mymain function i declare a variable namedpig of integer type i then print amessage stating that I have not yetforked the parent process I call thefork function without arguments and Iassign its return value to the Pittvariable upon completion of the forkfunction I will have two copies of myprogram running at the same time in thefirst copy where I called fork the valueof the pig variable will be set to theprocess ID of the child process in mychild process the value of the pigvariable will be set to zero my childprocess prints a message stating that itis the child my parent process prints amessage stating that it is the parentboth messages will be printed since thevalue of the pit' variable will be zeroonly in the child process however theorder in which the two messages areprinted is not guaranteed and may varybetween program runs the equivalentPython code is a bit shorter but looksrather similar owing to the fact thatpython is exposing the underlying clibrary to us to use the fork function Ineed to import the OS module I then setthe pit veryby calling OS dot fork and a mannersimilar to the corresponding C code uponreceiving this call the entire Pythoninterpreter process will be cloned thepit variable inside my script in theparent interpreter process will containthe process ID of the child Pythoninterpreter process in the childinterpreter the pit variable in myPython script will have the value 0since the value of pit is 0 in the childprocess the child message will beprinted in the parent process where thevalue of pit is not 0 the parent messagewill be printed both messages willappear in the output of the script butthe order of the messages is notguaranteed and may change while wesometimes fork processes in order tocreate parallel programs a more commonuse of forking is to start anotherprogram we can replace a currentlyrunning process with another program byusing the exec system call which is madeavailable through a variety of functionsin C and Python one important thing toremember about the exec system call isthat it completely replaces thecurrently running program with the newprogram a common error is to try to putprogram code after a call to exec in anattempt to perform some other operationafter the external program is finishedhowever any such code placed after thecall to exec will never execute sincethat code gets replaced with the rest ofthe original program now in practice theexec system call is implemented as acollection of functions not as a singlefunction these functions differ andwhether or not they take arguments as afixed set of parameters or as an arraythey also vary by allowing the operatingsystem to search the system path to findthe new program versus requiring theabsolute path to the new program to beprovided furthermore some of the execfunctions allow environment variables tobe set for the new programregardless of the version of exec thatis chosen a standard convention onunix-like systems is that the firstargument to a newly loaded program isthe name of the program itself exactlyas the user entered it this conventionallows a single program to be known inthe system by a variety of namespossibly allowing it to implementdifferent behaviors depending upon thename by which it was invokedas I mentioned there are quite a fewvariations in exec functions in the Cprogramming language versions with alowercase L in the name take a fixednumber of arguments where the finalargument is always a null pointer ofcharacter type alternatively versions ofthe lowercase V in the name take avector or array of arguments if alowercase P appears in the name theoperating system will search the systempath to find the new program versions ofthe lowercase e allow environmentvariables to be modified thecorresponding Python versions of execavailable in the OS module follow thesame conventions with respect to thelettering however it is not necessary topass a null pointer at the end of the Lversions now let's take a look at asimple C application that Forks a childthat execs the /bin slashecho program installed on the systemnothing has changed about the forkoperation the pit value returned to thechild is always zero while the valuereturned to the parent is always nonzero however in the child we are nowusing exec L to load the /bin slash echoprogram notice that slash bin slash echois both the name of the program and thefirst argument to the program themessage to be printed hellofollows finally we must terminate theparameter list with a null pointer whichneeds to be cast to a character pointertype when the child calls exec out it'scopy of the program code is completelyreplaced by the code for slash bin slashecho thus the child never prints thefinal message in the programthe message is thus printed only once bythe parentthe Python version of this code isshorter but otherwise similar there isno need nor is there any practical wayto pass a null pointer to OS exec l atthe end of the parameter list as is thecase with the C version of the code onlythe parent prints the message at thebottom the copy of the Pythoninterpreter and script that was createdby fork is completely replaced by thecalled OSX echo with the code for theslash bin slash echo program thus thechild is no longer executing the Pythoninterpreter and the final line of codeis never run in the child we have seenthat we can execute another programusing exec however what if we would liketo take some other action after theother program executes in that case wecan use a version of the wait systemcall in the parent to wait for the childto terminate before moving to examplecode for wait take a moment to note thatin some cases the parent process mayterminate before the child process on aLinux system termination of the parentbefore the child creates an orphan childprocess some programs are intentionallydesigned to create orphan processesthese programs are engineered to run inthe background performing various systemservices and these are known as demonsor service processes by convention theword daemon uses its archaic spellinghere with an AE in place of the e in themodern spelling however thepronunciation is the same daemon isincorrecteven though many people mispronounce itnow the C code illustrating the act ofwaiting on a child process to terminatebarely fits on one slide in order to getaccess to the weight pit function onLinux I need to include the sisslash wait H header file in this exampleI fork a child process that sleeps forfive seconds before exitingin my parent code I announced that theparent is waiting then I call wheat pedto wait for the child to terminate inthis simple example I need to pass threearguments to wait ped the process ID ofthe child which fork returned to theparent above followed by a null pointerfollowed by the number 0 the weight paidfunction blocks or stops and waits untilthe child process terminates oncetermination occurs the parent printsanother message the Python version ofthis example is considerably shorter butonce again it uses essentially the samecalls in addition to the OS module Ineed to import the time module to getaccess to the sleep function the majordifference in this code from thecorresponding C code is that I do notpass a null pointer is the secondargument to OS suite bid instead I skipthat argument and simply pass a 0insteaddiscuss process management I willdiscuss process contexts contextswitches and process scheduling eachprocess running on a system has acertain amount of information associatedwith it a minimal set of stateinformation that allows a process to bestopped and later restarted is calledprocess context process context includesthe current contents of CPU registersthe current program counter value forthe process in the contents of RAM theprocess is using switching betweenprocesses on a system is often called acontext switchalthough processed switch is a moreprecise term the operating system canperform a context switch from a processinto a section of the kernel and thenback to the same process withoutactually performing a process switchcontext switches require at least onemode switch to perform since the CPUmust enter supervisor mode enter thekernel relatively speaking contextswitches are a fairly expensiveoperation and frequent context switchingwill reduce system performancewhenever the operating system needs toswitch from one process to another itmust first make a context switch intothe kernel the kernel then saves thestate of the previously running processand restores the state of the process towhich it is switching a second contextswitch is then required to start thenewly restored process on UNIX systemsprocesses are created via the forksystem call following creation the CPUscheduler determines when and where theprocess will be run once the CPU core isselected the dispatcher starts theprocess whenever a process makes an i/orequest a system call into the kernel ismade which removes the process fromexecution while waiting for the i/o tocomplete the process yields any CPUcores it is currently using so thatanother process can use those resourceswhile the first process waits on therelatively slow i/o device operationsthat cause the process to yield the CPUcores and wait for some external eventto occur are called blocking operationsreading data from a file is an exampleof such an operation the process callsthe read function and the read functiondoes not return until it is read somedata the process may have been moved offthe CPU and then restored and returnedto the CPU while waiting for the readfunction to return some processes areCPU bound which means they perform largecomputations with few i/o requests orother blocking operations in order toenable the system to service otherprocesses and effectively implementmulti programming the CPU scheduler mustpreempt these types of processespreemption involuntarily saves theprocess state removes the process fromexecution and allows another process torun interrupts from hardware devices mayalso preempt running processes in favorof kernel interrupt handlers withoutthis type of preemption the system wouldappear to be unresponsive to user inputnow in order to store process stateinformation the operating system mustmaintain data structures about eachprocess these structures are calledprocess control blocks or PCBs PCBscontain fields where information about aprocess can be saved whenever a processis moved off the CPU once again thisinformation includes the contents of CPUregisters and current program countervalue the operating system storesprocess control blocks in linked liststructures within kernel memory spacehere is a process control block ingreater detail some of the informationfields include process state the uniqueID for the process the process programcounter CPU register contents memorylimits for regions of memory used by theprocess open file descriptors and otherdata when performing a process switch itis critical that the operating systemsaves the processes CPU state at atheoretical minimum this stateinformation includes the program counterand CPU register contents in practicemore information will be saved duringeach process switch this diagrampresents a simplified view of processswitching where only the program counterand register contents are saved andrestored here are the operating systemswitches from the process with ID 1 -the process with ID 2 the first step inthe process which is to perform a modeswitch into kernel mode along with thecontext switch to the section of thekernel that handles process switchingthat component of the kernel saves theprogram counter and CPU registers intothe process control block for process 1also the process State for process 1 isset to ready indicating that the processis ready to run again once the CPU corebecomes available the process switchingcode then restores the CPU registercontents and program counter value fromthe process control block for processtwo the state of process 2 is changedfrom ready to running the CPU privilegelevel is returned to user mode andcontexts to switch to process twoprocess two now begins executing duringthe lifetime of a process thecorresponding process control block ismoved between various cues in theoperating systemeach cue is a linked list of processcontrol blocks and multiple linked listsoverlap all PCBs are at all times in thejob queue which is a linked list of allprocess control blocks in the systemprocess control blocks corresponding toprocesses in the ready state are linkedinto the ready list processes waitingfor device IO have their PCBs linkedinto various different device queues inthis diagram we can see the PCBs forfive different processes all PCBs aremembers of the job list with list linksdepicted by the green arrows three jobsare in the ready list and two jobs arein a device queue waiting on IO thelinked lists within each queue arerepresented by the dark blue arrowsnotice that the two linked lists for thequeues overlap the linked lists for thejob list careful management of linkedlists is a major requirement ofoperating system kernel code now I'dlike to shift focus for a moment tomention scheduling since it is closelyrelated to the linked list management inoperating systems theory we typicallydivide scheduling into three types jobscheduling midterm scheduling and CPUscheduling job or long term schedulingrefers to the selection of processes toplace into the ready State this type ofscheduler has a long interval typicallyon the order of seconds to minutes oneof the clearest examples of jobscheduling on modern systems occurs onhigh-performance computational clusterson which users submit jobs that mayrequire hours to be scheduled andexecute midterm scheduling refers to theswapping of inactive processes out todisk and restoring swapped processesfrom diskmany of these tasks are now part of thevirtual memory subsystem CPU schedulingor short-term scheduling refers to theselection of processes from the readylist to run on CPU cores this type ofscheduling will be the subject of futurelectures one important operating systemcomponent related to short-termscheduling is the dispatcher whichreceives a process control block fromthe short-term scheduler and restoresthe context of the processthe dispatcher also completes thecontext switch to the process byperforming a mode switch into user modeand jumping to the instruction addressspecified by the newly restored programcounter