Operating SystemsSteven HandMichaelmas Term 201012 lectures for CST IAOperating Systems — N/H/[email protected]

Course Aims This course aims to:– explain the structure and functions of an operating system,– illustrate key operating system aspects by concrete example, and– prepare you for future courses. . . At the end of the course you should be able to:––––compare and contrast CPU scheduling algorithmsexplain the following: process, address space, file.distinguish paged and segmented virtual memory.discuss the relative merits of Unix and NT. . .Operating Systems — Aimsi

Course Outline Introduction to Operating Systems. Processes & Scheduling. Memory Management. I/O & Device Management. Protection. Filing Systems. Case Study: Unix. Case Study: Windows NT.Operating Systems — Outlineii

Recommended Reading Concurrent Systems or Operating SystemsBacon J [ and Harris T ], Addison Wesley 1997 [2003] Operating Systems Concepts (5th Ed.)Silberschatz A, Peterson J and Galvin P, Addison Wesley 1998. The Design and Implementation of the 4.3BSD UNIX OperatingSystemLeffler S J, Addison Wesley 1989 Inside Windows 2000 (3rd Ed) or Windows Internals (4th Ed)Solomon D and Russinovich M, Microsoft Press 2000 [2005]Operating Systems — Booksiii

What is an Operating System? A program which controls the execution of all other programs(applications). Acts as an intermediary between the user(s) and the computer. Objectives:– convenience,– efficiency,– extensibility. Similar to a government. . .Operating Systems — Introduction1

App NApp 2App 1An Abstract ViewOperating SystemHardware The Operating System (OS):– controls all execution.– multiplexes resources between applications.– abstracts away from complexity. Typically also have some libraries and some tools provided with OS. Are these part of the OS? Is IE a tool?– no-one can agree. . . For us, the OS the kernel.Operating Systems — Introduction2

In The Beginning. . . 1949: First stored-program machine (EDSAC) to 1955: “Open Shop”.– large machines with vacuum tubes.– I/O by paper tape / punch cards.– user programmer operator. To reduce cost, hire an operator :– programmers write programs and submit tape/cards to operator.– operator feeds cards, collects output from printer. Management like it. Programmers hate it. Operators hate it. need something better.Operating Systems — Evolution3

Batch Systems Introduction of tape drives allow batching of jobs:–––––programmers put jobs on cards as before.all cards read onto a tape.operator carries input tape to computer.results written to output tape.output tape taken to printer. Computer now has a resident monitor :– initially control is in monitor.– monitor reads job and transfer control.– at end of job, control transfers back to monitor. Even better: spooling systems.– use interrupt driven I/O.– use magnetic disk to cache input tape.– fire operator. Monitor now schedules jobs. . .Operating Systems — Evolution4

Multi-ProgrammingJob 4Job 4Job 4Job 3Job 3Job 3Job 2Job 2Job 2Job 1OperatingSystemJob 1OperatingSystemJob 1OperatingSystemTime Use memory to cache jobs from disk more than one job active simultaneously. Two stage scheduling:1. select jobs to load: job scheduling.2. select resident job to run: CPU scheduling. Users want more interaction time-sharing: e.g. CTSS, TSO, Unix, VMS, Windows NT. . .Operating Systems — Evolution5

Today and Tomorrow Single user systems: cheap and cheerful.– personal computers.– no other users ignore protection.– e.g. DOS, Windows, Win 95/98, . . . RT Systems: power is nothing without control.– hard-real time: nuclear reactor safety monitor.– soft-real time: mp3 player. Parallel Processing: the need for speed.– SMP: 2–8 processors in a box.– MIMD: super-computing. Distributed computing: global processing?––––Java: the network is the computer.Clustering: the network is the bus.CORBA: the computer is the network.NET: the network is an enabling framework. . .Operating Systems — Evolution6

Monolithic Operating SystemsApp.App.App.App.SchedulerS/WDevice DriverDevice DriverH/W Oldest kind of OS structure (“modern” examples are DOS, original MacOS) Problem: applications can e.g.–––––trash OS software.trash another application.hoard CPU time.abuse I/O devices.etc. . . No good for fault containment (or multi-user). Need a better solution. . .Operating Systems — Structures & Protection Mechanisms7

Dual-Mode Operation Want to stop buggy (or malicious) program from doing bad things. provide hardware support to distinguish between (at least) two different modes ofoperation:1. User Mode : when executing on behalf of a user (i.e. application programs).2. Kernel Mode : when executing on behalf of the operating system. Hardware contains a mode-bit, e.g. 0 means kernel, 1 means user.interrupt or faultresetKernelModeUserModeset user mode Make certain machine instructions only possible in kernel mode. . .Operating Systems — Structures & Protection Mechanisms8

Protecting I/O & Memory First try: make I/O instructions privileged.– applications can’t mask interrupts.– applications can’t control I/O devices. But:1. Application can rewrite interrupt vectors.2. Some devices accessed via memory Hence need to protect memory also, e.g. define base and limit for each program:0xFFFFJob 40xD800Job 30x9800limit register0x4800Job 20x50000x30000x0000Job 1OperatingSystem0x5000base register Accesses outside allowed range are protected.Operating Systems — Structures & Protection Mechanisms9

Memory Protection Hardwarebase limityesCPUnoyesnoMemorybasevector to OS (address error) Hardware checks every memory reference. Access out of range vector into operating system (just as for an interrupt). Only allow update of base and limit registers in kernel mode. Typically disable memory protection in kernel mode (although a bad idea). In reality, more complex protection h/w used:– main schemes are segmentation and paging– (covered later on in course)Operating Systems — Structures & Protection Mechanisms10

Protecting the CPU Need to ensure that the OS stays in control.– i.e. need to prevent any a malicious or badly-written application from ‘hogging’the CPU the whole time. use a timer device. Usually use a countdown timer, e.g.1. set timer to initial value (e.g. 0xFFFF).2. every tick (e.g. 1µs), timer decrements value.3. when value hits zero, interrupt. (Modern timers have programmable tick rate.) Hence OS gets to run periodically and do its stuff. Need to ensure only OS can load timer, and that interrupt cannot be masked.– use same scheme as for other devices.– (viz. privileged instructions, memory protection) Same scheme can be used to implement time-sharing (more on this later).Operating Systems — Structures & Protection Mechanisms11

Kernel-Based Operating SystemsApp.App.App.App.UnprivPrivKernelSystem CallsSchedulerFile SystemS/WDevice DriverProtocol CodeDevice DriverH/W Applications can’t do I/O due to protection operating system does it on their behalf. Need secure way for application to invoke operating system: require a special (unprivileged) instruction to allow transition from user tokernel mode. Generally called a software interrupt since operates similarly to a real (hardware)interrupt. . . Set of OS services accessible via software interrupt mechanism called system calls.Operating Systems — Structures & Protection Mechanisms12

Microkernel Operating rverDeviceDriverKernelDeviceDriverSchedulerH/W Alternative structure:– push some OS services into servers.– servers may be privileged (i.e. operate in kernel mode). Increases both modularity and extensibility. Still access kernel via system calls, but need new way to access servers: interprocess communication (IPC) schemes.Operating Systems — Structures & Protection Mechanisms13

Kernels versus MicrokernelsSo why isn’t everything a microkernel? Lots of IPC adds overhead microkernels usually perform less well. Microkernel implementation sometimes tricky: need to worry about concurrencyand synchronisation. Microkernels often end up with redundant copies of OS data structures.Hence today most common operating systems blur the distinction between kerneland microkernel. e.g. linux is a “kernel”, but has kernel modules and certain servers. e.g. Windows NT was originally microkernel (3.5), but now (4.0 onwards) pushedlots back into kernel for performance. Still not clear what the best OS structure is, or how much it really matters. . .Operating Systems — Structures & Protection Mechanisms14

Operating System Functions Regardless of structure, OS needs to securely multiplex resources:1. protect applications from each other, yet2. share physical resources between them. Also usually want to abstract away from grungy harware, i.e. OSprovides a virtual machine:– share CPU (in time) and provide each app with a virtual processor,– allocate and protect memory, and provide applications with theirown virtual address space,– present a set of (relatively) hardware independent virtual devices,– divide up storage space by using filing systems, and– do all this within the context of a security framework. Remainder of this part of the course will look at each of the aboveareas in turn. . .Operating Systems — Functions15

Process Concept From a user’s point of view, the operating system is there to execute programs:– on batch system, refer to jobs– on interactive system, refer to processes– (we’ll use both terms fairly interchangeably) Process 6 Program:– a program is static, while a process is dynamic – in fact, a process “a program in execution” (Note: “program” here is pretty low level, i.e. native machine code or executable) Process includes:1. program counter2. stack3. data section Processes execute on virtual processorsOperating Systems — Processes16

Process utor yieldevent-waiteventBlocked As a process executes, it changes state:– New: the process is being created– Running: instructions are being executed– Ready: the process is waiting for the CPU (and is prepared to run at any time)– Blocked: the process is waiting for some event to occur (and cannot run until itdoes)– Exit: the process has finished execution. The operating system is responsible for maintaining the state of each process.Operating Systems — Processes17

Process Control BlockProcess Number (or Process ID)Current Process StateCPU Scheduling InformationProgram CounterOther CPU RegistersMemory Mangement InformationOther Information(e.g. list of open files, name ofexecutable, identity of owner, CPUtime used so far, devices owned)Refs to previous and next PCBsOS maintains information about every process in a data structure called a processcontrol block (PCB): Unique process identifierProcess state (Running, Ready, etc.)CPU scheduling & accounting informationProgram counter & CPU registersMemory management information.Operating Systems — Processes18

Context SwitchingProcess AOperating SystemexecutingProcess BidleSave State into PCB AidleRestore State from PCB BexecutingSave State into PCB BidleexecutingRestore State from PCB A Process Context machine environment during the time the process is activelyusing the CPU. i.e. context includes program counter, general purpose registers, processor statusregister (with C, N, V and Z flags), . . . To switch between processes, the OS must:a) save the context of the currently executing process (if any), andb) restore the context of that being resumed. Time taken depends on h/w support.Operating Systems — Processes19

Scheduling QueuesJobQueueReady QueueadmitdispatchCPUreleasetimeout or yieldWait Queue(s)eventevent-waitcreatecreate(batch) (interactive) Job Queue: batch processes awaiting admission. Ready Queue: set of all processes residing in main memory, ready to execute. Wait Queue(s): set of processes waiting for an I/O device (or for other processes) Long-term & short-term schedulers:– Job scheduler selects which processes should be brought into the ready queue.– CPU scheduler decides which process should be executed next and allocates theCPU to it.Operating Systems — Process Life-cycle20

Process Creation Nearly all systems are hierarchical : parent processes create children processes. Resource sharing:– parent and children share all resources, or– children share subset of parent’s resources, or– parent and child share no resources. Execution:– parent and children execute concurrently, or– parent waits until children terminate. Address space:– child is duplicate of parent or– child has a program loaded into it. e.g. on Unix: fork() system call creates a new process– all resources shared (i.e. child is a clone).– execve() system call used to replace process’ memory with a new program. NT/2K/XP: CreateProcess() syscall includes name of program to be executed.Operating Systems — Process Life-cycle21

Process Termination Process executes last statement and asks the operating system to delete it (exit):– output data from child to parent (wait)– process’ resources are deallocated by the OS. Process performs an illegal operation, e.g.– makes an attempt to access memory to which it is not authorised,– attempts to execute a privileged instruction Parent may terminate execution of child processes (abort, kill), e.g. because––––child has exceeded allocated resourcestask assigned to child is no longer requiredparent is exiting (“cascading termination”)(many operating systems do not allow a child to continue if its parentterminates) e.g. Unix has wait(), exit() and kill() e.g. NT/2K/XP has ExitProcess() for self termination andTerminateProcess() for killing others.Operating Systems — Process Life-cycle22

Process Blocking In general a process blocks on an event, e.g.– an I/O device completes an operation,– anot