操作系统期末总复习
第2章操作系统的运行环境
OS的运行环境包括硬件环境和其他系统软件组成的软件环境，这些环境既是OS管理的对象，又是OS的支持者和协作者。
主要内容
?硬件环境：
?CPU
?主存储器
?缓冲
?中断
?时钟及时钟队列
?软件支持：
?重定位
一、概述
?操作系统运行的硬件环境组成
?中央处理器（CPU）
?存储系统
?中断机制
?时钟以及时钟队列
?任何系统软件都是硬件功能的延伸，操作系统直接依赖于硬件条件；
?OS的硬件环境以较分散的形式同各种管理相结合；
?实现操作系统时必须理解计算机基本结构、操作系统管理的重要资源；
二、中央处理器（CPU）
单机与多处理器系统
?如果一个计算机系统只有一个处理器，称之为单机系统；
?如果有多个处理器称之为多处理器系统。
指令系统
?早期的微处理器，指令系统的功能相对来说比较弱。
?当代的微处理器，结构非常复杂。
1、CPU的构成与基本工作方式
?处理器由运算器、控制器、一系列的寄存器以及高速缓存构成：
?运算器：实现指令中的算术和逻辑运算，是计算机计算的核心。
?控制器：负责控制程序运行的流程，包括取指令、维护CPU状态、CPU与内
存的交互等等。
?寄存器：是指令在CPU内部作处理的过程中暂存数据、地址以及指令信息的存
储设备，在计算机的存储系统中它具有最快的访问速度。
?高速缓存：处于CPU和物理内存之间，
?一般由控制器中的内存管理单元（MMU：Memory Management
Unit）管理；
?访问速度快于内存，低于寄存器。
?通过高速缓存可以使CPU的高速指令处理和低速内存访问得以匹配，
从而提高CPU的效率。
指令系统
?每台计算机机器指令的集合称指令系统，它反映了一台机器的功能和处理能力，可以
分为以下五类：
?数据处理类指令：
用于执行算术和逻辑运算。
?I/O类指令
用于启动外围设备，让主存和设备交换数据。
?寄存器数据交换类指令：
用于在处理器的寄存器和存储器之间交换数据。
?控制类指令：
如转移，用于改变执行指令序列。
?处理器控制指令：
修改处理器状态，改变处理器工作方式。
?在单道程序系统中，用户程序可以直接使用CPU指令启动I/O设备，进行I/O操作。
?问题是：在多道程序系统中，这种模式可不可行？
专门设计了一系列基本机制：
?具有特权级别的处理器状态，能在不同特权级运行的各种特权指令。
?硬件机制使得OS可以和普通程序隔离，实现保护和控制
2、特权指令和非特权指令
?特权指令：只能由操作系统使用的指令。如：
?启动某设备；
?设臵时钟；
?允许和禁止中断；
?清内存；
?在进程之间切换处理机；
?建立存储保护；
?存取用于内存保护的寄存器；
?执行输入输出操作；
?停止一个CPU的工作。
?使用多道程序设计技术的计算机指令系统必须要区分为特权指令和非特权指令。
?特权指令一般引起处理器状态的切换：
?处理器通过特殊的机制将处理器状态切换到操作系统运行的特权状态（管态）
?然后将处理权移交给操作系统中的一段特殊代码，这一个过程称为陷入?CPU如何知道当前运行的是操作系统还是一般应用软件？有赖于处理器状态的标识。
3、处理器的状态
?根据运行程序对资源和机器指令的使用权限将处理器设臵为不同状态。
?多数系统将处理器工作状态划分为管态和目态：
?管态：操作系统管理程序运行的状态，较高的特权级别，又称为特权态（特态）、
系统态。
?目态：用户程序运行时的状态，较低的特权级别，又称为普通态（普态）、用
户态。
有些系统将处理器状态划分核心状态，管理状态和用户程序状态（目标状态）三种
管态和目态的差别
?处理器处于管态时：
?可以执行全部指令（包括特权指令）
?可使用所有资源
?具有改变处理器状态的能力
?处理器处于目态时：
?只有非特权指令能执行
?特权级别不同，可运行指令集合也不同。
?特权级别越高，可以运行指令集合越大。
?高特权级别对应的可运行指令集合包含低特权级的。
管态和目态的切换
4、程序状态字PSW
在PSW中专门设臵一位，根据运行程序使用指令的权限而设臵，PSW (Program
Status Word ):
?CPU的工作状态码——指明管态还是目态，用来说明当前在CPU上执行的是操作系统
还是一般用户，从而决定其是否可以使用特权指令或拥有其它的特殊权力
?条件码——反映指令执行后的结果特征
?中断屏蔽码——指出是否允许中断
微处理器M68000的程序状态字
微处理器Intel 80386的程序状态字
?Pentium的处理器状态有四种，支持4个保护级别，0级权限最高，3级权限最低。一
种典型的应用是把4个保护级别依次设定为：
?0级为操作系统内核级。处理I/O、存储管理、和其他关键操作。
?1级为系统调用处理程序级。用户程序可以通过调用这里的过程执行系统调用，
但是只有一些特定的和受保护的过程可以被调用。
?2级为共享库过程级。它可以被很多正在运行的程序共享，用户程序可以调用
这些过程，读取它们的数据，但是不能修改它们。
?3级为用户程序级。它受到的保护最少。
?各个操作系统在实现过程中可以根据具体策略有选择地使用硬件提供的保护级别，如
运行在Pentium上的Windows操作系统只使用了0级和3级。
三、主存储器
支持OS运行硬件环境的一个重要方面：
?作业必须把它的程序和数据存放在主存储器（内存）中才能运行；
?多道程系统中，若干个程序和相关的数据要放入主存储器；
?操作系统要管理、保护程序和数据，使它们不至于受到破坏；
?操作系统本身也要存放在主存储器中并运行。
1、存储器的类型
两类存储器：读写型的存储器
只读型的存储器读写型的存储器
?可把数据存入其中任一地址单元，并可在以后的任何时候把数据读出，或者重新存入
新的数据的一种存储器
?常被称为随机访问存储器（RAM：Random Access Memory）
?RAM主要用作存放随机存取的程序的数据
只读型的存储器:
?只能从其中读取数据，但不能随意用普通方法写入数据（写入数据只能用特殊方法）?称为只读存储器（ROM：Read-Only Memory）
变型:PROM、EPROM和EEPROM
?PROM:一种可编程只读存储器，使用特殊PROM写入器写入数据
?EPROM:用特殊的紫外线光照射此芯片，以“擦去”信息，恢复原来状态，然后使用
特殊EPROM写入器写入数据
?EEPROM：电可擦除可编程ROM，又称闪存。
存储访问局部性原理
提高存储系统效能关键点：程序存储访问局部性原理
?程序执行时，有很多的循环和子程序调用，一旦进入这样的程序段，就会重复存取相
同的指令集合
?对数据存取也有局部性，在较短的时间内，稳定地保持在一个存储器的局部区域
?处理器主要和存储器的局部打交道
?在经过一段时间以后，使用的代码和数据集合会改变
2、存储分块
?存储最小单位:“二进位”，包含信息为0或1
?最小编址单位:字节，一个字节包含八个二进位
主流个人电脑
?主存:128MB～512MB之间
?辅助存储器:在20GB～70GB
工作站、服务器
?主存:512MB-4GB之间
?硬盘容量:数百GB
为简化分配和管理，存储器分成块,称一个物理页（Page）
?块的大小：512B、1K、4K、8K
3、存储保护设施
?对主存储器中的信息加以严格的保护，使操作系统及其它程序不被破坏，是其正确运
行的基本条件之一。
?多用户,多任务操作系统：
OS给每个运行进程分配一个存储区域。
?问题：
?多个程序同时在同一台机器上运行怎样才能互不侵犯？
存储保护的硬件支持
?界地址寄存器（界限寄存器）：
在CPU 中设臵一对界限寄存器来存放该用户作业在主存中的下限和上限地址，分别称为下限寄存器和上限寄存器。
?存储保护键：
每个存储块都有一个存储保护键，附加在每个存储块上。当操作系统挑选作业运行时，操作系统同时将该作业的存储键号存放到程序状态字PSW的存储键(“钥匙”)域中。
每当CPU访问主存时，都将对主存块的存储键与PSW中的“钥匙”进行比较。以判断访问是否合法。
四、缓冲技术
?缓冲区是硬件设备之间进行数据传输时，用来暂存数据的一个存储区域
?目的：解决部件之间速度不匹配的问题
?缓冲技术三种用途:
?处理器与主存储器之间
?处理器和其它外部设备之间
?设备与设备之间的通信
多缓冲区（Cache）技术
单缓冲区：
?设备向缓冲区输入数据直到装满后
必须等待CPU将其取完，才能继续向其中输入数据
?为了提高设备利用率，单缓冲区不够
多缓冲区（Cache）技术：
?Cache：离CPU最近，使CPU快速访问常使用的数据
?CPU首先到一级Cache中找
?如果没有，CPU到二级Cache中找
?如果没有，CPU到系统内存中找
五、中断技术
?中断概念：
?CPU对系统发生的某个事件作出的一种反应。
?CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处
理完成后返回断点，继续执行被打断的程序。
中断的作用
?中断处理是操作系统的一个重要组成部分；
?中断对于操作系统就像机器中的驱动齿轮一样；
?操作系统可以称为是由“中断驱动”或者“（中断）事件驱动”。
?中断是现代计算机系统中基本设施之一，是CPU与系统其他资源通信的重要手段，协
调系统对各种外部事件的响应和处理，使OS可以捕获普通程序发出的系统功能调用；
?中断是实现多道程序的必要条件；
?可以及时处理设备的中断请求；
?可以防止用户程序中破坏性的活动等等。
引入中断的目的
?解决主机与外设的并行工作问题
?提高可靠性
?实现多机联系?实现实时控制
特点：
1) 中断随机的
2) 中断是可恢复的
3) 中断是自动处理的
中断系统的概念
?中断系统是实现中断功能的部件，包括中断装臵和中断处理程序。
?中断装臵：指发现中断，响应中断的硬件。
?发现中断源，提出中断请求。
?保护现场
?启动处理中断事件的程序。
?中断处理程序：由软件来完成。
?主要任务是处理中断事件和恢复正常操作。
中断类型（1）
?强迫性中断
?正在运行的程序所不期望的，它由于某种硬件故障或外部请求引起的，包括：
?输入/输出(I/O)中断：主要来自外部设备通道
?程序性中断：运行程序中本身的中断，如：
溢出,缺页中断,缺段中断,地址越界
?时钟中断
?控制台中断
?硬件故障
中断类型（2）
?自愿性中断
?用户在程序中有意识安排的中断，是由于用户在编制程序时因为要求操作系统
提供服务，使用“访管”指令或系统调用，使中断发生。称为访管中断。包括：
?执行I/O，创建进程，分配内存;
?信号量操作，发送/接收消息。
中断响应
CPU如何响应中断, 两个问题：
?CPU何时响应中断？
通常在CPU执行了一条指令以后，更确切地，在指令周期最后时刻接受中断请求，或此时扫描中断寄存器
?如何知道提出中断请求的设备或中断源？
因为只有知道中断源或中断设备，才能调用相应的中断处理程序
中断优先级
?在计算机执行的每一瞬间，可能有几个中断事件同时发生。
?中断装臵按照预定的顺序来响应，这个预定的顺序称为中断的优先级，中断装臵首先
响应优先级高的中断事件。
?在一些机器中，中断优先级按中断类型划分：
?以机器故障中断的优先级最高；
?程序中断和访问中断次之；
?外部中断更次之；
?输入输出的优先级最低。
中断屏蔽
在CPU上运行的程序，有时由于种种原因，不希望其在执行过程中被别的事件所中断，称为中断屏蔽。
?在PSW中设臵中断屏蔽码以屏蔽某些指定的中断类型；
?如果其PSW的中断禁止位建立后，则屏蔽中断（不包括不可屏蔽的那些中断）；
?如果PSW中的中断禁止位未建立，则可以接受其中断优先级高于运行程序中断优先级
的那些中断；
?各设备接口中也有中断禁止位，以禁止该设备的中断。
中断处理
简单的中断处理- 典型的处理过程：
（1）设备给处理器发一个中断信号
（2）处理器处理完当前指令后响应中断，延迟非常短（要求处理器没有关闭中断）
（3）处理器处理完当前指令后检测到中断，判断出中断来源并向发送中断的设备发送了确认中断信号，确认信号使得该设备将中断信号恢复到一般状态
（4）处理器开始为软件处理中断做准备：
保存中断点的程序执行上下文环境，这通常包括程序状态字PSW，程序计数器PC中的下一条指令位臵，一些寄存器的值，它们通常保存在系统控制栈中,
处理器状态被切换到管态
（5）处理器根据中断源查询中断向量表，获得与该中断相联系的处理程序入口地址，并将PC 臵成该地址，处理器开始一个新的指令周期，控制转移到中断处理程序
（6）中断处理程序开始工作，包括检查I/O相关的状态信息，操纵I/O设备或者在设备和主存之间传送数据等等
（7）中断处理结束时，处理器检测到中断返回指令，被中断程序的上下文环境从系统堆栈中被恢复处理器状态恢复成原来的状态。
（8）PSW和PC被恢复成中断前的值，处理器开始一个新的指令周期，中断处理结束
六、时钟
?时钟是操作系统运行时必不可少的硬件设施：
?OS定时
?OS多道运转能力的推动力量。
?时钟可以支持计算机完成以下工作：
?在分时系统中，间隔时钟实现作业间按时间片轮转。
?在实时系统中，按要求的间隔输出正确时间信号给实时的控制设备（如A／D、
D/A转换设备）。
?定时唤醒要求延迟执行的各外部事件（如定时为各进程计算优先数，银行中定
时运行某类结账程序等）。
?提供用户和系统所需要的绝对时间，即年、月、日。
?当用户程序死循环时，时钟中断可以使系统恢复控制。
?时钟可分为硬件时钟和软时钟。
?硬件时钟分为：绝对时钟、间隔时钟。
?绝对时钟：记录当前时间（年、月、日、时分秒）。系统有一个绝对时钟寄存器，每
隔一个时间单位（定时器发一个信号）自动加1。绝对时钟由电池供电。
?间隔时钟：每隔固定的时间单位产生一次时钟中断。系统有一个间隔时钟寄存器，该
寄存器的初值由操作系统根据所需的间隔时间来设臵，以后每经过一个时间单位，时钟寄存器自动减1，直到为0时发出间隔时钟中断。时钟中断是操作系统完成一些重要功能的物质基础。
?时钟硬件：提供硬件时钟的硬件，PC机中的时间由三种时钟硬件提供：
?实时时钟（Real Time Clock，RTC）：所有的PC机就都包含一个叫做实时
时钟（RTC）的时钟芯片，以便在PC机断电后仍然能够继续保持时间。RTC
由主板上的电池来供电的，当PC机关掉电源后，RTC仍然会继续工作。通常，
CMOS RAM和RTC被集成到一块芯片上，因此RTC也称作“CMOS
Timer”。
?可编程间隔定时器（Programmable Interval Timer，PIT），每个PC机中都
有一个PIT，以通过IRQ0产生周期性的时钟中断信号，一秒钟之内将产生18.2
次时钟中断。
?时间戳计数器（Time Stamp Counter，TSC）：从Pentium开始，所有的Intel
80x86 CPU都包含一个64位的时间戳记数器（TSC）的寄存器。该寄存器实
际上是一个不断增加的计数器，它在CPU的每个时钟信号到来时加1。
?这些时钟硬件都基于固定频率的晶体振荡器来提供时钟方波信号输入。
?软时钟：用软件实现（需要间隔时钟支持），可以很多。用于满足各种不同的定时要
求。
?CPU保护：防止进程得到CPU后不放弃控制权。
?解决：分配给每个进程一段时间（时间片），时间片到，发时钟中断，控制权
交给操作系统。
七、重定位
1、基本概念
绝对地址（物理地址）
指存储控制部件能够识别的主存单元编号，即主存单元的实际地址。
相对地址（逻辑地址）
相对于某个基准量（通常为零）编址时所采用的地址，主要用于程序编写、编译过程中。
逻辑地址空间
用户的程序逻辑地址的集合，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。
物理地址空间
物理地址的集合，它是一个一维的线性空间。
2、重定位概念
?在多道环境下，用户不可能确定自己的程序要使用的主存区，因而，在编写程序时，
通常以相对地址来编写。当程序放入主存时，如果不把程序中与地址有关的内容变成内存控制机构能够识别的实际地址，而是直接装入，则程序可能不能正确执行的。要使程序装入主存后能够正确执行，就必须修改程序中所有与地址有关的项，这就是程序的重定位。
?重定位：把程序地址空间中使用的逻辑地址变换成主存物理地址的过程。分为静态重
定位和动态重定位。
3、重定位的两种技术
?静态重定位：程序装入内存时由连接装入程序完成从逻辑地址到物理地址的转换。
?在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，
并将用户程序中使用的访问内存的逻辑地址转换成物理地址。
?评价:
?优点是实现简单，不要硬件的支持。
?缺点是程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内
存时要将所有访问内存的地址转换成物理地址。
?动态重定位：在程序执行时由系统硬件完成从逻辑地址到物理地址的转换。
?系统中设臵了重定位寄存器。
?动态重定位是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，
这样节省了CPU的时间。
?重定位寄存器的内容由操作系统用特权指令来设臵，比较灵活。
?实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中
都采用动态地址映射技术。
?动态地址映射技术能满足以下目标：
?具有给一个用户程序任意分配内存区的能力；
?可实现虚拟存储；
?具有重新分配的能力
?对于一个用户程序，可以分配到多个不同的存储区
4、程序的装入
?绝对装入程序
?在单道程序系统中，机器的起始地址是知道的，只需依次将其按绝对地址的形
式装入主存就可以了。
?相对装入程序
?对多道程序系统而言，使用的是相对装入或相对连接程序，主要过程：
?装入程序对各个程序进行重定位。
?将主程序同各程序段连接起来
小结
?掌握：
?CPU：特权指令、工作状态、状态转换
?主存储器：存储保护机制
?重定位技术：静态重定位、动态重定位
?了解
?中断技术
?时钟
第三章进程管理
?掌握?
多道程序系统的特点
?进程的引入和定义
?进程的状态及状态变迁
?进程的描述：PCB
?了解?
进程的控制
1、进程的引入
进程的概念是操作系统中最基本、最重要的概念。它是在多道程序系统出现以后，为了刻画系统内部出现的情况，描述系统内部各作业的活动规律而引进的一个新概念，它是对程序的抽象。
多道程序系统的特点
?并行性
?在主存中同时存放多道作业，充分利用系统资源。
?制约性
?各程序同时存在于主存，可能因为竞争同一资源（如处理器、外部设备）而
相互制约。
?动态性
?各程序在系统中所处的状态在不变化。
2、进程的概念
定义：Process
进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。
?它对应处理机、存储器和外设等资源的分配和回收；
?引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了
OS 的复杂性；
进程与程序的区别
?进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进
程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。
?进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。
?进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
?进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，
一个进程可包括多个程序。
进程的性质
?并行性：各进行按各自独立的，不可预知的速度并发推进。并发和异步特性会导致程
序执行的不可再现性。
?制约性：并发进程之间存在着制约性，在进行的关键点上需要相互等待或互通消息。
?动态性：进程是程序在数据集合上的一次执行过程，是动态概念；而程序是一组有序
指令序列，是静态概念。
?进程有一个生命过程：创建、运行、等待等。
?进程具有动态的地址空间（数量和内容），地址空间上包括：
?代码（指令执行和CPU状态的改变）
?数据（变量的生成和赋值）
?系统控制信息（进程控制块的生成和删除）
进程的性质
?结构性：包括数据集合和运行于其上的程序。
?代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段
和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）
?共享性：同一程序同时运行于不同数据集合上时，构成不同的进程。
?独立性：是系统中资源分配和保护的基本单位，也是系统调度的独立单位(单线程进程)。
每个进程的地址空间相互独立，除非采用进程间通信手段；
3、进程的状态
?运行状态（Running）：进程占有CPU，并在CPU上运行。处于此状态的进程的数目
小于等于CPU的数目。
?在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系
统的idle进程（相当于空操作）。
?就绪状态（Ready）：进程已获得除处理机外的所需资源，等待分配处理机资源；只
要分配CPU就可执行。
?可以按多个优先级来划分队列，如：时间片用完－>低优，I/O完成－>中优，
页面调入完成－>高优
?等待状态（Blocked）：指进程因等待某种事件的发生而暂时不能运行的状态（即使
CPU空闲，该进程也不可运行）。等待的事件可以为：I/O操作或进程同步等。
进程状态转换
在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换。
就绪—运行 运行—就绪
●运行—等待?等待—就绪
进程的状态转换
进程转换
?就绪--> 运行
?调度：调度程序选择一个新的进程运行
?该转换可以由其他转换引起
?运行--> 就绪
?运行进程用完了时间片
?运行进程被中断，因为一高优先级进程处于就绪状态
?该转换可以引起其他转换发生
进程转换（续）
?运行--> 等待
?当一进程必须等待某事件发生，
?OS尚未完成服务
?对一资源的访问尚不能进行
?初始化I/O 且必须等待结果
?等待某一进程提供输入(IPC)
?可以引起其他转换发生
?等待--> 就绪
?当所等待的事件发生时
因果变迁
?如果一个状态变迁是由于另一个状态变迁引起的，则这两个变迁为因果变迁。
?思考下列说法是否对，为什么？（1）一个进程从运行状态变为就绪状态态，一定会引起另一个进程从就绪状态态变为运行状态。
（2）一个进程从运行状态变为阻塞状态态，一定会引起另一进程从运行状态变为就绪状态。（3）一个进程从阻塞状态变为就绪状态，一定会引起另一个进程从就绪状态变为运行状态。三状态进程模型(单队列结构)
进程的挂起和解挂
为了更好的管理和调度进程及适应系统的功能目标，许多系统都有“挂起”和“解挂”一个进程的功能，原因在于：
?系统有时可能出故障或某些功能受到破坏，需要暂时将系统中的进程挂起，以便故障
消除后再恢复。
?用户在执行自己的作业过程中，要求挂起他的进程，以便进行某些检查和改正。
?系统中负载过重，资源相对不足，造成系统效率下降，需要挂起一部分进程以调整系
统负荷
具有挂起功能的进程状态变化
?事件发生
?挂起
?解除挂起
?时间片完成
?被调度
?挂起
?时间发生
?挂起
?解除挂起
?等待事件
状态
?就绪状态(Readya)：进程在内存且可立即进入运行状态；
?等待状态(Blockeda)：进程在内存并等待某事件的出现；
?挂起等待状态（Blockeds）：进程在外存并等待某事件的出现；
?挂起就绪状态（Readys）：进程在外存，但只要进入内存，即可运行；
转换
?挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况：
?等待到挂起等待：没有进程处于就绪状态或就绪进程要求更多内存资源时，会
进行这种转换，以提交新进程或运行就绪进程；
?就绪到挂起就绪：当有高优先级等待（系统认为会很快就绪的）进程和低优先
级就绪进程时，系统会选择挂起低优先级就绪进程；
?运行到挂起就绪：对抢先式分时系统，当有高优先级挂起等待进程因事件出现
而进入挂起就绪时，系统可能会把运行进程转到挂起就绪状态；
?解挂（Activate）：把一个进程从外存转到内存；可能有以下几种情况：
?挂起就绪到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进
行这种转换；
?挂起等待到等待：当一个进程释放足够内存时，系统会把一个高优先级挂起等
待（系统认为会很快出现所等待的事件）进程；
4、进程的描述
?进程程序块
?进程数据块
?系统/用户堆栈
?进程控制块
进程控制块（Process Control Block）
?存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重
要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。
?用它来记录进程的外部特征，描述进程的运动变化过程。
?系统利用PCB来控制和管理进程，PCB是系统感知进程存在的唯一标志。PCB就象我
们的户口。
?进程与PCB是一一对应的。
进程控制块的内容
包含以下三类信息：
?进程标志信息
?处理器状态信息
?进程控制信息
进程标志信息
?本进程的标志ID：
?通常用系统中唯一的数字作为标记，该数字实际是该进程的PCB在系统的
PCB表中的表目序号。
?建立本进程的进程（父进程）的标志ID
?用户标记
处理器状态信息
?用户使用的寄存器
?控制和状态寄存器:
?包括程序计数器PC和条件寄存器（或程序状态字PSW）.
?堆栈指针
进程控制信息
?调度和状态信息：
?进程的状态，进程的调度优先级，与调度有关的信息
?进程在有关队列中的链接指针
?进程间的通信信息：
?包括标志位、信号或信号量、消息队列等
?主存使用信息：
?包括分给进程的主存大小和位臵
?进程使用的其他资源信息
?进程得到有关服务的优先级
进程管理
系统中的进程是很多的，状态也不一样。为了调度和管理进程，需将各进程的PCB 用适当的方法组织起来，以下有三种方法：
?单表：把所有的PCB组织在一个表格中。
?索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个
不同的index表。
?各状态的进程形成不同的索引表：就绪索引表、阻塞索引表
?链表：分别把具有相同状态的所有进程的PCB按优先级排成一个或多个队列，同一状
态的进程其PCB成一链表，多个状态对应多个不同的链表
?各状态的进程形成不同的链表：就绪链表、阻塞链表
PCB组织形式
5、进程控制
创建、撤消进程以及完成进程各状态之间的转换，通常由具有特定功能的原语完成。创建进程
?引起创建进程的事件
?用户登录。
?作业调度。
?提供服务。
?应用请求。
?创建进程的过程
?创建一个PCB
?赋予一个统一进程标识符
?为进程映象分配空间
?初始化进程控制块
?许多默认值(如: 状态为New，无I/O设备或文件...)
?设臵相应的链接
?如: 把新进程加到就绪队列的链表中
撤消进程
?进程完成其任务，希望终止时，调用撤消进程的系统调用（进程撤消原语）撤消进程。
?在一般操作系统中进程撤消的系统调用是：kill
?UNIX系统中是exit()。
?引起进程撤销的事件
?正常结束。
?异常结束。
?外界干预。
撤消进程
?两种策略：
?仅撤销指定标识符的进程；
?撤销一个子进程及该子进程的所有子孙。
撤消进程
?根据撤销进程标识号，从相应队列中找到它的PCB
?将该进程拥有的资源归还给父进程或操作系统
?若该进程拥有子进程，应先撤销元的所有子孙进程，以防它们脱离控制
?被撤销进程出队，将它的PCB归还到PCB池
进程的阻塞和唤醒
?引起进程阻塞和唤醒的事件
?请求系统服务。
?启动某种操作并等待操作完成。
?等待合作进程的协同配合。
?系统进程无新工作可做。
进程的阻塞和唤醒
?进程阻塞过程
?停止当前进程的执行；保存该进程的CPU现场信息；将进程状态改为阻塞态，
并将其PCB入相应的阻塞队列；转进程调度程序。
?进程唤醒过程
?首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态
由阻塞改为就绪，然后再将该PCB插入到就绪队列中。
进程切换
?进程切换：中断处于运行态的进程运行，让出处理器，恢复新进程的状态，使新进程
投入运行。
?当系统调度新进程占有处理器时，新老进程随之发生上下文切换。
?进程的运行被认为是在进程的上下文中执行的。
?进程上下文：操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文
（context）。进程实体+运行环境。
进程切换
进程上下文组成：
?用户级上下文：由用户程序块、用户数据块和用户堆栈组成的进程地址空间。
?系统级上下文：又进程控制块、内存管理信息、进程环境块，及系统堆栈等组成的进
程地址空间。
?寄存器上下文：由PSW寄存器和各类控制寄存器、地址寄存器、通用寄存器组成、用
户栈指针等组成。
进程切换
进程切换步骤：
?保存被中断进程的处理器现场信息
?修改被中断进程的进程控制块的有关信息，如进程状态等
?把被中断进程的PCB加入有关队列
?选择下一个占有处理器运行的进程
?修改被选中进程的PCB的有关信息
?根据被选中进程设臵操作系统用到的地址转换和存储保护信息
?根据被选中进程恢复处理器现场
改变优先级数原语
?进程的优先级数是表示进程的重要性及运行的优先级，进程调度程序以此来确定优先
调用哪一个进程到处理机上运行。
?为防止一些进程因优先数太低而长期不能运行，许多系统采用动态优先数。
?影响优先数的因素
?作业开始时的静态优先数
?过程的类型
?过程所使用的资源量
?在系统中的等待时间
6. 操作系统代码的执行
?通常，OS核心不是一个进程，其执行不被调度。
?OS通过中断方式获得CPU控制权。?OS与应用程序的切换会引起两个开关的变化：
?CPU执行模式开关：开销小
?存取PSW和模式改变指令
?进程间开关：开销大
?进程地址空间变换
?维护PCB信息
6. 操作系统代码的执行（续）
?OS和进程的关系：
?OS不作为进程地址空间的一部分：传统方法。
?OS作为进程地址空间的一部分：如UNIX
?OS功能分别在核心和系统服务进程中，只有OS核心作为进程地址空间的一部
分：如Windows NT
7 Windows NT进程管理举例
?NT的进程作为对象(Object)，以句柄(handle)来引用。相应地有控制对象的服务
(services)。
?进程对象的属性；PID, Access Token, Base Priority, 默认处理器集合等
7.1 NT的进程关系
?对NT核心而言，进程之间没有任何关系（包括父子关系）。那么，如何表达UNIX进
程之间的父子关系（以及其他关系）？由POSIX子系统来建立和维护
7.2 NT进程结构
7.3. 进程控制
?创建：CreateProcess()函数用于创建新进程及其主线程，以执行指定的程序。
?新进程可以继承：打开文件的句柄、各种对象（如进程、线程、信号量、管道
等）的句柄、环境变量、当前目录、原进程的控制终端、原进程的进程组（用
于发送Ctrl+C或Ctrl+Break信号给多个进程）－－每个句柄在创建或打开时
能指定是否可继承；
?新进程不能继承：优先权类、内存句柄、DLL模块句柄
?CREATE_NEW_CONSOLE表示新进程有一个新的控制台
?CREATE_NEW_PROCESS_GROUP表示新进程是一个新的进程组的根。
?退出：ExitProcess()或TerminateProcess()，则进程包含的线程全部终止；
?ExitProcess()终止一个进程和它的所有线程；它的终止操作是完整的，包括关
闭所有对象句柄、它的所有线程等；
?TerminateProcess()终止指定的进程和它的所有线程；它的终止操作是不完整
的（如：不向相关DLL通报关闭情况），通常只用于异常情况下对进程的终止。小结
?掌握
?多道程序系统的特点
?进程：定义、三个基本状态、状态变迁原因及因果关系
?进程控制块：定义、作用、包含的内容、组织形式
?了解
?进程控制原语
第四章多线程（thread）
线程是近年来操作系统领域出现的一个非常重要的机制和技术，其重要程度不亚于进程。线程机制可以提高程序执行的效率，而且也方便用户编程，不但适用于多机系统，对大多数单CPU的个人计算机也同样带来好处，因此当代操作系统都支持线程。
1、线程的引入
进程的两个基本属性:
?资源分配的基本单位：
给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度
?调度基本单位：
进程是一个执行轨迹。
以上两个属性构成进程并发执行的基础。
对进程系统必须完成的操作：
?创建进程
?撤消进程
?进程切换
缺点：
时间空间开销大，限制并发度的提高
引入线程的目的
?进程的局限性
?在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进
程的并发性时，人们发现进程切换开销占的比重越来越大；
?传统的进程不能很好的利用多处理器，因为一个进程在某个时刻只能使用一个
处理器；
?进程间通信的效率受到限制；
?引入线程的目的：
?减小（进程/线程）上下文切换开销；
?更好支持多处理器（MP），达到最大程度的并行；
?简化进程间的通信；
2、线程的概念
?定义：线程是进程内一个相对独立的、可调度的执行单元。有时称轻量级进程。
?将原来进程的两个属性分开处理。
?每个线程都具有
?执行状态；
?受保护的线程上下文，当线程不运行时，用于存储现场信息
?独立的程序指令计数器
?执行堆栈
?容纳局部变量的静态存储器
?可存取所在进程的内存和其他资源
线程的特性
?并行性：同一进程的多个线程可在一个或多个处理器上并发或并行运行
?共享性：同一个进程中的所有线程共享进程获得的主存空间和一切资源
?动态性：线程也是程序在相应数据集上的一次执行，由创建而产生，至撤销而消亡，
有其生命周期线程的性质
?线程是进程内一个相对独立的可执行单元
?线程是操作系统中的基本的调度单元
?进程中至少要有一个或一个以上的线程
?线程可以创建其他线程
?线程并不拥有资源，只是使用他们，进程是资源分配和拥有的基本单元。
?由于共享资源，线程间需要通信和同步机制
?线程有生命期，有诞生和死亡
线程的好处
?创建一个新线程花费时间少（结束亦如此）
?同一进程中两个线程的切换花费时间少，如果机器设有“存储[恢复]所有寄存器”指
令，则整个切换过程用几条指令即可完成）
?由于同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核
?适合多处理机系统
线程的应用
?前台和后台工作
?异步处理工作
?加快执行速度
?组织复杂工作
?多用户服务
线程的状态
由于线程是调度和执行的基本单位，在它的生命过程中有状态的变化：
就绪状态
线程已具备执行的条件，等待调度程序分配给一个CPU运行
运行状态
线程正在CPU上运行
等待状态
线程正等待某事件发生
进程与线程的比较
?调度：
进程中可能有多个线程，一个线程阻塞并不影响整个进程，进程中的其他线程仍然可以参与调度运行
?并发性：
进程间可并发，同一进程中的线程间亦可并发
?拥有资源：进程拥有资源，进程中有挂起操作，线程不拥有资源，没有权力决定进程
或自己从主存撤出，挂起只是进程一级的概念
?系统开销：线程上下文切换比进程上下文切换要快得多，同一进程中的线程切换系统
开销小。
?地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享－
－某进程内的线程在其他进程不可见。
?通信：进程间通信通过IPC，线程间可以直接读写进程数据段（如全局变量）来进行通
信－－需要进程同步和互斥手段的辅助，以保证数据的一致性
线程控制原语
?创建线程原语
?撤消线程原语
?阻塞或等待原语
?挂起一个线程
?恢复一个线程
?改变优先数
线程组（thread group）
?每个线程属于某个线程组
?每个线程创建时，用户可以显示的说明为它创建一个新的线程组；也可以由系统自动
把该线程归入创建该线程的线程所在的线程组
?线程组是多个线程的集合，系统将它们归入一个单独的对象，统一加以管理
?可为线程组设臵不同的特性和保密安全方法
?一个线程在已被创建后，不能更改移入其他线程组
单线程进程
多线程进程
基于线程的操作系统分类
单进程和单线程系统
单进程和多线程系统
多进程和单线程系统
多进程和多线程系统
3、线程的实现
?用户级线程
?内核级线程
?混合式线程
用户级线程（ULT）
User-Level Thread）
?由用户应用程序建立、调度和管理的线程。
不依赖于OS内核，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。
?线程库：基于多线程的应用程序的开发和运行环境。
?创建、撤消线程
?在线程之间传递消息和数据
?调度线程执行
?保护和恢复线程上下文
用户级线程的活动
?内核不知道线程的活动，但仍然管理线程所属进程的活动
?当线程调用系统调用时，整个进程阻塞
?但对线程库来说，线程仍然是运行状态
即线程状态是与进程状态独立的
用户级线程的优点
?线程切换不调用内核?调度是应用程序特定的：可以选择最好的算法
?ULT可运行在任何操作系统上（只需要线程库）
用户级线程的缺点
?大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞
?核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
内核级线程（KLT）
Kernel-Level Thread
?由操作系统的内核建立、调度和管理的线程。
?所有线程管理由内核完成
?没有线程库，但对内核线程工具提供API
?内核维护进程和线程的上下文
?线程之间的切换需要内核支持
?以线程为基础进行调度
?例子：Windows NT，OS/2
内核级线程的优点及缺点
优点：
?对多处理器，内核可以同时调度同一进程的多个线程
?阻塞是在线程一级完成
?内核例程是多线程的
缺点：
?在同一进程内的线程切换调用内核，导致速度下降
用户级和内核级线程比较
?调度和切换速度
ULT切换快，KLT切换与进程切换相似。ULT通常发生在一个应用进程的诸线程中，无需通过中断进入内核。
?系统调用
ULT进行系统调用时，会引起进程的阻塞；KLT进行系统调用时只会引起该线程阻塞。
?线程执行时间
ULT以进程为单位调度，KLT以线程为单位调度。
ULT：进程A有1个线程，进程B有100个线程，则A的线程比B快
KLT：进程A有1个线程，进程B有100个线程，则B比A快
?使用范围：
ULT广，任何OS，KLT需OS内核支持
?调度算法
ULT与OS调度算法无关，可针对应用优化
?多处理器支持
KLT可充分利用多处理器
ULT和KLT结合方法
?线程创建在用户空间完成
?大量线程调度和同步在用户空间完成
?程序员可以调整KLT的数量
?可以取两者中最好的
?例子：Solaris
用户级和内核级线程
根据线程运行的地址空间
?用户线程：
运行在用户地址空间的线程。
?内核线程：
运行在内核空间的线程。
?所有用户级线程都是用户线程；
?内核级线程可以是用户线程，也可以是内核线程。
NT线程的有关API
?CreateThread()函数在调用进程的地址空间上创建一个线程，以执行指定的函数；返
回值为所创建线程的句柄。
?ExitThread()函数用于结束本线程。
?SuspendThread()函数用于挂起指定的线程。
?ResumeThread()函数递减指定线程的挂起计数，挂起计数为0时，线程恢复执行。小结
?掌握
?线程引入的目的：线程和进程的比较
?线程的定义、特性和性质
?线程的实现方式：
?用户级线程
?内核级线程
?混合线程
?一些基本概念：
?线程库
?用户线程、内核线程
第五章并行性：互斥和同步
为了充分利用计算机各部分的能力，使之并行运行以提高计算机系统的效率和性能，计算机界一直在坚持不懈地、不遗余力地发展并行技术。近几十年来，随着多道程序设计、多处理器系统、分布式处理系统技术的发展，操作系统的并行技术不断完善。
?掌握
?程序顺序执行和并行执行的含义和特点
?并行执行的表示方法
?临界段的定义、目的、设计原则
?同步和互斥的含义、实现方式
?信号量机制：信号量定义、物理意义、信号量的使用（互斥、同步、生产者/
消费者，阅读者/写入者等）。
?进程通信
多道程序设计基础——并行程序设计
?并行程序设计
?进程间的同步和互斥
?同步和互斥的执行工具
?同步机构在实际程序设计中的应用
?进程通信?*管程
?*Windows NT中的同步和互斥机制
1、程序的顺序执行
?处理机逐条的一次只执行一条指令
?主存储块一次只访问一个字或字节
?外设一次只能传送一个数据块
?传统程序设计方法：顺序程序执行
程序的顺序执行
?概念:
?一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序
执行的方式就称为程序的顺序执行。
?例如：
程序顺序执行的特点
?顺序性
?处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之
前结束。
?封闭性
?程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，
其后的状态只能由程序本身确定，即只有本程序才能改变它。
?可再现性
?程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件
相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行
速度。
多道程序环境程序设计思想：
并行程序设计
?例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即I
i
,C
i
,P
i (i=1,2,3,...,n)。
?这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，
这是有序的，但有些操作是可以同时执行的。
?例如:
I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。
?程序并行执行（定义）
若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并行执行的。
程序并行性的表示之一：有向图
程序并行性的表示之二：并行语言
?并行语言：并行PASCAL，CSP/K语言，MODULA语言，扩充的Ada等.
?并行语句记号:
cobegin
S1;S2;S3;...;SN
coend;
?Si(i=1,2,3,...,n)表示n个语句（程序段），这n个语句用cobegin和coend括
起来表示这n个语句是可以并发执行的。co是concurrent的头两个字符。
?有的书用parbegin和parend表示。
?Si:简单语句，复合语句，并行语句。
?编译程序为每个并行语句Si设臵一个进程。
程序并行性表示举例
假设有一个程序由
S 0～S
n+1
个语句，
其中S
1
～S
n
语句是并发执行的。
程序如下：
S 0;
cobegin
S 1;S
2
;S
3
;...;S
N
coend;
S n+1;
程序并行性表示举例
算数表达式求值: (a-b)*(c-d)+(e/f)**2
并行程序设计的特点
?并行、异步的在系统内运行
?共享各类资源，彼此相互制约
?只有在严格遵循并行程序设计的原则下，程序运行的结果才是确定的，否则，可能产
生意料不到的情况
并发执行实例：誊抄
?一个循环程序顺序执行的誊抄
算法1：
输入：f 输出：g
{
while (f 不为空）
{
input ;
output ;
}
}
由这个程序完成誊抄工作是不会出错的。
并发执行实例：誊抄
?两个程序并发执行完成誊抄
?设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），
输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中
取数据，送标准设备输出。
并发执行实例：誊抄
算法：2
{ cobegin
f: Begin
while (不为结束符）/* 输入程序段*/
{ input; /* 从标准输入设备读入一个数据*/
write_buf; /* 将读入的数据送到bufferf */
}
End
g: Begin
while(buffer不为空）/* 输出程序段*/
{ read_buf; /* 从bufferf中取数据*/
output; /* 送打印机输出*/
}
End
coend
}
并发执行实例：誊抄
这两个程序段并发执行时可能出现如下情况：
1、输出程序运行的速度比输入程序快时，有些输出会重复；
如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。
2、输入程序执行的速度比输出程序快时，有些数据会丢失；
如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。
并发执行实例：誊抄
若程序错写成：
while(誊抄未完成）
{
cobegin
copy;
put;
get;
coend
}
然后，copy,put,get三个程序段并发执行，就有六种组合：
1、copy;put;get 导致结果：g=(R1,R1) ?
2、copy;get;put 导致结果：g=(R1,R1) ?
3、put;copy;get 导致结果：g=(R1,R1) ?
4、put;get;copy 导致结果：g=(R1,R1) ?
5、get;copy;put 导致结果：g=(R1,R2) √
6、get;put;copy 导致结果：g=(R1,R1) ?
这就是与时间有关的错误。
程序并发执行的特点
?失去了程序的封闭性
?如果程序执行的结果是一个与时间无关的函数，即具有封闭性。
?若一个程序的执行可改变另一个程序的变量，象二个并发程序完成誊抄的例
子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对
速度，在这种情况下就失去了程序的封闭性。
程序并发执行的特点
?程序并发执行的相互制约
?在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同
时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。
合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，
也有间接。
3、进程间的同步与互斥
?同步：指多个进程因协同合作而发生的一种直接制约关系。进程相互配合，共同完成
一个任务。
?互斥：指多个进程因竞争共享资源而发生的一种间接制约关系。有许多资源在使用上
具有排他性，或者说只能互斥作用，进程间需要互相竞争，才有可能使用这些资源，如打印机等。
?互斥也是一种同步。一种特殊的同步。
?互斥的概念来自于诸进程对独占使用资源（设备）的竞争，是进程之间的间接制约关
系。
?同步来源于多个进程的合作，是进程之间的直接制约关系。
临界段的提出
?临界资源：每次只允许一个进程访问的共享资源。
?临界段：进程中访问临界资源（共享变量）的代码段。
?访问同一临界资源的各临界段分散在各有关进程的程序中。
临界段设计原则
?互斥性：每次允许一个进程停留在临界段。
?有限逗留：进程只能在临界段内逗留有限时间。
?有限等待：进程不能无限期等待在临界段之外。
?前进性：临界段外进程不可以阻止其他进程进入临界段。
?有空让进：若有多个进程同时要求进入临界段，应在有限的时间内让其中一个进入临
界段，不应相互阻塞。
?通用性：不能预期和假定进程进展的相对速度以及可用的处理器的数目。（如进程的
速度、cpu个数、有无硬件指令支持等）。
互斥的实现方法
?临界段就是为了解决互斥资源的访问问题
?软件实现
?用软件解决方法来解决进程间的同步和互斥有着很大的局限性，并不是很理
想。
?硬件方法
?中断屏蔽方法
?硬件指令方法
软件方法
?解法1：双标志、先检查,后表态。
?标志表示是否已在临界段。
?问题：两个进程可能同时进入临界段，违背互斥性原则。
: flag[i] := true 软件方法
?解法2：用一个指针表示哪个应进入临界段，
?问题：强制两个进程轮流进入临界段，违背前进性原则。
P1让出后，P2使用前，p1不可能在进入
?解法3：双标志，先表态，后查看。
?问题：可能两个进程都进入不了临界段，违背有空让进。
: while flag[j] do skip
中断屏蔽法
?禁止一切中断发生。
?单CPU中，引起进程切换的唯一原因是中断，故单CPU下可行。
?缺点：
?代价高，影响并发性
?不安全，将禁止一切中断权利给了普通用户。
?局限性：不适合多CPU，一个进程只能禁止本CPU的中断。
硬件指令方法
?思路：一条指令完成读写两个操作
?手段：执行硬件指令的CPU封锁内存总线，以禁止其他CPU在该指令完成前访问内存。
?两种指令：
TS指令和Swap指令
硬件指令方法（续）
?TS：test-and-set指令，读出指定标志后把该标志设臵为True。
?该指令由PASCAL语言描述如下：
Function Test-and-Set(var flag:boolean):boolean
begin
Test-and-Set:=flag;
flag : =true
end
?TS指令的使用：
repeat
while TS(lock) do skip;
临界段代码；
lock：＝false；
其他代码；
forever
硬件指令方法（续）
?Swap指令：该指令的功能是交换两个字的内容。
?PASCAL语言描述如下：
Proceduce Swap(var a,b:boolean)
var temp : boolean;
begin
temp : =a; a:=b; b:=temp;
end
?swap使用：
repeat
key = true;
repeat
swap(lock,key);
until key＝false；
临界段代码；
lock :＝false;
其他代码；
forever
存在的缺点
?忙等待：上述硬件指令虽然可以有效的保证进程间互斥，但是进程在临界段中执行时，
其他想进入临界段的进程必须不断地检测布尔变量lock的值，这就造成了处理机时的浪费，通常称这种情况为“忙等待”。
?饥饿：由于采用随机从等待队列中选取进程，会出现有的进程一直处于等待。
?需CPU支持
硬件指令方法的优点
?不但适用于单处理器情况，而且适用于共享主存的SMP多处理器情况（即对称多处理
器）；
?方法简单，行而有效；
?可以被使用于多重临界段情况，每个临界段可以定义自己的共享变量。
4、信号量
用软件和硬件的方法来解决互斥的问题，都存在一定的缺点，荷兰著名的计算机科学家Dijkstra，于1965年提出了一个同步机构，称之为信号量。其基本原则是在多个相互合作的进程之间使用相同的信号来同步，一个进程强制的被停止在一个特定的地方直到收到一个专门的信号，这个信号也就是信号量。
信号量定义
?除初始化外，仅能由两个同步原语对其进行操作的整型变量。
?两个同步原语分别成为wait和signal（也称为P和V）。
?类型：
?二元信号量：信号量的值仅允许取0或1，主要用于互斥变量。
?一般信号量：信号量取值允许为非负整数，主要用于进程间的一般同步。
?在实际操作系统中，一般情况下是由机器硬件提供Wait、signal操作的指令，当然是
原子操作，若机器不提供wait、signal操作的指令，则操作系统提供Wait、Signal操作原语。
同步原语
?作为OS核心代码的一部分，其执行不受进程调度和执行的打断。
?进程的等待方式可以分为
?阻塞等待方式和忙等待方式
?在不同的等待方式下，Wait和signal操作实现的方式略有不同。
Wait操作
?阻塞等待方式
S:=S-1
若S>=0 则进程继续执行其他代码
若S<0 则进程被阻塞，并将其插入到该信号量等待队列中
?忙等待方式
若S<=0 则循环查询等待
若S>0 则S:=S-1
signal操作
?阻塞等待方式
S:=S+1
若S>0 则进程继续执行其他代码
若S<=0 则从该信号量等待队列中移出第一个进程，使其变为就绪状态，然后返回原进程继续执行其他代码
?忙等待方式
S:=S＋1
硬件指令实现互斥的同步原语
Wait(S):
While TS(lock) do skip /上锁
While S<=0 do skip; /同步原语代码
S: =S-1;
lock : =false; /开锁
Signals(S):
While TS(lock) do skip /上锁
S: =S+1; /同步原语代码
lock : =false; /开锁
信号量的数据结构
?整型：忙等待方式
?记录型结构：阻塞等待方式
type Semaphore＝Record
value:integer
L: point to PCB
end
两种比较方式的比较
?阻塞等待：
?信号量采用记录型数据结构
?实现复杂，须操作就绪队列和阻塞队列
?进程间开销大
?忙等待：
?信号量采用整型
?实现简单
?可减少进程间开关开销
?CPU资源浪费
信号量的物理意义
?信号量S的初值表示可用资源数
?当S>0时，S的值表示还剩可用资源数
?当S<=0时，表示已无资源可分配，其绝对值表示此时在等待队列中等待分配资源的进
程数
?Wait操作：申请资源，若S>0，意味着有资源可以申请，操作后，S=S-1意味着资源
减少
?Signal操作：释放资源，执行Signal操作之后，S=S+1,意味着资源数增加
信号量的物理意义
?信号量的变化范围：
设可用资源数为m，进程数为n
?忙等待：0<=S <=m
?阻塞等待: -(n-m)<=S <=m
利用信号量实现互斥
?描述：多个进程共享临界资源，并且对资源的访问是互斥的，资源可用单位数为1。利用信号量实现互斥
?为临界资源设臵一个互斥信号量mutex，其初值为1；在每个进程中将临界区代码臵于
wait(mutex)和signal(mutex)原语之间.
?必须成对使用wait和signal原语：遗漏wait原语则不能保证互斥访问，遗漏signal原
语则不能在使用临界资源之后将其释放（给其他等待的进程）；wait、signal原语不能次序错误、重复或遗漏.
利用信号量来实现同步
用信号量及wait、signal操作来描述左图
1、说明进程的同步关系
进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。
2、设臵信号灯，说明含义、初值。
s13 = 0 表示进程P1尚未执行完成；
s23 = 0 表示进程P2尚未执行完成；
利用信号量来实现同步
?程序描述
main()
{ int s13=0;s23=0;
parbegin
p1;
p2;
p3;
parend;
}
共享缓冲区的合作进程的同步
?设有一个缓冲区buffer，大小为一个字节，
?CP进程不断产生字符，送buffer，
?IOP进程从buffer中取出字符打印。
?如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的
打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。
?要保证打印结果的正确，CP、IOP必须遵循以下同步规则:
?当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待；
?当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须
等待。
Main()
{
int sb=1;sa=0;
cobegin
CP();
IOP();
coend
}
生产者、消费者问题
?定义：指若干进程通过有限的共享缓冲区交换数据时，对缓冲区资源的使用问题。
?生产者：向共享缓冲区写入数据的进程。
?消费者：从共享缓冲区读取数据的进程。
生产者、消费者问题
?描述：
?若共享区为n个，可将这n个缓冲区视为共享资源。
?任何时刻，一个缓存区只允许一个进程对其操作。
?缓冲区空时，生产者可写入数据（不许写重），否则等待。消费者读取数据后
的缓存成为生产者的可用资源。
?缓冲区中有数据时，消费者读取数据（不许取重），否则等待。生产者写入数
据的缓存成为消费者的可用资源。
?生产者和消费者都以异步方式运行，但必须保持同步，即各自只能操作各自的
可用资源。
生产者、消费者问题
?缓冲池：N个缓冲区
?P：一组生产者共用的指向空缓冲区
头的指针；
?C：一组消费者共用的指向满缓冲区
头的指针。
?互斥操作：
?分配空缓冲区和移动指针P;
?释放满缓冲区和移动指针C;
生产者、消费者问题
?信号量设臵
3个信号量
?E：表示空的缓冲区数，初值为n；
?F：表示满的缓冲区数，初值为0；
?Mutex：分配缓冲区的互斥信号量，初值为1。
生产者、消费者问题
var E,F: Semaphore；
muntex: binary Semaphore;
Procedure producer
begin
repeat
wait(E);
wait(mutex);
“分配空缓冲区并调整指针P的临界段”；
Signal(mutex);
“向缓冲区中装入数据”；Signal(F);
forever
end
生产者、消费者问题
Procedure Consumers
begin
repeat
wait(F);
wait(mutex);
“分配满缓冲区并调整指针C的临界段”；
signal(mutex);
“从缓冲区中取出数据”；
signal(E);
forever
end
生产者、消费者问题
Main（）
begin
F:=0; E:=n; mutex:= 1;
cobegin
Producer 1;
Producer 2;
……
Producer n;
Consumer1;
Consumer2;
……
Consumer m;
coend
end
生产者、消费者问题
?特点
?Wait次序不能颠倒，否则会出现死锁
?当E＝0，F＝n时，
P：wait（mutex）->p:wait(E)->
S:wait(mutex)->S:wait(F)
?当E＝n，F＝0时，
S：wait（mutex）->S:wait(F)->
P:wait(mutex)->P:wait(E)
?生产者和消费者的缓冲指针P、C不能同时移动。即缓冲分配不能同时进
行。?可改进：将两个互斥信号量来分别控制对指针P、C的操作。
阅读者、写入者问题
?定义：指多个进程对一个共享资源进行读写操作的问题。
?阅读者：对共享资源进行读操作的进程。
?写入者：对共享资源进行写操作的进程
?原则：
?任何时候写入者最多只允许1个，阅读者可有多个；
?对共享资源的读写操作限制关系包括:
“读”－“写”：互斥“写”－“写”：互斥“读”－“读”：允许
?当无写入者正在访问共享数据集时，阅读者可以进行访问，否则必须等待。
?当无阅读者正在访问共享数据集时，写入者可以进行访问，否则必须等待。阅读者、写入者问题
信号量的考虑：
?两个共享资源：
?Readcount:记录正在读的阅读者人数。
?共享数据集
?Readcount的访问：对阅读者是互斥的，用m u t e x作访问的互斥信号量。
?共享数据集的访问：对写操作互斥，读写操作互斥，用w r t作访问的互斥信号量。
阅读者、写入者问题
阅读者、写入者问题
?特点：
?某种程度上，阅读者优先，写入者总在所有阅读者完成后才进行。
?各阅读者可并发运行。
练习：
读者优先=> 写入者优先
两种情形：
1、写入者封锁后来的阅读者；
2、第一个写入者封锁后来的阅读者，并且后来的写入者可以优先于阅读者；
写入优先
Var v,w,r,mutwx,k:semaphore; RC,WC:integer;
begin w:=r:=v:=k:=1;RC:=WC:=0;
parbegin
READER:
begin
wait(r);wait(v);
if RC=0 then wait(w);
RC:=RC+1;
signal(v);signal(r);
阅读；
wait(v);
RC:=RC-1;
if RC=0 then signal(w);
signal(v);
end
哲学家用餐问题
?一个典型的进程同步问题。
?问题的描述：有五个哲学家，他们的生活是交替地进行思考和就餐。哲学家们共一张
圆桌，周围放有五张椅子，每人坐一张。在圆桌上有五个碗和五只筷子，当一个哲学家思考时，他不与同事交谈，饥饿时便试图取左、右最靠近他的筷子，但他可能一支都拿不到。只有在他拿到两支筷子时方能就餐。餐毕，放下筷子继续思考。
?上述解法可保证不会有两个相邻的哲学家同时就餐;
?但可能引起死锁。假如五个哲学家同时饥饿而拿起各自左边的筷子，使五个信号量
chopstick均为0；当他们再试图去拿右边的筷子时，他们都无限期地等待。
?死锁问题可采取以下解决方法：
?至多只允许四个哲学家同时就餐，以保证至少有一个哲学家可以就餐，最终总
会释放出他所用过的筷子，从而可使更多的哲学家就餐；
?仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子就餐；
?规定奇数号哲学家先拿起其左边筷子，然后再去拿右边筷子；而偶数号哲学家
则相反。按此规定，1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子，
即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶号筷子，最后总会有
某一个哲学家能获得两支筷子而就餐。
睡着的理发师问题
?问题描述：在理发馆中，有一个理发师，一张理发椅和n个为等待顾客所设的椅子。如
果没有顾客来，理发师就会坐在理发椅上睡觉，当一个顾客来到时，他必须唤醒睡着了的理发师。如果在理发师理发时，又有别的顾客到达，他们要么坐下(如果有空的椅子)，要么离开(如果所有的椅子都被坐满)。用信号量和wait、signal操作写出理发师和顾客行为的程序描述。
5、进程间的通信
?进程通信：指进程之间的信息交换。
?作业－>若干个可并行执行的进程－>协同完成一个工作（同步）－>进程通信
（在进程之间交换一定数量的信息）。
?进程通信方式：
?低级通信原语：交换信息量较少。如互斥，同步机构。
?高级通信原语：交换信息量较多。如直接通信，间接通信。
?高级通信原语：
?直接通信：一个进程直接发送消息给接受者进程；
Send( P, Msg ); Receive( P, Msg );
?间接通信：进程通过一个“信箱”来传递消息。Send( A,
Msg ); Receive( A, Msg );
直接通信
?要求发送进程和接收进程都以显示的方式提供对方的标识符。通常系统提供两条通信
原语。
?原语send（P，消息）：把一个消息发送给进程P
?原语receive（Q，消息）：从进程Q接收一个消息
消息队列
通常一个进程可以与多个进程通信，即可以向多个进程发送消息，也可以接收来自多个进程的消息。为了便于进程接收和处理这些消息，一般采用消息队列通信机制，
将消息组织成消息队列，用链指针链接起来，头指针放在进程的PCB中。
有关数据结构
?消息队列
type Msg ＝record
MsgSend；
MsgSize；
MsgText；
MsgNext；
end
发送和接收过程
?发送进程在自己地址空间设臵一发送区，将发送的消息正文，发送者进程标示符，消
息长度填入其中，然后调用发送原语。
?发送原语根据发送区的消息长度，申请一缓冲区，将发送区的消息复制到缓冲区中。
并获得接收进程的内部标识符，然后将缓冲区挂在接收进程的消息队列上。
?接收进程调用接收原语，从自己的消息队列中摘下消息队列中的消息，并将其中的数
据复制到指定的消息接收区。
同步机制
?信号量：
?互斥信号量（mutex）：对消息对列指针的操作
?等待信号量（swait）：消息资源数
间接通信
?进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件
?原语send（A，信件）：把一封信件（消息）传送到信箱A
?原语receive（A，信件）：从信箱A接收一封信件（消息）
间接通信的实现
?信箱是存放信件的存储区域，每个信箱可以分成信箱特征和信箱体两部分。信箱特征
指出信箱容量、信件格式、指针等；信箱体用来存放信件
?发送信件：如果指定的信箱未满，则将信件送入信箱中由指针所指示的位臵，并释放
等待该信箱中信件的等待者；否则发送信件者被臵成等待信箱状态
?接收信件：如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则
接收信件者被臵成等待信箱中信件的状态
6、管道
?管道（pipeline）源自“贝尔实验室”开发的Unix,是Unix最具特色的进程通信方式；
?也称共享文件方式，基于文件系统，利用一个打开的共享文件实现进程间的相互通信，
文件作为缓冲传输介质。
?管道是进程间以字节流方式传送的通信通道，通过通常的IO 接口来存取。创建管道
后，通过使用操作系统的任何读或写IO 系统调用来读或者写它。
?管道通常是单向的；常用于命令行所指定的输入输出重定向和管道命令。在使用管道
前要建立相应的管道，然后才可使用。
?Windows 管道与Linux 管道的区别：
?Windows 使用单一句柄（类似于Linux 文件描述符）支持双向IO。
?Linux 管道返回两个文件描述符来实现双向IO。
?管道具有如下三个突出的特点
?发送进程能以比较简单的方式，源源不断地把产生的消息以自然流的方式写入
管道，而不需要考虑对每次传送的信息长度的限制。
?接收进程能在适当的时机从管道按需提取信息，同样也不必以固定的消息长度
为单位进行。
?发送和接收进程都能以一定的方式了解对方进程是否存在，并且可以通过管道
的现存消息情况（管道空、管道有信息、管道满）等相互协调动作。
7、套接字
?套接字（socket）起源于Unix BSD版本，目前已经被Unix和Windows操作系统广泛
采用，并支持TCP/IP协议，即支持本机的进程间通信，也支持网络级的进程间通信?双向的，数据格式为字节流（一对一）或报文（多对一，一对多）；主要用于网络通
信；
?支持client-server模式和peer-to-peer模式，本机或网络中的两个或多个进程进行交
互。提供TCP/IP协议支持
?UNIX套接字(基于TCP/IP)：send, sendto, recv, recvfrom;
?在Windows NT中的规范称为"Winsock"(与协议独立，或支持多种协议)：WSASend,
WSASendto, WSARecv, WSARecvfrom;
8、Windows NT中的同步和互斥机制
?NT是多机操作系统,支持对称多处理模式, 同步和互斥由多种机制实现.
?内核中的同步和互斥机制：实现多处理器之间的同步.
提高临界段代码执行的中断优先级：实现同一处理机中的互斥；
?转锁机制（spin-lock）：用T-S指令实现多处理机间的互斥。
Windows NT中的同步和互斥机制
?“等待和信号设臵”机制：实现线程之间的同步(即一个线程主动停止执行并等待其他
现成执行一些操作)。
?进程通信机制: 客户进程与服务器进程间的通信采用交换信息的方式.
?小消息通信方法: 少于256bytes(将消息传给与服务器相连的端口对象)；
?大消息通信方法: 多于256bytes (将消息指针传给与服务器相连的端口对象,
并把消息存放在共享的主存区域中)；
?多通信端口机制: 当子系统有多个通信端口时用。
Windows NT同步对象
?Mutex对象：互斥对象，相当于互斥信号量，在一个时刻只能被一个线程使用。有关
的API：
?CreateMutex创建一个互斥对象，返回对象句柄；
?OpenMutex返回一个已存在的互斥对象的句柄，用于后续访问；
?ReleaseMutex释放对互斥对象的占用，使之成为可用；
?Semaphore对象：相当于资源信号量，取值在0到指定最大值之间，用于限制并发访
问的线程数。有关的API：
?CreateSemaphore创建一个信号量对象，指定最大值和初值，返回对象句柄；
?OpenSemaphore返回一个已存在的信号量对象的句柄，用于后续访问；
?ReleaseSemaphore释放对信号量对象的占用；
?Event对象：事件对象，相当于"触发器"，可通知一个或多个线程某事件的出现。有关
的API：
?CreateEvent创建一个事件对象，返回对象句柄；
?OpenEvent返回一个已存在的事件对象的句柄，用于后续访问；
?SetEvent和PulseEvent设臵指定事件对象为可用状态；
?ResetEvent设臵指定事件对象为不可用状态（nonsignaled）；手工复位，
并唤醒所有等待线程；
（2）同步对象等待
（3）子进程对同步对象的继承
（4）其他同步方法
?Critical Section对象：只能在同一进程内使用的临界区，同一进程内各线程对它的访
问是互斥进行的。把变量说明为CRITICAL_SECTION类型，就可作为临界区使用。
有关的API：
?InitializeCriticalSection对临界区对象进行初始化；
?EnterCriticalSection等待占用临界区的使用权，得到使用权时返回；
?TryEnterCriticalSection非等待方式申请临界区的使用权；申请失败时，返
回0；
?LeaveCriticalSection释放临界区的使用权；
?DeleteCriticalSection释放与临界区对象相关的所有系统资源；
?互锁变量访问：相当于硬件指令，对一个整数（进程内的变量或进程间的共享变量）
进行操作。其目的是避免线程间切换的影响。有关的API：
?InterlockedExchange进行32位数据的先读后写原子操作；
?InterlockedCompareExchange依据比较结果进行赋值的原子操作；
?InterlockedExchangeAdd先加后存结果的原子操作；
?InterlockedDecrement先减1后存结果的原子操作；
?InterlockedIncrement先加1后存结果的原子操作；
Windows NT的文件映射
?采用文件映射(file mapping)机制：可以将整个文件映射为进程虚拟地址空间的一部分
来加以访问。在CreateFileMapping和OpenFileMapping时可以指定对象名称。
?CreateFileMapping为指定文件创建一个文件映射对象，返回对象指针；
?OpenFileMapping打开一个命名的文件映射对象，返回对象指针；
?MapViewOfFile把文件映射到本进程的地址空间，返回映射地址空间的首地
址；
?这时可利用首地址进行读写；
?FlushViewOfFile可把映射地址空间的内容写到物理文件中；
?UnmapViewOfFile拆除文件映射与本进程地址空间间映射关系；
?随后，可利用CloseHandle关闭文件映射对象；
小结
?掌握
?程序顺序执行和并行执行的含义和特点
?并行执行的表示方法
?临界段的定义、目的、设计原则
?同步和互斥的含义、实现方式
?信号量机制：信号量定义、物理意义、信号量的使用（互斥、同步、生产者/
消费者，阅读者/写入者等）。
?进程通信
?作业
? 5.8
? 5.16
? 5.18
? 5.19
第六章多处理器系统和处理器管理
?掌握
?多处理器分类
?调度的层次
?调度算法的性能评价
?各种调度算法的基本思想
?了解
?多处理器硬件组织结构
?Windows2000/XP的调度思想
无论是在操作系统控制下执行的程序，还是操作系统程序自己，都最终是要在处理器上执行，以便实现其功能。计算机系统的核心是中央处理器。
?如果一个计算机系统只包括一个中央处理器，称之为单处理器系统。
?如果有多个中央处理器，则称之为多处理器系统。
6.1 多处理器系统
随着信息和网络技术的发展，进入信息时代，带给计算机领域的一个重要的趋势是越来越普遍的使用多重处理，即配臵一个有几个甚至几百个处理器的计算机系统。主要原因是由于人们要求处理的信息越来越庞大，要求具有更高性能更高处理速度的计算机系统。
多处理器系统的优点
?可靠性；
?高度并行性；
?多处理器可增强单处理器计算机系统的能力，而又不比显著增加费用、价格；
?建立多重处理，既增强了系统的处理能力，又不必增强完整的额外系统；
?多处理器系统提供了重要的灵活性。
多处理器的硬件组织
?总线式结构
?单总线结构
?多总线结构
?交叉开关结构
?多端口存储器结构
单总线结构
多总线结构
交叉开关式结构
多端口存储器结构
?核心：多端口存储器模块
6.2 多处理器系统的分类
?多处理器簇（Cluster，又称分布式系统）
多处理器簇是指每个处理器都有自己专用的存储器，每个单元都有自包含的计算机，计算机之间的通信或者经由专用的线路，或者通过网络。?共享存储器的多处理器系统
多个处理器共享公用存储器，每个处理器共享对公用存储器中的程序和数据的访问。
这种多处理器系统常分为：
主从式多处理器结构和对称式多处理器结构
主/从式处理器系统
在主从式处理器系统中，指定一个处理器作为主处理器，其他处理器皆为从处理器，由于处理器地位是不平等的，所以又称为非对称。只有主处理器可运行操作系统，从处理器仅可执行用户程序。
主/从处理器系统的缺点
?主处理负载过重；
?主处理器故障将引起整个系统故障，可靠性差；
?若主处理器不能充分有效地满足从处理器的服务请求，从处理器的利用率会降低。对称式多处理器系统
?系统中有多个处理器，所有的处理器处于同等地位
?每个处理器都可以运行操作系统和内核程序处理中断、调度进程等；
?每个处理器都同样可以控制I/O设备和系统中其他资源；
?系统中所有处理器共享主存储器，没有自己私用的存储器
SMP的组织
6.3 调度的层次
从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同类型。
按照调度的层次，调度可分为三级：
?长期调度
?按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存，并
为作业做好运行前的准备工作和作业完成后的善后工作。
?中期调度
?决定哪些进程被允许参与竞争处理资源。将进程的部分或全部换出到外存上，
将当前所需部分换入到内存。
?短期调度
?按照某种原则将处理器分配给就绪进程或线程
处理机调度的层次
1. 作业调度
作业的状态：
?提交状态
?作业被提交给机房后或用户通过终端键盘向计算机中键入其作业时所处的状
态。
?后备状态
?作业的全部信息都已通过输入设备输入，并由操作系统将其存放在磁盘的某些
盘区中等待运行。
?运行状态
?作业调度程序选中而被送入主存，并建立进程投入运行。
?完成状态
?作业完成其全部运行，释放其所占用的全部资源。
作业调度
?作业调度由作业调度程序来完成
?作业调度时的两个决定
?接纳多少个作业：
?作业调度每次要接纳多少个作业进入内存，取决于多道程序度。应根
据系统的规模和运行速度等因素。
?接纳哪些作业：
?即应将哪些作业从外存调入内存，这取决于所采用的调度算法。
作业调度程序的功能
?按照某种调度算法从后备作业队列中挑选作业
?为选中的作业分配主存和外设资源
?为选中的作业建立相应的进程
?为选中的作业运行时所需的有关表格，如作业表等
?作业结束时完成该作业的善后处理作业
选择调度算法时考虑的问题
?设计目标
?资源利用率
?均衡地处理系统和用户地要求
?在使用优先级地系统中，每个进程都有一个优先级，调度算法应优先运行高优先级进
程
?在使用优先数的系统中，调度策略还可分为“可抢占”和“不可抢占”两种方式
调度的性能准则
面向用户的调度性能准则
?周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，
CPU上执行，就绪队列和阻塞队列中等待，结果输出等待－－批处理系统
?平均周转时间t
?平均带权周转时间（带权周转时间W是t(周转)/t(CPU执行)〕
?响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间
－－分时系统
?截止时间：开始截止时间和完成截止时间－－实时系统，与周转时间有些相似。
?公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。
?优先级：可以使关键任务达到更好的指标。
面向用户的调度性能准则
?平均周转时间t:
面向用户的调度性能准则
平均带权周转时间w为：
t
ri
为作业i的实际执行时间
一般来说，系统应选择使作业的平均周转时间（或带权周转时间）短的某种算法。因为，作业的平均周转时间越短，意味着这些作业在系统内停留的时间越短，因而系统资源的利用率也就越高。
2. 面向系统的调度性能准则?吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系－－批处
理系统
?平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：
在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时?处理机利用率：－－大中型主机
?各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作
业搭配－－大中型主机
3. 调度算法本身的调度性能准则
?易于实现
?执行开销比
处理器调度的两种方式
?非抢占方式：
?采用该方式，一旦将处理器分配给某进程后，便让进程一直执行，直到该进程
完成和其因等待某事件而阻塞时，才将处理器分配给其他进程。
?优点：实现简单，系统开销小
?缺点：难以满足紧急任务的要求
处理器调度的两种方式
?抢占方式
?采用这种方式，允许调度程序根据某种原则停止正在处理器上运行的进程，将
处理器重新分配给其他进程。
?优点：能满足及时响应紧急任务
?缺点：增加了系统开销
6.4 单处理调度算法
?先进先出调度算法
?优先级调度算法
?时间片轮转算法
?最短进程优先调度算法
?最短剩余时间优先调度算法
?最高响应比优先调度算法
?多级反馈队列调度算法
先进先出调度算法
?基本原则：按照作业提交或进程进入就绪队列的先后次序来选择。
?调度方式：不可抢占。
?缺点：
?比较有利于长作业，而不利于短作业。
?有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
?应用：
?不作为主要的调度策略，尤其不能用于分时和实时系统。常结合其他调度策略
使用。
?可用于作业调度和进程调度
先进先出调度算法
优先级调度算法
?原则：按照进程
计算机操作系统教学大纲
《计算机操作系统》课程教学大纲 一. 课程名称 操作系统原理 二. 学时与学分 学时共64学时（52+12+8） 其中，52为理论课学时，12为实验学时，8为课外实验学时 学分 4 三. 先修课程 《计算机组成原理》、《C语言程序设计》、 《IBM—PC宏汇编程序设计语言》、《数据结构》 四. 课程教学目标 通过本课程的学习，要达到如下目标： 1．掌握操作系统的基本原理与实现技术，包括现代操作系统对计算机系统资源的管理策略与方法、操作系统进程管理机制、现代操作系统的用户界面。 2．了解操作系统的结构与设计。 3．具备系统软件开发技能，为以后从事各种研究、开发工作(如：设计、分析或改进各种系统软件和应用软件) 提供必要的软件基础和基本技能。 4．为进一步学习数据库系统、计算机网络、分布式系统等课程打下基础。 五. 适用学科专业 信息大类各专业
六. 基本教学内容与学时安排 主要内容： 本课程全面系统地阐述计算机操作系统的基本原理、主要功能及实现技术，重点论述多用户、多任务操作系统的运行机制；系统资源管理的策略和方法；操作系统提供的用户界面。讨论现代操作系统采用的并行处理技术和虚拟技术。本书以Linux系统为实例，剖析了其特点和具体的实现技术。 理论课学时：52学时 （48学时，课堂讨论2学时，考试2学时） ?绪论4学时 ?操作系统的结构和硬件支持4学时 ?操作系统的用户界面4学时 ?进程及进程管理8学时 ?资源分配与调度4学时 ?存储管理6学时 ?设备管理4学时 ?文件系统6学时 ?Linux系统8学时 七、教材 《计算机操作系统》(第2版)，庞丽萍阳富民人民邮电出版社，2014年2月 八、考核方式 闭卷考试
操作系统期末复习真题 附答案
操作系统期末复习真题11_附答案 线程是操作系统的概念，已具有线程管理的操作系统有( )。 A．Windows 3.2 B．OS /2 C．Windows NT D．Mach 此题答案为：BC 此题难度等级为：B. 下面属于进程基本状态的是( )。 A．就绪 B．运行 C．后备 D．阻塞 此题答案为：AD 此题难度等级为：A . 下列各项工作步骤，( )是创建进程所必须的步骤。 A．建立一个PCB B．由CPU调度程序为进程调度CPU C．为进程分配内存等必要资源 D．将PCB接入进程就绪队列 此题答案为：B 此题难度等级为：C . 关于进程的正确说法是( )。 A．进程就是程序，或者说进程是程序的另一叫法 B．一个被创建了的进程，在它被消灭之前，大多数时刻处于进程的三种基本状态之一C．多个不同的进程可以包含相同的程序 D．一个处于等待队列中的进程，即使进入其他状态，仍然放在等待队列中 此题答案为：B 此题难度等级为：D . 在( )时，可能挂起某进程。 A．进程出现死锁 B．进程的数目太少 C．进程数目太多 D．进程出现故障 此题答案为：AC 此题难度等级为：A . 多道程序系统进程从执行状态转换到就绪状态的原因是( )。
A．时间片完 B．等待其他进程的执行结果 C．等待I/O D．有更高优先级的进程到来 此题答案为：A 此题难度等级为：B . 有关进程的描述中，（）是正确的。 A．进程执行的相对速度不能由进程自己来控制 B．利用信号量的P.V操作可以交换大量信息 C．同步是指并发进程之间存在的一种制约关系 D．并发进程在访问共享资源时，不可能出现与时间有关的错误 此题答案为：AB 此题难度等级为：B . 下列资源中（）是临界资源。 A．打印机 B．非共享的资源 C．共享变量 D．共享缓冲区 此题答案为：ACD 此题难度等级为：A . 一个进程从执行状态转换到阻塞状态的可能原因是本进程（）。A．时间片完 B．需要等待其他进程的执行结果 C．执行了V操作 D．执行了P操作 此题答案为：A 此题难度等级为：C . 一个进程从阻塞状态转换到就绪状态的可能原因是其他进程（）。A．时间片完 B．执行了唤醒原语 C．执行了V操作 D．执行了P操作
操作系统期末复习参考
第一章 1、计算机软件是指安装在计算机系统中的程序和有关的文件 2、软件可分为：系统软件、支撑软件、应用软件 3、操作系统属性系统软件；各种接口软件和工具组。属于支撑软件 4、操作系统：操作系统是计算机系统中的系统软件，是能有效地组织和管理计算机系统中的硬件和软件资源，合理地组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使得用户能够合理、方便、有效地使用计算机，使整个计算机系统能够高效运行的一组程序模块的集合。 5、操作系统主要有一下两个方面的作用： 1、操作系统要管理计算机系统中的各个资源，包括硬件及软件资源 2、操作系统要为用户提供良好的界面（最终用户和系统用户） 6、操作系统的目标：1、方便性、2、有效性、3、可扩充性、4、开放性 7、操作系统发展的主要动力：1、不断提高计算机资源利用率的需求2、方便用户3、器件的不断更新换代4、计算机体系结构的不断发展 8、操作系统的主要功能：1、处理机管理（用于分配和控制处理机）2、存储器管理（负责内存的分配和回收）3、I/O设备管理（负责I/O设备分配和操作）4、文件管理（负责文件的存取、共享和保护） 9、计算机硬件是指计算机系统中由电子、机械、和光电元件等组成的各种部件设备。 10、处理机管理功能：1、进程控制2、进程同步3、进程通信、4、调度 11、存储器管理的功能：1、内存分配2、内存保护3、地址映射4、内存扩充 12、文件管理的功能：1、文件存储空间管理2、目录管理3、文件读写管理和存取管理 13、内存分配：1、静态分配方式2、动态分配方式 14、内存分配结构和功能：1、内存分配数据结构2、内存分配功能3、内存回收功能 15、操作系统的特征：1、并发性2、共享性3、虚拟性4、异步性 16、处理机的构成：1、运算器2、控制器3、一系列的寄存器4、高速缓存 17、处理机分为二类寄存器：1、用户可见寄存器2、控制和状态寄存器 18、指令执行的基本过程（步骤）：处理机先从存取中每次读取一条指令，然后执行这条指令，一个这样的单条指令过程称为一个指令周期。程序的执行就是由不断取指令和执行指令的指令周期组成。
操作系统期末复习
第一章操作系统引论 1 什么是操作系统？ 1.用户与计算机硬件之间的接口 2.控制和管理计算机资源的软件 2 计算机由什么硬件组成？ CPU、存储器、输入/输出设备、总线等 3多道批处理系统 在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。 【特征】（优缺点）： 资源利用率高、系统吞吐量大、平均周转时间长、无交互能力 3 分时系统 分时系统是指在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。 【特征】（优缺点）： 多路性、独立性、及时性、交互性 4 实时系统 实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。 【特征】（优缺点）： 多路性、独立性、及时性、交互性、可靠性 5 OS的特性和功能 OS的基本特性： 并发性、共享性、虚拟技术性、异步性。其中“并发”是最重要最基本的特性 OS的主要功能：资源管理器和用户接口 资源管理功能：处理机管理、存储器管理、设备管理、文件管理 操作系统和用户之间的接口： 用户接口：联机用户接口，脱机用户接口和图形用户接口 程序接口：该接口是为用户程序在执行中访问系统资源而设置的，它是由一组系统调用组成。
第二章进程管理 1 进程的基本概念 程序顺序执行时的特征：顺序性、封闭性、可再现性 程序并发执行时的特征：顺序性、间断性、失去封闭性、不可再现性 前趋图是一个有向无循环图DAG(Directed Acyclic Graph)。 进程的定义： 进程是程序的一次执行。 进程是可以和其它计算并发执行的计算。 进程是程序在一个数据集合上的运行过程。 进程是一个程序与其使用的数据在处理机上顺序执行时发生的活动。 进程是系统进行资源分配和调度的一个基本单位。 进程的特征： 动态性、并发性、独立性、异步性、结构特性 进程控制块： 是进程实体（进程映像）的一部分。在PCB中记录了OS所需的，用于描述进程情况及控制进程运行所需的全部信息；它使一个在多道程序环境下不能独立运行的程序（包含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。OS 就是根据PCB来对并发执行的进程进行控制和管理的，它是进程存在的唯一标志。 进程的三个基本状态： 就绪态(ready)、运行态(running)、阻塞态(blocked) （新状态（创建态）和终止状态）
操作系统课程教学大纲
GDOU-B-11-213 《操作系统》课程教学大纲 课程简介 课程简介: 本课程主要讲述操作系统的原理，使学生不仅能够从系统内部了解操作系统的工作原理，而且可以学到软件设计的思想方法和技术方法。主要内容 包括：操作系统的概论；操作系统的作业管理；操作系统的文件管理原理； 操作系统的进程概念、进程调度和控制、进程互斥和同步等；操作系统的各 种存储管理方式以及存储保护和共享；操作系统的设备管理一般原理。其次 在实验环节介绍实例操作系统的若干实现技术，如：Windows操作系统、Linux 操作系统等。 课程大纲 一、课程的性质与任务： 本课程计算机学科的软件工程专业中是一门专业方向课，也可以面向计算机类的其它专业。其任务是讲授操作系统的原理，从系统内部了解操作系统的工作原理以级软件设计的思想方法和技术方法；同时介绍实例操作系统的若干实现技术。 二、课程的目的与基本要求： 通过本课程的教学使学生能够从操作系统内部获知操作系统的工作原理，理解操作系统几大管理模块的分工和管理思想，学习设计系统软件的思想方法，通过实验环节掌握操作系统实例的若干实现技术，如：Windows操作系统、Linux操作系统等。 三、面向专业： 软件工程、计算机类 四、先修课程: 计算系统基础，C/C++语言程序设计，计算机组成结构，数据结构。 五、本课程与其它课程的联系：
本课程以计算系统基础，C/C++语言程序设计，计算机组成结构，数据结构等为先修课程，在学习本课程之前要求学生掌握先修课程的知识，在学习本课程的过程中能将数据结构、计算机组成结构等课程的知识融入到本课程之中。 六、教学内容安排、要求、学时分配及作业： 第一章：操作系统概论（2学时） 第一节：操作系统的地位及作用 操作系统的地位（A）；操作系统的作用（A）。 第二节：操作系统的功能 单道系统与多道系统（B）；操作系统的功能（A）。 第三节：操作系统的分类 批处理操作系统（B）；分时操作系统（B）；实时操作系统（B）。 第二章：作业管理（2学时） 第一节：作业的组织 作业与作业步（B）；作业的分类（B）；作业的状态（B）；作业控制块（B）。 第二节：操作系统的用户接口 程序级接口（A）；作业控制级接口（A）。 第三节：作业调度 作业调度程序的功能（B）；作业调度策略（B）；作业调度算法（B）。 第四节：作业控制 脱机控制方式（A）；联机控制方式（A）。 第三章：文件管理（8学时） 第一节：文件与文件系统（1学时） 文件（B）；文件的种类（B）；文件系统及其功能（A）。 第二节：文件的组织结构（1学时） 文件的逻辑结构（A）；文件的物理结构（A）。 第三节：文件目录结构（1学时） 文件说明（B）；文件目录的结构（A）；当前目录和目录文件（B）。 第四节：文件存取与操作（1学时） 文件的存取方法（A）；文件存储设备（C）；活动文件（B）；文件操作（A）。 第五节：文件存储空间的管理（2学时） 空闲块表（A）；空闲区表（A）；空闲块链（A）；位示图（A）。 第六节：文件的共享和保护（2学时）
计算机操作系统期末复习题(答案最全)
计算机操作系统期末复习题 注：1-简单2-一般3-较难4-难 第一部分操作系统基本概念 一、选择题(选择最确切的一个答案，将其代码填入括号中) 1、操作系统是一种（）。 A、应用软件 B、系统软件 C、通用软件 D、工具软件 答案-1：B 2、计算机系统的组成包括（）。 A、程序和数据 B、处理器和内存 C、计算机硬件和计算机软件 D、处理器、存储器和外围设备 答案-1：C 3、下面关于计算机软件的描述正确的是（）。 A、它是系统赖以工作的实体 B、它是指计算机的程序及文档 C、位于计算机系统的最外层 D、分为系统软件和支撑软件两大类 答案-2：B 4、财务软件是一种（）。 A、系统软件 B、接口软件 C、应用软件 D、用户软件 答案-2：C 5、世界上第一个操作系统是（）。 A、分时系统 B、单道批处理系统 C、多道批处理系统 D、实时系统 答案-1：B 6、批处理操作系统提高了计算机的工作效率，但（）。 A、系统资源利用率不高 B、在作业执行时用户不能直接干预 C、系统吞吐量小 D、不具备并行性 答案-3：B 7、引入多道程序的目的是（）。 A、为了充分利用主存储器 B、增强系统的交互能力
C、提高实时响应速度 D、充分利用CPU，减少CPU的等待时间 答案-3：D 8、在多道程序设计的计算机系统中，CPU（）。 A、只能被一个程序占用 B、可以被多个程序同时占用 C、可以被多个程序交替占用 D、以上都不对 答案-2：C 9、多道程序设计是指（）。 A、有多个程序同时进入CPU运行 B、有多个程序同时进入主存并行运行 C、程序段执行不是顺序的 D、同一个程序可以对应多个不同的进程 答案-3：B 10、从总体上说，采用多道程序设计技术可以（）单位时间的算题量，但对每一个算题，从算题开始到全部完成所需的时间比单道执行所需的时间可能要（）。 A、增加减少 B、增加延长 C、减少延长 D、减少减少 答案-4：B 11、允许多个用户以交互使用计算机的操作系统是（）。 A、分时系统 B、单道批处理系统 C、多道批处理系统 D、实时系统 答案-2：A 12、下面关于操作系统的叙述正确的是（）。 A、批处理作业必须具有作业控制信息 B、分时系统不一定都具有人机交互功能 C、从响应时间的角度看，实时系统与分时系统差不多 D、由于采用了分时技术，用户可以独占计算机的资源 答案-3：A 13、操作系统是一组（）。 A、文件管理程序 B、中断处理程序 C、资源管理程序 D、设备管理程序 答案-1：C 14、现代操作系统的两个基本特征是（）和资源共享。 A、多道程序设计 B、中断处理 C、程序的并发执行 D、实现分时与实时处理 答案-1：C 15、（）不是操作系统关心的主要问题。 A、管理计算机裸机
操作系统期末复习
操作系统期末复习 选择题和判断题中蓝色的为正确答案。 一、选择题（选择一个正确答案的代码填入括号中） 1.在计算机系统中，控制和管理各种资源、有效地组织多道程序运行的系统软件称作 （）。 A．管理信息系统B．文件系统 C．操作系统D．数据库管理系统 2.按照所起的作用和需要的运行环境，操作系统属于（）。 A．用户软件B．应用软件 C．支撑软件D．系统软件 3.操作系统的基本职能是（）。 A．提供功能强大的网络管理工具 B．提供用户界面，方便用户使用 C．提供方便的可视化编辑程序 D．控制和管理系统各种资源，有效地组织多道程序的运行 4.现代操作系统的基本特征是（）、资源共享和操作的异步性。 A．多道程序设计B．中断处理 C．程序的并发执行D．实现分时与实时处理 5.引入多道程序的目的在于（）。 A．充分利用存储器B．提高实时响应速度 C．充分利用CPU，减少CPU等待时间 D．有利于代码共享，减少主、辅存信息交换量 6.以下不属于操作系统具备的主要功能的是（）。 A．文档编辑B．中断处理 C．存管理D．CPU调度 7.为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。这 属于操作系统的( )。 A．处理器管理B．作业管理C．文件管理D．存储管理 8.在实时系统中，一旦有处理请求和要求处理的数据时，CPU就应该立即处理该数据并 将结果及时送回。下面属于实时系统的是（）。 A．航空订票系统B．办公自动化系统 C．计算机辅助设计系统D．计算机激光照排系统 9.为了使系统中所有的用户都能得到及时的响应，该操作系统应该是（）。
A．多道批处理系统B．分时系统 C．实时系统D．网络系统 10.下列不属于分时系统特征的是( )。 A．为多用户设计B．可靠性比实时系统要求高 C．方便用户与计算机的交互D．需要中断机构及时钟系统的支持 11.以下著名的操作系统中，属于多用户、多进程、多任务分时系统的是（）。 A．DOS系统B．UNIX系统 C．Windows NT系统D．OS/2系统 12.操作系统核与用户程序、应用程序之间的接口是（）。 A．shell命令B．系统调用 C．图形界面D．C语言函数 13.系统调用是由操作系统提供的部调用，它（）。 A．直接通过键盘交互方式使用B．只能通过用户程序间接使用 C．是命令接口中的命令D．与系统的命令一样 14.系统调用的目的是（）。 A．申请系统资源B．终止系统服务 C．释放系统资源D．请求系统服务 15.进程与程序之间有密切联系，但又是不同的概念。二者的一个本质区别是（）。 A．程序是静态概念，进程是动态概念 B．程序是动态概念，进程是静态概念 C．程序保存在文件中，进程存放在存中 D．程序顺序执行，进程并发执行 16.在操作系统中，进程的最基本的特征是（）。 A．与程序的对应性B．顺序性和可再现性 C．动态性和并发性D．执行过程的封闭性 17.进程在系统中存在的唯一标志是( )。 A．所运行的程序B．进程控制块 C．进程队列D．所运行的程序和数据 18.进程的动态、并发等特征是利用（）表现出来的。 A．进程控制块B．数据 C．程序和数据D．程序 19.在单处理机系统中，处于运行状态的进程( )。 A．只有一个B．可以有多个 C．不能被挂起D．必须在执行完后才能被撤下
操作系统期末复习资料
一．主要知识点： 1.PCB(进程控制块)：使并发执行的每个程序都能独立运行。 1.1PCB已成为进程存在于系统中的唯一标志。 1.2由程序段、相关的数据段和PCB构成了进程实体。 2.进程控制一般由OS的内核中的原语来实现的。 3.同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待。 4.四种信号量：整形型信号量、记录型信号量、AND型信号量、信号量集。 5.死锁：指多个进程在运行时因争夺资源而造成的一个僵局。 6.引起死锁的原因：竞争资源、进程推进顺序不当。 7.产生死锁的必要条件：互斥、请求和保持、不可抢占、循环等待。 8.处理死锁的方法：预防死锁、避免死锁、检测死锁、解除死锁。 9.程序的三种装入方式： （1）绝对装入方式：只适用于单道程序环境，只能将目标模块装入到内存中事先指定的位置；（2）可重定位装入方式：可用于多道程序环境，但不允许在程序运行时在内存中移动位置；（3）动态运行时的装入方式：可移动在内存中的位置。 注：装入内存后，并不立即把其逻辑地址转换为物理地址，而是在程序真正执行时才能进行地址转换。 10.对换空间的管理： （1）对文件区空间的管理采取离散分配的方式 （2）对对换空间的管理采取连续分配方式 11.四种连续分配方式：
（1）单一连续分配：单道程序环境； （2）固定分区分配：多道程序环境； （3）动态分区分配：涉及到所用的数据结构、分配算法、分区的分配和回收操作； 重点：基于顺序搜索的动态分区分配算法 首次适应算法：空闲分区以地址递增的次序链接 最佳适应算法：空闲分区以容量大小递增的次序链接 最坏适应算法：空闲分区以容量大小递减的次序链接 （4）动态可重定位分区分配：与动态分区分配的差别是，增加了紧凑的功能。 12.三种离散分配方式： （1）分页存储管理：逻辑地址分为页号和页内地址两部分。页表（作用是实现从页号到物理块号的地址映射）。页表寄存器（存放页表在内存中的始址和页表的长度）。需要2次访问内存。为了提高速度，采用了快表。 （2）分段存储管理：逻辑地址分为段号和段内地址。段表（作用是实现从逻辑段到物理内存区的地址映射）。段表寄存器（存放段表在内存中的始址和段表的长度）。 （3）段页式存储管理：地址结构由段号、段内页号、页内地址组成。段表寄存器（存放段表在内存中的始址和段表的长度）。需要访问3次内存。 13.虚拟存储器特征：1）多次性2）对换性 3）虚拟性 ①虚拟性即不是物理上而是逻辑上扩充了内存容量 ②多次性即每个作业不是全部一次性地装入内存，而是只装入一部分 ③对换性即所需的全部程序和数据要分成多次调入内存
操作系统课程设计2014教学大纲
《操作系统课程设计》大纲 一、设计目的和要求 目的：本课程设计是为配合计算机相关专业的重要专业课《操作系统》而开设的，其主要内容是让学生实际进行操作系统功能模块的设计和编程实现。通过本课程设计的实施，使学生能将操作系统的概念具体化，并从整体和动态的角度去理解和把握操作系统，以巩固和补充操作系统的原理教学，提高学生解决操作系统设计及实现过程中的具体问题的能力。 要求：通过本课程设计的实施，要求培养学生以下能力： （1）培养学生在模拟条件下与实际环境中实现功能模块和系统的能力：课程设计要求学生实际进行操作系统功能模块的设计和编程实现，具体包括：基于线程的多任务调度系统的设计与实现；一个简单文件系统的设计与实现。 （2）培养学生设计和实施工程实验的能力，合理分析试验结果的能力：学生在完成项目的过程中，需要进行实验设计、程序调试、错误分析，从而熟悉实验设计方法及实验结果的分析方法。 （3）培养学生综合运用理论和技术手段设计系统和过程的能力：学生需根据设计项目的功能要求及操作系统原理的相关理论提出自己的解决方案，需考虑项目实现的软硬件环境，设计相关数据结构及算法，在实现过程中发现解决方案的问题并进行分析改进。 （4）培养学生分析并清楚阐述设计合理性的能力：要求学生在项目上机验收和实验报告中分析阐述设计思路的合理性和正确性。 （5）培养学生的组织管理能力、人际交往能力、团队协作能力：课程设计分小组进行，每个小组有一个组长，负责组织本组成员的分工及合作。 二、设计学时和学分 学时：32 ；学分：1 三、设计的主要内容 以下三个题目中：1、2中选做一题，第3题必做。 1、基于线程的多任务调度系统的设计与实现 （1）线程的创建、撤消和CPU切换。 掌握线程的定义和特征，线程的基本状态，线程的私有堆栈，线程控制块TCB，理解线程与进程的区别，实现线程的创建、撤消和CPU切换。 （2）时间片轮转调度 理解各种调度算法、调度的原因，完成时钟中断的截取，具体实现调度程序。 （3）最高优先权优先调度 理解优先权的概念，并实现最高优先权优先调度策略。 （4）利用记录型信号量实现线程的同步
计算机操作系统期末复习题(带答案)
57计算机操作系统期末复习题 第一部分操作系统基本概念 一、选择题(选择最确切的一个答案，将其代码填入括号中) 多道程序设计是指（ B ）。 A、有多个程序同时进入CPU运行 B、有多个程序同时进入主存并行运行 C、程序段执行不是顺序的 D、同一个程序可以对应多个不同的进程 从总体上说，采用多道程序设计技术可以（B ）单位时间的算题量，但对每一个算题，从算题开始到全部完成所需的时间比单道执行所需的时间可能要（B ）。 A、增加减少 B、增加延长 C、减少延长 D、减少减少 现代操作系统的两个基本特征是（C ）和资源共享。 A、多道程序设计 B、中断处理 C、程序的并发执行 D、实现分时与实时处理-3：C 以下（C ）项功能不是操作系统具备的主要功能。 A、内存管理 B、中断处理 C、文档编辑 D、CPU调度 用户在一次计算过程中，或者一次事物处理中，要求计算机完成所做的工作的集合，这是指（C ）。 A、进程 B、程序 C、作业 D、系统调用 CPU状态分为系统态和用户态，从用户态转换到系统态的唯一途径是（C ）。 A、运行进程修改程序状态字 B、中断屏蔽 C、系统调用 D、进程调度程序 系统调用的目的是（A ）。
A、请求系统服务 B、终止系统服务 C、申请系统资源 D、释放系统资源 为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率的是（B ）。 A、处理器管理 B、存储器管理 C、文件管理 D、作业管理 二、填空题 计算机操作系统是方便用户、管理和控制计算机_软硬件资源_的系统软件。 采用多道程序设计技术能充分发挥处理器与外围设备与外围设备之间并行工作的能力。操作系统目前有五大类型：_批处理_、_分时_、_实时_、_网络_和_分布式_。 操作系统的五大功能是：_处理机管理_、_储存管理_、_设备管理_、_信息管理_和_用户接口_。 UNIX系统是多用户分时交互型操作系统，DOS系统是单用户单任务操作系统。计算机中的CPU的工作分为系统态和用户态两种，系统态运行操作系统程序，用户态运行应用程序。 第二部分进程管理 一、选择题(选择最确切的一个答案，将其代码填入括号中) 顺序程序和并发程序的执行相比，（C）。 A、基本相同 B、有点不同 C、并发程序执行总体上执行时间快 D、顺序程序执行总体上执行时间快 并发进程失去了封闭性是指（D ）。 A、多个相对独立的进程以各自的速度向前推进 B、并发进程的执行结果与速度无关 C、并发进程执行时，在不同时刻发生的错误
操作系统期末复习重点(史上最全)
操作系统（Operating System）复习要点 第一章 操作系统：计算机系统中的一组系统软件，由它统一管理计算机系统的各种资源并合理组织计算机的工作流程，方便用户使用。具有管理和服务功能 操作系统的特征：并发性，共享性，随机性，可重构性，虚拟性。并发是指计算机系统中同时存在多个程序，宏观上看，这些程序是同时向前推进的。 共享性：批操作系统程序与多个用户程序共用系统中的各种资源虚拟性：物理实体转化为若干逻辑上的对应物。 操作系统的功能：1，进程管理；2，存储管理；3，文件管理；4，作业管理；5，设备管理；6，其他功能（系统安全，网络通信）。 传统OS中，进程是系统调度的最小单位，是程序的一次执行；而现代OS中则是线程，是程序一次相对独立的执行过程。 操作系统的发展历史 1,手工操作：穿孔卡片 2,监督程序——早期批处理：计算机高级语言出现，单道批处理单道批处理：串行执行作业中，由监督程序识别一个作业，进行处理后再取下一个作业的自动定序处理方式3,多道批处理系统——现代意义上的操作系统 多道批处理：允许多个程序同时存在于主存之中，由中央处理机以切换方式为之服务，使得多个程序可以“同时”执行。 操作系统分类：批处理OS，分时OS，实时OS，嵌入式OS，个人计算机OS，网络OS，分布式OS，智能卡OS。 操作系统类型：批处理OS，分时OS，实时OS，网络OS，分布式OS。 分时系统：支持多个终端用户共享一个计算机系统而互不干扰，能实现人机交互的系统。 特点：支持多用户，具有同时性、独立性、及时性、交互性。实时系统：使计算机系统接收到外部信号后及时进行处理，并且在严格的规定时间内处理结束、再给出反馈信号的系统。 特点：及时响应，快速处理，安全可靠。 宏观和微观两个发展方向：网络OS、分布式OS（大型系统）、嵌入式OS（微机） 研究操作系统的几种视角：软件的视角、用户接口、资源管理、虚拟机、服务提供者视角 第二章作业的定义：用户要求计算机系统处理的一个计算问题。（或参考 “小结”） 作业的两种控制方式 1，批处理：操作系统按各作业的作业控制说明书的要求，分别控制相应的作业按指定步骤执行。 2，交互：在作业执行过程中，操作系统与用户之间不断交互作用。 作业调度：从后备作业队列中选取某个作业投入主存参与多道运行。 调度算法原则：①尽可能运行更多的作业，优先考虑短作业； ②使处理机保持繁忙，优先考虑计算量大的作业； ③使I/O设备保持繁忙，优先考虑I/O繁忙的作业； ④对所有的作业都是公平合理的。 选择原则：①选择的调度算法与系统的整体设计目标一致； ②注意系统资源的均衡使用，使I/O作业与CPU作业 搭配合理； ③作业应该在规定时间内完成，能缩短作业周转时间。调度性能的衡量——周转时间、平均周转时间、带权周转时间、平均带权周转时间 周转时间=完成时间－提交时间； 运行时间=完成时间－开始时间； 带权周转时间=周转时间÷运行时间； 响应比＝１＋等待时间÷运行时间 调度算法：（注意：一律以小时为单位） FCFS：按到达先后顺序执行； 短作业优先法：按运行时间最短优先； 响应比优先法：按响应比最高的作业优先，注意每执行完一 次作业计算一次响应比。 交互式作业的管理—接口（①操作控制命令②菜单技术③窗口技术）：字符（命令行）、菜单、图形 用户和操作系统之间的接口：①程序一级接口②作业控制一级接口P42 中的第二题（应用题），必做。 第三章 进程的定义：具有独立功能的并行程序一次执行过程 进程和程序的区别与联系： 区别：①程序是指令的有序集合，静态；进程是程序的一次运行活动，动态； ②进程是一个独立运行单位，共享资源的实体，能并发执行； 而程序不能。 联系：①一个程序对应多个进程，一个进程至少对应一段程序； ②静态地观察进程，与程序一样都由指令集和数据构成。 精品
操作系统课程教学网站论文
摘要 通过操作系统教学网站的建设，完成了对于操作系统课程的远程化授课。可以使学生不受时间空间的限制，通过网络对于这门课程进行学习。建立起了基于B/C的网络化教学系统。本网站采用当前最流行的JSP网络编程技术，可以实现数据的高效、动态、交互访问，具有强大的Server/Client交互能力。本文中所做的主要工作：介绍Win2000 +JSP(J2DK+TOMCAT)系统并且嵌入 JAVABEAN的一般原理；阐述整个操作系统教学网站的概要设计，系统结构及工作原理；分析了系统实现中的特殊性、难点和重点；详细设计实现学院介绍、教学资源、课程表、课堂教学、在线答疑、其他课程、课件下载、留言反馈、自我测试、成绩管理、站内搜索、公告专栏、友情链接、校园风景、新闻中心、栏目导航等程序模块；各个模块的具体实现，且分析并解决实现中的若干技术问题；建立完整的实验网站，进行测试并分析结果。 关键字： JAVABEAN JSP 交互访问 JAVASCRIPT JDBC
Abstract Through the operating system teaching website construction, completed long-distance has taught regarding the operating system curriculum, was allowed to cause the student without the time space limit, and carried on the study through the network regarding this curriculum. Established based on the B/C network teaching system. This website uses the current most popular JSP network programming technology, may realize the data to be highly effective, dynamically, alternately visits, and has the formidable Server/Client interactive ability. In this article does main work: Introduced Win2000 +JSP (J2DK+TOMCAT) the system and to insert JA V ABEAN the general principle; Elaborates the entire operating system teaching website outline design, the system structure and the principle of work; Has analyzed in the system realization particularity, the difficulty and key; The detailed design realization institute introduced, in the teaching resources, the class schedule, the classroom instruction, the on-line Q/A, other curricula, class downloading, the message feedback, the self- test, the result management, the station search, program module and so on announcement column, friendship link, campus scenery, news center, column navigation; Each module concrete realization, also in analysis and solution realization certain technical questions; The establishment integrity experimental website, carries on the test and the analysis result. Key words: JA V ABEAN JSP alternately visits JA V ASCRIPT JDBC
计算机操作系统期末复习题与答案
一、名词解释(每题2分,共10分) 1、原语 2、进程 3、管态 4、原子操作 5、临界区 6、死锁 7、虚拟存储器 8、缺页中断 二、选择题(每题1分,共10分) 1、在现代操作系统中引入了（），从而使并发和共享成为可能。 A.单道程序 B. 磁盘 C. 对象 D.多道程序 2、( )操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互地使用计算机。 A.网络 B.分布式 C.分时 D.实时 3、从用户的观点看，操作系统是（）。 A. 用户与计算机硬件之间的接口 B.控制和管理计算机资源的软件 C. 合理组织计算机工作流程的软件 D.计算机资源的的管理者 4、在下列性质中，哪一个不是分时系统的特征。（） A. 交互性 B. 多路性 C. 成批性 D. 独占性 5、引入多道程序的目的在于（）。 A.充分利用CPU，减少CPU等待时间 B.提高实时响应速度 C.有利于代码共享，减少主、辅存信息交换量 D.充分利用存储器 6、当CPU处于管态时，它可以执行的指令是（）。
A. 计算机系统中的全部指令 B. 仅限于非特权指令 C. 仅限于访管指令 D. 仅限于特权指令 7、下列各项步骤中，哪一个不是创建进程所必须的步骤（）。 A. 建立一个进程控制块PCB B. 由CPU调度程序为进程调度CPU C.为进程分配存等必要的资源 D.将PCB链入进程就绪队列 8、为了对紧急进程或重要进程进行调度，调度算法应采用（）。 A.先进先出调度算法 B. 优先数法 C.最短作业优先调度 D. 定时轮转法 9、进程调度的关键问题是选择合理的（），并恰当地进行代码转换。 A.时间片间隔 B. 调度算法 C.CPU速度 D. 存空间 10、并发性是指若干事件在（）发生。 A.同一时刻 B.同一时间间隔 C.不同时刻 D.不同时间间隔 11、如果某一进程获得除CPU外的所有所需运行资源，经调度，分配给它CPU，该进程将进入（）。 A.就绪状态 B. 运行状态 C.等待状态 D. 活动状态
操作系统期末复习复习过程
一、选择题 1．引入多道程序的目的在于（）。 A.有利于代码共享，减少主、辅存信息交换量B．充分利用存储器 C.充分利用CPU，减少CPU等待时间D．提高实时响应速度 2. 在单处理机计算机系统中，（）是并行操作的。 A.程序与程序 B.处理机的操作与通道的操作 C.主程序与子程序 D.用户程序与操作系统程序 3.下面哪一个不是程序在并发系统内执行的特点（）。 A.产生死锁的必然性 B.资源分配的动态性 C.程序执行的间断性 D.相互通信的可能性 4．进程和程序的一个本质区别是( )。 A. 进程分时使用CPU，程序独占CPU B．进程存储在内存，程序存储在外存 C. 进程在一个文件中，程序在多个文件中 D．进程为动态的，程序为静态的 5．在下列情况( )，系统需要进行进程调度。 A. 某一进程正访问一临界资源 B．某一进程运行时因缺乏资源进入阻塞状态 C．某一进程处于运行状态，而另一进程处于自由状态 D．某一进程正在访问打印机，而另一进程处于就绪状态 6．与设备控制器关系最密切的软件是（）。 A.编译程序 B.设备驱动程序 C.存储管理程序 D.处理机管理 7. 若进程P一旦被唤醒就能够投入运行，系统可能（）。 A.在抢占调度方式中，P的优先级高于当前运行的进程 B.进程P的优先级最高 C.就绪队列为空队列 D.在抢占调度方式中，P的优先级高于就绪队列中所有的进程 8. 在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图法 C.资源随意分配 D.银行家算法 9. 如果要使装入内存的程序，在内存中移动后仍能正常运行，必须要有( )的支持。 A. 静态重定位 B.动态重定位 C. 动态链接 D.静态链接 10. 段页式管理中，地址转换表是( )。 A. 每个进程一张段表，一张页表 B．每个进程的每个段一张段表，一张页表 C．每个进程一张段表，每个段一张页表
完整word版,《操作系统》期末复习题及答案
中国石油大学（北京）远程教育学院期末复习题 《操作系统》 一．单项选择题 1.操作系统是（） A．对软件进行管理的软件 B．对硬件进行管理的软件 C．对计算机资源进行管理的软件 D．对应用程序进行管理的软件 2. 在操作系统中引入多道程序设计的主要目的是（） A．缩短程序执行时间 B．减少响应时间 C．提高系统效率和增强系统处理能力 D．提高人机交互速度 3.进程与程序之间有密切联系，但又是不同的概念。二者的一个本质区别是( )。 A．程序是静态概念，进程是动态概念 B．程序是动态概念，进程是静态概念 C．程序保存在文件中，进程存放在内存中 D．程序顺序执行，进程并发执行 4. 进程有多个状态，不会发生的状态转换是（） A．就绪→运行 B．阻塞→进行 C．运行→阻塞 D．阻塞→就绪 5. 为了实现从逻辑地址空间到物理地址空间的地址转换，在硬件上必须提供一套（） A．DMA控制器 B．联想寄存器 C．地址变换机构 D．通道 6. CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用( )。 A．并行技术 B．通道技术 C．缓冲技术 D．虚存技术
7.在可变分区存储管理中，最优适应分配算法要求对空闲区表项按( )进行排列。 A.地址从大到小 B.地址从小到大 C.尺寸从大到小 D.尺寸从小到大 8.通常不采用( )方法来解除死锁。 A.终止一个死锁进程 B.终止所有死锁进程 C.从死锁进程处抢夺资源 D.从非死锁进程处抢夺资源 9.下列哪项不是设备管理的基本功能（） A.掌握并记录设备的状态 B.按用户的I／O请求进行设备分配 C.死锁检测 D.完成实际的I／O操作 10.设两个进程共用一个临界资源的互斥信号量为mutex,当mutex=-1时表示（） A．一个进程进入了临界区,另一个进程等待 B．没有一个进程进入了临界区 C．两个进程都进入了临界区 D．两个进程都在等待 11. 以下关于分时系统与批处理系统的说法正确的是( ) A.批处理系统是实现人机交互的系统 B.分时系统是实现自动控制无需人为干预的系统 C.批处理系统具有批处理能力，但不具有分时交互能力 D.分时系统本身既具有分时交互能力，又具有批处理能力 12.当系统采用资源有序分配方法预防死锁时，它破坏了产生死锁的必要条件中的（）。 A. 互斥条件 B.请求和保持条件 C.不可剥夺条件 D.环路等待 13. 银行家算法是用来（）。 A.避免死锁 B. 预防死锁 C.检测死锁 D.解除死锁 14. 在下面对进程的描述中，不正确的是（） A.进程是动态的概念 B.进程执行需要处理机 C.进程是有生命期的 D.进程是指令的集合 15. 用P、V操作管理临界区时，信号量的初值应定义为（） A.-1 B.0 C.1 D.任意值 16. 在下列解决死锁的方法中，属于死锁预防策略的是（）
操作系统教学计划.doc
操作系统 一、说明 （一）课程性质 本课程是计算机科学与技术专业的核心课程之一，属于必修课程。 “操作系统”是计算机系统不可缺少的组成部分，负责对系统中各种资源进行有效的管理和对各种活动进行正确的组织，使整个计算机系统协调一致且高效地工作，指挥计算机系统正常运行。操作系统基于硬件，并对硬件实施管理，并构成对所有软件运行的支持平台，给用户使用计算机而提供方便灵活友好的接口。 本课程的先修课为计算机组成原理、微机原理、数据结构、高级语言程序设计；后续课程为数据库系统原理、计算机网络、分布式系统等。 （二）教学目的 通过本课程的学习，使学生在深刻理解计算机系统整体概念的基础之上，掌握操作系统的基本内容及实现方法，掌握操作系统对计算机系统中各种资源的管理和控制功能，从而使学生具备一定的系统软件开发技能，为以后从事的研究、开发工作（如设计、分析或改进各种系统软件和应用软件）提供必要的软件基础和基本技能。 （三）教学内容 本课程内容包括：绪论，是对操作系统的一般性描述，包括什么是操作系统，操作系统在整个计算机系统的地位及其发展历史，它的功能、分类等；作业管理和linux用户接口，介绍作业和操作系统用户接口，包括作业的基本概念和作业的建立过程、linux介绍和它所提供的用户接口等；进程管理，主要介绍进程和线程的概念、进程控制、进程同步/互斥、死锁、进程间通信、线程等；处理机调度，主要介绍作业调度、进程调度、各种调度算法及其评价等；存储管理，介绍常见存储管理的方法，虚拟存储管理的实现等；linux进程和存储管理；文件系统，包括文件系统的概念、文件结构和文件存取、文件目录管理、linux文件管理等；设备管理；面向对象的操作系统和分布式操作系统。 （四）教学时数 课内学时：72 （五）教学方式 本课程的教学环节包括：课堂讲授、习题课、课堂讨论、批改作业、课外辅导、实验相结合，并逐步采用cai、网络教学等教学手段。通过本课程各个教学环节的教学，重点培养学生的自学能力、分析问题解决问题的能力。 教学方法：采用启发式教学，鼓励学生自己针对某种操作系统进行分析和研究，培养学生的自学能力，以“少而精”为原则，精选教学内容，精讲多练，调动学生学习的主观能动性。教学手段：开展电子教案、cai课件的研制、引进和应用，研制多媒体教学系统。 考试环节：考试形式采用笔试，考试题型分为：填空题、选择题、判断题、简答题、分析设计题。 二、本文 第1章绪论 教学要点： 操作系统的概念及其发展历史、分类，操作系统功能，研究操作系统的观点。本章是对操作系统的一般性描述。 教学时数：4学时 1.1 操作系统概念（0.5学时） 掌握操作系统的概念及其在计算机系统中的作用。 1.2 操作系统的发展历史（1学时）