chap2123 处理器中断技术进程及其实现2013

1、操作系统第二章 处理器管理,南京大学软件学院 2013,第二章 处理器管理,2.1 中央处理器 2.2 中断技术 2.3 进程及其实现 2.4 线程及其实现 2.5 Linux进程和线程 2.6 Windows 2003进程和线程 2.7 处理器调度 2.8 处理器调度算法 2.9 Linux调度算法 2.10 Windows 2003调度算法,2.1中央处理器,计算机组织结构 处理器寄存器 指令执行 多处理器系统与多核处理器系统,2.1中央处理器1. 计算机组织结构,Processor Main Memory referred to as real memory or primary mem

2、ory Volatile(挥发的 持久的 persistent) I/O modules Secondary memory devices Input/Output devices, terminals Communications equipment System bus communication among processors, memory, and I/O modules,Top-Level Components,User-visible Registers Enable programmer to minimize main-memory references by optimi

3、zing 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,2.1中央处理器2. 处理器寄存器,User-Visible Registers,May be referenced by machine language Available to all programs - application program

4、s and system programs Types of registers Data Address,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 stac

5、k,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): record all status of an executing program. (the term used by OS) Program counter condition code

6、s Interrupt enable/disable Supervisor/user mode,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,特权指令和处理器状态,从资源管理和控制程序执行的角度出发，必须设置特权指令

7、，提供给操作系统的核心程序使用 处理器状态 管理状态(特权状态、系统模式、特态或管态): 处理器可以执行全部指令，使用所有资源，并具有改变处理器状态的能力 用户状态(目标状态、用户模式、常态或目态): 处理器只能执行非特权指令 核心状态、管理状态和用户状态,Pentium的处理器状态,0级为操作系统内核级：处理I/O、存储管理、和其他关键操作 1级为系统调用处理程序级：用户程序可以通过调用这里的过程执行系统调用，但是只有一些特定的和受保护的过程可以被调用 2级为共享库过程级：它可以被很多正在运行的程序共享，用户程序可以调用这些过程，读取它们的数据，但是不能修改它们 3级为用户程序级,IBM的程

8、序状态字寄存器,CMWP位依次为基本/扩充控制方式位、开/关中断位、运行/等待位、目态/特态位,2.1中央处理器3.指令执行: 指令与指令寄存器,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

9、 execution Fetched instruction is placed in the instruction register,Instruction Cycle,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,Example of P

10、rogram Execution,I/O Function,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 Example: Direct Memory Access (DMA),多处理器系统分类： 共享存储(紧密耦合)多处理机系统 分布存储(松散耦合)多处理机系统。 多处理器指在一个体系结构上放置多个CPU芯片，

11、而多核则指在同一块CPU芯片上放置多个核(core)，即执行单元。,2.1中央处理器4.多处理器系统与多核处理器系统,多处理器系统与多核处理器系统,x86体系结构下，处理器4个演变阶段。 (1) 多处理器结构、 (2) 超线程结构、 (3)多核结构、 (4)多核超线程结构。,(1)多处理器结构,多处理器系统与多核处理器系统,(2)超线程结构,多处理器系统与多核处理器系统,双核,多处理器系统与多核处理器系统,(3)多核结构,Intel 酷睿 i7 四核CPU,四核,多处理器系统与多核处理器系统,(3)多核结构,(4)多核超线程结构,多处理器系统与多核处理器系统,操作系统与多核处理器,处理器通信支

12、持 进程/线程数据共享支持 存储器层次及管理 程序并行执行模型支持 同步支持 调度及优化 能耗管理,多处理器系统与多核处理器系统,2.2中断技术,中断概念与中断事件处理 中断优先级和多重中断 Linux中断处理 Windows 2003中断处理,中断的定义,中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。,2.2中断技术,1.中断概念与中断事件处理,An interruption of the normal sequence of execution Improves proce

13、ssing 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,2.2中断技术,Classes of Interrupts,Program arithmetic overflow divisi

14、on by zero execute illegal instruction reference outside users memory space Timer I/O Hardware failure,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,Interrupt

15、Cycle,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,中断与中断源,强迫性中断事件 硬件故障中断事件(硬件故障引起) 电源故障, 主存储器故障, 程序性中断事件(执行机器指令引起) 除数为零, 操作数溢

16、出, 非法指令, 目态下使用特权指令, 地址越界, 外部中断事件(外部事件引起) 时钟中断, 重启动中断, I/O中断事件(I/O控制系统发现外设完成I/O或I/O出错引起) 打印完成, 打印缺纸, ,中断与中断源,自愿性中断事件 (进程执行访管指令请求OS服务引起) 请求分配外设, 请求I/O, 关于中断的分类 中断、异常与系统服务(中断俘获、陷阱、系统陷阱) 内中断、外中断、软中断、自由中断,两类中断事件的中断处理过程,两类中断事件与中断处理过程,中断装置,中断寄存器: 记录强迫性中断事件的寄存器，每一种中断可设置一个中断寄存器 中断字: 中断寄存器的内容, 记录了所发生中断的类型和原因(

17、如I/O中断的中断字为”通道号,设备号”) 中断装置是一种硬件, 当中断事件发生后, 它能改变处理器内操作的顺序,中断装置与中断响应,发现中断源，提出中断请求 发现内容非零的中断寄存器 决定这些中断是否应该屏蔽 当有多个要响应的中断源时，根据规定的优先级选取一个 把中断字送到当前PSW的中断码字段 中断当前程序的执行 保存当前程序的PSW到内存约定单元 启动操作系统的中断处理程序 从内存约定单元取出中断处理程序的PSW,中断装置与中断响应,中断的处理,中断处理程序 处理中断事件的控制程序, 主要任务是处理中断事件和恢复正常操作 中断处理过程 保护未被硬件保护的一些必需的处理状态 通过分析被中断

18、进程的PSW中断码字段,识别中断源 分别处理发生的中断事件 恢复正常操作,处理器中断事件的处理,电源故障的处理: 处理器现场信息送主存 停止外围设备工作 停止处理器工作 故障排除后, 从约定点重新启动操作系统 必要时操作员干预 主存储器故障的处理 中止有关程序的运行, 向操作员报告,程序性中断事件的处理,对于无法克服的程序性中断事件(如非法指令, 目态下使用特权指令, 地址越界, ): 向操作员报告请求干预 对于除数为零, 操作数溢出等程序性中断事件: 可以由用户程序自行处理, 或由操作系统进行标准处理,外部中断事件的处理,时钟中断事件: 每隔一个时间间隔发生一次, 操作系统自动更改系统时钟和

19、间隔时钟的计时；且当间隔时钟寄存器的值为临界值时, 操作系统进行专门处理 控制台中断事件(重启动中断, 关机中断, ): 操作员利用控制台发出命令, 请求服务, 操作系统响应并服务,自愿性中断事件的处理,用户程序执行系统调用(访管指令,广义指令); 操作系统把系统调用参数作为中断字, 分析检查后进行相应处理,中断控制流程,2.2中断技术,2.中断优先级与多重中断,中断优先级与中断屏蔽,中断优先级：当计算机同时检测到多个中断时, 中断装置响应中断的顺序。常见的处理次序可能是处理器中断事件、自愿性中断事件、程序性中断事件、时钟中断等外部中断事件、输入输出中断事件、重启动和关机中断事件 中断屏蔽：当

20、计算机检测到中断时, 中断装置通过中断屏蔽位决定是否响应已发生的中断,中断优先级与中断屏蔽,决定中断处理次序的因素 中断屏蔽可以使中断装置不响应某些中断 中断优先级决定了中断装置响应中断的次序 中断可以嵌套处理, 但嵌套的层数应有限制 中断的嵌套处理改变了中断处理的次序,(1) Linux内核处理流程,2.2中断技术,3.Linux中断处理,快中断与慢中断, Linux中，区分快中断和慢中断两类中断事件。 处理慢中断前需保存所有寄存器的内容，而快中断处理仅要保存被常规C函数修改的寄存器；慢中断处理时，不屏蔽其他中断信号，而快中断处理时会屏蔽所有其他中断； 慢中断处理完毕后，通常不立即返回被中断

21、的进程，而是进入调度程序重新调度，调度结果未必是被中断的进程运行(是抢先式调度)。而快中断处理完毕后，通常恢复现场返回被中断的进程继续执行(是非抢先式调度)。,(2) 下半部分处理概述,中断处理程序的特点 什么是下半部分处理? Top half Bottom half,中断处理程序特点,以异步方式运行，可能会打断关键代码的执行，甚至打断其他中断处理程序的执行； 在屏蔽中断状态下运行，最坏的情况会禁止所有中断； 要对硬件进行操作，有很高的时限要求；它在中断上下文中运行，故不能被阻塞 。,Linux各种下半部分机制,bottom half、 task queue、 tasklet、 work qu

22、eue、 Softirq。,Windows2003陷阱调度,2.2中断技术,3. Windows 2003中断处理,Windows2003中断请求级别,Windows 2003中断屏蔽,系统服务调度(1),A0,SUB0,SUB1,SUBi,SUBn,A1,Ai,An,A0,A1,Ai,An,系统调用的处理过程,System Call,用户程序,系统调用处理子程序,取系统功能号 找入口地址表 相应入口地址,结束处理 恢复现场,保护CPU现场,自陷指令,系统调用陷入机构,入口地址表,系统服务调度(2),61,第二章 处理器管理,2.1 中央处理器 2.2 中断技术 2.3 进程及其实现 2.4

23、线程及其实现 2.5 Linux进程和线程 2.6 Windows 2003进程和线程 2.7 处理器调度 2.8 处理器调度算法 2.9 Linux调度算法 2.10 Windows 2003调度算法,本主题教学目标,掌握进程的概念，可再入过程 掌握进程的状态、进程的挂起，以及队列实现模型 掌握操作系统的控制结构 掌握进程描述与控制的数据结构 掌握处理机模式的概念 掌握进程创建、模式切换、进程切换、进程队列、进程原语等进程实现的原理 了解操作系统的执行模型 了解SVR4的进程管理,2.3 进程及其实现,进程的概念 进程的状态和转换 进程的描述和组成 进程控制和管理,Major Require

24、ments of an OS,Interleave the execution of several processes to maximize processor utilization while providing reasonable response time Allocate resources to processes Support interprocess communication(IPC) and user creation of processes,1. 进程的概念,Process,Also called a task Execution of an individua

25、l program Can be traced list the sequence of instructions that execute,Process Definition,进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动 A process is a program in execution, including: Process id and Data structure for process management and execution Code: program in memory Data: data in memory and its values Reg

26、ister values Program status word,Process Definition,Processi: (Pi, Ci, Di, Ri, Pswi) Program(data) Program(data) in memory (P1, C1, D1, R1, Psw1) and (P2, C2, D2, R2, Psw2) C1 and C2(different program) , but D1 and D2(different data) C1 and C2(different program) , but D1 and D2(same data) C1 and C2(

27、same program), but D1 and D2(different data) C1 and C2(same program), but D1 and D2(same data) (P1, C1, D1, R1, Psw1) and (P2, C2, D1, R2, Psw2) Concurrent programming(in fact, only share some data) (P1, C1, D1, R1, Psw1) and (P2, C1, D2, R2, Psw2) Share code(Reentrant program, Reentrant Procedure),

28、Process States Two-State Process Model Three-State Process Model Five-State Process Model Process Suspend,2. 进程的状态和转换,Two-State Process Model,Process may be in one of two states Running Not-running,2. 进程的状态和转换,Not-Running Process in a Queue,Process Creation,Submission of a batch job User logs on Cre

29、ated to provide a service such as printing Process creates another process,Process Termination,Batch job issues Halt instruction User logs off Quit an application Error and fault conditions,Reasons for Process Termination,Normal completion Time limit exceeded Memory unavailable Bounds violation Prot

30、ection error example write to read-only file Arithmetic error Time overrun process waited longer than a specified maximum for an event,Reasons for Process Termination,I/O failure Invalid instruction happens when try to execute data Privileged instruction Data misuse Operating system intervention suc

31、h as when deadlock occurs Parent terminates so child processes terminate Parent request,Process States Two-State Process Model Three-State Process Model Five-State Process Model Process Suspend,2. 进程的状态和转换,Three-State Process Model,Not-running(Ready ) ready to execute Blocked(Waiting ) waiting for I

32、/O Dispatcher cannot select the blocked process,2. 进程的状态和转换,Process State: Three States,Running, Ready, and Blocked(Wait),Process State: Three States,运行态等待态：等待使用资源；等待外设传输；等待人工干预/信号 等待态就绪态：资源得到满足；外设传输结束；人工干预/信号完成 运行态就绪态：运行时间到；出现有更高优先权进程 就绪态运行态：CPU空闲时选择一个就绪进程,Process States Process Two-State Process M

33、odel Three-State Process Model Five-State Process Model Process Suspend,2. 进程的状态和转换,Five-State Process Model,Running Ready Blocked New Exit,2. 进程的状态和转换,Five-State Process Model,Process State: Five States,NULL新建态：执行一个程序/创建一个子进程 新建态就绪态：当OS完成了进程创建的必要操作，且当前系统的性能和虚拟内存的容量均允许 运行态终止态：当一个进程到达了自然结束点，或出现了无法克服的

34、错误，或被操作系统所终结，或被其他有终止权的进程所终结 终止态NULL：完成善后操作 就绪态终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程 等待态终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程,Using Two Queues,89,事件1 发生,事件2 发生,事件n 发生,允许进入,分派,释放,分派,分派,Yet another queuing model：每个优先级对应一个就绪队列,90,有挂起态的排队模型， 每个事件一个阻塞队列,91,Representation of Process Scheduling,Process States Process

35、 Two-State Process Model Three-State Process Model Five-State Process Model Process Suspend,2. 进程的状态和转换,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 d

36、isk Two new states Blocked, suspend Ready, suspend,2. 进程的状态和转换,Process State: Suspended,由于进程的不断创建，系统的资源已经不能满足进程运行的要求，这个时候就必须把某些进程挂起(suspend)，对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的,One Suspend State,Two Suspend States,97,改进：每个优先级一就绪个队列,Process State: Suspended,一个挂起进程等同于不在主存的进程，它将不参与进程调度直到它们被对换进主存。它具有如下特征：

37、 该进程不能立即被执行 挂起进程可能会等待一个事件，但所等待的事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件 进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行 结束进程挂起状态的命令只能通过操作系统或父进程发出,Process State: Suspended,等待态挂起等待态：如果当前不存在就绪进程，那么至少有一个等待态进程将被对换出去成为挂起等待态；操作系统根据当前资源状况和性能要求，也可以决定把等待态进程将被对换出去成为挂起等待态 挂起等待态挂起就绪态：引起进程等待的事件发生之后，相应的挂起等待态进程将转换为挂起就绪态 就绪态挂起就绪态：操作系统根据当前资源状况和

38、性能要求，也可以决定把就绪态进程将被对换出去成为挂起就绪态,Process State: Suspended,运行态挂起就绪态：当一个具有较高优先级的挂起等待态进程的等待事件结束后，它需要抢占了CPU，而此时主存空间有不够，从而可能导致正在运行的进程转化为挂起就绪态。另外处于运行态的进程也可以自己挂起自己 新建态挂起就绪态：考虑到系统当前资源状况和性能要求，可以决定新建的进程将被对换出去成为挂起就绪态,Process State: Suspended,挂起就绪态就绪态：当内存中没有就绪态进程，或者挂起就绪态进程具有比就绪态进程更高的优先级，系统将把挂起就绪态进程转换成就绪态 挂起等待态等待态：

39、当一个进程等待一个事件时，原则上时不需要把它调入内存的。但是在下面一种情况下，这一状态变化时可能的。当一个进程退出后，主存已经有了一大块自由空间，而某个挂起等待态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生了这一状态变化,Reasons for Process Suspension,Process Description and Control,Process States Process Description Processes and Resources OS Control Structures Process Control Structures Pr

40、ocess Control Examples: Process,3. 进程的描述和组成,Process Description,Process Description and Control,Process States Process Description Processes and Resources OS Control Structures Process Control Structures Process Control Examples: Process,3. 进程的描述和组成,Operating System Control Structures,Information ab

41、out the current status of each process and resource Tables are constructed for each entity the operating system manages,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 man

42、age virtual memory,I/O Tables,I/O device is available or assigned Status of I/O operation Location in main memory being used as the source or destination of the I/O transfer,File Tables,Existence of files Location on secondary memory Current Status Attributes Sometimes this information is maintained

43、 by a file-management system,Process Table,Where process is located Attributes necessary for its management Process ID Process state Location in memory,OS Control Structure,Process Description and Control,Process States Process Description Processes and Resources OS Control Structures Process Contro

44、l Structures Process Location Process Attributes Process Control Examples: Process,3. 进程的描述和组成,Process Location,Process includes set of programs and data Programs: the program to be executed User Data: the modifiable part of the user space, include program data, user stack, and program that may be m

45、odified System Stack: used to store parameters and calling addresses for system call Process Control Block (PCB): Collection of attributes Process image Collection of program, data, stack, and attributes (PCB),114,进程映像 进程控制块：存储进程标志信息、现场信息和控制信息。 进程程序块：被执行的程序，规定进程一次运行应完成的功能。通常它是纯代码，作为一种系统资源可被多个进程共享。 进

46、程核心栈：每个进程捆绑一个，进程在核心态下工作时使用，用来保存中断/异常现场，及执行函数调用的参数和返回地址，系统调用的参数和返回地址等。 进程数据块：即进程私有地址空间，存放各种私有数据，用户栈也在数据块中开辟，用于函数调用时存放栈帧、局部变量等参数，包括程序数据、用户栈和可修改的程序。,3. 进程的描述和组成,115,程序块,数据块,PCB,进程映像,核心栈,Process Description and Control,Process States Process Description Processes and Resources OS Control Structures Proc

47、ess Control Structures Process Location Process Attributes Process Control Examples: Process,3. 进程的描述和组成,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 cr

48、eated this process (parent process) User identifier,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, altho

49、ugh some RISC implementations have over 100.,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 instruct

50、ion 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,Process Control Block,Processor State Information Stack Pointers Each process has one

51、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.,Process Control Block,Process Control Information Scheduling and State Information: This is i

52、nformation that is needed by the operating system to perform its scheduling function. Typical items of information: Process state Priority Scheduling-related information: This will depend on the scheduling algorithm used Event: Identity of event the process is awaiting before it can be resumed,Proce

53、ss 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-crea

54、ted) relationship with another process. The process control block may contain pointers to other processes to support these structures.,Process Control Block,Process Control Information InterProcess Communication Various flags, signals, and messages may be associated with communication between two in

55、dependent processes. Some or all of this information may be maintained in the process control block.,Process Control Block,Process Control Information Process Privileges Processes are granted privileges in terms of the memory that may be accessed and the types of instructions that may be executed. I

56、n addition, privileges may apply to the use of system utilities and services.,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 Utilizat

57、ion 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.,Process List Stuctures,Processor State Information,Contents of processor registers User-

58、visible registers Control and status registers Stack pointers Program status word (PSW) contains status information Example: the EFLAGS register on Pentium machines,Pentium II EFLAGS Register,Process Context (进程上下文),User-level context: include process program, process data, user stack Register conte

59、xt: include PSW, stack pointer, general-purpose register System-level context: include PCB, memory region table, kernel stack,Process States Process Description Process Control Modes of Execution Process Creation Process Switching Execution of the OS Summary Examples: Process,4. 进程控制和管理,Modes of Execution,User mode Less-privileged mode User programs typically execute in this mode System mode, control mode, or kernel mode More-privileged mode Kernel of the operating system,4.进程的控制和管理,Process States Process Description Process Control Modes of Executio