Transcription of Notes on Operating Systems - cs.huji.ac.il
1 Notes on Operating SystemsDror G. FeitelsonSchool of Computer Science and EngineeringThe Hebrew University of Jerusalem91904 Jerusalem, Israelc 2011 ContentsI Background11 Operating System Functionality .. Abstraction and Virtualization .. Hardware Support for the Operating System .. Roadmap .. Scope and Limitations .. 15 Bibliography .. 17A Background on Computer Architecture19II The Classics232 Processes and What Are Processes and Threads? .. Processes Provide Context .. Process States .. Threads .. Operations on Processes and Threads .. Multiprogramming: Having Multiple Processes in the System.
2 Multiprogramming and Responsiveness .. Multiprogramming and Utilization .. Multitasking for Concurrency .. The Cost .. Scheduling Processes and Threads .. Performance Metrics .. Handling a Given Set of Jobs .. Using Preemption .. Priority Scheduling .. Starvation, Stability, and Allocations .. Fair Share Scheduling .. Summary .. 54 Bibliography .. 56B UNIX Processes58 Bibliography .. 633 Mutual Exclusion for Shared Data Structures .. Concurrency and the Synchronization Problem .. Mutual Exclusion Algorithms .. Semaphores and Monitors .. Locks and Disabling Interrupts.
3 Multiprocessor Synchronization .. Resource Contention and Deadlock .. Deadlock and Livelock .. A Formal Setting .. Deadlock Prevention .. Deadlock Avoidance .. Deadlock Detection .. Real Life .. Lock-Free Programming .. Summary .. 92 Bibliography .. 934 Memory Mapping Memory Addresses .. Segmentation and Contiguous Allocation .. Support for Segmentation .. Algorithms for Contiguous Allocation .. Paging and Virtual Memory .. The Concept of Paging .. Benefits and Costs .. Address Translation .. Algorithms for Page Replacement .. Disk Space Allocation .. Swapping.
4 Summary .. 121 Bibliography .. 122iii5 File What is a File? .. File Naming .. Directories .. Links .. Alternatives for File Identification .. Access to File Data .. Data Access .. Caching and Prefetching .. Memory-Mapped Files .. Storing Files on Disk .. Mapping File Blocks .. Data Layout on the Disk .. Reliability .. Summary .. 147 Bibliography .. 148C Mechanics of Disk Addressing Disk Blocks .. Disk Scheduling .. The Unix Fast File System .. 152 Bibliography .. 1536 Review of Basic Virtualization .. Resource Management .. Reduction .. Hardware Support and Co-Design.
5 159 III Crosscutting Issues1617 Identification, Permissions, and System Security .. Levels of Security .. Mechanisms for Restricting Access .. User Identification .. Controling Access to System Objects .. Summary .. 168 Bibliography .. 169iv8 SMPs and Operating Systems for SMPs .. Parallelism vs. Concurrency .. Kernel Locking .. Conflicts .. SMP Scheduling .. Multiprocessor Scheduling .. Supporting Multicore Environments .. 1729 Operating System System Composition .. Monolithic Kernel Structure .. Code Structure .. Data Structures .. Preemption .. Microkernels .. Extensible Systems .
6 Operating Systems and Virtual Machines .. 180 Bibliography .. 18210 Performance Performance Metrics .. Workload Considerations .. Statistical Characterization of Workloads .. Workload Behavior Over Time .. Analysis, Simulation, and Measurement .. Modeling: the Realism/Complexity Tradeoff .. Queueing Systems .. Waiting in Queues .. Queueing Analysis .. Open vs. Closed Systems .. Simulation Methodology .. Incremental Accuracy .. Workloads: Overload and (Lack of) Steady State .. Summary .. 205 Bibliography .. 206D Self-Similar Fractals .. The Hurst Effect .. 210 Bibliography .. 211v11 Booting the System.
7 Timers .. Kernel Priorities .. Logging into the System .. Login .. The Shell .. Starting a Process .. Constructing the Address Space .. Context Switching .. Making a System Call .. Kernel Address Mapping .. To Kernel Mode and Back .. Error Handling .. 220 Bibliography .. 222IV Communication and Distributed Systems22312 Interprocess Naming .. Programming Interfaces and Abstractions .. Shared Memory .. Remote Procedure Call .. Message Passing .. Streams: Unix Pipes, FIFOs, and Sockets .. Sockets and Client-Server Systems .. Distributed System Structures .. The Sockets Interface .. Middleware.
8 Summary .. 237 Bibliography .. 23813 (Inter) Communication Protocols .. Protocol Stacks .. The TCP/IP Protocol Suite .. Implementation Issues .. Error Detection and Correction .. Buffering and Flow Control .. TCP Congestion Control .. Routing .. Summary .. 257viBibliography .. 25814 Distributed System Authentication and Security .. Authentication .. Security .. Networked File Systems .. Load Balancing .. 267 Bibliography .. 270E Using Unix Pipes271F The ISO-OSI Communication Model274 Bibliography .. 275viiviiiPart IBackgroundWe start with an introductory chapter, that deals with what Operating Systems are,and the context in which they operate.
9 In particular, it emphasizes the issues ofsoftware layers and abstraction, and the interaction betweenthe Operating systemand the is supported by an appendix reviewing some background information on com-puter 1 IntroductionIn 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 Operating System FunctionalityThe Operating system controls the machineIt is common to draw the following picture to show the place of the Operating system:applicationoperating systemhardwareuserThis is a misleading picture, because applications mostly execute machine instruc-tions that do not go through the Operating system.
10 A better picture is:2applicationcallssystemoperatingsyste mhardwareinterruptsinstructionsinstructi onsnon privilegedprivilegedmachinewhere 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: ap-plications can execute only non-privileged machine instructions, and they may alsocall 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 inaddition, various hardware devices may generate interrupts that lead to the execu-tion of Operating system possible sequence of actions in such a system is the following:1.
