• Have any questions?
  • info.zbook.org@gmail.com

Advanced Topic In Operating Systems Lecture Notes

6m ago
26 Views
0 Downloads
2.69 MB
96 Pages
Last View : 8d ago
Last Download : n/a
Upload by : Laura Ramon
Share:
Transcription

Advanced Topic in Operating SystemsLecture NotesDr. Warren ToomeySchool of Information TechnologyBond UniversityQueensland, AustraliaWith quotes from ‘The New Hacker’s Dictionary’Third Session, 2003c 1992-2003, Warren Toomey

Contents1 Introduction to Operating Systems11.1What is an Operating System? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2Kernel Mode and User Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21.3Other System Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21.4Types of Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32 Design Principles & Concepts32.1The Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.2Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.3Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.4Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.5Operating System Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.6Unix and Laboratory Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52.7Operating System Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.8The Monolithic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.9Client-Server Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 The OS/Machine Interface103.1The CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103.2Main Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .113.3Buses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .113.4Peripheral Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .133.5Interrupts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143.6Interrupt Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143.7The OS vs The User . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153.8Traps and System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154 Operating System History and Evolution164.11st Generation: 1945 – 1955 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .164.22nd Generation: 1955 – 1965 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .174.33rd Generation: 1965 – 1980 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .184.4Timesharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .184.53rd Generation – Part 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .194.64th Generation: 1980 onwards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195 Processes205.1What is a Process? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205.2The Process Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20i

5.3System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205.4Layout of a Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205.5Process Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215.6How the Operating System Deals with System Calls . . . . . . . . . . . . . . . . . . . . . . .225.7Process Control Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .235.8Context Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .246 Process Scheduling256.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .256.2Scheduling Algorithms – Interactive (Pre-emption) . . . . . . . . . . . . . . . . . . . . . . . .266.3First Come First Served/ Round Robin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .266.4Timeslice Priority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .266.5Multiple Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .276.6Long-Term Schedulers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .276.7The Unix Long-Term Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .276.8Which is the Right Scheduling Algorithm to Use? . . . . . . . . . . . . . . . . . . . . . . . .286.9The Idle Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .287 Introduction to Input/Output297.1Why does the Operating System do I/O? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .297.2Devices and the Machine Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .297.3Direct Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .308 Principles of Input/Output318.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .318.2Goals of I/O Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .318.3Interrupt Handlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .328.4Device Drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .338.5The Device-Independent Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .338.6Clocks – Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .348.7Clocks – Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .359 Device Drivers and Interrupt Handlers3510 The Disk Device3610.1 Disk Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3710.2 Disk Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3710.3 Arm Scheduling – FCFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3810.4 Shortest Seek Time First . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3810.5 SCAN Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38ii

10.6 C-SCAN Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3910.7 Sector Queueing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4010.8 Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4010.9 Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4010.10Recent Disk Advances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4111 Terminals4111.1 Terminal Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4111.2 Serial Terminal Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4211.3 Memory-Mapped Terminals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4311.4 Terminal Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4311.5 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4412 Introduction to Memory Management4512.1 What is Memory & Why Manage It? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4512.2 Process Compilation & Memory Locations . . . . . . . . . . . . . . . . . . . . . . . . . . . .4512.3 Bare Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4612.4 Operating System in ROM – Resident Monitor . . . . . . . . . . . . . . . . . . . . . . . . . .4612.5 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4612.6 Allocating & Placing Partitions in Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . .4713 Pages4813.1 Problems with Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4813.2 Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4913.3 An Example Page Entry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5013.4 Pages vs. Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5113.5 Huge Logical Memory Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5113.6 Problems of Paged Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5113.7 Sharing Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5213.8 Copy-on-Write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5213.9 Operating System Use of Page Entry Protections . . . . . . . . . . . . . . . . . . . . . . . . .5314 Virtual Memory5314.1 Why Use Virtual Memory? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5414.2 Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5414.3 Paging – How It Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5414.4 Hardware Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5514.5 Optimal Page Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5514.6 Not Recently Used Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56iii

14.7 FIFO Algorithm – First In, First Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5614.8 Second Chance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5614.9 Least Recently Used (LRU) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5614.10VM Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5714.11Initial Process Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5815 Introduction to File Systems5815.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5815.2 What’s a File? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5815.3 File Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5915.4 File Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5915.5 Directories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6015.6 Filesystem Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6115.7 Directory Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6115.8 File System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6216 File System Layout6516.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6516.2 The MS-DOS Filesystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6516.3 The System V Unix Filesystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6616.4 The Berkeley Fast Filesystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6817 File System Reliability & Performance6917.1 File System Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6917.2 Bad Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7017.3 Backups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7017.4 File System Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7017.5 File System Performance – Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7117.6 File Block Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7217.7 Holey Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7218 Interprocess Communication (IPC)7218.1 Why Do Processes Intercommunicate? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7218.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7318.3 Pipes – Unidirectional Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7318.4 Bidirectional Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7318.5 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7418.6 Remote Procedure Call – RPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7418.7 Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .76iv

19 Synchronisation7619.1 Race Conditions and Critical Sections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7619.2 Avoiding a Critical Section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7719.3 Infinite Timeslices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7719.4 Strict Alternation/Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7719.5 Test and Set Lock Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7819.6 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7819.7 Monitors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7919.8 Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7919.9 Synchronisation Within the Operating System . . . . . . . . . . . . . . . . . . . . . . . . . .8020 Threads8120.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8120.2 Kernel Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8320.3 Lightweight Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8320.4 Mediumweight Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8420.5 User Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8420.6 Performance Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8421 Windows NT8521.1 Overall Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8621.2 Environment Subsystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8721.3 Processes and Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8721.4 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8921.5 Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9021.6 The NT Filesystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90v

1 Introduction to Operating Systems1.1 What is an Operating System?Textbook reference: Stallings ppg 53 – 100; Tanenbaum & Woodhull ppg 1 – 5Without software, a computer is effectively useless. Computer software controls the use of the hardware(CPU, memory, disks etc.), and makes the computer into a useful tool for its users.In most computers, the software can be regarded as a set of layers, as shown in the following diagram.Each layer hides much of the complexity of the layer below, and provides a set of abstract services andconcepts to the layer above.MoreabstractUsersApplication ProgramsSystem SoftwareLessabstractComputer HardwareFor example, the computer’s hard disk allows data to be stored on it in a set of fixed-sized blocks. Thesystem software hides this complexity, and provides the concept of files to the application software. Inturn, an application program such as a word processor hides the idea of a file, and allows the user to workwith documents instead.Computer software can be thus be divided into 2 categories: system software, which manages the computer’s operation, and applications software, which allows users to do useful things.The most fundamental of all system software is the operating system. It has three main tasks to perform. The operating system must shield the details of the hardware from the application programs, andthus from the user. The operating system has to provide a set of abstract services to the application programs, instead.When applications use these abstract services, the operations must be translated into real hardwareoperations. Finally, the resources in a computer (CPU, memory, disk space) are limited. The operating systemmust act as a resource manager, optimising the use of the resources, and protecting them againstmisuse and abuse. When a system provides multiuser or multitasking capabilities, resources mustbe allocated fairly and equitably amongst a number of competing requests.operating system: (Often abbreviated ‘OS’) The foundation software of a machine, of course; that whichschedules tasks, allocates storage, and presents a default interface to the user between applications.The facilities an operating system provides and its general design philosophy exert an extremely stronginfluence on programming style and on the technical cultures that grow up around its host machines.1

1.2 Kernel Mode and User ModeTextbook reference: Tanenbaum & Woodhull pg 3Because an operating system must hide the computer’s hardware, and manage the hardware resources,it needs to prevent the application software from accessing the hardware directly. Without this sort ofprotection, the operating system would not be able to do its job.The computer’s CPU provides two modes of operation which enforce this protection. The operatingsystem runs in kernel mode, also known as supervisor mode or privileged mode. In kernel mode, thesoftware has complete access to all of the computer’s hardware, and can control the switching betweenthe CPU modes.The rest of the software runs in user mode. In this mode, direct access to the hardware is prohibited, andso is any arbitrary switching to kernel mode. Any attempts to violate these restrictions are reported to thekernel mode software: in other words, to the operating system itself.By having two modes of operation which are enforced by the computer’s own hardware, the operatingsystem can force application programs to use the operating system’s abstract services, instead of circumventing any resource allocations by direct hardware access.1.3 Other System SoftwareTextbook reference: Tanenbaum & Woodhull pg 2Before we go on with our introduction to operating systems, we should look at what other system softwarethere amsUserprogramsUsermodeLibrary routinesSystem callsOperating SystemLessabstractKernelmodeComputer HardwareAt the top of the operating system are th

Operating System mode Library routines At the top of the operating system are the system calls. These are the set of abstract operations that the operating system provides to the applications programs, and thus are also known as the application pro-gram interface, or API. This interface is generally constant: users cannot change what is in the .