操作系统 - Operating System.ppt

1、1,Operating System 【1-4】,Chapter 1,2,Chapter 1,1.1 What is an operating system 1.2 History of operating systems 1.3 The operating system zoo 1.4 Computer hardware review 1.5 Operating system concepts 1.6 System calls 1.7 Operating system structure,Introduction,3,Introduction,A computer system consis

2、ts of hardware system programs application programs,4,What is an Operating System,It is an extended machine Hides the messy details which must be performed Presents user with a virtual machine, easier to use It is a resource manager Each program gets time with the resource Each program gets space on

3、 the resource,5,History of Operating Systems (1),Early batch system bring cards to 1401 read cards to tape put tape on 7094 which does computing put tape on 1401 which prints output,6,History of Operating Systems (2),First generation 1945 - 1955 vacuum tubes, plug boards Second generation 1955 - 196

4、5 transistors, batch systems Third generation 1965 1980 ICs and multiprogramming Fourth generation 1980 present personal computers,7,History of Operating Systems (3),Structure of a typical FMS job 2nd generation,8,History of Operating Systems (4),Multiprogramming system three jobs in memory 3rd gene

5、ration,9,The Operating System Zoo,Mainframe operating systems Server operating systems Multiprocessor operating systems Personal computer operating systems Real-time operating systems Embedded operating systems Smart card operating systems,10,Computer Hardware Review (1),Components of a simple perso

6、nal computer,Monitor,Bus,11,Computer Hardware Review (2),(a) A three-stage pipeline (b) A superscalar CPU,12,Computer Hardware Review (3),Typical memory hierarchy numbers shown are rough approximations,13,Computer Hardware Review (4),Structure of a disk drive,14,Computer Hardware Review (5),One base

7、-limit pair and two base-limit pairs,15,Computer Hardware Review (6),(a) Steps in starting an I/O device and getting interrupt (b) How the CPU is interrupted,(a),(b),16,Computer Hardware Review (7),Structure of a large Pentium system,17,Operating System Concepts (1),A process tree A created two chil

8、d processes, B and C B created three child processes, D, E, and F,18,Operating System Concepts (2),(a) A potential deadlock. (b) an actual deadlock.,19,Operating System Concepts (3),File system for a university department,20,Operating System Concepts (4),Before mounting, files on floppy are inaccess

9、ible After mounting floppy on b, files on floppy are part of file hierarchy,21,Operating System Concepts (5),Two processes connected by a pipe,22,Steps in Making a System Call,There are 11 steps in making the system call read (fd, buffer, nbytes),23,Some System Calls For Process Management,24,Some S

10、ystem Calls For File Management,25,Some System Calls For Directory Management,26,Some System Calls For Miscellaneous Tasks,27,System Calls (1),A stripped down shell: while (TRUE) /* repeat forever */ type_prompt( );/* display prompt */ read_command (command, parameters)/* input from terminal */ if (

11、fork() != 0) /* fork off child process */ /* Parent code */ waitpid( -1, /* execute command */ ,28,System Calls (2),Processes have three segments: text, data, stack,29,System Calls (3),(a) Two directories before linking/usr/jim/memo to asts directory (b) The same directories after linking,30,System

12、Calls (4),(a) File system before the mount (b) File system after the mount,31,System Calls (5),Some Win32 API calls,32,Operating System Structure (1),Simple structuring model for a monolithic system,33,Operating System Structure (2),Structure of the THE operating system,34,Operating System Structure

13、 (3),Structure of VM/370 with CMS,35,Operating System Structure (4),The client-server model,36,Operating System Structure (5),The client-server model in a distributed system,37,Metric Units,The metric prefixes,38,Chapter 2,2.1 Processes 2.2 Threads 2.3 Interprocess communication 2.4 Classical IPC pr

14、oblems 2.5 Scheduling,Processes and Threads,39,ProcessesThe Process Model,Multiprogramming of four programs Conceptual model of 4 independent, sequential processes Only one program active at any instant,40,Process Creation,Principal events that cause process creation System initialization Execution

15、of a process creation system User request to create a new process Initiation of a batch job,41,Process Termination,Conditions which terminate processes Normal exit (voluntary) Error exit (voluntary) Fatal error (involuntary) Killed by another process (involuntary),42,Process Hierarchies,Parent creat

16、es a child process, child processes can create its own process Forms a hierarchy UNIX calls this a process group Windows has no concept of process hierarchy all processes are created equal,43,Process States (1),Possible process states running blocked ready Transitions between states shown,44,Process

17、 States (2),Lowest layer of process-structured OS handles interrupts, scheduling Above that layer are sequential processes,45,Implementation of Processes (1),Fields of a process table entry,46,Implementation of Processes (2),Skeleton of what lowest level of OS does when an interrupt occurs,47,Thread

18、sThe Thread Model (1),(a) Three processes each with one thread (b) One process with three threads,48,The Thread Model (2),Items shared by all threads in a process Items private to each thread,49,The Thread Model (3),Each thread has its own stack,50,Thread Usage (1),A word processor with three thread

19、s,51,Thread Usage (2),A multithreaded Web server,52,Thread Usage (3),Rough outline of code for previous slide (a) Dispatcher thread (b) Worker thread,53,Thread Usage (4),Three ways to construct a server,54,Implementing Threads in User Space,A user-level threads package,55,Implementing Threads in the

20、 Kernel,A threads package managed by the kernel,56,Hybrid Implementations,Multiplexing user-level threads onto kernel- level threads,57,Scheduler Activations,Goal mimic functionality of kernel threads gain performance of user space threads Avoids unnecessary user/kernel transitions Kernel assigns vi

21、rtual processors to each process lets runtime system allocate threads to processors Problem: Fundamental reliance on kernel (lower layer) calling procedures in user space (higher layer),58,Pop-Up Threads,Creation of a new thread when message arrives (a) before message arrives (b) after message arriv

22、es,59,Making Single-Threaded Code Multithreaded (1),Conflicts between threads over the use of a global variable,60,Making Single-Threaded Code Multithreaded (2),Threads can have private global variables,61,Interprocess CommunicationRace Conditions,Two processes want to access shared memory at same t

23、ime,62,Critical Regions (1),Four conditions to provide mutual exclusion No two processes simultaneously in critical region No assumptions made about speeds or numbers of CPUs No process running outside its critical region may block another process No process must wait forever to enter its critical r

24、egion,63,Critical Regions (2),Mutual exclusion using critical regions,64,Mutual Exclusion with Busy Waiting (1),Proposed solution to critical region problem (a) Process 0. (b) Process 1.,65,Mutual Exclusion with Busy Waiting (2),Petersons solution for achieving mutual exclusion,66,Mutual Exclusion w

25、ith Busy Waiting (3),Entering and leaving a critical region using the TSL instruction,67,Sleep and Wakeup,Producer-consumer problem with fatal race condition,68,Semaphores,The producer-consumer problem using semaphores,69,Mutexes,Implementation of mutex_lock and mutex_unlock,70,Monitors (1),Example

26、of a monitor,71,Monitors (2),Outline of producer-consumer problem with monitors only one monitor procedure active at one time buffer has N slots,72,Monitors (3),Solution to producer-consumer problem in Java (part 1),73,Monitors (4),Solution to producer-consumer problem in Java (part 2),74,Message Pa

27、ssing,The producer-consumer problem with N messages,75,Barriers,Use of a barrier processes approaching a barrier all processes but one blocked at barrier last process arrives, all are let through,76,Dining Philosophers (1),Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to pr

28、event deadlock,77,Dining Philosophers (2),A nonsolution to the dining philosophers problem,78,Dining Philosophers (3),Solution to dining philosophers problem (part 1),79,Dining Philosophers (4),Solution to dining philosophers problem (part 2),80,The Readers and Writers Problem,A solution to the read

29、ers and writers problem,81,The Sleeping Barber Problem (1),82,The Sleeping Barber Problem (2),Solution to sleeping barber problem.,83,SchedulingIntroduction to Scheduling (1),Bursts of CPU usage alternate with periods of I/O wait a CPU-bound process an I/O bound process,84,Introduction to Scheduling

30、 (2),Scheduling Algorithm Goals,85,Scheduling in Batch Systems (1),An example of shortest job first scheduling,86,Scheduling in Batch Systems (2),Three level scheduling,87,Scheduling in Interactive Systems (1),Round Robin Scheduling list of runnable processes list of runnable processes after B uses

31、up its quantum,88,Scheduling in Interactive Systems (2),A scheduling algorithm with four priority classes,89,Scheduling in Real-Time Systems,Schedulable real-time system Given m periodic events event i occurs within period Pi and requires Ci seconds Then the load can only be handled if,90,Policy ver

32、sus Mechanism,Separate what is allowed to be done with how it is done a process knows which of its children threads are important and need priority Scheduling algorithm parameterized mechanism in the kernel Parameters filled in by user processes policy set by user process,91,Thread Scheduling (1),Po

33、ssible scheduling of user-level threads 50-msec process quantum threads run 5 msec/CPU burst,92,Thread Scheduling (2),Possible scheduling of kernel-level threads 50-msec process quantum threads run 5 msec/CPU burst,93,Chapter 3,3.1. Resource 3.2. Introduction to deadlocks 3.3. The ostrich algorithm

34、3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues,Deadlocks,94,Resources,Examples of computer resources printers tape drives tables Processes need access to resources in reasonable order Suppose a process holds resource A and requests resource B

35、at same time another process holds B and requests A both are blocked and remain so,95,Resources (1),Deadlocks occur when processes are granted exclusive access to devices we refer to these devices generally as resources Preemptable resources can be taken away from a process with no ill effects Nonpr

36、eemptable resources will cause the process to fail if taken away,96,Resources (2),Sequence of events required to use a resource request the resource use the resource release the resource Must wait if request is denied requesting process may be blocked may fail with error code,97,Introduction to Dead

37、locks,Formal definition :A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause Usually the event is release of a currently held resource None of the processes can run release resources be awakened,98,Four Conditions for Dea

38、dlock,Mutual exclusion condition each resource assigned to 1 process or is available Hold and wait condition process holding resources can request additional No preemption condition previously granted resources cannot forcibly taken away Circular wait condition must be a circular chain of 2 or more

39、processes each is waiting for resource held by next member of the chain,99,Deadlock Modeling (2),Modeled with directed graphs resource R assigned to process A process B is requesting/waiting for resource S process C and D are in deadlock over resources T and U,100,Deadlock Modeling (3),Strategies fo

40、r dealing with Deadlocks just ignore the problem altogether detection and recovery dynamic avoidance careful resource allocation prevention negating one of the four necessary conditions,101,How deadlock occurs,A B C,Deadlock Modeling (4),102,Deadlock Modeling (5),How deadlock can be avoided,(o) (p)

41、(q),103,The Ostrich Algorithm,Pretend there is no problem Reasonable if deadlocks occur very rarely cost of prevention is high UNIX and Windows takes this approach It is a trade off between convenience correctness,104,Detection with One Resource of Each Type (1),Note the resource ownership and reque

42、sts A cycle can be found within the graph, denoting deadlock,105,Detection with One Resource of Each Type (2),Data structures needed by deadlock detection algorithm,106,Detection with One Resource of Each Type (3),An example for the deadlock detection algorithm,107,Recovery from Deadlock (1),Recover

43、y through preemption take a resource from some other process depends on nature of the resource Recovery through rollback checkpoint a process periodically use this saved state restart the process if it is found deadlocked,108,Recovery from Deadlock (2),Recovery through killing processes crudest but

44、simplest way to break a deadlock kill one of the processes in the deadlock cycle the other processes get its resources choose process that can be rerun from the beginning,109,Deadlock AvoidanceResource Trajectories,Two process resource trajectories,110,Safe and Unsafe States (1),Demonstration that t

45、he state in (a) is safe,(a) (b) (c) (d) (e),111,Safe and Unsafe States (2),Demonstration that the sate in b is not safe,(a) (b) (c) (d),112,The Bankers Algorithm for a Single Resource,Three resource allocation states safe safe unsafe,(a) (b) (c),113,Bankers Algorithm for Multiple Resources,Example o

46、f bankers algorithm with multiple resources,114,Deadlock PreventionAttacking the Mutual Exclusion Condition,Some devices (such as printer) can be spooled only the printer daemon uses printer resource thus deadlock for printer eliminated Not all devices can be spooled Principle: avoid assigning resou

47、rce when not absolutely necessary as few processes as possible actually claim the resource,115,Attacking the Hold and Wait Condition,Require processes to request resources before starting a process never has to wait for what it needs Problems may not know required resources at start of run also ties

48、 up resources other processes could be using Variation: process must give up all resources then request all immediately needed,116,Attacking the No Preemption Condition,This is not a viable option Consider a process given the printer halfway through its job now forcibly take away printer !?,117,Atta

49、cking the Circular Wait Condition (1),Normally ordered resources A resource graph,(a) (b),118,Attacking the Circular Wait Condition (1),Summary of approaches to deadlock prevention,119,Other IssuesTwo-Phase Locking,Phase One process tries to lock all records it needs, one at a time if needed record

50、found locked, start over (no real work done in phase one) If phase one succeeds, it starts second phase, performing updates releasing locks Note similarity to requesting all resources at once Algorithm works where programmer can arrange program can be stopped, restarted,120,Nonresource Deadlocks,Pos

51、sible for two processes to deadlock each is waiting for the other to do some task Can happen with semaphores each process required to do a down() on two semaphores (mutex and another) if done in wrong order, deadlock results,121,Starvation,Algorithm to allocate a resource may be to give to shortest

52、job first Works great for multiple short jobs in a system May cause long job to be postponed indefinitely even though not blocked Solution: First-come, first-serve policy,122,Chapter 4,4.1 Basic memory management 4.2 Swapping 4.3 Virtual memory 4.4 Page replacement algorithms 4.5 Modeling page repla

53、cement algorithms 4.6 Design issues for paging systems 4.7 Implementation issues 4.8 Segmentation,Memory Management,123,Memory Management,Ideally programmers want memory that is large fast non volatile Memory hierarchy small amount of fast, expensive memory cache some medium-speed, medium price main

54、 memory gigabytes of slow, cheap disk storage Memory manager handles the memory hierarchy,124,Basic Memory ManagementMonoprogramming without Swapping or Paging,Three simple ways of organizing memory - an operating system with one user process,125,Multiprogramming with Fixed Partitions,Fixed memory p

55、artitions separate input queues for each partition single input queue,126,Modeling Multiprogramming,CPU utilization as a function of number of processes in memory,Degree of multiprogramming,127,Analysis of Multiprogramming System Performance,Arrival and work requirements of 4 jobs CPU utilization fo

56、r 1 4 jobs with 80% I/O wait Sequence of events as jobs arrive and finish note numbers show amout of CPU time jobs get in each interval,128,Relocation and Protection,Cannot be sure where program will be loaded in memory address locations of variables, code routines cannot be absolute must keep a pro

57、gram out of other processes partitions Use base and limit values address locations added to base value to map to physical addr address locations larger than limit value is an error,129,Swapping (1),Memory allocation changes as processes come into memory leave memory Shaded regions are unused memory,

58、130,Swapping (2),Allocating space for growing data segment Allocating space for growing stack & data segment,131,Memory Management with Bit Maps,Part of memory with 5 processes, 3 holes tick marks show allocation units shaded regions are free Corresponding bit map Same information as a list,132,Memo

59、ry Management with Linked Lists,Four neighbor combinations for the terminating process X,133,Virtual MemoryPaging (1),The position and function of the MMU,134,Paging (2),The relation betweenvirtual addressesand physical memory addres-ses given bypage table,135,Page Tables (1),Internal operation of MMU with 16 4 KB pages,136,Page Tables (2),32 bit address with 2 page table fields Two-level page tables,Second-level page tables,Top-level page table,137,Page Tables (3),Typi