Lecture notes on Operating systems

how operating systems switch between processes and how is operating system a resource manager | pdf free download
JackBrown Profile Pic
Published Date:11-07-2017
Your Website URL(Optional)
NotesonOperatingSystems DrorG.Feitelson SchoolofComputerScienceandEngineering TheHebrewUniversityofJerusalem 91904Jerusalem,Israel c 2011Chapter1 Introduction Inthesimplestscenario,theoperatingsystemisthefirstpieceofsoftwaretorunona computerwhenitisbooted. Itsjobistocoordinatetheexecutionofallothersoftware, mainly user applications. It also provides various common services that are needed byusersandapplications. 1.1 OperatingSystemFunctionality Theoperatingsystemcontrolsthemachine Itiscommontodrawthefollowingpicturetoshowtheplaceoftheoperatingsystem: user application operating system hardware This is a misleading picture, because applications mostly execute machine instruc- tionsthatdonotgothroughtheoperatingsystem. Abetterpictureis: 2application system calls operating system non−privileged privileged interrupts machine instructions instructions hardware where we have used a 3-D perspective to show that there is one hardware base, one operating system, but many applications. It also shows the important interfaces: ap- plications can execute only non-privileged machine instructions, and they may also call upon the operating system to perform some service for them. The operating sys- tem may use privileged instructions that are not available to applications. And in addition, various hardware devices may generate interrupts that lead to the execu- tionofoperatingsystemcode. Apossiblesequenceofactionsinsuchasystemisthefollowing: 1. Theoperatingsystemexecutes,andschedulesanapplication(makesitrun). 2. Thechosenapplicationruns: theCPUexecutesits(non-privileged)instructions, andtheoperatingsystemisnotinvolvedatall. 3. ThesystemclockinterruptstheCPU,causingittoswitchtotheclock’sinterrupt handler,whichisanoperatingsystemfunction. 4. The clock interrupt handler updates the operating system’s notion of time, and callstheschedulertodecidewhattodonext. 5. The operating system scheduler chooses another application to run in place of thepreviousone,thusperformingacontextswitch. 6. The chosen application runs directly on the hardware; again, the operating sys- tem is not involved. After some time, the application performs a system call to readfromafile. 7. The system call causes a trap into the operating system The operating system setsthingsupfortheI/Ooperation(usingsomeprivilegedinstructions). Itthen puts the calling application to sleep, to await the I/O completion, and chooses anotherapplicationtoruninitsplace. 8. Thethirdapplicationruns. 31 Theimportantthingtonoticeisthatatanygiventime,onlyoneprogramisrunning . Sometimes this is the operating system, and at other times it is a user application. When a user application is running, the operating system loses its control over the machine. It regains control if the user application performs a system call, or if there isahardwareinterrupt. Exercise 1 Howcantheoperatingsystemguaranteethattherewillbeasystemcallor interrupt,sothatitwillregaincontrol? Theoperatingsystemisareactiveprogram Anotherimportantthingtonoticeisthattheoperatingsystemisareactiveprogram. It does not get an input, do some processing, and produce an output. Instead, it is constantly waiting for someevent to happen. When the event happens, the operating system reacts. This usually involves some administration to handle whatever it is that happened. Then the operating system schedules another application, and waits forthenextevent. Because it is a reactive system, the logical flow of control is also different. “Nor- mal” programs, which accept an input and compute an output, have amain function thatistheprogram’sentrypoint. maintypicallycallsotherfunctions,andwhenitre- turns the program terminates. An operating system, in contradistinction, has many differententrypoints,oneforeacheventtype. Anditisnotsupposedtoterminate— whenitfinisheshandlingoneevent,itjustwaitsforthenextevent. Events can be classified into two types: interrupts and system calls. These are described in more detail below. The goal of the operating system is to run as little as possible,handletheeventsquickly,andletapplicationsrunmostofthetime. Exercise 2 Make a list of applications you use in everyday activities. Which of them arereactive? Arereactiveprogramscommonorrare? Theoperatingsystemperformsresourcemanagement Oneofthemainfeaturesofoperatingsystemsissupportformultiprogramming. This means that multiple programs may execute “at the same time”. But given that there is only one processor, this concurrent execution is actually a fiction. In reality, the operating system juggles the system’s resources between the competing programs, tryingtomakeitlookasifeachonehasthecomputerforitself. At the heart of multiprogramming lies resource management — deciding which running program will get what resources. Resource management is akin to the short blanket problem: everyone wants to be covered, but the blanket is too short to cover everyoneatonce. 1 This is not strictly true on modern microprocessors with hyper-threading or multiple cores, but we’llassumeasimplesingle-CPUsystemfornow. 4Theresourcesinacomputersystemincludetheobviouspiecesofhardwareneeded byprograms: • TheCPUitself. • Memorytostoreprogramsandtheirdata. • Diskspaceforfiles. Buttherearealsointernalresourcesneededbytheoperatingsystem: • Diskspaceforpagingmemory. • Entriesinsystemtables,suchastheprocesstableandopenfilestable. All the applications want to run on the CPU, but only one can run at a time. Thereforetheoperatingsystemletseachonerunforashortwhile,andthenpreempts itandgivestheCPUtoanother. Thisiscalledtimeslicing. Thedecisionaboutwhich applicationtorunisscheduling(discussedinChapter2). As for memory, each application gets some memory frames to store its code and data. If the sum of the requirements of all the applications is more than the avail- able physical memory, paging is used: memory pages that are not currently used are temporarilystoredondisk(we’llgettothisinChapter4). With disk space (and possibly also with entries in system tables) there is usually a hard limit. The system makes allocations as long as they are possible. When the resource runs out, additional requests are failed. However, they can try again later, whensomeresourceshavehopefullybeenreleasedbytheirusers. Exercise 3 As system tables are part of the operating system, they can be made as big aswewant. Whyisthisabadidea? Whatsizesshouldbechosen? Theoperatingsystemprovidesservices In addition, the operating system provides various services to the applications run- ning on the system. These services typically have two aspects: abstraction and isola- tion. Abstraction means that the services provide a more convenient working environ- mentforapplications,byhidingsomeofthedetailsofthehardware,andallowingthe applications to operate at a higher level of abstraction. For example, the operating systemprovidestheabstractionofafilesystem,andapplicationsdon’tneedtohandle rawdiskinterfacesdirectly. Isolation means that many applications can co-exist at the same time, using the same hardware devices, without falling over each other’s feet. These two issues are discussed next. For example, if several applications send and receive data over a network,theoperatingsystemkeepsthedatastreamsseparatedfromeachother. 51.2 AbstractionandVirtualization Theoperatingsystempresentsanabstractmachine The dynamics of a multiprogrammed computer system are rather complex: each ap- plication runs for some time, then it is preempted, runs again, and so on. One of the roles of the operating system is to present the applications with an environment in which these complexities are hidden. Rather than seeing all the complexities of the real system, each application sees a simplerabstractmachine, which seems to be dedicated to itself. It is blissfully unaware of the other applications and of operating systemactivity. Aspartoftheabstractmachine,theoperatingsystemalsosupportssomeabstrac- tions that do not exist at the hardware level. The chief one is files: persistent repos- itories of data with names. The hardware (in this case, the disks) only supports per- sistent storage of data blocks. The operating system builds the file system above this support, and creates named sequences of blocks (as explained in Chapter 5). Thus applicationsaresparedtheneedtointeractdirectlywithdisks. Exercise 4 What features exist in the hardware but are not available in the abstract machinepresentedtoapplications? Exercise 5 Cantheabstractionincludenewinstructionstoo? Theabstractmachinesareisolated An important aspect of multiprogrammed systems is that there is not one abstract machine, but many abstract machines. Each running application gets its own ab- stractmachine. Averyimportantfeatureoftheabstractmachinespresentedtoapplicationsisthat theyareisolatedfromeachother. Partoftheabstractionistohideallthoseresources that are being used to support other running applications. Each running application thereforeseesthesystemasifitwerededicatedtoitself. Theoperatingsystemjuggles resourcesamongthesecompetingabstractmachinesinordertosupportthisillusion. Oneexampleofthisisscheduling: allocatingtheCPUtoeachapplicationinitsturn. Exercise 6 Can an application nevertheless find out that it is actually sharing the machinewithotherapplications? Virtualizationallowsfordecouplingfromphysicalrestrictions The abstract machine presented by the operating system is “better” than the hard- ware by virtue of supporting more convenient abstractions. Another important im- provement is that it is also not limited by the physical resource limitations of the underlying hardware: it is a virtual machine. This means that the application does 6not access the physical resources directly. Instead, there is a level of indirection, managedbytheoperatingsystem. virtual machines physical machine seen by applications available in hardware CPU CPU machine instructions machine instructions (non−priviledged) (priviledged and not) registers registers (special (general purpose) and general purpose) mapping memory cache memory by the 4 GB contiguous operating limited address space physical memory system file system persistent storage persistent block−addressable named files disk The main reason for using virtualization is to make up for limited resources. If the physical hardware machine at our disposal has only 1GB of memory, and each abstract machine presents its application with a 4GB address space, then obviously a direct mapping from these address spaces to the available memory is impossible. Theoperatingsystemsolvesthisproblembycouplingitsresourcemanagementfunc- tionalitywiththesupportfortheabstractmachines. Ineffect,itjugglestheavailable resources among the competing virtual machines, trying to hide the deficiency. The specificcaseofvirtualmemoryisdescribedinChapter4. Virtualizationdoesnotnecessarilyimplyabstraction Virtualization does not necessarily involve abstraction. In recent years there is a growing trend of using virtualization to create multiple copies of the same hardware base. This allows one to run a different operating system on each one. As each op- erating system provides different abstractions, this decouples the issue of creating abstractionswithinavirtualmachinefromtheprovisioningofresourcestothediffer- entvirtualmachines. The idea of virtual machines is not new. It originated with MVS, the operating system for the IBM mainframes. In this system, time slicing and abstractions are completely decoupled. MVS actually only does the time slicing, and creates multiple exact copies of the original physical machine. Then, a single-user operating system calledCMSisexecutedineachvirtualmachine. CMSprovidestheabstractionsofthe userenvironment,suchasafilesystem. 7As each virtual machine is an exact copy of the physical machine, it was also pos- sible to run MVS itself on such a virtual machine. This was useful to debug new ver- sions of the operating system on a running system. If the new version is buggy, only its virtual machine will crash, but the parent MVS will not. This practice continues today, and VMware has been used as a platform for allowing students to experiment withoperatingsystems. WewilldiscussvirtualmachinesupportinSection9.5. To read more: HistorybuffscanreadmoreaboutMVSinthebookbyJohnson7. Thingscangetcomplicated The structure of virtual machines running different operating systems may lead to a confusion in terminology. In particular, the allocation of resources to competing vir- tualmachinesmaybedonebyaverythinlayerofsoftwarethatdoesnotreallyqualify asafull-fledgedoperatingsystem. Suchsoftwareisusuallycalledahypervisor. On the other hand, virtualization can also be done at the application level. A re- markableexampleisgivenbyVMware. Thisisactuallyauser-levelapplication,that runs on top of a conventional operating system such as Linux or Windows. It creates a set of virtual machines that mimic the underlying hardware. Each of these virtual machines can boot an independent operating system, and run different applications. Thustheissueofwhatexactlyconstitutestheoperatingsystemcanbemurky. Inpar- ticular, several layers of virtualization and operating systems may be involved with theexecutionofasingleapplication. In these notes we’ll ignore such complexities, at least initially. We’ll take the (somewhatoutdated)viewthatalltheoperatingsystemisamonolithicpieceofcode, which is called the kernel. But in later chapters we’ll consider some deviations from thisviewpoint. 1.3 HardwareSupportfortheOperatingSystem Theoperatingsystemdoesn’tneedtodoeverythingitself—itgetssomehelpfromthe hardware. Thereareevenquiteafewhardwarefeaturesthatareincludedspecifically fortheoperatingsystem,anddonotserveuserapplicationsdirectly. Theoperatingsystemenjoysaprivilegedexecutionmode CPUstypicallyhave(atleast)twoexecutionmodes: usermodeandkernelmode. User applicationsruninusermode. Theheartoftheoperatingsystemiscalledthekernel. This is the collection of functions that perform the basic services such as scheduling applications. The kernel runs in kernel mode. Kernel mode is also called supervisor modeorprivileged mode. The execution mode is indicated by a bit in a special register called the processor status word (PSW). Various CPU instructions are only available to software running 8in kernel mode, i.e., when the bit is set. Hence these privileged instructions can only beexecutedbytheoperatingsystem,andnotbyuserapplications. Examplesinclude: • Instructions to set the interrupt priority level (IPL). This can be used to block certain classes of interrupts from occurring, thus guaranteeing undisturbed ex- ecution. • Instructionstosetthehardwareclocktogenerateaninterruptatacertaintime inthefuture. • InstructionstoactivateI/Odevices. TheseareusedtoimplementI/Ooperations onfiles. • Instructions to load and store special CPU registers, such as those used to de- fine the accessible memory addresses, and the mapping from each application’s virtualaddressestotheappropriateaddressesinthephysicalmemory. • Instructionstoloadandstorevaluesfrommemorydirectly,withoutgoingthrough theusualmapping. Thisallowstheoperatingsystemtoaccessallthememory. Exercise 7 Whichofthefollowinginstructionsshouldbeprivileged? 1. Changetheprogramcounter 2. Haltthemachine 3. Dividebyzero 4. Changetheexecutionmode Exercise 8 Youcanwriteaprograminassemblerthatincludesprivilegedinstructions. Whatwillhappenifyouattempttoexecutethisprogram? Example: levelsofprotectiononIntelprocessors Atthehardwarelevel,Intelprocessorsprovidenottwobutfourlevelsofprotection. Level0 isthemostprotectedandintendedforusebythekernel. Level1 isintendedforother,non-kernelpartsoftheoperatingsystem. Level2 is offered for device drivers: needy of protection from user applications, but not 2 trustedasmuchastheoperatingsystemproper . Level3 istheleastprotectedandintendedforusebyuserapplications. Each data segment in memory is also tagged by a level. A program running in a certain level can only access data that is in the same level or (numerically) higher, that is, has the same or lesser protection. For example, this could be used to protect kernel data structures from being manipulated directly by untrusted device drivers; instead, drivers would be forced to use pre-defined interfaces to request the service they need from the kernel. Programs running in numerically higher levels are also restricted from issuing certaininstructions,suchasthatforhaltingthemachine. Despite this support, most operating systems (includingUnix, Linux, and Windows) only usetwoofthefourlevels,correspondingtokernelandusermodes. 2 Indeed,devicedrivers are typicallybuggier thantherestofthekernel5. 9Onlypredefinedsoftwarecanruninkernelmode Obviously,softwarerunninginkernelmodecancontrolthecomputer. Ifauserappli- cation was to run in kernel mode, it could prevent other applications from running, destroy their data, etc. It is therefore important to guarantee that user code will neverruninkernelmode. The trick is that when the CPU switches to kernel mode, it also changes the pro- 3 gram counter (PC) to point at operating system code. Thus user code will never get toruninkernelmode. Note: kernelmodeandsuperuser Unix has a special privileged user called the “superuser”. The superuser can override various protection mechanisms imposed by the operating system; for example, he can access other users’ private files. However, this does not imply running in kernel mode. The difference is between restrictions imposed by the operating system software, as part oftheoperatingsystemservices,andrestrictionsimposedbythehardware. Therearetwowaystoenterkernelmode: interruptsandsystemcalls. Interruptscauseaswitchtokernelmode Interrupts are special conditions that cause the CPU not to execute the next instruc- tion. Instead,itenterskernelmodeandexecutesanoperatingsysteminterrupthan- dler. But how does the CPU (hardware) know the address of the appropriate kernel function? This depends on what operating system is running, and the operating sys- tem might not have been written yet when the CPU was manufactured The answer to this problem is to use an agreement between the hardware and the software. This agreementisasymmetric,asthehardwarewastherefirst. Thus,partofthehardware architecture is the definition of certain features and how the operating system is ex- pected to use them. All operating systems written for this architecture must comply withthesespecifications. Two particular details of the specification are the numbering of interrupts, and the designation of a certain physical memory address that will serve as an interrupt vector. When the system is booted, the operating system stores the addresses of the interrupt handling functions in the interrupt vector. When an interrupt occurs, the hardware stores the current PSW and PC, and loads the appropriate PSW and PC values for the interrupt handler. The PSW indicates execution in kernel mode. The PC is obtained by using the interrupt number as an index into the interrupt vector, andusingtheaddressfoundthere. 3 ThePCisaspecialregisterthatholdstheaddressofthenextinstructiontobeexecuted. Thisisn’t avery goodname. Foranoverview ofthisandotherspecialregisters seeAppendix A. 10load PC from interrupt vector CPU memory PC 1 PSW set status to interrupt handler kernel mode (OS function) Note that the hardware does this blindly, using the predefined address of the inter- rupt vector as a base. It is up to the operating system to actually store the correct addressesinthecorrectplaces. Ifitdoesnot,thisisabugintheoperatingsystem. Exercise 9 Andwhathappensifsuchabugoccurs? Therearetwomaintypesofinterrupts: asynchronousandinternal. Asynchronous (external)interruptsaregeneratedbyexternaldevicesatunpredictabletimes. Exam- plesinclude: • Clock interrupt. This tells the operating system that a certain amount of time has passed. It’s handler is the operating system function that keeps track of time. Sometimes, this function also calls the scheduler which might preempt the current application and run another in its place. Without clock interrupts, theapplicationmightrunforeverandmonopolizethecomputer. Exercise 10 A typical value for clock interrupt resolution is once every 10 mil- liseconds. Howdoesthisaffecttheresolutionoftimingvariousthings? • I/O device interrupt. This tells the operating system that an I/O operation has completed. The operating system then wakes up the application that requested theI/Ooperation. Internal (synchronous) interrupts occur as a result of an exception condition when executing the current instruction (as this is a result of what the software did, this is sometimes also called a “software interrupt”). This means that the processor cannot complete the current instruction for some reason, so it transfers responsibility to the operatingsystem. Therearetwomaintypesofexceptions: • An error condition: this tells the operating system that the current application did something illegal (divide by zero, try to issue a privileged instruction, etc.). Thehandleristheoperatingsystemfunctionthatdealswithmisbehavedappli- cations;usually,itkillsthem. 11• Atemporaryproblem: forexample,theprocesstriedtoaccessapageofmemory thatisnotallocatedatthemoment. Thisisanerrorconditionthattheoperating system can handle, and it does so by bringing the required page into memory. WewilldiscussthisinChapter4. Exercise 11 Cananotherinterruptoccurwhenthesystemisstillintheinterrupthan- dlerforapreviousinterrupt? Whathappensthen? When the handler finishes its execution, the execution of the interrupted applica- tioncontinueswhereitleftoff—exceptiftheoperatingsystemkilledtheapplication ordecidedtoscheduleanotherone. To read more: Stallings 18, Sect. 1.4 provides a detailed discussion of interrupts, and how theyareintegratedwiththeinstructionexecutioncycle. Systemcallsexplicitlyaskfortheoperatingsystem An application can also explicitly transfer control to the operating system by per- forming a system call. This is implemented by issuing the trap instruction. This instruction causes the CPU to enter kernel mode, and set the program counter to a special operating system entry point. The operating system then performs some ser- vice on behalf of the application. Technically, this is actually just another (internal) interrupt—butadesirableonethatwasgeneratedbyanexplicit request. Asanoperatingsystemcanhavemorethanahundredsystemcalls,thehardware cannot be expected to know about all of them (as opposed to interrupts, which are a hardware thing to begin with). The sequence of events leading to the execution of a systemcallisthereforeslightlymoreinvolved: 1. The application calls a library function that serves as a wrapper for the system call. 2. Thelibraryfunction(stillrunninginusermode)storesthesystemcallidentifier andtheprovided argumentsinadesignatedplaceinmemory. 3. Itthenissuesthetrapinstruction. 4. ThehardwareswitchestoprivilegedmodeandloadsthePCwiththeaddressof theoperatingsystemfunctionthatservesasanentrypointforsystemcalls. 5. The entry point function starts running (in kernel mode). It looks in the desig- natedplacetofindwhichsystemcallisrequested. 6. The system call identifier is used in a big switch statement to find and call the appropriate operating system function to actually perform the desired service. Thisfunctionstartsbyretrievingitsargumentsfromwheretheywerestoredby thewrapperlibraryfunction. 12Exercise 12 Should the library of system-call wrappers be part of the distribution of thecompileroroftheoperatingsystem? Typicalsystemcallsinclude: • Open,close,read,orwritetoafile. • Createanewprocess(thatis,startrunninganotherapplication). • Getsomeinformationfromthesystem,e.g.thetimeofday. • Request to change the status of the application, e.g. to reduce its priority or to allowittousemorememory. When the system call finishes, it simply returns to its caller like any other function. Ofcourse,theCPUmustreturntonormalexecutionmode. Thehardwarehasspecialfeaturestohelptheoperatingsystem Inadditiontokernelmodeandtheinterruptvector,computershavevariousfeatures thatarespecificallydesignedtohelptheoperatingsystem. Themostcommonarefeaturesusedtohelpwithmemorymanagement. Examples include: • Hardware to translate each virtual memory address to a physical address. This allows the operating system to allocate various scattered memory pages to an application, rather than having to allocate one long continuous stretch of mem- ory. • “Used”bitsonmemorypages,whicharesetautomaticallywheneveranyaddress in the page is accessed. This allows the operating system to see which pages wereaccessed(bitis1)andwhichwerenot(bitis0). We’ll review specific hardware features used by the operating system as we need them. 1.4 Roadmap Therearedifferentviewsofoperatingsystems Anoperatingsystemcanbeviewedinthreeways: • Accordingtotheservicesitprovidestousers,suchas – Timeslicing. – Afilesystem. • Byitsprogramminginterface,i.e.itssystemcalls. 13• Accordingtoitsinternalstructure,algorithms,anddatastructures. An operating system is defined by its interface — different implementation of the same interface are equivalent as far as users and programs are concerned. However, these notes are organized according to services, and for each one we will detail the internalstructuresandalgorithmsused. Occasionally, wewill alsoprovide examples ofinterfaces,mainlyfromUnix. To read more: To actually use the services provided by a system, you need to read a book that describes that system’s system calls. Good books for Unix programming are Rochkind 15andStevens19. AgoodbookforWindowsprogrammingisRichter14. Notethatthese booksteachyouabouthowtheoperatingsystemlooks“fromtheoutside”;incontrast,wewill focusonhowitisbuiltinternally. Operatingsystemcomponentscanbestudiedinisolation Themaincomponentsthatwewillfocusonare • Process handling. Processes are the agents of processing. The operating system creates them, schedules them, and coordinates their interactions. In particular, multipleprocessesmayco-existinthesystem(thisiscalledmultiprogramming). • Memory management. Memory is allocated to processes as needed, but there typicallyisnotenoughforall,sopagingisused. • Filesystem. Filesareanabstractionprovidingnameddatarepositoriesbasedon disksthatstoreindividualblocks. Theoperatingsystemdoesthebookkeeping. In addition there are a host of other issues, such as security, protection, accounting, errorhandling,etc. Thesewillbediscussedlaterorinthecontextofthelargerissues. Butinalivingsystem,thecomponentsinteract Itisimportanttounderstandthatinarealsystemthedifferentcomponentsinteract allthetime. Forexample, • When a process performs an I/O operation on a file, it is descheduled until the operation completes, and another process is scheduled in its place. This im- proves system utilization by overlapping the computation of one process with theI/Oofanother: I/O operation I/O finished process 1 running waiting ready running context switch duration of I/O context switch process 2 ready running ready time 14ThusboththeCPUandtheI/Osubsystemarebusyatthesametime,insteadof idlingtheCPUtowaitfortheI/Otocomplete. • If a process does not have a memory page it requires, it suffers a page fault (thisis atypeofinterrupt). Again,thisresultsin anI/Ooperation,andanother processisruninthemeanwhile. • Memoryavailabilitymaydetermineifanewprocessisstartedormadetowait. We will initially ignore such interactions to keep things simple. They will be men- tionedlateron. Thenthere’stheinteractionamongmultiplesystems Theaboveparagraphsrelatetoasinglesystemwithasingleprocessor. Thefirstpart of these notes is restricted to such systems. The second part of the notes is about distributedsystems,wheremultipleindependentsystemsinteract. Distributed systems are based on networking and communication. We therefore discuss these issues, even though they belong in a separate course on computer com- munications. We’llthengoontodiscusstheservicesprovidedbytheoperatingsystem in order to manage and use a distributed environment. Finally, we’ll discuss the con- struction of heterogeneous systems using middleware. While this is not strictly part oftheoperatingsystemcurriculum,itmakessensetomentionithere. Andwe’llleaveafewadvancedtopicstotheend Finally, there are a few advanced topics that are best discussed in isolation after we alreadyhaveasolidbackgroundinthebasics. Thesetopicsinclude • The structuring of operating systems, the concept of microkernels, and the pos- sibilityofextensiblesystems • Operatingsystemsandmobilecomputing,suchasdisconnectedoperationoflap- tops • Operating systems for parallel processing, and how things change when each userapplicationiscomposedofmultipleinteractingprocessesorthreads. 1.5 ScopeandLimitations Thekernelisasmallpartofadistribution All the things we mentioned so far relate to the operating system kernel. This will indeedbeourfocus. Butitshouldbenotedthatingeneral,whenonetalksofacertain operating system, one is actually referring to a distribution. For example, a typical Unixdistributioncontainsthefollowing elements: 15• TheUnixkernelitself. Strictlyspeaking,thisis“theoperatingsystem”. • Thelibc library. This provides the runtime environment for programs written in C. For example, is contains printf, the function to format printed output, 4 andstrncpy,thefunctiontocopystrings . • Varioustools,suchasgcc,theGNUCcompiler. • Many utilities, which are useful programs you may need. Examples include a windowingsystem,desktop,andshell. As noted above, we will focus exclusively on the kernel — what it is supposed to do, andhowitdoesit. Youcan(andshould) readmoreelsewhere Thesenotesshouldnotbeconsideredtobethefullstory. Forexample,mostoperating systemtextbookscontainhistoricalinformationonthedevelopmentofoperatingsys- tems, which is an interesting story and is not included here. They also contain more detailsandexamplesformanyofthetopicsthatarecoveredhere. The main recommended textbooks are Stallings 18, Silberschatz et al. 17, and Tanenbaum 21. These are general books covering the principles of both theoretical work and the practice in various systems. In general, Stallings is more detailed, and gives extensive examples and descriptions of real systems; Tanenbaum has a somewhatbroaderscope. Of course it is also possible to use other operating system textbooks. For exam- ple, one approach is to use an educational system to provide students with hands-on experience of operating systems. The best known is Tanenbaum 22, who wrote the Minix system specifically for this purpose; the book contains extensive descriptions of Minix as well as full source code (This is the same Tanenbaum as above, but a different book). Nutt 13 uses Linux as his main example. Another approach is to emphasize principles rather than actual examples. Good (though somewhat dated) booksinthiscategoryincludeKrakowiak8andFinkel6. Finally,somebookscon- centrateonacertainclassofsystemsratherthanthefullscope,suchasTanenbaum’s book on distributed operating systems 20 (the same Tanenbaum again; indeed, one of the problems in the field is that a few prolific authors have each written a number ofbooksonrelatedissues;trynottogetconfused). In addition, there are a number of books on specific (real) systems. The first and most detailed description of Unix system V is by Bach 1. A similar description of 4.4BSD was written by McKusick and friends 12. The most recent is a book on Solaris 10. Vahalia is another very good book, with focus on advanced issues in different Unix versions 23. Linux has been described in detail by Card and friends 4, by Beck and other friends 2, and by Bovet and Cesati 3; of these, the first 4 Alwaysusestrncpy,notstrcpy 16gives a very detailed low-level description, including all the fields in all major data structures. Alternatively, source code with extensive commentary is available for Unix version 6 (old but a classic) 9 and for Linux 11. It is hard to find anything withtechnicaldetailsaboutWindows. ThebestavailableisRussinovichandSolomon 16. While these notes attempt to represent the lectures, and therefore have consid- erable overlap with textbooks (or, rather, are subsumed by the textbooks), they do have some unique parts that are not commonly found in textbooks. These include an emphasis on understanding system behavior and dynamics. Specifically, we focus on the complementary roles of hardware and software, and on the importance of know- ing the expected workload in order to be able to make design decisions and perform reliableevaluations. Bibliography 1 M.J.Bach,TheDesignoftheUNIXOperatingSystem. Prentice-Hall,1986. 2 M. Beck, H. Bohme, M. Dziadzka, U. Kunitz, R. Magnus, and D. Verworner, LinuxKernelInternals. Addison-Wesley, 2nded.,1998. 3 D.P.BovetandM.Cesati,UnderstandingtheLinuxKernel. O’Reilly, 2001. 4 R.Card,E.Dumas,andF.Me´vel,TheLinuxKernelBook. Wiley,1998. 5 A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler, “An empirical study of operating system errors”. In 18th Symp. Operating Systems Principles, pp. 73– 88,Oct2001. 6 R. A. Finkel, An Operating Systems Vade Mecum. Prentice-Hall Inc., 2nd ed., 1988. 7 R.H.Johnson,MVS:ConceptsandFacilities. McGraw-Hill,1989. 8 S.Krakowiak,PrinciplesofOperatingSystems. MITPress,1988. 9 J.Lions,Lions’CommentaryonUNIX6thEdition,withSourceCode.Annabooks, 1996. 10 J.MauroandR.McDougall,SolarisInternals. PrenticeHall,2001. 11 S.Maxwell,LinuxCoreKernelCommentary. CoriolisOpenPress,1999. 12 M. K. McKusick, K. Bostic, M. J. Karels, and J. S. Quarterman, The Design and Implementationofthe4.4BSDOperatingSystem. AddisonWesley,1996. 13 G.J.Nutt,OperatingSystems: AModernPerspective. Addison-Wesley, 1997. 1714 J. Richter, Programming Applications for Microsoft Windows. Microsoft Press, 4thed.,1999. 15 M.J.Rochkind,AdvancedUnixProgramming. Prentice-Hall,1985. 16 M. E. Russinovic and D. A. Solomon, Microsoft Windows Internals. Microsoft Press,4thed.,2005. 17 A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts. John Wiley&Sons,7thed.,2005. 18 W.Stallings,OperatingSystems: InternalsandDesignPrinciples. Prentice-Hall, 5thed.,2005. 19 W. R. Stevens, AdvancedProgrammingintheUnixEnvironment. Addison Wes- ley,1993. 20 A.S.Tanenbaum,DistributedOperatingSystems. PrenticeHall,1995. 21 A. S. Tanenbaum, Modern Operating Systems. Pearson Prentice Hall, 3rd ed., 2008. 22 A.S.TanenbaumandA.S.Woodhull,OperatingSystems: DesignandImplemen- tation. Prentice-Hall,2nded.,1997. 23 U.Vahalia,UnixInternals: TheNewFrontiers. PrenticeHall,1996. 18AppendixA BackgroundonComputer Architecture Operatingsystemsaretightlycoupledwiththearchitectureofthecomputeronwhich theyarerunning. Somebackgroundonhowthehardwareworksisthereforerequired. This appendix summarizes the main points. Note, however, that this is only a high- level simplified description, and does not correspond directly to any specific real-life architecture. At a very schematic level, we will consider the com- puter hardware as containing two main components: thememoryandtheCPU(centralprocessingunit). The memory is where programs and data are stored. The CPU does the actual computation. It contains general- purpose registers, an ALU (arithmetic logic unit), and some special purpose registers. The general-purpose registers are simply very fast memory; the compiler ALU typicallyusesthemtostorethosevariablesthatarethe most heavily used in each subroutine. The special pur- PSW PC pose registers have specific control functions, some of whichwillbedescribedhere. MEM SP The CPU operates according to a hardware clock. This defines the computer’s “speed”: whenyoubuya3GHzmachine,thismeansthattheclockdictates3,000,000,000 cycleseachsecond. Inoursimplisticview,we’llassumethataninstructionisexecuted ineverysuchcycle. InmodernCPUseachinstructiontakesmorethanasinglecycle, as instruction execution is done in a pipelined manner. To compensate for this, real CPUs are superscalar, meaning they try to execute more than one instruction per cycle,andemployvariousothersophisticatedoptimizations. 19 CPU memory registersdata program One of the CPU’s special registers is the program counter (PC). This register points to the next instruc- tionthatwillbeexecuted. Ateachcycle,theCPUloads this instruction and executes it. Executing it may in- clude the copying of the instruction’s operands from memory to the CPU’s registers, using the ALU to per- form some operation on these values, and storing the ALU resultinanotherregister. Thedetailsdependonthear- chitecture, i.e. what the hardware is capable of. Some architectures require operands to be in registers, while PSW PC othersallowoperandsinmemory. MEM SP Exercise 13 IsitpossibletoloadavalueintothePC? Exercise 14 WhathappensifanarbitraryvalueisloadedintothePC? Inadditiontoprovidingbasicinstructionssuchasadd,subtract,andmultiply,the hardware also provides specific support for running applications. One of the main examples is support for calling subroutines and returning from them, using the in- structionscall andret. The reason for supporting this in hardware is that several things need to be done at once. As the called subroutine does not know the context from which it was called, it cannot know what is currently stored in the registers. Therefore we need to store these values in a safe place before the call, allow the called subroutine to operate in a “clean” environment, and then restore the register valueswhenthesubroutineterminates. Thecallinstructiondoesthefirstpart: data stack program 1. It stores the register values on the stack, at the location pointed to by the stack pointer (another specialregister,abbreviatedSP). 2. It also stores the return address (i.e. the address afterthecallinstruction)onthestack. 3. ItloadsthePCwiththeaddressoftheentry-point ALU ofthecalledsubroutine. 4. Itincrementsthestackpointertopointtothenew PSW PC top of the stack, in anticipation of additional sub- routinecalls. MEM SP Afterthesubroutineruns,theretinstructionrestoresthepreviousstate: 1. Itrestorestheregistervaluesfromthestack. 20 CPU memory CPU memory registers registers sub

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.