Notes On Operating Systems - Huji.ac.il
Notes on Operating SystemsDror G. FeitelsonSchool of Computer Science and EngineeringThe Hebrew University of Jerusalem91904 Jerusalem, Israelc 2011
ContentsIBackground11 Introduction1.1 Operating System Functionality . . . . . . .1.2 Abstraction and Virtualization . . . . . . . .1.3 Hardware Support for the Operating System1.4 Roadmap . . . . . . . . . . . . . . . . . . . . .1.5 Scope and Limitations . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . . .2. 2. 6. 8. 13. 15. 17A Background on Computer Architecture19II The Classics232 Processes and Threads2.1 What Are Processes and Threads? . . . . . . . . . . . . . . . .2.1.1 Processes Provide Context . . . . . . . . . . . . . . . . .2.1.2 Process States . . . . . . . . . . . . . . . . . . . . . . . .2.1.3 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.4 Operations on Processes and Threads . . . . . . . . . .2.2 Multiprogramming: Having Multiple Processes in the System2.2.1 Multiprogramming and Responsiveness . . . . . . . . .2.2.2 Multiprogramming and Utilization . . . . . . . . . . . .2.2.3 Multitasking for Concurrency . . . . . . . . . . . . . . .2.2.4 The Cost . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Scheduling Processes and Threads . . . . . . . . . . . . . . . .2.3.1 Performance Metrics . . . . . . . . . . . . . . . . . . . .2.3.2 Handling a Given Set of Jobs . . . . . . . . . . . . . . .2.3.3 Using Preemption . . . . . . . . . . . . . . . . . . . . . .2.3.4 Priority Scheduling . . . . . . . . . . . . . . . . . . . . .ii.24242427293435353840404141434648
2.3.5 Starvation, Stability, and Allocations2.3.6 Fair Share Scheduling . . . . . . . .2.4 Summary . . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . .51535456B UNIX Processes58Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 Concurrency3.1 Mutual Exclusion for Shared Data Structures . . . .3.1.1 Concurrency and the Synchronization Problem3.1.2 Mutual Exclusion Algorithms . . . . . . . . . .3.1.3 Semaphores and Monitors . . . . . . . . . . . .3.1.4 Locks and Disabling Interrupts . . . . . . . . .3.1.5 Multiprocessor Synchronization . . . . . . . . .3.2 Resource Contention and Deadlock . . . . . . . . . . .3.2.1 Deadlock and Livelock . . . . . . . . . . . . . .3.2.2 A Formal Setting . . . . . . . . . . . . . . . . .3.2.3 Deadlock Prevention . . . . . . . . . . . . . . .3.2.4 Deadlock Avoidance . . . . . . . . . . . . . . . .3.2.5 Deadlock Detection . . . . . . . . . . . . . . . .3.2.6 Real Life . . . . . . . . . . . . . . . . . . . . . .3.3 Lock-Free Programming . . . . . . . . . . . . . . . . .3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . .4 Memory Management4.1 Mapping Memory Addresses . . . . . . . . . .4.2 Segmentation and Contiguous Allocation . .4.2.1 Support for Segmentation . . . . . . .4.2.2 Algorithms for Contiguous Allocation4.3 Paging and Virtual Memory . . . . . . . . . .4.3.1 The Concept of Paging . . . . . . . . .4.3.2 Benefits and Costs . . . . . . . . . . .4.3.3 Address Translation . . . . . . . . . .4.3.4 Algorithms for Page Replacement . . .4.3.5 Disk Space Allocation . . . . . . . . . .4.4 Swapping . . . . . . . . . . . . . . . . . . . . .4.5 Summary . . . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . . 0103103106108114119120121122
5 File Systems5.1 What is a File? . . . . . . . . . . . . . . . .5.2 File Naming . . . . . . . . . . . . . . . . .5.2.1 Directories . . . . . . . . . . . . . .5.2.2 Links . . . . . . . . . . . . . . . . .5.2.3 Alternatives for File Identification5.3 Access to File Data . . . . . . . . . . . . .5.3.1 Data Access . . . . . . . . . . . . .5.3.2 Caching and Prefetching . . . . . .5.3.3 Memory-Mapped Files . . . . . . .5.4 Storing Files on Disk . . . . . . . . . . . .5.4.1 Mapping File Blocks . . . . . . . .5.4.2 Data Layout on the Disk . . . . . .5.4.3 Reliability . . . . . . . . . . . . . .5.5 Summary . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . .C Mechanics of Disk AccessC.1 Addressing Disk Blocks . .C.2 Disk Scheduling . . . . . .C.3 The Unix Fast File SystemBibliography . . . . . . . . . . .6 Review of Basic Principles6.1 Virtualization . . . . . . . . . . . .6.2 Resource Management . . . . . . .6.3 Reduction . . . . . . . . . . . . . . .6.4 Hardware Support and Co-Design.III Crosscutting 47148.150150151152153.1541541551581591617 Identification, Permissions, and Security7.1 System Security . . . . . . . . . . . . . . .7.1.1 Levels of Security . . . . . . . . . .7.1.2 Mechanisms for Restricting Access7.2 User Identification . . . . . . . . . . . . .7.3 Controling Access to System Objects . . .7.4 Summary . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . .iv.162162163164165166168169
8 SMPs and Multicore8.1 Operating Systems for SMPs . . . .8.1.1 Parallelism vs. Concurrency .8.1.2 Kernel Locking . . . . . . . .8.1.3 Conflicts . . . . . . . . . . . .8.1.4 SMP Scheduling . . . . . . . .8.1.5 Multiprocessor Scheduling . .8.2 Supporting Multicore 01202202203205206D Self-Similar WorkloadsD.1 Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .D.2 The Hurst Effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208208210211.9 Operating System Structure9.1 System Composition . . . . . . . . . . . .9.2 Monolithic Kernel Structure . . . . . . . .9.2.1 Code Structure . . . . . . . . . . .9.2.2 Data Structures . . . . . . . . . . .9.2.3 Preemption . . . . . . . . . . . . . .9.3 Microkernels . . . . . . . . . . . . . . . . .9.4 Extensible Systems . . . . . . . . . . . . .9.5 Operating Systems and Virtual MachinesBibliography . . . . . . . . . . . . . . . . . . . .10 Performance Evaluation10.1 Performance Metrics . . . . . . . . . . . . . . . . . . . .10.2 Workload Considerations . . . . . . . . . . . . . . . . . .10.2.1 Statistical Characterization of Workloads . . . .10.2.2 Workload Behavior Over Time . . . . . . . . . .10.3 Analysis, Simulation, and Measurement . . . . . . . . .10.4 Modeling: the Realism/Complexity Tradeoff . . . . . . .10.5 Queueing Systems . . . . . . . . . . . . . . . . . . . . . .10.5.1 Waiting in Queues . . . . . . . . . . . . . . . . .10.5.2 Queueing Analysis . . . . . . . . . . . . . . . . .10.5.3 Open vs. Closed Systems . . . . . . . . . . . . . .10.6 Simulation Methodology . . . . . . . . . . . . . . . . . .10.6.1 Incremental Accuracy . . . . . . . . . . . . . . .10.6.2 Workloads: Overload and (Lack of) Steady State10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . .v.
11 Technicalities11.1 Booting the System . . . . . . . . . . . .11.2 Timers . . . . . . . . . . . . . . . . . . .11.3 Kernel Priorities . . . . . . . . . . . . . .11.4 Logging into the System . . . . . . . . .11.4.1 Login . . . . . . . . . . . . . . . .11.4.2 The Shell . . . . . . . . . . . . . .11.5 Starting a Process . . . . . . . . . . . . .11.5.1 Constructing the Address Space11.6 Context Switching . . . . . . . . . . . . .11.7 Making a System Call . . . . . . . . . .11.7.1 Kernel Address Mapping . . . . .11.7.2 To Kernel Mode and Back . . . .11.8 Error Handling . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . .IV.Communication and Distributed Systems12 Interprocess Communication12.1 Naming . . . . . . . . . . . . . . . . . . . . . . . .12.2 Programming Interfaces and Abstractions . . . .12.2.1 Shared Memory . . . . . . . . . . . . . . .12.2.2 Remote Procedure Call . . . . . . . . . . .12.2.3 Message Passing . . . . . . . . . . . . . .12.2.4 Streams: Unix Pipes, FIFOs, and Sockets12.3 Sockets and Client-Server Systems . . . . . . . .12.3.1 Distributed System Structures . . . . . .12.3.2 The Sockets Interface . . . . . . . . . . . .12.4 Middleware . . . . . . . . . . . . . . . . . . . . . .12.5 Summary . . . . . . . . . . . . . . . . . . . . . . .Bibliography . . . . . . . . . . . . . . . . . . . . . . . .13 (Inter)networking13.1 Communication Protocols . . . . . . .13.1.1 Protocol Stacks . . . . . . . . .13.1.2 The TCP/IP Protocol Suite . . .13.2 Implementation Issues . . . . . . . . .13.2.1 Error Detection and Correction13.2.2 Buffering and Flow Control . .13.2.3 TCP Congestion Control . . . .13.2.4 Routing . . . . . . . . . . . . . .13.3 Summary . . . . . . . . . . . . . . . . 39243246246249251255257
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25814 Distributed System Services14.1 Authentication and Security14.1.1 Authentication . . . .14.1.2 Security . . . . . . . .14.2 Networked File Systems . .14.3 Load Balancing . . . . . . .Bibliography . . . . . . . . . . . .E Using Unix Pipes.260260260262263267270271F The ISO-OSI Communication Model274Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275vii
viii
Part IBackgroundWe start with an introductory chapter, that deals with what operating systems are,and the context in which they operate. In particular, it emphasizes the issues ofsoftware layers and abstraction, and the interaction between the operating systemand the hardware.This is supported by an appendix reviewing some background information on computer architecture.
Chapter 1IntroductionIn the simplest scenario, the operating system is the first piece of software to run on acomputer when it is booted. Its job is to coordinate the execution of all other software,mainly user applications. It also provides various common services that are neededby users and applications.1.1 Operating System FunctionalityThe operating system controls the machineIt is common to draw the following picture to show the place of the operating system:userapplicationoperating systemhardwareThis is a misleading picture, because applications mostly execute machine instructions that do not go through the operating system. A better picture is:2
applicationsystemcallsnon egedinstructionsinterruptshardwarewhere we have used a 3-D perspective to show that there is one hardware base, oneoperating system, but many applications. It also shows the important interfaces: applications can execute only non-privileged machine instructions, and they may alsocall upon the operating system to perform some service for them. The operating system may use privileged instructions that are not available to applications. And inaddition, various hardware devices may generate interrupts that lead to the execution of operating system code.A possible sequence of actions in such a system is the following:1. The operating system executes, and schedules an application (makes it run).2. The chosen application runs: the CPU executes its (non-privileged) instructions,and the operating system is not involved at all.3. The system clock interrupts the CPU, causing it to switch to the clock’s interrupthandler, which is an operating system function.4. The clock interrupt handler updates the operating system’s notion of time, andcalls the scheduler to decide what to do next.5. The operating system scheduler chooses another application to run in place ofthe previous one, thus performing a context switch.6. The chosen application runs directly on the hardware; again, the operating system is not involved. After some time, the application performs a system call toread from a file.7. The system call causes a trap into the operating system The operating systemsets things up for the I/O operation (using some privileged instructions). It thenputs the calling application to sleep, to await the I/O completion, and choosesanother application to run in its place.8. The third application runs.3
The important thing to notice is that at any given time, only one program is running1 .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 themachine. It regains control if the user application performs a system call, or if thereis a hardware interrupt.Exercise 1 How can the operating system guarantee that there will be a system call orinterrupt, so that it will regain control?The operating system is a reactive programAnother important thing to notice is that the operating system is a reactive program.It does not get an input, do some processing, and produce an output. Instead, it isconstantly waiting for some event to happen. When the event happens, the operatingsystem reacts. This usually involves some administration to handle whatever it isthat happened. Then the operating system schedules another application, and waitsfor the next event.Because it is a reactive system, the logical flow of control is also different. “Normal” programs, which accept an input and compute an output, have a main functionthat is the program’s entry point. main typically calls other functions, and when it returns the program terminates. An operating system, in contradistinction, has manydifferent entry points, one for each event type. And it is not supposed to terminate —when it finishes handling one event, it just waits for the next event.Events can be classified into two types: interrupts and system calls. These aredescribed in more detail below. The goal of the operating system is to run as little aspossible, handle the events quickly, and let applications run most of the time.Exercise 2 Make a list of applications you use in everyday activities. Which of themare reactive? Are reactive programs common or rare?The operating system performs resource managementOne of the main features of operating systems is support for multiprogramming. Thismeans that multiple programs may execute “at the same time”. But given that thereis only one processor, this concurrent execution is actually a fiction. In reality, theoperating system juggles the system’s resources between the competing programs,trying to make it look as if each one has the computer for itself.At the heart of multiprogramming lies resource management — deciding whichrunning program will get what resources. Resource management is akin to the shortblanket problem: everyone wants to be covered, but the blanket is too short to covereveryone at once.1This is not strictly true on modern microprocessors with hyper-threading or multiple cores, butwe’ll assume a simple single-CPU system for now.4
The resources in a computer system include the obvious pieces of hardware neededby programs: The CPU itself. Memory to store programs and their data. Disk space for files.But there are also internal resources needed by the operating system: Disk space for paging memory. Entries in system tables, such as the process table and open files table.All the applications want to run on the CPU, but only one can run at a time.Therefore the operating system lets each one run for a short while, and then preemptsit and gives the CPU to another. This is called time slicing. The decision about whichapplication to run is scheduling (discussed in Chapter 2).As for memory, each application gets some memory frames to store its code anddata. If the sum of the requirements of all the applications is more than the available physical memory, paging is used: memory pages that are not currently used aretemporarily stored on disk (we’ll get to this in Chapter 4).With disk space (and possibly also with entries in system tables) there is usuallya hard limit. The system makes allocations as long as they are possible. When theresource runs out, additional requests are failed. However, they can try again later,when some resources have hopefully been released by their users.Exercise 3 As system tables are part of the operating system, they can be made as bigas we want. Why is this a bad idea? What sizes should be chosen?The operating system provides servicesIn addition, the operating system provides various services to the applications running on the system. These services typically have two aspects: abstraction and isolation.Abstraction means that the services provide a more convenient working environment for applications, by hiding some of the details of the hardware, and allowing theapplications to operate at a higher level of abstraction. For example, the operatingsystem provides the abstraction of a file system, and applications don’t need to handleraw disk interfaces directly.Isolation means that many applications can co-exist at the same time, using thesame hardware devices, without falling over each other’s feet. These two issues arediscussed next. For example, if several applications send and receive data over anetwork, the operating system keeps the data streams separated from each other.5
1.2 Abstraction and VirtualizationThe operating system presents an abstract machineThe dynamics of a multiprogrammed computer system are rather complex: each application runs for some time, then it is preemp
1.1 Operating System Functionality The operating system controls the machine It is common to draw the following picture to show the place of the operating system: application operating system hardware user This is a misleading picture, because applications mostly execute machine instruc-tions that do not go through the operating system.
Part I Background We start with two introductory chapters. The first deals with what operating systems are, and the context in which they operate.
GEOMETRY NOTES Lecture 1 Notes GEO001-01 GEO001-02 . 2 Lecture 2 Notes GEO002-01 GEO002-02 GEO002-03 GEO002-04 . 3 Lecture 3 Notes GEO003-01 GEO003-02 GEO003-03 GEO003-04 . 4 Lecture 4 Notes GEO004-01 GEO004-02 GEO004-03 GEO004-04 . 5 Lecture 4 Notes, Continued GEO004-05 . 6
Operating Systems, Embedded Systems, and Real-Time Systems Janez Puhan Ljubljana, 2015. CIP-CatalogingInPublication NationalandUniversityLibrary,Ljubljana 004.451(078.5)(0.034.2) PUHAN,Janez,1969-Operating Systems, Embedded Systems, and Real-Time Systems [Electronic
Operating Systems: Design and Implementation, 3rd edition This popular text on operating systems is the only book covering both the princi ples of operating systems and their application to a real system. All the traditional operating systems topics are covered in detail. In addition, the principles are care
Operating Systems and Utility Programs Describe the two types of software Understand the startup process for a personal computer Describe the term user interface Explain features common to most operating systems Know the difference between stand-alone operating systems and network operating systems Identify various stand-alone operating systems
Chris Dupont Operating Systems Programmer/Analyst 3 Theresa Chu Operating Systems Programmer/Analyst 3 Gabe Abreu Operating Systems Programmer/Analyst 1 Temitope Leshi Operating Systems Programmer/Analyst 1 Identity and Acceess Management Dylan Marquis Operating Systems Porgrammer/Anlayst 3 R
notes.cc.sunysb.edu Step 4: Launch Notes for the First Time Click the Notes icon in your Dock, or double-click the Notes icon in the Lotus Notes folder. Click New Setup Click Next. In the Your name box enter your first and last name, as listed in the SUNYSB Address Book. In the Domino server name box, enter notes.cc.sunysb.edu.
Taking responsibility for our own physical, emotional, mental and spiritual well-being can be a radical political act in these times where legislation and standardised medical practice often support or even create ill-health. Also, rapid cultural change has been facilitated through access to personal computer technology. It is now easy to find ‘alternative versions’ of events, both .
