1、第1章操作系统引论,参考书：操作系统精髓与设计原理第五版 William Stalling 著 操作系统原理与设计 曹先彬 陈兰香 编操作系统第二版 孟庆昌 牛欣源 编,本章内容提要,计算机硬件结构 什么是操作系统操作系统概念 操作系统的主要功能 操作系统的地位 操作系统的发展历程操作系统的类型操作系统的特征操作系统结构设计,1.1计算机硬件结构,计算机系统是由硬件和软件组成的 硬件是软件建立与活动的基础 软件是对硬件进行管理和功能扩充 计算机硬件结构 由五大功能部件组成，即：运算器、控制器、存储器、输入设备和输出设备。它们经由系统总线连接在一起，实现彼此通信。,现代计算机硬件结构,1.1.1
2、 处理器,CPU工作的基本周期是： 提取指令，译码分析，执行指令 每个CPU可以执行的指令集是专用的所有CPU都包含某些寄存器通用寄存器 专用寄存器 程序计数器栈指针 PSW（程序状态字）两种处理机执行状态 核心态 用户态,1.1.2 存储器,寄存器高速缓存 内存磁盘磁带,1.1.3 I/O设备,通常由控制器和设备本身两部分组成控制器设备 设备驱动程序,1.1.4 总线,总线分类数据总线地址总线控制总线,1.2 什么是操作系统,1.2.1 操作系统概念1操作系统作为扩展机器 把硬件细节与程序员隔离开，隐藏了底层硬件的特性 功能更强、使用更方便 2操作系统作为资源管理器监视各种资源，随时记录它们
3、的状态；实施某种策略以决定谁获得资源，何时获得，获得多少；分配资源供需求者使用；回收资源，以便再分配。3. 操作系统的用户观点和系统观点,定义： 操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。, 操作系统是系统软件 基本职能是控制和管理系统内各种资源，有效地组织多道程序的运行提供众多服务，方便用户使用，扩充硬件功能,1.2.2 操作系统的主要功能,1存储管理 内存分配 地址映射 内存保护 内存扩充,1.2.2 操作系统的主要功能,2作业和进程管理 作业和进程调度 进程控制 进程通信,1.2.2 操作系统的主要功能,
4、3设备管理 缓冲区管理 设备分配 设备驱动 设备无关性,1.2.2 操作系统的主要功能,4文件管理功能 文件存储空间的管理 文件操作的一般管理 目录管理 文件的读/写管理和存取控制,1.2.2 操作系统的主要功能,5用户接口程序接口命令行接口图形用户接口（GUI）,1.2.3 操作系统的地位,计算机系统的层次关系,简言之，软件是计算机执行的程序软件通常可分为三大类 应用软件 支撑软件 系统软件操作系统是裸机之上的第1层软件，它只在核心态模式下运行。通常把经过软件扩充功能后的机器称为“虚拟机”,1.3 操作系统的发展历程,1.3.1 操作系统的形成 1手工操作阶段 2早期批处理阶段 早期联机批处
5、理 早期脱机批处理 3多道批处理系统,多道批处理系统,多道程序设计： 在内存中同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。 并发：多道程序在CPU上交替运行 系统吞吐量： 在一段给定的时间内，计算机所能完成的总工作量。,1.3.2 操作系统的发展,1.3.3 推动操作系统发展的动力,硬件技术更新 应用需求扩大,1.4 操作系统的类型,5大基本类型 批处理系统 分时系统 实时系统 网络系统 分布式系统,1.4.1 批处理系统,1作业是用户定义的、由计算机完成的工作单位。它通常包括一组计算机程序、文件和对操作系统的控制语句。作业步 由作业控制语句明确标识的
6、计算机程序的执行过程,2工作流程,多道批处理系统中的作业流程,批处理系统,3.特点 多道：系统在内存中存放多个作业，并且在外存上还保存大量的后备作业。 成批：系统按批次调度作业，而在系统运行过程中不允许用户和机器之间发生交互作用。批处理系统的主要优点： 系统资源利用率高 系统吞吐量大明显缺点： 用户作业的等待时间长 没有交互能力,1.4.2 分时系统,1分时概念和分时系统的实现方法分时：广义上，是指对时间的共享。 在分时系统中，分时主要是指若干并发程序对CPU时间的共享并行：是指在同一时刻有两个或两个以上的活动发生。时间片,分时系统,2分时系统的特征和优点 基本特征 同时性 交互性 独立性 及
7、时性主要优点 人机交互友好 应用方便 资源共享,1.4.3 实时系统,1实时系统的引入实时系统 具有实时特性，能够支持实时控制系统工作的操作系统。 重要特征：对时间有严格限制和要求 三种典型应用形式 过程控制系统 信息查询系统 事务处理系统,2实时系统与分时系统的差别 交互性 实时性 可靠性,实时系统,3实现方式 硬式实时系统 对时间严格约束 软式实时系统 对时间限制稍弱一些,1.4.4 网络操作系统,1计算机网络的特征 分布性 自治性 互连性 可见性,2网络操作系统 服务器 客户机 网络操作系统实现网络通信、资源共享和保护， 以及提供网络服务和网络接口等 本地操作系统完成本地资源的管理和服务
8、功能 客户-服务器模式 Sun公司的NFSNovell公司的Netware 5.0Microsoft公司的Windows NT Server 4.0IBM公司的LAN Server 4.0SCO公司的UNIX Ware 7.1自由软件Linux,3网络操作系统的特性接口一致性 资源透明性 操作可靠性 处理自主性 执行并行性,1.4.5 分布式操作系统,分布式系统特点 透明性 灵活性 可靠性 高性能 可扩充性,1.4.6 其他操作系统,1.个人机系统 Windows XP、Windows Vista、UNIX、Linux 2.多处理器系统 对称多处理（SMP）系统 增加吞吐量 提高性能/价格比
9、提高可靠性 3嵌入式系统,1.5 操作系统的特征,（1）并发 两个或多个活动在同一给定的时间间隔中进行。（2）共享 计算机系统中的资源被多个进程所共用。（3）不确定性 系统中各种事件发生顺序的不可预测性。,1.6 操作系统结构设计,1.6.1 整体系统 任意调用，耦合紧密， 实现的效率高 结构关系不清晰， 系统的可靠性降低,模块调用示意图,1.6.2 层次式系统,THE操作系统的层次结构具有整体系统的长处新优点结构关系清晰，提高系统的可靠性、可移植性和可维护性。,1.6.3 虚拟机结构,带CMS的VM/370结构,通过共享物理机器资源来实现主要优点 同时运行多个操作系统 系统安全,有效地保护系
10、统资源 提供良好的工作环境 组建虚拟网络,1.6.4 客户-服务器系统,客户-服务器系统模型 微内核,客户-服务器系统,适于在分布式系统中应用,分布式系统中的客户-服务器模型,第2章 进程和线程,本章内容提要,进程概念 进程的状态和组成进程管理 线程 进程的同步和通信 经典进程同步问题 管程 进程通信,2.1 进程概念,2.1.1 多道程序设计 1顺序程序活动的特点 顺序性 封闭性 可再现性 2多道程序设计 程序并发执行 提高系统资源利用率 增加作业吞吐量,多道程序设计,3程序并发执行的特征 失去封闭性 程序与计算不再一一对应 并发程序在执行期间相互制约,2.1.2 进程概念,1进程概念的引入
11、 多道程序并发执行所引发的一系列新情况,2进程概念,进程最根本的属性是动态性和并发性进程定义：程序在并发环境中的执行过程进程和程序的区别 （1）动态性 （2）并发性 （3）非对应性 （4）异步性,进程概念,3进程的基本特征 （1）动态性 （2）并发性 （3）调度性,2.2 进程的状态和组成,2.2.1 进程的状态及其转换 1进程的基本状态 运行状态（Running） 就绪状态（Ready） 阻塞状态（Blocked）,进程的5种基本状态及其转换,2进程状态的转换,（1）新建就绪（2）就绪运行（3）运行阻塞（4）阻塞就绪（5）运行就绪（6）运行终止,2.2.2 进程描述,1进程映像 进程映像通常
12、就由程序、数据集合、栈和PCB等4部分组成,进程映像模型,进程描述,2进程控制块的组成进程控制块（PCB） 也称进程描述块（Process Descriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据。,进程描述,进程控制块应包含的主要内容：进程名特征信息进程状态信息调度优先权通信信息现场保护区资源需求进程实体信息族系关系其他信息,进程描述,3进程控制块的作用每个进程有惟一的进程控制块操作系统根据PCB对进程实施控制和管理进程的动态、并发等特征是利用PCB表现出来的PCB是进程存在的唯一标识,2.2.3 进程队
13、列,1线性方式,PCB线性队列示意图,进程队列,2链接方式,PCB链接队列示意图,PCB索引结构示意图,3索引方式,进程队列,2.3 进 程 管 理,2.3.1 进程图 进程图（Process Graph）是描述进程族系关系的有向树,进程创建的层次关系,2.3.2 进程创建,引发创建进程的事件：调度新作业用户登录 操作系统提供特定服务 派生新进程,进程创建,创建新进程时要执行创建进程的系统调用（如UNIX/Linux系统中的fork）其主要操作过程有如下四步： （1）申请一个空闲的PCB （2）为新进程分配资源 （3）将新进程的PCB初始化 （4）将新进程加到就绪队列中,#include #i
14、nclude #include int main(int argc,char *argv)int pid; pid = fork(); /* 创建一个子进程*/if (pid 0) /* 出现错误。进程ID号不可能小于0 */fprintf(stderr, Fork Failed); /* 输出出错消息Fork Failed */exit(-1); /* 程序终止，返回码-1*/ else if (pid = 0) /* 下面是子进程执行*/ execlp( /bin/ls, ls,NULL); /* 执行目录/bin下面的ls命令*/ else /* 下面是父进程执行*/ wait(NULL
15、); /* 父进程等待子进程完成*/ printf( Child Complete ); /* 输出子进程完成的信息*/ exit(0); /* 终止*/ ,2.3.3 进程终止,导致进程终止的三种情况： 正常终止异常终止外部干扰,进程终止,终止进程的主要操作过程如下：找到指定进程的PCB终止该进程的运行回收该进程所占用的全部资源终止其所有子孙进程，回收它们所占用的全部资源。将被终止进程的PCB从原来队列中摘走,2.3.4进程阻塞,进程阻塞的过程如下：立即停止当前进程的执行现行进程的CPU现场保存现行状态由“运行”改为“阻塞”转到进程调度程序,2.3.5 进程唤醒,唤醒原语执行过程如下：把阻塞
16、进程从相应的阻塞队列中摘下将现行状态改为就绪状态，然后把该进程插入就绪队列中如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志,2.4 线程,2.4.1 线程概念现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体线程。线程（Thread）是进程中实施调度和分派的基本单位,线程概念,1线程的组成每个线程有一个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下4个基本部分组成：一个唯一的线程标识符 一组寄存器 两个栈指针 一个私有存储区,thread结构示意图,线程的组成,线程必须在某个进程内执行一个进程可以包含一个线程或多个线程,单线程和多线程的进程
17、模型,2线程的状态运行状态就绪状态 阻塞状态终止状态,3线程的管理 线程创建 线程终止 线程等待 线程让权,4线程和进程的关系 一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。 资源分配给进程，同一进程的所有线程共享该进程的所有资源。 处理机分配给线程，即真正在处理机上运行的是线程。 线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。,5引入线程的好处 易于调度 提高并发性 开销少 利于充分发挥多处理器的功能,2.4.2线程的实现,在用户空间实现 优点：切换速度快；调度算法可专用 ；可运行在任何操作系统上 缺点：阻塞问题；多处理器
18、利用问题 在核心空间实现 优点：克服了用户级线程方式的两个主要缺陷；本身也可以是多线程的 缺点：控制转移开销大 组合方式,2.5 进程的同步和通信,进程间的相互关系主要分为如下三种形式： 互斥竞争同一资源而发生相互制约 同步协同完成一项任务 通信交换信息,2.5.1 进程的同步与互斥,1同步 同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。在协调动作的情况下，多个进程可以共同完成一项任务。,2互斥在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。它们的运行不具有时间次序的特征,互斥示例 假定进程P
19、a负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。 打印机分配表（初始情况） 打印机分配表（出错情况）,竞争条件（Race Condition） 两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。,2.5.2 临界资源和临界区,1临界资源和临界区临界资源（Critical Resource） 一次仅允许一个进程使用的共享资源临界区（Critical Section），简称CS区 在每个进程中访问临界资源的那段程序,2进程的一般结构,典型进程的一般结构,3临界区进入准则 单独进入 独占该区 限时退出 主动让权,进程A和
20、进程B互斥使用临界区的过程,2.5.3 互斥实现方式,1利用硬件方法解决进程互斥问题 禁止中断 进入临界区之后立即关闭所有的中断 专用机器指令 TSL（Test and Set Lock，即测试并上锁）的指令：TSL RX，LOCK 汇编代码示例 enter_region: TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region: MOVE LOCK,#0 RET,2原语是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomic action），即一个操作中的所有动作
21、要么全做，要么全不做。执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。,3利用软件方法解决进程互斥问题 可为每类临界区设置一把锁，该锁有打开和关闭两种状态。 关锁原语lock (W): while (W=1); W=1; 开锁原语unlock (W): w=0;,进程A lock(W);打印信息S; CS区 unlock(W);,进程B lock(W);打印信息S; CS区 unlock(W);,用锁实现进程互斥设系统中有一台打印机，有两个进程A和B都要使用它，以变量W表示锁，预先把它的值置为0。,2.5.4 信号量,1整型信号量P操作最初源于荷兰语proberen，表示测试；V操作源于
22、荷兰语verhogen，表示增加。在有些书上将P操作称做wait或者DOWN操作，将V操作称做signal或者UP操作。对信号量的操作有以下限制： 信号量可以初始化为一个非负值。 只能由P和V两个操作来访问信号量。,整型信号量,P和V操作都是原语伪代码形式 P(S) V(S) while(S0); S+; S-; 实现互斥的伪代码形式 do P(mutex); 临界区 V(mutex); 其他代码区 while(1);,信号量,2结构型信号量结构型信号量又称计数信号量，简称信号量 一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。 typede
23、f struct int value; struct PCB *list; semaphore;,结构型信号量,信号量的值与相应资源的使用情况有关信号量的一般结构及PCB队列,对信号量的操作有如下严格限制：信号量可以赋初值，且初值为非负数。 在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。,结构型信号量,P、V操作的定义 void P(semaphore S) void V(semaphore S) S.value-; S.value+； if(S.value0) if (S.value=0) 把这个进程加到S.list队列； 从S.list队
24、列中移走进程Q； block( )； wakeup(Q)； 在具体实现时应注意，P, V操作都应作为一个整体实施，不允许分割或相互穿插执行,结构型信号量,结构型 信号量3二值信号量 一种特例，它的值只能在0和1之间选择,typedef struct enumfalse,truevalue; /*枚举量*/ struct PCB *list;B_semaphore;void P_B(B_semaphore S) if (S.value=true) S.value=false; else 把该进程放入S.list队列; block( ); ,void V_B(B_semaphore S) if(S
25、.list=NULL) S.value=true; else 从S.list队列中移走进程Q; wakeup(Q); ,2.5.5 信号量的一般应用,1用信号量实现进程互斥 打印机分配表的互斥使用 Pa: Pb: P(mutex) P(mutex) 分配打印机 释放打印机 （读写分配表） （读写分配表） V(mutex) V(mutex) ,用信号量实现进程互斥,利用信号量实现互斥的一般模型是： 进程P1 进程P2 进程Pn P(mutex); P(mutex); P(mutex); 临界区 临界区 临界区 V(mutex); V(mutex); V(mutex); ,用信号量实现进程互斥,注
26、意点： 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。 互斥信号量mutex的初值一般为1。,2用信号量实现进程简单同步 对缓冲区的同步使用问题,简单供者和用者对缓冲区的使用关系,用信号量实现进程简单同步,供者和用者间要交换两个消息： 缓冲区空 缓冲区满设置两个信号量： S1表示缓冲区是否空（0表示不空，1表示空）。 S2表示缓冲区是否满（0表示不满，1表示满）。 规定S1和S2的初值分别为1和0,用信号量实现进程简单同步,供者进程 用者进程 L1: P(S1) L2: 启动读卡机 P(S2) ; 从缓冲区取出信息 收到输入
27、结束中断 V(S1); V(S2); 加工并且存盘 goto L1; goto L2;,用信号量实现进程简单同步,用P和V操作实现同步时应注意如下三点： 分析进程间的制约关系，确定信号量种类。 信号量的初值与相应资源的数量有关，也与P, V操作在程序代码中出现的位置有关。 同一信号量的P, V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。,2.6 经典进程同步问题,1生产者-消费者问题生产者:能产生并释放资源的进程消费者:单纯使用（消耗）资源的进程问题表述 一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产品）送入缓冲
28、区，消费者进程从中取出产品。 假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池。,生产者-消费者问题,生产者-消费者问题环形缓冲池,它们应满足如下同步条件： 任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）。 所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。,生产者-消费者问题,设缓冲区的编号为0N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。设置三个信号量： full：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任
29、何时候只有一个进程使用缓冲区。,生产者-消费者问题,生产者进程Producer： 消费者进程Consumer： while(TRUE) while(TRUE) P(empty); P(full); P(mutex); P(mutex); 产品送往buffer(in); 从buffer(out)中取出产品； in=(in+1)mod N; out=(out+1)mod N; /*以N为模*/ /*以N为模*/ V(mutex); V(mutex); V(full); V(empty); ,2读者-写者问题 读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大
30、型数据库，很多竞争进程要对它进行读、写。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即修改）数据库，那么就不允许其他进程访问它 既不允许写，也不允许读。,读者-写者问题,信号量设置： 读互斥信号量rmutex 初值为1 写互斥信号量wmutex 初值为1 rmutex：读者互斥地访问readcount wmutex：保证一个写者与其他读者/写者互斥地访问共享资源,读计数器readcount，整型变量，初值为0。,读者-写者问题,读者Readers while(TRUE) P(rmutex); readcount=readcount+1; if(readcount=1) P(wm
31、utex); V(rmutex); 执行读操作 P(rmutex); readcount=readcount-1; if(readcount=0) V(wmutex); V(rmutex); 使用读取的数据 ,写者Writers while(TRUE) P(wmutex); 执行写操作 V(wmutex); ,这个算法隐含读者的优先级高于写者,3哲学家进餐问题五位哲学家围坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。每位哲学家在用两根筷子夹面条吃饭前独自进行思考，感到饥饿时便试图占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进
32、餐；餐毕，要把筷子放回原处并继续思考问题。,哲学家进餐问题,哲学家进餐问题,=#define N 5#define LEFT (i-1)%N#define RIGHT (i+1)%N#define THINKING 0#define HUNGRY 1#define EATING 2 typedef struct /* 定义结构型信号量 */ int value; struct PCB *list; semaphore; int stateN; semaphore mutex=1; /* 互斥进入临界区 */ semaphore sN; /* 每位哲学家一个信号量 */,哲学家进餐问题,void
33、 philosopher(int i) while(TRUE) think(); /* 哲学家在思考问题 */ take_chopstick(i); /* 拿到两根筷子或者等待 */ eat(); /* 进餐 */ put_chopstick(i); /* 把筷子放回原处 */ void take_chopstick(int i) P(mutex); statei=HUNGRY; test(i); /* 试图拿两根筷子 */ V(mutex); P(si);,哲学家进餐问题,void put_chopstick(int i) P(mutex); statei=THINKING; test(LE
34、FT); /* 查看左邻，现在能否进餐 */ test(RIGHT); /* 查看右邻，现在能否进餐 */ V(mutex); void test(int i) if(statei=HUNGRY =,打瞌睡的理发师,4打瞌睡的理发师问题理发店有一名理发师，一把理发椅和几把座椅，等待理发者可坐在上面。如果没有顾客到来，理发师就坐在理发椅上打盹。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，该顾客就坐在椅子上排队；如果满座了，他就离开这个理发店，到别处去理发。,打瞌睡的理发师问题,理发师和每位顾客都分别是一个进程 =#define CHAIRS 5typedef struct int value; struct PCB *list; semaphore;semaphore customers=0;semaphore barbers=0;semaphore mutex=1;int waiting=0;,void barber(void) while(TRUE) P(customers); /*如果没有顾客，则理发师打瞌睡*/ P(mutex); /*互斥进入临界区*/ waiting-; V(barbers); /*一个理发师准备理发*/ V(mutex); /*退出临界区*/ cut_hair(); /*理发（在临界区之外）*/ ,
