Operating System （操作系统） 计算机科学与技术系 教授 孙 辉 博士.

Presentation on theme: "Operating System （操作系统） 计算机科学与技术系 教授 孙 辉 博士."— Presentation transcript:

1 Operating System （操作系统） 计算机科学与技术系 教授 孙 辉 博士

2 操作系统课程的主要内容及学习目的 一、 主要内容 1. 操作系统概述及相关的背景知识介绍 2. 进程管理及处理机调度
3. 存储管理及虚拟内存管理 4. 设备管理 5. 文件管理

3 二、学习目的 1. 通过系统学习操作系统知识，深入了解其工作原理和计算机运作过程，更好地使用操作系统； 2. 通过学习，了解系统编程的方法。
2. 通过学习，了解系统编程的方法。 3. 学习系统程序设计中的思考方式和处理问题的技巧,提高程序设计能力和计算机应用能力。 4. 为后续相关课程打下基础。

4 三、主要参考书 1. William Stallings，Operating Systems Internals and Design Principles 操作系统——精髓与设计原理 （第五版,影印版），电子工业出版社,2006.3, 本课程教材 2 Abraham Silberschatz,Peter Galvin,Greg Gagne OPERATING SYSTEM CONCEPTS，操作系统概念 （第六版,影印版）高等教育出版社,2002.5 3 孙钟秀主编，操作系统教程（第三版），高等教育出版社，2003年8月，附电子讲稿 4. 陈莉君，深入分析 Linux 内核源代码，人民邮电出版社 5. Jim Mauro Richard McDougall，Solaris 内核结构，冯锐等译，机械工业出版社

5 Introduction of Operating System
Chapter 1 Introduction of Operating System 操作系统概述

6 Main points 1 计算机系统的基本知识 2 操作系统的基本概念 3 操作系统的发展 4 操作系统的主要成就 5 现代操作系统的特征
6 典型的操作系统简介

7 1.1 Computer System Overview
（hardware） （计算机系统概述）

8 1.1.1 Basic Elements （计算机的基本元素）
Processor（中央处理器） Main Memory（主存储器，物理内存） Referred to as real memory or primary memory Volatile（多变性） I/O modules（输入/输出设备） secondary memory devices（辅助存储器，外存） communications equipment terminals System bus（系统总线） communication among processors, memory, and I/O modules

9 Top-Level Components

10 1.1.2 Processor Registers （处理器寄存器）

11 1.1.3 Instruction Cycle （指令执行周期） Instruction Fetch Execute Instruction
Fetch Cycle Execute Cycle Fetch Next Instruction Execute Instruction START HALT Instruction Fetch Execute Instruction Register 程序执行例

12 1.1.4 Direct Memory Access (DMA)
（直接存储器存取） I/O exchanges occur directly with memory Processor grants I/O module authority to read from or write to memory Relieves the processor responsibility for the exchange Processor is free to do other things

13 1.1.5 Interrupts Interrupts Classes of Interrupts Interrupt Handler
中断的概念 Classes of Interrupts 中断的分类 Interrupt Handler 中断处理 Interrupt Cycle 中断周期

14 1.2 Operating System Overview
(software) （操作系统概述）

15 1.2.1 Operating System 操作系统定义
1、A program that controls the execution of application programs （一个控制应用程序的执行的程序） 2、An interface between applications and hardware （应用程序和计算机硬件之间的接口）

16 Operating System 操作系统控制整个计算机的运行，但与一般的控制机制相比，有如下两点不同：
Functions same way as ordinary computer software It is program that is executed Operating system relinquishes（释放） control of the processor to execute other programs

17 操作系统作为资源管理器

18 1.2.2 Operating System Objectives
操作系统设计的目标 Convenience（方便） Makes the computer more convenient to use Efficiency（效率） Allows computer system resources to be used in an efficient manner Ability to evolve（扩展能力） Permit effective development, testing, and introduction of new system functions without interfering with service

19 1.2.3 Layers of Computer System
最终用户面对的是应用程序 程序员面对的是操作系统和应用系统 操作系统设计者面对的是计算机硬件

20

21 by the Operating System
Services Provided by the Operating System 操作系统提供的服务 Program development（程序开发） Editors and debuggers Program execution（程序运行） Access to I/O devices（访问I/O设备） Controlled access to files（控制访问文件） System access（系统访问）

22 Error detection and response（错误检测和响应）
internal and external hardware errors memory error device failure software errors arithmetic overflow access forbidden memory locations operating system cannot grant request of application Accounting（统计） collect statistics monitor performance used to anticipate future enhancements used for billing users

23 1.2.4 Kernel 内核 Portion of operating system that is in main memory
Contains most-frequently used functions Also called the nucleus 内核是操作系统最基本的部分，也可以认为，操作系统的一种定义就是内核，本程课程所介绍的操作系统即为内核。

24 1.2.5 Evolution of an Operating System
操作系统的易扩展性 Hardware upgrades and new types of hardware （硬件的升级和新硬件的出现） New services（新的服务） Fixes（纠正错误）

25 1.3 Evolution of Operating Systems 操作系统的发展
Serial Processing (串行处理) Simple Batch Systems (简单批处理系统) Multiprogramming (多道程序批处理系统) Time Sharing (分时系统)

26 1.4 Major Achievements 操作系统的主要成就 Processes（进程） Memory Management（内存管理）
Information protection and security（信息保护和安全） Scheduling and resource management（调度和资源管理） System structure（系统结构）

27

28 1.5 Characteristics of Modern Operating Systems
现代操作系统的特征 Microkernel architecture（微内核结构） Multithreading（多线程） Symmetric multiprocessing（对称多处理） Distributed operating systems（分布式） Object-oriented design（面向对象）

29 1.6 典型操作系统 WINDOWS 2000 操作系统 1.6.2 UINX 操作系统

30 Migration of Operating-System Concepts and Features

31 Process Description and Control
Chapter 2 Process Description and Control （进程描述和控制）

32 2.1 Process Description （进程描述） A process is a program in execution; process execution must progress in sequential fashion. Can be characterized by its trace A process requires resources, which are managed by the operating system The OS interleaves the execution of several processes to maximize processor utilization OS supports InterProcess Communication (IPC) and user creation of processes 进程的各种定义 三进程迸发执行 动画

33 2.2 Process States （进程状态及转换）
从上面的三进程的例子可看到，由于有几个进程同时在运行，在某一时刻，不同的进程有不同的状态，如正在运行的进程，等待运行的进程，还有等待I/O设备的进程，所以，进程的状态及转换是一个重要的概念。 一个进程的生命期可以划分为一组状态，这些状态刻划了整个进程。 进程的状态反映进程执行过程的变化。 进程的状态转换是一个非常复杂的过程。从一种状态到另一种状态的转换除了要使用不同的控制过程，有时还要借助于硬件触发器才能完成。

34

35 2.2.1 Two-State Process Model
两状态的进程模型 Process may be in one of two states Running（运行） Not-running（不运行） Not Running Enter Dispatch Pause Exit State transition diagram

36 2.2.2 Queuing Diagram 两状态进程队列图 Dispatcher（分派程序）
Processor Queue Exit Enter Pause Queuing diagram Dispatcher（分派程序） Program that assigns the processor to one process or another（分派CPU给一个个进程） Prevents a single process from monopolizing processor time（防止一个进程独占CPU时间）

37 As a process executes, it changes state
Process States （进程的5种状态） As a process executes, it changes state New（新建）: The process is being created. Running : Instructions are being executed. （运行） Waiting or blocked: The process is waiting for some event to occur. 等待或阻塞 Ready : The process is waiting to be assigned to a process. （就绪） Terminate or Exit: The process has finished execution.

38 Diagram of Process State
新建进程允许进入就绪队列 新建 结束 中断 运行 就绪 进程调度 等待 I/O或事件完成，进程从阻塞队列转入就绪队列 请求I/O或其它资源，进程转入阻塞队列中

39 Example for 3 Processes 三个进程运行状态转换的例子

40 Using Two Queues 两个队列：就绪队列和单一阻塞队列
使用单一阻塞队列，当队列中有大量的进程，导致效率下降。因为如果系统释放一个资源，要搜索整个阻塞队列。

41 分类型的多个阻塞队列模型

42 2.2.5 Suspended Processes （挂起的进程）
Processor is faster than I/O so all processes could be waiting for I/O Swap these processes to disk to free up more memory Blocked state becomes suspend state when swapped to disk Two new states Blocked, suspend Ready, suspend 进程的挂起就是进程被交换到外存中

43 One Suspend State 等待事件，进程转入阻塞状态 等待的事件发生，进程转入就绪状态 阻塞进程被挂起
挂起的就绪进程被激活，进入就绪队列 等待事件，进程转入阻塞状态 等待的事件发生，进程转入就绪状态 阻塞进程被挂起

44 2.2.6 Reasons for Process Suspension
Swapping The operating system needs to release sufficient main memory to bring in a process that is ready to execute（操作系统需要更多的主存空间，以调入并执行处于就绪状态的进程） Other OS reason The operating system may suspend a background or utility process or a process that is suspected of causing a problem（操作系统可能挂起后台进程或工具程序进程，或者因导致问题而已经挂起的进程） Interactive user request A user may wish to suspend execution of a program for purposes of debugging or in connection with the use of a resource（用户可能希望挂起一个进程的执行，目的是为了调试或者与一个资源的使用进行连接）

45 Reasons for Process Suspension
Timing A process may be executed periodically (e.g. an accounting or system monitoring process) and may be suspended while waiting for the next time interval（一个进程可能会周期性地执行—如计账程序或系统监控程序，而且可能在等待下一个时间间隔被挂起） Parent process request A parent process may wish to suspend execution of a descendent to examine or modify the suspended process, or to coordinate the activity of various descendents（父进程可能会希望挂起后代进程的执行，以检查或修改挂起的进程，或者协调不同后代进程之间的行为）

46 2. 3 Process Creation and Termination
进程的创建与终止 Process Creation Submission of a batch job（新的作业） User logs on（用户登录） Created to provide a service such as printing（提供新的服务） Process creates another process（现有进程生成）

47 2.3.2 Process Termination 进程的终止
Batch job issues Halt instruction（批处理指令） User logs off（用户退出） Quit an application（结束应用程序） Error and fault conditions（硬件错误）

48 2.3.3 Reasons for Process Termination
终止进程的原因 Normal completion（正常完成） Time limit exceeded（超过时限） Memory unavailable（无可用存储器） Bounds violation（越界） Protection error（保护错误） example write to read-only file（如写只读文件） Arithmetic error（算术错误） Time overrun（时间超出） process waited longer than a specified maximum for an event

49 Reasons for Process Termination
I/O failure（I/O失败） Invalid instruction（无效指令） happens when try to execute data Privileged instruction（特权指令，只有操作系统才能使用） Data misuse（数据误用） Operating system intervention（操作员或操作系统干涉） such as when deadlock occurs（如出现死锁） Parent terminates so child processes terminate（父进程终止子进程） Parent request（父进程请求）

50 2.4 Operating System Control Structures
进程控制结构

51 2.4.1 Operating System Control Structures
Information about the current status of each process and resource Tables are constructed for each entity the operating system manages

52 OS Control Structures Memory Tables Process Image Memory I/O Tables
User data User program System stack PCB I/O File File Tables Processes Processes Table Process 1 Process 2 … Process N

53 2.4.2 Process Control Block (PCB)进程控制块
Information associated with each process. Process state（进程状态） Program counter（程序计数寄存器） CPU registers（CPU寄存器） CPU scheduling information（CPU调度信息） Memory-management information（内存管理信息） Accounting information（记账信息） I/O status information（I/O状态信息）

54

55 Process Context (cont)
Hardware context（寄存器上下文） program counter stack pointer processor status word memory management registers FPU registers Machine registers saved in u area's process control block (PCB) during context switch to another process

56 2.4.5 Process Address Space 0xffffffff Kernel stack
Kernel address space 0x7fffffff Data stack Text (shared) Process address space 0x

57 2.4.6 用户进程的虚拟地址

58 2.4.7 Big Picture kernel memory proc struct Kernel stack/u area
User Stack User Stack User Stack Data Data Data Text (shared) Text (shared) Text (shared)

59 2.4.8 Control Information U area. Proc
Part of user space (above stack). typically mapped to a fixed address. contains info needed with running. Can be swapped Proc contains info needed when not running. Not swapped out. traditionally fixed size table

60 U area and Proc structures
PCB - HW context pointer to proc real/effective ids args, return values or errors to current syscall. Signal info file descriptor table controlling terminal vnode Proc structure process ID and group u area pointer process state queue pointers - scheduler, sleep, etc. Priority memory management info flags

61 User Credentials Every user is assigned a unique user id (uid) and group id (gid). Superuser (root) has uid == 0 and gid == 0 every process both a real and effective pair of Ids. effective id => file creation and access, real id => sending signals. Senders real/effective == receivers real

62 2.5 Process Scheduling （进程调度概念简介）

63 2.5.1 Process Scheduling Queues
Job queue – set of all processes in the system. Ready queue – set of all processes residing in main memory, ready and waiting to execute. Device queues – set of processes waiting for an I/O device. Process migration between the various queues.

64 Ready Queue, I/O Device Queues

65 Process Scheduling

66 2.6.3 Schedulers Long-term scheduler: job scheduler
selects which processes should be brought into the ready queue. invoked infrequently (seconds, minutes) controls the degree of multiprogramming Medium-term scheduler allocates memory for process. invoked periodically or as needed. Short-term scheduler: CPU scheduler selects which process should be executed next and allocates CPU. invoked frequently (ms)

67 2.6 Change of Process State 进程切换

68 Change of Process State
进程切换（上下文切换） Save context of processor including program counter and other registers Update the process control block of the process that is currently running Move process control block to appropriate queue - ready, blocked Select another process for execution

69 Change of Process State
进程切换 Update the process control block of the process selected Update memory-management data structures Restore context of the selected process

70 CPU Context Switch

71 2.6.2 When to Switch a Process
何时进行进程切换 Clock interrupt process has executed for the maximum allowable time slice I/O interrupt Memory fault memory address is in virtual memory so it must be brought into main memory

72 When to Switch a Process
Trap error occurred may cause process to be moved to Exit state Supervisor call such as file open

73 Execution of the Operating System
Non-process Kernel execute kernel outside of any process operating system code is executed as a separate entity that operates in privileged mode Execution Within User Processes operating system software within context of a user process process executes in privileged mode when executing operating system code

74 Execution of the Operating System
Process-Based Operating System major kernel functions are separate processes Useful in multi-processor or multi-computer environment

75 2.6.4 Process Creation 进程创建的过程 Assign a unique process identifier
Allocate space for the process Initialize process control block Set up appropriate linkages Ex: add new process to linked list used for scheduling queue Create of expand other data structures Ex: maintain an accounting file

76

77 2.7 Process and Thread 进程与线程

78 2.7.1 Process的特点 Resource ownership - process is allocated a virtual address space to hold the process image（资源所有权—分配虚拟地址空间保存进程映像及对处理器、其它进程、文件和I/O资源的存取进行了保护） Scheduling/execution- follows an execution path that may be interleaved with other processes（调度/执行—沿着某一执行路径执行，并与其它进程交替进行） These two characteristics are treated independently by the operating system（对操作系统来说，这两种特性是分开的） 将进程的第2个特征与第1个特征分开，单独设计具有第2个特征的结构，这就导致了线程的出现。

79 2.7.2 Thread（线程） A thread (or lightweight process) is a basic unit of CPU utilization; it consists of: program counter register set stack space A thread shares with its peer threads its: code section data section operating-system resources collectively know as a task. A traditional or heavyweight process is equal to a task with one thread

80 Thread An execution state (running, ready, etc.)
Saved thread context when not running Has an execution stack Per-thread static storage for local variables Access to the memory and resources of its process all threads of a process share this

81 Threads Suspending a process involves suspending all threads of the process since all threads share the same address space Termination of a process, terminates all threads within the process

82 Introduction to Threads
Multithreaded Process Model Single-Threaded Process Model Thread Thread Thread Thread Control Block Thread Control Block Thread Control Block Process Control Block User Stack Process Control Block User Stack User Stack User Stack User Address Space Kernel Stack User Address Space Kernel Stack Kernel Stack Kernel Stack

83 2.7.3 Benefits of Threads 线程的优势
Takes less time to create a new thread than a process（创造线程比进程的时间少） Less time to terminate a thread than a process（结束一个线程比进程的时间少） Less time to switch between two threads within the same process（线程切换比进程切换更省时间） Since threads within the same process share memory and files, they can communicate with each other without invoking the kernel（线程在同一个进程中，共享相同的内存和文件，它们之间的通信不用内核干涉，所以更节省时间）

84 2.7.4 Multithreading Operating system supports multiple threads of execution within a single process MS-DOS supports a single thread UNIX supports multiple user processes but only supports one thread per process Windows 2000, Solaris, Linux, Mach, and OS/2 support multiple threads

85

86 Uses of Threads in a Single-User Multiprocessing System
Foreground to background work（前台和后台操作） Asynchronous processing（异步处理） Speed execution（加速执行） Modular program structure（模块化程序结构）

87 2.7.5 Thread States States associated with a change in thread state
Spawn（产生） Spawn another thread Block Unblock Finish Deallocate register context and stacks

88

89 2.7.6 Remote Procedure Call Using Threads
按顺序执行，依次等待来自每个服务器的响应

90 Remote Procedure Call Using Threads
并行执行，同时等待来自每个服务器的响应

91 2.7.7 User-Level Threads 用户级线程
All thread management is done by the application The kernel is not aware of the existence of threads 优点：线程切换无需内核干涉，节省了在两种模式下的开销；调度算法是程序专用的，不会扰乱底层的操作系统调度程序；可以在任何操作系统下运行。 缺点：许多系统调用会阻塞，如果一个线程进行系统调用，则整个进程中的所有线程都会被阻塞；多线程技术不能利用多处理器技术，内核一次只把一个进程分配给一个处理器。

92 2.7.9 Combined Approaches Example is Solaris
Thread creation done in the user space Bulk of scheduling and synchronization of threads done in the user space

93 User-Level and Kernel-Level Threads

94 2.7.10 Relationship Between Threads and Processes
Threads:Process Description Example Systems 1:1 Each thread of execution is a unique process with its own address space and resources. Traditional UNIX implementations M:1 A process defines an address space and dynamic resource ownership. Multiple threads may be created and executed within that process. Windows NT, Solaris, OS/2, OS/390, MACH

95 Relationship Between Threads and Processes
Threads:Process Description Example Systems 1:M A thread may migrate from one process environment to another. This allows a thread to be easily moved among distinct systems. Ra (Clouds), Emerald M:M Combines attributes of M:1 and 1:M cases TRIX

96 2.7.11 Categories of Computer Systems
Single Instruction Single Data (SISD) single processor executes a single instruction stream to operate on data stored in a single memory Single Instruction Multiple Data (SIMD) each instruction is executed on a different set of data by the different processors

97 Categories of Computer Systems
Multiple Instruction Single Data (MISD) a sequence of data is transmitted to a set of processors, each of which executes a different instruction sequence. Never implemented Multiple Instruction Multiple Data (MIMD) a set of processors simultaneously execute different instruction sequences on different data sets

98 Parallel Processor Architectures

99 Symmetric Multiprocessing
Kernel can execute on any processor Typically each processor does self-scheduling form the pool of available process or threads

100 Multiprocessor Operating System Design Considerations
Simultaneous concurrent processes or threads Scheduling Synchronization Memory Management Reliability and Fault Tolerance

101 2.7.12 Microkernels Small operating system core
Contains only essential operating systems functions Many services traditionally included in the operating system are now external subsystems device drivers file systems virtual memory manager windowing system security services

102 Benefits of a Microkernel Organization
Uniform interface on request made by a process All services are provided by means of message passing Extensibility Allows the addition of new services Flexibility New features added Existing features can be subtracted

103 Benefits of a Microkernel Organization
Portability Changes needed to port the system to a new processor is changed in the microkernel - not in the other services Reliability Modular design Small microkernel can be rigorously tested

104 Benefits of Microkernel Organization
Distributed system support Message are sent without knowing what the target machine is Object-oriented operating system Components are objects with clearly defined interfaces that can be interconnected to form software

105 Microkernel Design Low-level memory management
mapping each virtual page to a physical page frame Inter-process communication I/O and interrupt management

106 2.7.13 Windows 2000 Process and Its Resources

107 Windows 2000 Process Object

108 Windows Thread Object

109 Windows 2000 Thread States Ready
Standby（备用，线程被选择下一次在一个特定的处理器上运行，线程在该状态下等待直到该处理器可用） Running Waiting Transition（一个线程在等待后，如果准备好运行但资源不可用时，进行该状态） Terminated

110 Windows Thread States

111 Solaris Process includes the user’s address space, stack, and process control block User-level threads Lightweight processes Kernel threads

112 Solaris Multithreaded Architecture Example

113 Process Structure in Traditional UNIX and Solaris

114 Solaris Thread Execution
Synchronization Suspension Preemption Yielding

115 Solaris User-Level Thread and LWP States

116 2.7.15 Linux Process’s task_struct
State Scheduling information Identifiers Interprocess communication Links Times and timers File system Virtual memory Processor-specific context

117 Linux States of a Process
Running Interruptable Uninterruptable Stopped Zombie

118

119 Concurrency: Mutual Exclusion and Synchronization
Chapter 3 Concurrency: Mutual Exclusion and Synchronization 并发性：互斥与同步

120 3.1 进程并发的概念 操作系统设计的核心问题是进程和线程的管理 1、多道程序技术：管理单处理器中的多个进程
2、多处理技术：管理多处理系统中的多个进程 3、分布处理技术：管理多台分布式计算机系统中多个进程的执行 在单处理器中，进程交替执行；在多处理器中，进程不但能交替执行，还能重叠执行。 这些都表现出并发执行的外部特征。

121 并发执行中操作系统要处理的问题 Communication among processes（进程间的通信） Sharing and competing for resources（资源共享与竞争） Synchronization of multiple processes（多进程同步） Allocation of processor time（分配处理器时间）

122 3.1.2 Difficulties with Concurrency
进程并发带来的困难 Sharing global resources（全局资源的共享充满了风险） Management of allocation of resources（操作系统很难最佳地分配资源） Programming errors difficult to locate（定位程序设计错误非常困难）

123 Example: Race Conditions
Two processes want to access shared memory at same time Solution: Synchronize Access

124 3.1.3 进程并发执行带来的问题的 例：设有堆栈S，栈指针 top，栈中存放内存中相应的数据块地址。设有两个程序段getaddr(top) 和 reladdr(blk)， getaddr(top) 从给定的top所指栈中取出相应的内存数据块地址， reladdr(blk)将内存数据块地址blk放入椎栈中。它们的描述如下： Procedure getaddr(top) begin local r r ←(top) top ←top-1 return r end Procedure reladdr(blk) begin top ← top+1 (top) ← blk end 例

125 执行过程中的问题 a a a b b b e e e f f f CPU的执行过程： 执行过程reladdr(blk)
随机 a b e f a b e f a b e f 完成top ←top+1 top top 进程切换， 执行getaddr(top) top 完成getaddr(top) 最后，getaddr过程取到的数据为一随机值，结果出错。 堆栈的取和存数过程

126 3.2 Operating System Concerns
Result of processing must be independent of the speed of execution（进程的结果不依赖执行速度） Process Interactions（进程的交互） Processes unaware of each other（互不知道） Compete for resources（竞争资源、使用的办法--互斥、带来问题--死锁、饿死） Processes indirectly aware of each other Cooperation by sharing（共享合作、办法--互斥、问题--死锁） Process directly aware of each other（直接知道） Cooperation by communication（通信合作、带来的问题--死锁、饿死）

127 3.2.1 Competition for Resources
Problem: Execution of one process may affect the behavior of competing processes Solution: Mutual Exclusion（互斥） a critical section is the fragment of code that accesses shared data（临界区是一段存取共享数据的代码） when one process is executing in its critical section, no other process is allowed to execute in its critical section（当一个进程在临界区执行，其它的进程不能进入临界区） Issue: Deadlock and Starvation（死锁或饿死） blocked process will never get access to the resource and never terminate

128 进程控制原语 所谓原语，是一种特殊的广义指令，又称为原子操作，它的功能由系统通过一段不可分割的操作指令来完成。原语在核心态下完成。进程的控制操作如创建、撤消、阻塞、挂起等大多为原语。

129 3.2.3 Mutual Exclusion Requirements
互斥的要求 Mutually exclusive access to critical section（互斥存取临界区） Progress. （处理） If no process is executing in its critical section and there exist some processes that wishes to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.（如果没有进程在临界区中，其它进程想进入临界区，则选择进入临界区的进程不能无限延时进入临界区。其实，这是要求不能出现死锁。）

130 Mutual Exclusion Requirements
Bounded Waiting. （有限等待） A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.（在一个进程发出一个要求要进入临界区之后和它被充许进入临界区之前，等待进入临界区的时间是有限的。这里指的是饿死） Assume each process executes at a nonzero speed （假设每个进程的执行速度不是零） No assumption concerning relative speed of n processes.（但并不考虑各进程的相对速度）

131 3.2.4 Cooperation by Sharing
共享合作 Processes use and update shared data such as shared variables, files, and data bases Writing must be mutually exclusive Critical sections are used to provide data integrity

132 Cooperation by Communication
Communication provides a way to synchronize, or coordinate, the various activities no sharing => mutual exclusion not required Possible to have deadlock each process waiting for a message from the other process Possible to have starvation two processes sending message to each other while another process waits for a message

133 3.2.5 Consumer Producer Example
消费者、生产者程序实例 Bounded Buffer Problem Shared data #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0;

134 Producer Process 生产进程 item nextProduced; while (1) {
while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; }

135 Consumer Process 消费者进程 item nextConsumed; while (1) {
while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; }

136 Bounded Buffer 有限缓冲区 The statements counter++; counter--; must be performed atomically. Atomic operation means an operation that completes in its entirety without interruption.

137 Bounded Buffer The statement “count++” may be implemented in machine language as: register1 = counter register1 = register1 + 1 counter = register1 The statement “count—” may be implemented as: register2 = counter register2 = register2 – 1 counter = register2

138 Bounded Buffer If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved. Interleaving depends upon how the producer and consumer processes are scheduled.

139 Bounded Buffer Assume counter is initially 5. One interleaving of statements is: producer: register1 = counter (register1 = 5) producer: register1 = register1 + 1 (register1 = 6) consumer: register2 = counter (register2 = 5) consumer: register2 = register2 – 1 (register2 = 4) producer: counter = register1 (counter = 6) consumer: counter = register2 (counter = 4) The value of counter may be either 4 or 6, where the correct result should be 5. 进程切换 进程切换

140 Race Condition Race condition: The situation where several processes access – and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. To prevent race conditions, concurrent processes must be synchronized.

141 3.2.6 Initial Attempts to Solve Problem
Only 2 processes, P0 and P1 General structure of process Pi (other process Pj) do { entry section critical section exit section reminder section } while (1); Processes may share some common variables to synchronize their actions.

142 Algorithm 1（动画） Shared variables: Process Pi do { while (turn != i) ;
int turn; initially turn = 0 turn - i  Pi can enter its critical section Process Pi do { while (turn != i) ; critical section turn = j; reminder section } while (1); Satisfies mutual exclusion, but not progress 进程轮流使用临界区，执行步调由较慢的进程决定 如果一个进程失败（不论是否在临界区），另一个进程被永久阻塞 例

143 Algorithm 3（Peterson算法）
Combined shared variables of algorithms 1 and 2. Process Pi do { flag [i]= true; turn = j; while (flag [j] && turn ==j) ; critical section flag [i] = false; remainder section } while (1); Meets all three requirements; solves the critical-section problem for two processes.

144 Mutual Exclusion - Interrupt Disabling
Process runs until requests OS service or interrupted Process disables interrupts for MUTEX Processor has limited ability to interleave programs Efficiency of execution may be degraded Multiprocessing（多处理器情形） disabling interrupts on one processor will not guarantee mutual exclusion

145 Mutual Exclusion Instructions
Special Machine Instructions Performed in a single instruction cycle Not subject to interference from other instructions Reading and writing Reading and testing

146 Test and Set Operation (Return original value of lock)
boolean TestAndSet (boolean &lock) { boolean tmp = lock; lock = True; return tmp; } When calling TestAndSet(lock) if lock == False before calling TestAndSet it is set to True and False is returned if lock == True before calling TestAndSet it is set to True and True is returned

147 Mutual Exclusion with Test-and-Set
Shared data: boolean lock = False; Process Pi do { while (TestAndSet(lock) == True) continue; // do nothing -- critical section -- lock = False; -- remainder section } while (1);

148 Exchange Instruction (Atomically swap two variables)
void Swap(boolean &a, boolean &b) { int temp = a; a = b; b = temp; }; After calling swap, a == original value of b b = original value of a

149 Mutual Exclusion with Swap
Shared data (initialized to false): boolean lock; boolean waiting[n]; Process Pi do { key = True; while (key == True) Swap(lock,key); -- critical section lock = false; -- remainder section }

150 Machine Instructions Advantages
Applicable to any number of processes on either a single processor or multiple processors sharing main memory It is simple and therefore easy to verify It can be used to support multiple critical sections

151 Mutual Exclusion Instructions
Disadvantages Busy-waiting consumes processor time Starvation is possible when a process leaves a critical section and more than one process is waiting. Who is next? Deadlock - If a low priority process has the critical region and a higher priority process needs, the higher priority process will obtain the processor to wait for the critical region

152 3.3 Intro to Semaphores 信号量简介
Synchronization tool that does not require busy waiting（利用信号量同步不需要忙等待，信号量S为系统拥有的临界资源数） Integer variable accessable via two indivisible (atomic) operations （整型变量的存取由2个原子操作组成） wait(s): s = s - 1, if s < 0 then block process on the semaphore queue (wait)（P操作） signal(s): s = s + 1, if s <= 0 then wake one sleeping process (signal).（V操作） Each Semaphore has an associated queue.（每个信号量都有一个与之相联的队列） Can define a non-blocking version of wait(s).

153 wait操作的详细说明 设有一台计算机，带两台打印机，现有m个进程，竞争两台打印机。
对于此情形，则系统拥有的资源数为2，也就是开始时2 → s，当进程 P1 申请打印机资源，先对信号量s进行wait(P)操作，（s-1）→s，s>=0，进程获取临界资源。 当新进程 P2 申请打印机资源，仍需要对信号量s进行wait(P)操作，（s-1）→s，s>=0，进程获取临界资源。 当新进程 P3 申请打印机资源时，对信号量s进行wait(P)操作，（s-1）→s，(s=-1)，s<0，进程不能获取临界资源，被阻塞在信号队列中。 当 s 值为负，则s的绝对值代表信号队列中等待资源的进程数。

154 signal操作的详细说明 当一个进程如P2使用完临界资源，进行signal（V）操作。先将s+1→s，此时 s=0，s<=0，说明信号队列中有等待资源的进程，signal操作将唤醒信号队列中的进程，将其放入就绪队列。 当另一个进程如P1使用完临界资源，进行signal（V）操作。先将s+1→s，此时 s=1，s>0，说明信号队列中没有等待资源的进程，signal操作除将执行s+1→s外，不执行任何其它操作。

155 3.3.1 Critical Section of n Processes
Shared data: semaphore mutex; //initially mutex = 1 Process Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1); 进程在进入临界区前，先对信号量执行P操作，如果临界区可用，进程继续，否则，进程被阻塞。 进程退出临界区，执行V操作，如果有进程被阻塞，则唤醒一个进程 例

156 3.3.2 Semaphore Implementation
Define a semaphore as a record typedef struct { int value; struct process *L; } semaphore; Assume two simple operations: block suspends the process that invokes it. wakeup(P) resumes the execution of a blocked process P.

157 Some Reference Background
Used in Initial MP implementations Threads are woken up in FIFO order (convoys) Used to provide Mutual exclusion (initialized to 1) Event-waiting (initialized to 0) Resource counting (initialized to number available)

158 3.4 Classical Problems of Synchronization
Bounded-Buffer Problem（有限缓冲区问题） Readers and Writers Problem（读、写问题） Dining-Philosophers Problem（哲学家就餐问题）

159 3.4.1 Bounded-Buffer Problem
有界缓冲区问题 此问题也称生产者、消费者问题。 两个进程，生产者进程生产数据，消费者进程消费生产进程生产的数据。两进程通过共享一有限缓冲区实现数据的生产和消费。 在此问题中，即有进程互斥—当一个进程操作共享缓冲区时，另一进程必须等待。如生产者进程往缓冲区写数据时，消费进程不能从缓冲区读数据。反之，当消费进程从缓冲区中读数据时，生产者进程不能向共享缓冲区写数据。

160 Bounded-Buffer Problem
同时，该问题还有进程同步问题。 当缓冲区满时，生产者进程必须等待消费者进程将数据消费掉才能向共享缓冲区中写入数据。反之，当共享缓冲区空时，消费者进程必须等待生产者进程生产数据后才能从共享缓冲区中读数据。两个进程在执行时一个进程的行为受到另一个进程的制约，这就需要同步。 进程互斥要求有互斥信号量或公有信号量，进程同步要求有进程私有信号量。

161 Bounded-Buffer Problem
对于此类问题，进程在进入临界区前，有两件事要做：一是判断临界区中是否有进程在执行，这要用进程互斥标志或公有信号量，二是判断临界区是否能进行操作，这一判断只与本进程有关，与其它的进程无关，所以要私有信号量。

162 Bounded-Buffer Problem
Shared data semaphore full, empty, mutex; Initially: full = 0, empty = n, mutex = 1 empty— 生产者进程私有信号量(缓冲区中剩余空间)， full—消费者进程私有信号量(缓冲区中剩余数据数)， mutex—互斥信号量（公有信号量）

163 Bounded-Buffer Problem Producer
do { … produce an item in nextp … wait(empty); // Decrement free cnt wait(mutex); // Lock buffers … add nextp to buffer … signal(mutex); // release buffer lock signal(full); // Increment item count } while (1); 动画演示

164 Bounded-Buffer Problem Consumer
do { wait(full) // decrement item count wait(mutex); // lock buffers … remove item from buffer nextc … signal(mutex); // release lock signal(empty); // increment free count … consume item in nextc … } while (1); 动画演示

165 临界区满，生产者进程必须在empty信号量上等待
do { wait(full) wait(mutex); … remove item from buffer nextc … signal(mutex); signal(empty); … consume item in nextc … } while (1); do { … produce an item in nextp … wait(empty); wait(mutex); … add nextp to buffer … signal(mutex); signal(full); } while (1); 说明： 正常情况，两进程在临界区互斥执行 临界区满，生产者进程必须在empty信号量上等待 临界空区，消费者进程必须在full信号量上等待 颠倒信号量的顺序，则发生死锁。

166 3.4.2 Readers-Writers Problem
读、写问题 读、写问题是处理同步与并发机制问题的一个经典问题。 读写问题定义如下： 有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间，甚至可以是一组处理器寄存器；有一些只读取这个数据区的进程（reader)和一些只往数据区中写数据的进程（writer）；此外，还必须满足以下条件： 1 任意多的进程可以同时读这个文件； 2 一次只有一个写进程可以往文件中写； 3 如果一个写进程正在往文件 中写，禁止任何读进程读文件。

167 Readers-Writers Problem
在进行算法设计时，如果考虑读进程优先，要考虑两点： 1 当临界区中有读进程时，其它读进程可直接进入临界区，因此要一个变量readcount记录临界区中的读进程数； 2 只有当临界区无读进程时（ readcount =0），写进程才能进入临界区写数据。

168 Readers-Writers Problem
对读、问题，也可从另外的角度来看待它，比如图书馆阅览室的读者、管理员问题： 阅览室可同时有多个读者在里面看书，当读者看书时，管理员不能整理图书，当有一个读者在看书时，其他读者可随意进入阅览室； 2 只有当阅览室无读者时，管理员才能进入阅览室整理图书。管理员在整理图书时，读者不能进入阅览室看书。

169 Readers-Writers Problem
全局变量，记录读进程数目 Readers-Writers Problem x—确保readcount被正确地更新,因为同时有若干个读进程可以更新它 wsem—读、写进程互斥的信号量 int readcount; semaphore x=1,wsem=1; void reader() { while(true) { wait(x); readcount++; if(readcount==1) wait(wsem); signal(x); READUNIT(); readcount--; if(readcount==0) signal (wsem); } void writer() { while(true) { wait(wsem); WRITEUNIT(); signal(wsem); } 第1个读进程，需要判断临界区中是否有写进程 读进程已全部退出临界区，写进程可以使用临界区 void(main() { readcount=0; parbegin(reader,writer); } 此处的方法为读进程优先，写进程有可能被饿死

170 写进程用信号量 rsem阻止读进程进入临界区
读、写问题，写进程优先示意图 所谓写进程优先，是指当有 写 进程要进入临界区写时，如果临界区有读进程，则它利用信号量（rsem）阻止其它的读进程进入临界区。当然，它自己也要等到临界区中所有的读进程退出才能进入临界区。 其它读进程在信号量z上排队 仅1个读进程在信号量rsem上等待 读进程进入临界区 第1个读进程用wsem阻止写进程进入临界区 临界区 第1个准备进入临界区的写进程用信号量rsem阻止读进程进入临界区，因为在信号量rsem上只有一个读进程排队，所以写进程不用在rsem上排队 写进程进入临界区 写进程用信号量 rsem阻止读进程进入临界区 写进程在信号量wsem上排队

171 Readers-Writers Problem
Shared data semaphore mutex, wrt; Initially mutex = 1, wrt = 1, readcount = 0

172 Readers-Writers Problem: Writer
wait(wrt); … writing is performed signal(wrt);

173 Readers-Writers Problem: Reader
wait(mutex); readcount++; if (readcount == 1) // First reader wait(wrt); // Keeps writes out signal(mutex); … reading is performed … readcount--; if (readcount == 0) // Last reader signal(wrt); // Alow writer in signal(mutex):

174 RW Locks Preferred solution, writer wakes up all sleeping readers.
But, this could lead to writer starvation. How is this fixed? What about when a reader wants to upgrade to an exclusive lock? Deadlocks? If pending writers, should a new reader get a lock?

175 3.4.3 Dining-Philosophers Problem
Shared data semaphore chopstick[5]; Initially all values are 1

176 Dining-Philosophers Problem
Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) … eat … signal(chopstick[i]); signal(chopstick[(i+1) % 5]); … think … } while (1);

177 Dining Philosophers Example
#define N // 哲学家数目 #define LEFT (i-1)%N // i 左边的邻居数目 #define RIGHT (i+1)%N // i 右边的邻居数目 #define THINKING // 哲学家正在思考 #define HUNGRY // 哲学家试图得到叉子 #define EATING // 哲学家正在吃 typedef int semaphore; int state[N]; // 跟踪每个人的状态数组 semaphore mutex=1; // 用于临界区的互斥 semaphord s[N]; // 每个哲学家一个信号量 void philosopher (int i) // 哲学家编号 { while(TRUE){ think( ); // 哲学家正在思考 take_forks(i); // 获得两把叉子或阻塞 eat( ); // 美味的面条 put_forks(i); // 把两把叉子放回桌面 }

178 void take_forks (int i)
{ wait(mutex); // 哲学家进入临界区 state[i]=HUNGRY; // 记录哲学家i饥饿的事实 test(i); // 试图获得两把叉子 signal(mutex); // 退出临界区 wait(s[i]); // 如果得不到叉子，则阻塞 } void put_forks( int i) wait (mutex); // 哲学家进入临界区 state[i]=THINKING; // 哲学家结束吃饭 test(LEFT); // 看左边的邻居现在是否能吃 test(RIGHT); // 看右边的邻居现在是否能吃 signal(mutex); // 退出临界区 void test (int i) { if(state[i]==HUNGRY && state[LEFT] !=EATING && state[RIGHT] !=EATING) { state[i] =EATING; signal (s[i] ); }

179 Potential Problems Incorrect use of semaphores can lead to problems
Critical section using semaphores: must keep to a strict protocol wait(S); {critical section}; signal(S) Problems: No mutual exclusion: Reverse: signal(S); {critical section}; wait(S); Omit wait(S) Deadlock: wait(S); {critical section}; wait(S); Omit signal(S)

180 Potential Solutions How do we protect ourselves from these kinds of errors? Develop language constructs that can be validated automatically by the compiler or run-time environment Critical Regions Monitors

181 3.5 Monitors High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes. monitor monitor-name { shared variable declarations procedure body P1 (…) { } procedure body P2 (…) { } procedure body Pn (…) { } { initialization code } }

182 Monitors To allow a process to wait within the monitor, a condition variable must be declared, as condition x, y; Condition variable can only be used with the operations wait and signal. The operation x.wait(); means that the process invoking this operation is suspended until another process invokes x.signal(); The x.signal operation resumes exactly one suspended process. If no process is suspended, then the signal operation has no effect.

183 Schematic View of a Monitor

184 Monitor With Condition Variables

185

186 Dining Philosophers Example
monitor dp { enum { thinking, hungry, eating } state[5]; condition self[5]; void pickup(int i) // following slides void putdown(int i) // following slides void test(int i) // following slides void init() { for (int i = 0; i < 5; i++) state[i] = thinking; }

187 Dining Philosophers void pickup(int i) { state[i] = hungry; test(i);
if (state[i] != eating) self[i].wait(); } void putdown(int i) { state[i] = thinking; // test left and right neighbors test((i+4) % 5); test((i+1) % 5);

188 Dining Philosophers (test)
void test(int i) { if ( (state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)) { state[i] = eating; self[i].signal(); }

189 3.6 Message Passing Enforce mutual exclusion Exchange information
send (destination, message) receive (source, message)

190 Synchronization Sender and receiver may or may not be blocking (waiting for message) Blocking send, blocking receive Both sender and receiver are blocked until message is delivered Called a rendezvous

191 Synchronization Nonblocking send, blocking receive
Sender continues processing such as sending messages as quickly as possible Receiver is blocked until the requested message arrives Nonblocking send, nonblocking receive Neither party is required to wait

192 Addressing Direct addressing
send primitive includes a specific identifier of the destination process receive primitive could know ahead of time which process a message is expected receive primitive could use source parameter to return a value when the receive operation has been performed

193 Addressing Indirect addressing
messages are sent to a shared data structure consisting of queues queues are called mailboxes one process sends a message to the mailbox and the other process picks up the message from the mailbox

194

195 Message Format Header Body Message Type Destination ID Source ID
Message Length Control Information Message Contents Header Body

196 Message Passing 使用消息的互斥 void main() const int n=/*进程数*/ {
create_mailbox(mutex); send(mutex,null); parbegin(P(1),P(2),…P(n)); } const int n=/*进程数*/ void P(int i) { message msg; while(true) receive(mutex,msg); critical section; sedn(mutex,msg); reminder } 1 如果有一条消息，它仅仅被传递给一个进程，其它进程被阻塞 2 如果消息队列为空，所有进程被阻塞；当有一条消息可用时，只有一个阻塞进程被激活并得到这条消息。

197 用消息解决有界缓冲区问题 void consumer( ) const int; { capacity = /* 缓冲区容量 */
message cmsg; while(true) receive(mayconsume,cmsg); consume(cmsg); send(mayproduce,null); } const int; capacity = /* 缓冲区容量 */ null = /* 空消息 */ int i; void producer() { message pmsg; while(true) receive(mayproduce, pmsg); pmsg=procuce(); send(mayconsume, pmsg); } void main() { create_mailbox(mayproduce); creatd_mailbox(mayconsume); for(int i=1; i<=capacity; i++) send(mayproduce,null); parbegin(producer,consumer); }

198 有关信号量的系统调用 信号量是个整数计数器，用来记录可用资源的数量和等待进程的数量。
semget( ) ： 创建一个新的信号量集，或存取一个已存在的信号量集。 #include<sys/types.h> #include<sys/ipc.h> #include<sem.h> Int semget(key_t key , int nsems , int semflg); key 键值，为IPC_PRIVATE时，创建一个新的信号集。否则，打开或存取一个信号集，具体操作依赖于semflg参数。 nsems ： 新创建的信号集中信号的个数

199 sembuf 结构 struct sembuf { ushort sem_num ; //信号在数组中的索引 short sem _op; // 信号量操作传值，正、负或零 short sem_flg; // 操作标志，IPC_NOWAIT SEM_NUDO } sem_op 为负，相当P操作，从信号量的值中减去sem_op的绝对值。如果没有指定IPC_NOWAIT，则调用进程睡眠进入等待队列，否则出错返回。大于0，则进程可以使用临界资源进入临界区。如果等于0，调用进程将睡眠直到信号量的值为0。

200

201 Processor Registers （处理器寄存器） User-visible registers（用户可见寄存器）
Enable programmer to minimize main-memory references by optimizing register use（程序员可通过优化这些寄存器的使用使程序减少访问主存储器） Control and status registers（控制和状态寄存器） Used by processor to control operating of the processor（由处理器使用以控制处理器的操作） Used by operating-system routines to control the execution of programs（由具有特权的操作系统例程来控制程序的执行）

202 User-Visible Registers
（用户可见寄存器） May be referenced by machine language Available to all programs - application programs and system programs Types of registers Data （在某些情况下，它们是通用寄存器） Address（包括数据和指令的主存储器地址） Index（变址寻址寄存器） Segment pointer（段指示字或段指针） Stack pointer （栈指示字或栈指针）

203 User-Visible Registers
（用户可见寄存器） Address Registers（地址寄存器） Index（变址寄存器） involves adding an index to a base value to get an address（通过给一个基值加一个变址来获得有效地址） Segment pointer（段指示字或段指针） when memory is divided into segments, memory is referenced by a segment and an offset（当内存被分段时，内存由段指针和偏移量引用） Stack pointer（栈指示字或栈指针） points to top of stack（指向栈顶）

204 Control and Status Registers
（控制和状态寄存器） Program Counter (PC，程序计数器) Contains the address of an instruction to be fetched Instruction Register (IR，指令寄存器) Contains the instruction most recently fetched Program Status Word (PSW，程序状态字) condition codes Interrupt enable/disable Supervisor/user mode

205 Control and Status Registers
（控制和状态寄存器） Condition Codes or Flags（条件码或标记） Bits set by the processor hardware as a result of operations（由处理器硬件为操作结果设置的位） Can be accessed by a program but not altered（程序可以存取这些结果但不能修改它） Examples positive result（结果为正） negative result（结果为负） Zero（零） Overflow（溢出）

206 Instruction Fetch and Execute
（取指令和执行指令） The processor fetches the instruction from memory（处理器从内存中取一条指令） Program counter (PC) holds address of the instruction to be fetched next（程序计数器保存有下一次要取的指令的地址） Program counter is incremented after each fetch（程序计数器在取指令后自动加 1，指向下一条要执行的指令的地址）

207 Instruction Register （指令寄存器）
Fetched instruction is placed in the instruction register（取到的指令放在指令寄存器中） Types of instructions Processor-memory transfer data between processor and memory Processor-I/O data transferred to or from a peripheral device Data processing arithmetic or logic operation on data Control alter sequence of execution

208 Example of Program Execution
（程序执行的例） 第1步：PC指向第 1 条指令的地址300，地址内容并被送入指令寄存器，PC增1。 IR中最初的4位表示需要加载AC（累加器），乘下的12位表示加载的地址。 操作码 第3步：从301单元取下一条指令（5941），PC增1 AC中的内容和941单元的内容相加，结果保存在AC中 第5步：从302单元取下一条指令（2941），PC增1 AC中的内容被存储在941单元中。

209 Interrupts 中断的概念 An interruption of the normal processing of processor
Improves processing efficiency Allows the processor to execute other instructions while an I/O operation is in progress A suspension of a process caused by an event external to that process and performed in such a way that the process can be resumed

210 Classes of Interrupts （中断的分类） Program（程序中断）
arithmetic overflow（算术溢出） division by zero（除数为零） execute illegal instruction（试图执行非法指令） reference outside user’s memory space（访问用户不允许访问的存储器） Timer（时钟中断，由处理器内部的计时器产生，允许操作系统以一定的规律执行函数） I/O（I/O中断，由I/O控制器产生，用于发信号通知一个操作的正常完成或各种错误条件） Hardware failure（硬件失败）

211 Interrupt Handler （中断处理程序）
A program that determines nature of the interrupt and performs whatever actions are needed Control is transferred to this program Generally part of the operating system

212 Interrupt Cycle （中断周期） START HALT Fetch Next Instruction Execute
Fetch Cycle Execute Cycle Interrupt Cycle Interrupts Disabled Fetch Next Instruction Execute Instruction Chech for Interrupt; Process interrupt START Interrupts Enable HALT

213 Interrupt Cycle （中断周期） Processor checks for interrupts（处理器检查中断）
If no interrupts fetch the next instruction for the current program（无中断，取当前程序的下一条指令） If an interrupt is pending, suspend execution of the current program, and execute the interrupt handler（当为断发生时，暂停当前程序的执行，执行中断处理程序）

214 Serial Processing （串行处理） Serial Processing No operating system
Machines run from a console with display lights and toggle switches（触发器）, input device, and printer Schedule tome Setup included loading the compiler, source program, saving compiled program, and loading and linking

215 Simple Batch Systems 简单批处理系统 Simple Batch Systems Monitors
使用一个称作监控程序的软件。用户将卡片或磁带中的作业提交给计算机操作员，操作员按顺序组织成一批，并将整个批作业放在输入设备上，供监控程序使用。监控程序自动加载下一个程序，每个程序完成处理后返回到监控程序。由此，用户不用直接访问计算机。 Simple Batch Systems Monitors Software that controls the running programs Batch jobs together Program branches back to monitor when finished Resident monitor is in main memory and available for execution

216 Job Control Language (JCL)
简单批处理系统所需的作业控制语言 Job Control Language (JCL) Special type of programming language Provides instruction to the monitor what compiler to use what data to use

217 Hardware Features 硬件的特征 Memory protection（内存保护） Timer（时 钟）
简单批处理系统所需硬件 Hardware Features 硬件的特征 Memory protection（内存保护） do not allow the memory area containing the monitor to be altered Timer（时 钟） prevents a job from monopolizing the system（防止一个作业独占系统资源）

218 Hardware Features Privileged instructions（特权指令） Interrupts（中 断）
简单批处理系统所需硬件 Hardware Features Privileged instructions（特权指令） executed only by the monitor an interrupt occurs if a user program tries these instructions Interrupts（中 断） provides flexibility for controlling user program

219 Uniprogramming 单道程序设计
Processor must wait for I/O instruction to complete before preceding Run wait Program A time Uniprogramming

220 Multiprogramming When one job needs to wait for I/O, the processor can switch to the other job Run wait Program A Run wait Program B Run B wait A Combined time

221 Multiprogramming Program A wait Program B Program C wait Combined time
Run wait Program A Program B Program C Run B wait A Combined time

222 Example JOB1 JOB2 JOB3 Type of job Heavy compute Heavy I/O Heavy I/O
Duration min min min. Memory required K K K Need disk? No No Yes Need terminal No Yes No Need printer? No No Yes

223 Effects of Multiprogramming
Uniprogramming Multiprogramming Processor use % % Memory use % % Disk use % % Printer use % % Elapsed time min min. Throughput rate jobs/hr jobs/hr Mean response time 18 min min.

224 利用率直方图

225 Time Sharing （分时系统） Using multiprogramming to handle multiple interactive jobs Processor’s time is shared among multiple users Multiple users simultaneously access the system through terminals

226 Batch Multiprogramming versus Time Sharing
Principal objective 主要目标 Maximize processor use 最有效地使用处理器 Minimize response time 减少响应时间 Source of directives to operating system 操作系统指令源 Job control language commands provided with the job 作业控制语言 作业提供的命令 Commands entered at the terminal 终端键入的命令

227 Microkernel architecture
Characteristics of Modern Operating Systems Microkernel architecture assigns only a few essential functions to the kernel（只给内核分配一些最基本的功能） address space（地址空间） interprocess communication (IPC)（进程间通信） basic scheduling（基本的调度） Microkernel architecture 微内核结构 Monolithic kernel 单一内核

228 Characteristics of Modern Operating Systems
Multithreading（多线程） process is divided into threads that can run simultaneously（应用程序的进程可以分成多个可以同时并行运行的线程） Thread（线程） dispatchable unit of work（可以分派的工作单元，它包括处理器上下文环境和栈中自己的数据区域） executes sequentially and is interruptable（顺序执行，并且是可中断的） Process is a collection of one or more threads（进程是一个或多个线程和相关系统资源的集合）

229 Characteristics of Modern Operating Systems
Symmetric multiprocessing（对称多处理，SMP） there are multiple processors（具有多个处理器） these processors share same main memory and I/O facilities（这些处理器共享同一个主存储器和I/O设备，它们之间通过通信总线或别的内部连接方案互相连接） All processors can perform the same functions（所有的处理器可执行相同的功能）

230 Characteristics of Modern Operating Systems
Distributed operating systems（分布式操作系统） provides the illusion of a single main memory and single secondary memory space（给用户产生一个错觉，好象是单一的主存空间和辅存空间） used for distributed file system（使用分布式文件系统）

231 Characteristics of Modern Operating Systems
Object-oriented design（面向对象设计） used for adding modular extensions to a small kernel（用于给小内核增加模块化的扩展） enables programmers to customize an operating system without disrupting system integrity（使程序员可以事实上定制操作系统，而不会破坏系统的完整性。）

232 Windows 2000 Exploits the power of today’s 32-bit microprocessors（充分利用32位微处理器的特性） Provides full multitasking in a single-user environment（在单用户环境下提供完全的多任务环境） Client/Server computing（客户机/服务器结构）

233 Windows 2000 Architecture Modular structure for flexibility（模块结构为系统提供了灵活性） Executes on a variety of hardware platforms（能在多个硬件平台上运行） Supports application written for a variety of other operating system（可运行多种为别的平台编写的应用程序）

234

235 OS Organization OS的组织 Modified microkernel architecture（改进的微内核结构）
Not a pure microkernel （不是纯的微内核） Many system functions outside of the microkernel run in kernel mode（许多在微内核外的系统函数以内核模式运行） Any module can be removed, upgraded, or replaced without rewriting the entire system（任何模块可以被移走、升级、取代等而不用重写整个系统）

236 Layered Structure Hardware abstraction layer (硬件抽象层、HAL)
-Isolates the operating system from platform- specific hardware differences Microkernel（内核） Most-used and most fundamental components of the operating system（由操作系统最有用、最基本的部件组成） Device drivers（设备驱动程序） Translate user I/O function calls into specific hardware device I/O requests

237 W2K Executive I/O manager（I/O管理程序） Object manager（对象管理程序）
Security reference monitor（安全访问监控程序） Process/thread manager（进程与线程的管理） Local procedure call (LPC) Facility（本地过程调用机制） Virtual memory manager（虚拟存储器管理程序） Cache manager（Cache管理） Windows/graphics modules（窗口/图形模块）

238 User Processes Special system support processes
Ex: logon process and the session manager Server processes Environment subsystems User applications

239 Client/Server Model Simplifies the Executive（简化和程序的执行）
客户/服务器模型 Client/Server Model Simplifies the Executive（简化和程序的执行） possible to construct a variety of APIs Improves reliability（提高了可靠性） each service runs as a separate process with its own partition of memory clients can not directly access hardware Provides a uniform means for applications to communicate via LPC（为应用程序间通过LPC进行通信提供了一致的方法） Provides base for distributed computing（为分布式计算提供了适当的基础）

240 Threads and SMP 线程与对称多处理
Different routines can execute simultaneously on different processors Multiple threads of execution within a single process may execute on different processors simultaneously Server processes may use multiple threads Share data and resources between process

241 1.6.2 UNIX 操作系统 Hardware is surrounded by the operating-system
Operating system is called the kernel Comes with a number of user services and interfaces shell C compiler

242 UNIX UNIX命令和库函数 系统调用界面 内核 用户编写的应用程序

243 Modern UNIX Systems System V Release 4 (SVR4) Solaris 2.x 4.4BSD Linux

244 Process Also called a task Execution of an individual program
Can be traced list the sequence of instructions that execute

245 内存中的三个进程及分派程序例 每个进程每次最多只能执行6条指令 分派程序，地址100开始 进程A，起始地址500 进程B，起始地址800
进程C，起始地址1200

246 进程示意图 进程A 进程B 进程C 分派进程 … … … 12008 12009 12010 12011 … 进程在内存中的地址

247 三进程迸发运行示意图 带有阴影的部分为分派进程 进程C时间片用完 首先，进程A运行 进程A用完时间片 分派进程运行，进程切换
进程B在时间片尚未用完时发I/O请求 进程B仍在等待I/O设备，现在轮到进程C运行 进程B换出，等待I/O设备，分派进程将CPU切换到进程C 三进程迸发运行示意图 带有阴影的部分为分派进程

248 3进程并发执行示意图 Time out Time out Time out I/O request Time out 5000 41 100
5001 5002 5003 5004 5005 Time out Time out Time out 分派进程 I/O request 进程 A Time out 进程B 3进程并发执行示意图 进程C

249 三进程迸发运行示意图 带有阴影的部分为分派进程 进程C时间片用完，进入就绪队列 首先，进程A运行 进程A进入就绪队列 分派进程运行，进程切换
进程A从就绪队列调入CPU运行 进程B在时间片尚未用完时发I/O请求，并进入阻塞队列 进程B仍在阻塞队列等待I/O设备，进程C运行 进程B换出，等待I/O设备，分派进程将CPU切换到进程C 三进程迸发运行示意图 带有阴影的部分为分派进程

250 UNIX System V 由AT&T和Ｓun Microsystem 联合开发的SVR4结合了SVR3、4.3BSD、Microsoft Xenix SystemV和SunOS 的特点。它几乎重写了系统Ｖ的内核，产生了一个整洁的，有些复杂的实现版本。这个版本中的新特点包括对实时处理的支持、进程调度类，动态分配数据结构、虚拟存储管理、虚拟文件系统和可以剥夺的内核。 SVR4同时吸收了商业设计者和学院设计者的成果，为商业UNIX的部署提供了统一的平台。它可以从32位的微处理器到超级计算上运行。

251 Multiple Interrupts Disable interrupts while an interrupt is being processed Processor ignores any new interrupt request signals

252 Multiple Interrupts Sequential Order
Disable interrupts so processor can complete task Interrupts remain pending until the processor enables interrupts After interrupt handler routine completes, the processor checks for additional interrupts

253 Multiple Interrupts Priorities
Higher priority interrupts cause lower-priority interrupts to wait Causes a lower-priority interrupt handler to be interrupted Example when input arrives from communication line, it needs to be absorbed quickly to make room for more input

254 Processes （进 程） A program in execution（正在执行的程序）
（进 程） A program in execution（正在执行的程序） An instance of a program running on a computer（计算机中一个正在运行的程序的一个实例） The entity that can be assigned to and executed on a processor（可以分配给处理器并由处理器执行的一个实体） A unit of activity characterized by a single sequential thread of execution, a current state, and an associated set of system resources（由一个顺序执行的线程、一个当前的状态和一组相关的系统资源所刻画的活动单元）

255 Difficulties with Designing System Software
Improper synchronization（不正确的同步） ensure a process waiting for an I/O device receives the signal Failed mutual exclusion（失败的互斥） Nondeterminate program operation（不确定的程序操作） program should only depend on input to it, not relying on common memory areas Deadlocks（死锁）

256 Memory Management 存储器管理 Process isolation（进程隔离）
Automatic allocation and management（自动分配和管理） Support for modular programming（支持模块化程序设计） Protection and access control（保护和访问控制） Long-term storage（长期存储）

257 Virtual Memory 虚拟内存 Allows programmers to address memory from a logical point of view（允许程序员从逻辑的角度来访问存储器） While one process is written out to secondary store and the successor process read in there in no hiatus（空隙）（当一个进程被写入到辅助存储器中并且后继进程被读入时，在连续的进程执行之间将没有缝隙）

258 File System 文件系统 Implements long-term store
文件系统实现了长期存储，它在一个有名字的对象中保存信息，这个对象称作文件。对程序员来说，文件是一个很方便的概念；对操作系统来说，文件是访问控制和保护的一个有用单元。 Implements long-term store Information stored in named objects called files

259 Paging 页 Allows process to be comprised of a number of fixed-size blocks, called pages（进程由许多固定大小的块组成，这些块称为页） Virtual address is a page number and an offset within the page（虚拟地址由页号和页内偏移量组成） Each page may be located any where in main memory（进程的每一页可以放在主存的任何地方） Real address or physical address in main memory（分页系统提供了程序中使用的虚地址和主存中的实地址或物理地址的映射）

260

261 Virtual Memory Addressing
Real Address Main Memory Processor Memory Management Unit Virtual Address Disk Address Secondary Memory

262 Information Protection and Security
Access control（存取控制） regulate user access to the system Information flow control（信息流控制） regulate flow of data within the system and its delivery to users Certification（认证） proving that access and flow control perform according to specifications

263 Scheduling and Resource Management
调度和资源管理 Fairness（公平性） give equal and fair access to all processes Differential responsiveness（有差别的响应性） discriminate between different classes of jobs Efficiency（有效性） maximize throughput, minimize response time, and accommodate as many uses as possible

264 Major Elements of Operating System

265 System Structure 系统结构 View the system as a series of levels
Each level performs a related subset of functions Each level relies on the next lower level to perform more primitive functions This decomposes a problem into a number of more manageable subproblems

266 Operating System Design Hierarchy
操作系统设计的层次 Level Name Objects Example Operations 13 Shell User programming Statements in shell language environment 12 User processes User processes Quit, kill, suspend, resume 11 Directories Directories Create, destroy, attach, detach, search, list 10 Devices External devices, such Open, close, as printer, displays read, write and keyboards 9 File system Files Create, destroy, open, close read, write 8 Communications Pipes Create, destroy, open. close,

267 处理器硬件 Level Name Objects Example Operations
7 Virtual Memory Segments, pages Read, write, fetch 6 Local secondary Blocks of data, device channels Read, write, allocate, free store 5 Primitive processes Primitive process, Suspend, resume, wait, signal （原始过程） semaphores, ready list（原始过程、信号装置） 处理器硬件 4 Interrupts programs Interrupt-handling Invoke, mask, unmask, retry Procedures Procedures, call stack, Mark stack, call, return （过程） display 2 Instruction Set Evaluation stack, micro Load, store, add, subtract （指令集合） program interpreter, branch scalar and array data 1 Electronic circuits Registers, gates, buses, etc. Clear, transfer, activate, （电路） complement

268 进程的定义 进程是操作系统中最核心的概念，进程的定义有多种，以下是常用的定义： ※ 一个正在执行的程序 ※ 计算机中正在运行的程序的一个实例
※ 一个正在执行的程序 ※ 计算机中正在运行的程序的一个实例 ※ 可以分配给处理器并由处理器执行的一个实体 ※ 由一个顺序的执行线程、一个当前状态和一组相关的系统资源所刻画的活动单元

269 进程与程序的区别 进程是由正文段（text）、用户数据段（User Segment）及系统数据段（System Segment）或上下文（context）共同组成的一个执行环境。 程序只是一个普通的文件，是一个机器代码指令和数据的集合。这些指令和数据存储在磁盘上的一个可执行映像（Executable Image） 中。 进程除了包含程序中的所有内容外，还包含一些额外的数据

270 Consists of three components
进程包含三部分 Consists of three components An executable program Associated data needed by the program Execution context of the program All information the operating system needs to manage the process

271 进程示意图

272 Process identification
Process Control Block Process identification 进程标识信息 Identifiers Numeric identifiers that may be stored with the process control block include Identifier of this process （本进程标识符） Identifier of the process that created this process (parent process，父进程标识符) User identifier （用户标识符）

273 Processor State Information
Process Control Block Processor State Information 进程状态信息 User-Visible Registers A user-visible register is one that may be referenced by means of the machine language that the processor executes. Typically, there are from 8 to 32 of these registers, although some RISC implementations have over 100.

274 Processor State Information
Process Control Block Processor State Information 进程状态信息 Control and Status Registers These are a variety of processor registers that are employed to control the operation of the processor. These include •Program counter: Contains the address of the next instruction to be fetched •Condition codes: Result of the most recent arithmetic or logical operation (e.g., sign, zero, carry, equal, overflow) •Status information: Includes interrupt enabled/disabled flags, execution mode

275 Processor State Information
Process Control Block Processor State Information 进程状态信息 Stack Pointers Each process has one or more last-in-first-out (LIFO) system stacks associated with it. A stack is used to store parameters and calling addresses for procedure and system calls. The stack pointer points to the top of the stack.

276 Process Control Information
Process Control Block Process Control Information Scheduling and State Information This is information that is needed by the operating system to perform its scheduling function. Typical items of information: •Process state: defines the readiness of the process to be scheduled for execution (e.g., running, ready, waiting, halted). •Priority: One or more fields may be used to describe the scheduling priority of the process. In some systems, several values are required (e.g., default, current, highest-allowable) •Scheduling-related information: This will depend on the scheduling algorithm used. Examples are the amount of time that the process has been waiting and the amount of time that the process executed the last time it was running. •Event: Identity of event the process is awaiting before it can be resumed

277 Process Control Information
Process Control Block Process Control Information Data Structuring A process may be linked to other process in a queue, ring, or some other structure. For example, all processes in a waiting state for a particular priority level may be linked in a queue. A process may exhibit a parent-child (creator-created) relationship with another process. The process control block may contain pointers to other processes to support these structures.

278 Process Control Information
Process Control Block Process Control Information Interprocess Communication Various flags, signals, and messages may be associated with communication between two independent processes. Some or all of this information may be maintained in the process control block. Process Privileges Processes are granted privileges in terms of the memory that may be accessed and the types of instructions that may be executed. In addition, privileges may apply to the use of system utilities and services.

279 Process Control Information
Process Control Block Process Control Information Memory Management This section may include pointers to segment and/or page tables that describe the virtual memory assigned to this process. Resource Ownership and Utilization Resources controlled by the process may be indicated, such as opened files. A history of utilization of the processor or other resources may also be included; this information may be needed by the scheduler.

280 Memory Tables Allocation of main memory to processes（分配给进程的主存）
Allocation of secondary memory to processes（分配给进程的辅存） Protection attributes for access to shared memory regions（主存块或虚存块的任何保护属性，如那些进程可以访问某些共享存储器区域） Information needed to manage virtual memory（管理虚存所需要的信息）

281 I/O Tables I/O device is available or assigned（I/O设备可用或已分配给某进程）
Status of I/O operation（如正在进行I/O操作，操作系统需要知道I/O操作的状态和） Location in main memory being used as the source or destination of the I/O transfer（作为I/O传送的源和目标的主存单元）

282 File Tables Existence of files（文件是否存在）
Location on secondary memory（文件在辅存中的位置） Current Status（文件的当前状态） Attributes（文件的属性） Sometimes this information is maintained by a file-management system（有时，这些信息由文件管理系统维护）

283 Process Table Where process is located
Attributes necessary for its management Process ID Process state Location in memory

284 Process Location Process includes set of programs to be executed
Data locations for local and global variables Any defined constants Stack Process control block Collection of attributes Process image Collection of program, data, stack, and attributes

285

286 Processes and Resources (resource allocation at one snapshot in time)
进程和资源（某一时刻的资源分配） Processes and Resources (resource allocation at one snapshot in time)

287 算法1的例（栈的存取） 现有两个进程，procedure 1 和 procedure 2 ，前者用来从栈中取数据，后者用来向栈中压数据。临界区为两进程中的对栈进行操作的代码。公用变量 turn 为两进程进入临界区的标记。 procedure 1 getaddr(top) while(turn!=1); //进入临界区 begin local r r ←(top) top ←top-1 return r end // 退出临界区 turn=2; 临界区 procedure 2 reladdr(blk) while(turn!=2); //进入临界区 begin top ← top+1 (top) ← blk end // 退出临界区 turn=1; 临界区

288 带互斥的执行过程 a a a b b b e e e f f f 最后，getaddr过程取到的数据为正确值。 CPU的执行过程：
执行过程reladdr(blk) 完成top ←top+1 进程切换， 执行getaddr(top) C a b e f a b e f a b e f getadd首先要测试共享变量turn的值是否为2，此时由于进行reladdr尚在临界区中，turn的值为1，getadd只能不停地测试turn 的值而不能执行其它操作。 top top C top 当reladdr 执行完压入数据，退出临界区后，进程getaddr(top)才能执行。 最后，getaddr过程取到的数据为正确值。 堆栈的取和存数过程

289 P，V操作的例 有一个铁笼子，每次只能放入一个动物。猎手向笼中放入老虎，农民向笼中放入猪；动物园等待取笼中的老虎，饭店等待取笼中的猪。请用P、V（wait signal）原语写出同步执行的程序。 解：本题中，猎手、农民、动物园和饭店共享一个笼子，且笼中每次只能放入一个动物。当笼子为空时，猎手或农民可将一个动物放入笼中。若放入笼中的是老虎，则允许动物园取老虎，饭店必须等待；若放入的是猪，则饭店可取猪，动物园必须等待。 所以，要设置3个信号量，Scage,Spig,Stiger。信号量Scage表示笼中是否为空，其初值为1（开始假设是空的），信号量Spig表示笼中是否有猪，其初值为零。信号量Stiger表示笼中是否有老虎，初值为零。除主函数外，该问题共有四个同步描述函数。

290 用P、V操作实现在一个笼子里放猪和老虎的问题
semaphore Scage=1; semaphore Spig=0; semaphore Stiger=0; main(){ cobegin hunter(); peasant(); hotel(); zoo(); coend } hotel(){ while(true) { P(Spig); 从笼中取出猪； V(Scage); … } zoo(){ P(Stiger); 从笼中取老虎； peasant(){ while(true) { … p(Scage); 将猪放入笼子； V（Spig); } hunter(){ while(true) { … P(Scage); 将老虎放入笼中； V(Stiger); }

291 多进程并发执行，两队列模型

292 算法之二

293 多等待队列运行示意图

294 互斥算法1的动画演示

295 用信号量处理有界缓冲区问题之一

296 有界缓冲区问题之二——缓冲区满

297 有界缓冲区问题之三——缓冲区空

298 有界缓冲区问题之四——死锁

299 本电子讲稿的使用说明 一、讲稿的使用环境 1 主操作系统：windows 2000、windows XP pro、windows 2003
2 辅操作系统：Red Hat Linux 8或相应linux操作系统，用虚拟PC安装在windowns中，要求安装gcc编译器并带有调试器kdbg 3 应用软件：MS PowerPoint 2002或以上版本 4 其它软件：Flash MX 、Visual C/C++6.0

300 二、使用方法 讲稿按教学过程制作，上课或自学时可顺序执行。移动鼠标，当讲稿中有“小手”时，表明该处有超级链接，单击时可进入超级链接。
按Esc键，可随时退出超级链接，回到原来的页面。 当单击“小手”处，出现要执行程序时，如果找不到相应的程序，如VC++6.0的编译程序时，说明可执行文件的路径与讲稿中预先设置的不符，需要手工执行程序。