计算机操作系统课件.ppt

计算机操作系统,南京工业大学信息学院计算机系,2,总 目 录,第1章 操作系统引论 第2章 进程管理 第3章 处理机调度与死锁 第4章 存储器管理 第5章 设备管理 第6章 文件管理 第7章 操作系统接口,3,课内上机实验,进程的创建 线程的创建 进程同步 进程通信 进程调度 银行家算法 页面置换算法的模拟 磁盘I/O 命令解释程序,【说明】以上9个上机实验，共计22学时(包括2个进阶要求的4学时)，可以选择其中的4次实验(共8学时)作为课内上机实验任务。,第1次实验(进程管理),第4次实验(操作系统接口),第3次实验,(存储器管理) (设备管理),(4选1),(2选1),(2选1),4,第1章 操作系统引论,1.1 OS的目标和作用 1.2 OS的发展过程 1.3 操作系统的基本特征 1.4 操作系统的主要功能 1.5 操作系统的结构设计 第1章复习题,5,1.1.1 OS的目标,有效性 方便性 可扩展性 开放性,操作系统（Operating System , OS）是计算机硬件上的第一层软件，是计算机必须配置的最基本、最重要的系统软件。,1.1 OS的目标和作用,6,1有效性(早期OS的主要目标) 有效提高CPU和I/O设备利用率 提高的方法：合理地组织计算机的工作流程 2方便性(现在OS越来越重视方便性) 可使计算机系统更容易使用(解释之),方便性和有效性是设计OS的两个最重要的目标,7,3可扩展性,计算机硬件和体系结构的发展，对OS提出了更高的功能和性能要求 计算机网络，特别是Internet的发展，也对OS提出了一系列更高的要求,为什么要有可扩充性？ 因为：,OS为了能适应发展的要求，须具有良好的可扩充性。,如何才有可扩充性？ 应采用新的OS结构，如微内核结构和客户服务器模式。,8,4开放性 为什么要有开放性？ 计算机网络，特别是LAN的迅速发展，使OS的应用环境由单机转向网络环境。为使不同厂家的计算机和设备能通过网络加以集成化，并能正确、有效地协同工作，实现应用的可移植性和互操作性，必须具有统一的开放环境，进而要求OS具有开放性。 什么是开放性？ 开放性是指系统能遵循世界标准规范，特别是遵循开放系统互连（OSI）国际标准。,9,从用户观点看，OS是用户和计算机硬件系统之间的接口 从资源管理观点看，OS是计算机系统资源（软、硬）的管理者,1.1.2 OS的作用,1OS作为用户和计算机硬件系统的接口 2OS作为计算机资源的管理者 3OS实现了对计算机资源的抽象,操作系统的作用:,10,1.OS作为用户和计算机硬件系统的接口(用户接口),用户可以通过三种方式使用计算机：,命令方式（键盘命令） 图标、窗口方式（GUI） 系统调用方式（程序接口）,操作接口,1.1.2 OS的作用,11,计算机系统资源可归结为四类：处理器、存储器、I/O设备、信息（数据和程序） OS的主要功能也正是针对这四类资源进行有效管理：,2. OS作为计算机资源的管理者,处理机管理：分配和控制处理机 存储器管理：主要是内存分配和回收 I/O设备管理：I/O设备的分配与操纵 文件管理：文件的存取、共享和保护,12,完全无软件的计算机裸机。 “裸机”难于使用。 裸机覆盖了一层I/O设备管理软件如图1-2所示，由它来实现对I/O设备操作的细节，并向上提供一组I/O操作命令，如Read和Write命令，用户可以利用它进行数据输入/输出，而无需关心I/O实现的细节。此时用户所看到的是一台功能显著增强、使用极为方便的的机器，它向上提供了一组抽象的I/O设备，称为扩充机或虚拟机。,3. OS实现了对计算机资源的抽象,虚拟性是OS的基本特征之一,第一层软件,第二层软件,13,为了方便用户使用文件系统，又在第一层软件上再覆盖一层用于文件的管理软件，用它来实现对文件操作的细节，并向上提供一组对文件进行存取操作的命令。第二个层次的抽象。 又在文件管理软件上再覆盖一层面向用户的窗口软件，用户便可在窗口环境下方便地使用计算机，形成一台功能更强的虚拟机。 由此可知，操作系统是铺设在硬件上的多层系统软件，它们不仅增强了系统功能，而且还隐藏了对硬件操作的细节，由它们实现对计算机硬件的多个层次的抽象。,14,1.1.3 推动OS发展的主要动力,1不断提高计算机资源利用率。,2方便用户: 继续发展的因素分时系统（或称多用户系统）,3器件的不断更新换代,4计算机体系结构的不断发展,最初发展的动力。批处理系统,8位机16位机32位机64位机(8位OS 16位OS . ),单机系统多处理机系统：单机OS多处理机OS 计算机网络：网络OS,15,1.2 OS的发展过程,20世纪50年代中期，第一个简单的批处理系统 60年代中期，多道程序批处理系统，随后出现分时系统 上世纪80年代开始至21世纪初，微型机、多处理机、计算机网络大发展年代微机OS、多处理机OS和网络OS的形成和大发展年代。,16,1.2.1 无OS的计算机系统,人工操作方式 脱机输入/输出（Off-Line I/O）方式 （20世纪50年代末 ）,这一时期有两种操作方式：,17,1人工操作方式,程序员将事先已穿孔（对应于程序和数据）的纸带（或卡片）装入纸带输入机（或卡片输入机）； 再启动输入机将程序和数据输入计算机； 然后启动计算机运行。 当程序运行完毕并取走计算结果后，才让下一个用户上机。,缺点：,用户独占全机； CPU等待人工操作,18,2脱机输入/输出方式,优点：,（1）减少了CPU的空闲时间 （2）提高了I/O速度,19,1.2.2 单道批处理系统,把一批作业以脱机方式输入到磁带上； 在监督程序（Monitor）控制下使这批作业 一个接一个地连续处理。 参看下页的图1-3,它是OS的前身，而非现在人们理解的OS。,1. 单道批处理系统的处理过程,20,开始,还有下一个作业？,停止,把下一个作业的源程序转换为目标程序,源程序有错吗？,装配目标程序,目标程序运行 直到结束,否,是,是,否,图1-3 单道批处理系统的处理流程,21,2. 单道批处理系统的特征,(1) 自动性,在磁带上的作业能自动地逐个地依次运行，而无需人工干预。,(2) 顺序性,(3) 单道性,磁带上的各道作业是顺序地进入内存，各道作业的完成顺序与它们进入内存的顺序相同，即先调入内存的作业先完成。,在内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。,22,1.2.3 多道批处理系统,多道程序设计的基本概念,20世纪60年代中期,用户提交的作业事先存放在外存上，形成“后备队列” 作业调度程序按一定算法从后备队列中选择若干作业调入内存，使它们共享CPU和系统中的各种资源。,好处：,（1）提高CPU利用率 （2）提高内存和I/O设备利用率 （3）增加系统吞吐量,23,多道批处理系统的特征,(1) 多道性：,多道程序在内存中并发执行。提高了资源利用率和系统吞吐量。,(2) 无序性：,先进入内存的作业可能后完成；后进入内存的作业可能先完成。,(3) 调度性：,作业从提交到完成，需经过两种调度：作业调度和进程调度。,24,多道批处理系统的优缺点：,（1）资源利用率高。(CPU、内存、I/O设备利用率),（2）系统吞吐量大。,（3）周转时间长。,（4）无交互能力。,系统吞吐量是指系统在单位时间内所完成的总工作量。,作业周转时间是指从作业进入系统（提交）开始，直至它完成并退出系统为止所经历的时间。,对修改和调试程序极不方便。,25,多道批处理系统需要解决的问题,（1）处理机管理问题(处理机分配、提高利用率) （2）内存管理问题(分配、保护等) （3）I/O设备管理问题(方便用户、提高利用率) （4）文件管理问题(方便用户、数据安全一致) （5）作业管理问题(计算型、I/O型不同处理),26,1.2.4 分时系统,分时系统是指在一台主机上连接多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。,27,1. 分时系统的产生,是为了满足用户的以下需求而产生的：,（1）人-机交互 （2）共享主机 （3）便于用户上机,28,2分时系统实现中的关键问题,（1）及时接收 （2）及时处理,用户作业不能先进入磁盘，然后再调入内存 不允许一个作业长期占用处理机，直至它运行结束或出现I/O请求后，方才调度其它作业运行 应该规定每个作业只运行一个很短的时间（称为时间片）,要做到上述两条，必须彻底改变批处理系统的运行方式，即：,29,3分时系统的特征,（1）多路性：,允许一台主机上同时联接多个联机终端,（2）独立性：,每个用户各占一个终端，彼此独立操作，互不干扰。,（3）及时性：,用户的请求能在很短时间内获得响应。,（4）交互性：,用户可通过终端与系统进行广泛的对话。,30,1.2.5 实时系统,实时系统（Real-Time System） 是指系统能及时响应外部事件的请求，在规定时间内完成该事件的处理，并控制所有实时任务协调一致地运行。,定义：,31,1应用需求,（1）实时控制。,飞机或火车的订票系统、情报检索系统等 。,（2）实时信息处理。,实时数据采集处理；执行机构；自动控制,32,2实时任务,在实时系统中必然存在着若干个实时任务，这些实时任务通常与某个（某些）外部设备相关，能反映或控制相应的外部设备，因而带有某种程度的紧迫性。,周期性实时任务,按指定周期循环执行，以便周期性地控制某外部设备。,非周期性实时任务,外部设备发出的激励信号无明显周期性，但都必须联系着一个截止时间。,开始截止时间任务在某时间以前必须开始执行 完成截止时间任务在某时间以前必须完成,分类：按执行是否周期性划分,33,分类：实时任务按对截止时间要求划分,硬实时任务,软实时任务,系统必须满足任务对截止时间的要求，否则可能出现难于预测的结果。,它也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。,34,3实时系统与分时系统特征的比较,（1）多路性：,实时系统的多路性主要表现在：系统经常对多路的现场信息进行采集，以及对多个对象或多个执行机构进行控制。,（2）独立性：,实时系统中对信息的采集和对对象的控制，也都是彼此互不干扰,（3）及时性：,实时系统的及时性，是以控制对象所要求的开始截止时间或完成截止时间来确定的。一般为秒级、百毫秒级直至毫秒级，甚至有的要低于100微秒。,（4）交互性：,实时系统的交互性仅限于访问系统中某些特定的专用服务程序，不象分时系统那样能向终端用户提供数据处理服务、资源共享等服务。,（5）可靠性：,实时系统要求系统高度可靠，往往采用多级容错措施来保证系统的安全性及数据的安全性。,35,1.2.6 微机操作系统的发展,1单用户单任务操作系统,CP/M 上世纪70年代(8位机) MS-DOS 上世纪80年代(16位机/32位机),2单用户多任务操作系统,Windows 95 Windows 98 Windows XP Windows NT,兼容16位应用程序的32位操作系统,36,3多用户多任务操作系统,UNIX OS(AT&T的Bell实验室) Solaris OS(SUN公司) Linux OS(UNIX重要变种，芬兰学生；集体开发),37,操作系统的定义,操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。,无统一的定义,38,1.3 操作系统的基本特征,1.3.1 并发（Concurrence）,OS最重要的特征，其它三个特征都以并发为前提的。,并行与并发：,并行性两个或多个事件在同一时刻发生。,并发性两个或多个事件在同一时间间隔内发生。,在多道程序环境下，并发性是指在一段时间内，宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却只能有一道程序执行，故微观上这些程序只能是分时地交替执行。若计算机系统中有多个处理机，则这些可以并发执行的程序可被分配到多个处理机上，实现并行执行。,39,与并发紧密相连的概念进程,通常的程序是静态实体，它是不能并发执行的。为了使程序能并发执行，系统必须分别为每个程序建立进程（Process）。,进程是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个活动实体。,多个进程之间可以并发执行和交换信息。,40,在OS中引入进程的目的，是使多个程序能并发执行。 进程和并发是现代OS中最重要的基本概念，也是OS运行的基础。 直到80年代中期，人们才提出了比进程更小的单位 线程（Threads）。 一个进程通常包含若干线程。 近年来推出的OS 都引入了线程。,关于进程、线程的初步概念：,41,1.3.2 共享（sharing）,共享是指系统中的资源可供内存中多个并发执行的进程（线程）共同使用。,目前主要有以下两种资源共享方式：,（1）互斥共享方式,对于临界资源，要求被互斥地共享。,什么叫临界资源？ 临界资源例子。,（2）同时访问方式,对于共享资源,允许在一段时间内由多个进程“同时”对它进行访问。这里所说的“同时”往往是宏观上的，而微观上，这些进程可能是交替地对该资源进行访问。,共享资源,42,资源的共享是以进程的并发执行为条件的，若系统不允许程序并发执行，自然不存在资源共享问题； 若系统不能对资源共享实施有效管理，协调好诸进程对共享资源的访问，也必然影响到程序并发执行的程度，甚至根本无法并发执行。,并发和共享是操作系统的两个最基本的特征，它们是互为存在条件的。,43,1.3.3. 虚拟（Virtual）,虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。,OS中利用了两种方式实现虚拟技术，即时分复用技术和空分复用技术，分别用来实现虚拟处理机、虚拟内存、虚拟外部设备和虚拟信道等。,44,1. 时分复用技术,时分复用技术最早用于电信行业，它将一条物理信道虚拟为多条逻辑信道，将每条逻辑信道供一对用户通话。操作系统中利用时分复用技术来实现虚拟处理机、虚拟设备等，以提高资源利用率。 1) 虚拟处理机技术 利用多道程序设计技术，为每道程序建立一个进程，让多道程序并发地执行，以此来分时使用一台处理机。此时，虽然系统中只有一台处理机，但它能同时为多个用户服务，使每个终端用户都认为有一台处理机在专门为他服务，亦即把一台物理上的CPU虚拟为多台逻辑上的CPU，也称为虚拟处理机。,45,通过虚拟设备技术，将一台物理I/O设备虚拟为多台逻辑上的I/O设备，允许每个用户占用一台逻辑上的I/O设备，这样便可使原来在一段时间仅允许一个用户访问的设备（即临界资源），变为在一段时间内允许多个用户同时访问的共享设备。例如，虚拟打印机。,2) 虚拟设备技术,46,2. 空分复用技术,上世纪初，电信业中就利用频分复用技术来提高信道的利用率。计算机中使用空分复用技术来提高存储空间的利用率。,1) 虚拟磁盘技术,通过虚拟磁盘技术，将一台硬盘虚拟成多台虚拟磁盘，这样使用起来方便、安全。虚拟磁盘技术采用了空分复用技术，它将硬盘划分成几个卷，再通过安装程序将它们分别安装在C、D、E .逻辑驱动器上。磁盘分区,47,2) 虚拟存储器技术,在单道程序环境下，内存会有很多空闲空间，空分复用则是利用存储器的空闲空间来存放其它程序，以提高内存利用率。 单纯的空分复用存储器只能提高内存的利用率，不能实现在逻辑上扩大存储器容量的功能，必须引入虚拟存储技术才能达到此目的。虚拟存储器技术在本质上就是使内存时分复用和空分复用。该技术将一道程序划分成若干部分，物理内存也划分成多个部分，通过“请求调入功能”和“置换功能”，每次只把用户程序的一部分调入内存运行，这样便实现了用户程序各个部分分时进入内存运行的功能，从而在逻辑上扩充存储器的容量。,48,4 异步性（Asynchronism）,由于资源等因素的限制，使进程的执行通常不是“一气呵成”，而是以“停停等等”的方式运行。 内存中的每个进程在何时能获得处理机运行，何时又因提出某种资源请求而暂停，以及进程以怎样的速度向前推进，每道程序总共需要多少时间才能完成等等，都是不可预知的。很可能是先进入内存的作业后完成，而后进入内存的作业先完成，或者说，进程是以人们不可预知的速度向前推进，此即进程的异步性。,49,1.4 操作系统的主要功能,处理机管理功能 存储器管理功能 设备管理功能 文件管理功能 用户接口,50,处理机管理功能,在传统的多道程序设计系统中，处理机的分配和运行，都是以进为基本单位的，因而对处理机的管理，可以归结为对进程的管理。 在引入线程的OS中，还包含对线程的管理。,也可称为进程管理,51,处理机管理的主要功能是：,创建和撤消进程（线程）,对诸进程（线程）的运行进行协调,实现进程（线程）之间的信息交换,按照一定的算法把处理机分配给进程（线程）,进程控制,进程同步,进程通信,进程调度(处理机调度),52,存储器管理,存储器管理应具有以下功能：,内存分配 (静态 、动态分配方式 ) 内存保护 (硬件检查越界，软件处理) 地址映射 (逻辑、物理地址，硬件支持) 内存扩充 (虚拟存储技术),53,主要任务： l 完成进程提出的I/O请求； l为用户进程分配其所需的I/O设备； l 提高CPU和I/O设备的利用率； l 提高I/O速度； l方便用户使用I/O设备。,设备管理功能,54,设备管理应具有以下功能：,缓冲管理在设备和CPU之间引入缓冲，可有效地缓和CPU和I/O设备速度不匹配的矛盾，提高CPU的利用率，进而提高系统的吞吐量。 设备分配按某种策略将设备分配给用户进程。需设备控制表等数据结构。 设备处理设备处理程序又称为设备驱动程序。基本任务是实现CPU与设备控制器通信：CPU 发I/O命令；设备控制器发中断请求。,55,主要任务： 对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性。 文件管理应具有以下功能： 1文件存储空间的管理 2目录管理 3文件的读/写管理和保护,4. 文件管理,56,命令接口(联机命令、脱机命令) 程序接口(系统调用) 图形接口(GUI),5. 用户接口,57,1.5 操作系统的结构设计,OS的结构经历了四代变革：,第一代的OS是无结构的 第二代OS采用了模块式结构 第三代OS是层次式结构,传统的操作系统结构,第四代OS采用微内核结构,20世纪80年代后期,58,微内核OS结构现代OS结构,微内核结构能有效地支持多处理机运行，故非常使用于分布式系统环境。 Windows NT采用微内核结构。,在与微内核技术发展的同时，客户/服务器技术、面向对象技术也在迅速发展，把它们应用到基于微内核结构的OS中，便具有了以微内核为OS核心，以客户/服务器为基础，并且采用了面向对象的程序设计方法的特征。,59,微内核技术,微内核技术是指精心设计的、能实现现代OS核心功能的小型内核。,OS的变庞大，使对OS的开发、维护和移植变得十分困难。 为了减少OS的复杂性，增加OS的可扩展性和可维护性而产生了微内核技术。,产生背景,60,1. 微内核操作系统的基本概念,1）足够小的内核,微内核是指精心设计的、能实现现代OS最基本的核心功能的部分。,2）基于客户/服务器模式,把OS的最基本部分放在内核中，把OS的绝大部分功能放在内核外面的一组服务器(进程)中实现。,61,62,3）应用“机制与策略分离”原理,所谓机制，是指实现某一功能的具体执行机构。 策略是在机制基础上，借助于某些参数和算法来实现该功能的优化，或达到不同的功能目标。 机制处于系统的低层，而策略处于系统的高层。 传统OS将机制放在内核低层，策略放在内核高层。 微内核OS将机制放在微内核中，策略放在微内核外。,4）采用面向对象技术,63,2. 微内核的基本功能,1）进程（线程）管理,进程队列属于调度功能的机制部分，放在微内核中；确定、修改优先级，属于策略问题，放在进程管理服务器中。 进程(线程)通信、进程切换、线程调度、多处理机之间的同步等功能也放在微内核中。,2）低级存储管理,页表机制和地址变换机制在微内核中；实现虚存的策略，包括页面置换算法、内存分配回收策略等放在存储器服务器中。,64,3）中断和陷入处理,大多数微内核操作系统都将与硬件紧密相关的一小部分放入微内核中处理。此时，微内核的主要功能，是捕获所发生的中断和陷入事件，并进行相应的前期处理。如进行中断现场保护，识别中断或陷入类型，然后将有关事件的信息转换成消息后，发送给相应的服务器作中断后期处理。,65,3. 微内核的优点,1）提高了系统的可扩展性,2）增强了系统的可靠性,3）可移植性,4）提供了对分布式系统的支持,5）融入了面向对象技术,66,4. 微内核操作系统存在的问题,微内核OS的运行效率有所降低。 原因是：在完成一次客户对OS提出的服务请求时，需要利用消息实现多次交互和进行用户/内核模式及上下文的多次切换。 解决的办法： 重新将一些常用的操作系统基本功能，有服务器移入微内核中。,67,第1章复习题,1计算机操作系统的功能是 。 A. 把源程序代码转换为目标代码 B. 实现计算机用户之间的相互交流 C. 完成计算机硬件与软件之间的转换 D. 控制、管理计算机系统的资源和程序的执行 2_不是分时系统的特点。 A多个用户是经过网络连接，同时使用计算机系统 B各用户可同时请求系统服务 C各用户的请求彼此独立，互不干扰 D用户以会话方式控制自己的程序运行,D,A,68,3分时操作系统的主要目的是 。 A计算机系统的交互性 B计算机系统的实时性 C计算机系统的可靠性 D提高软件的运行速度 4以下描述与操作系统无关的是 。 A. 方便用户的程序集合 B. 控制和管理计算机系统的硬件和软件资源 C. 计算机系统的硬件和软件资源的集合 D. 合理地组织计算机工作流程,A,C,69,5分时操作系统的特点是 。 交互性、同时性、独立性、及时性 可靠性、交互性、独立性、及时性 C. 可靠性、实时性、独立性、及时性 D. 交互性、同时性、独立性、实时性 6下列各项中， 不是现代操作系统的主要特征。 并发性 B. 共享性 C. 确定性 D. 虚拟性 7在下列操作系统中，对响应时间要求最高的是 。 A批处理系统 B. 分时系统 C. 实时系统 D. 网络操作系统,A,C,C,70,8对出现的中断事件是由 进行处理的。 A. 硬件 B. 操作系统 C. 用户程序 D. 解释程序 9. 多道批处理系统的主要缺点是 。 A. CPU利用率低 B. 不能并发执行 C. 缺少交互性 D. 以上都不是 10操作系统是对 进行管理的软件。 A系统软件 B系统硬件 C计算机资源 D计算机程序,C,C,C,71,11设计实时操作系统时，首先要考虑系统的 。 A实时性和可靠性 B实时性和灵活性 C灵活性和可靠性 D灵活性和可移植性 12. UNIX操作系统是一种多用户的、人机交互的 。 A. 多道批处理系统 B. 实时系统 C. 分时系统 D. 分布式系统 13操作系统在计算机系统中处于 之间的位置。 A计算机硬件和软件 B计算机硬件和用户 C处理机和用户 D外部设备和处理机,A,C,B,72,14操作系统提供给用户程序的接口是 。 A命令解释程序 B系统调用 CP、V操作 D对话框 15分时系统响应时间与 有关。 A每个应用进程分配的时间片长度 B进程大小 C就绪进程数目 D就绪进程数目和时间片长度 16在操作系统中， 部分属于微内核。 A作业调度软件 B用户命令解释程序 C磁盘文件目录管理软件 D进程通信服务例程,返回总目录,B,D,D,73,第2章 进程管理,2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程同步问题 2.5 管程机制 实现互斥的软件机制和硬件机制(补充) 2.6 进程通信 2.7 线程 第一次课内上机实验,74,2.1 进程的基本概念,程序的顺序执行及其特征 程序的并发执行及其特征 进程的特征与状态 进程控制块,75,2.1.1 程序的顺序执行及其特征,顺序执行包含两层含义：,在单道批处理系统中，对于多个用户程序来说，所有程序是依次执行的。(外部顺序性) 对于一个程序来说，在若干个程序段之间，必须按照某种先后次序顺序执行；对同一个程序段中的多条指令，也是按某种顺序执行的。(内部顺序性),程序的顺序执行主要是指第一种，即各个程序依次执行。,76,程序顺序执行的特征,（1）顺序性：,处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束（或者说下一操作必须在当前操作结束后才能开始）。,（2）封闭性：,程序是在封闭的环境下执行的。即,（3）可再现性：,只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。,程序运行时独占全机资源，资源的状态（除初始态外）只有本程序才能改变它。 程序一旦开始执行, 其执行结果不受外界影响。,77,程序的并发执行包括两层含义：,对于一个程序来说，它的所有指令是按序执行的。（内部顺序性） 对于多个执行中的程序(进程)来说，所有进程是交叉执行的。(外部并发性),2.1.3 程序的并发执行及其特征,78,1）间断性:,程序在并发执行时，由于它们共享系统资源，以及为完成同一任务而相互合作，致使这些并发执行的程序之间形成了相互制约的关系。（互斥关系、同步关系）,相互制约导致并发执行的程序具有“执行暂停执行”这种间断性活动规律。,2）失去封闭性：,程序在并发执行时，由于多个程序共享系统资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。,某程序的执行时，会受到其他程序的影响。,程序并发执行的特征,79,3）不可再现性与时间有关的错误,程序在并发执行时，由于失去了封闭性，也将导致其失去可再现性。 例如：有两个循环程序A和B，它们共享一个变量N,L1：N = N+1； goto L1；,L2：print (N)； N = 0； goto L2；,程序A,程序B,程序A和B并发执行时，可能出现下述三种情况(设当前N的值为10)： (1) N=N+1在print(N)和N=0之前，此时得到的N值分别为11,11,0。 (2) N=N+1在print(N)和N=0之后，此时得到的N值分别为10,0,1。 (3) N=N+1在print(N)和N=0之间，此时得到的N值分别为10,11,0。,上述三种情况中，(1)、(2)结果正确，(3)结果出错。可见计算结果已与并发程序的执行速度(推进速度)有关，从而使程序执行失去了可再现性。,80,2.1.4 进程的特征与状态,1进程的定义和特征,进程是程序在一个数据集上的运行过程，是系统进行资源分配和调度的一个独立单位。 (传统OS中对进程的定义),定义,1）结构特征：,程序段、相关的数据段、PCB三部分构成了进程实体。,2）动态性：,进程的实质是进程实体的一次执行过程，故动态性是进程的最基本特征。,进程的特征：,81,4）独立性 ：,在传统的OS中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。,5）异步性 ：,是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。,3）并发性：,这是指多个进程实体同存于内存中，且能在一段时间内同时运行。,82,2. 进程的三种基本状态,1）就绪（Ready）状态：,当进程已分配到除CPU以外的所有资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。,2）执行（Running）状态:,进程已获得CPU，其程序正在执行。,3）阻塞（Blocked）状态:,正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态（或等待状态）。,83,进程的三种基本状态的转换：,进程调度：就绪态执行态 时间片完：执行态就绪态 请求I/O：执行态阻塞态 I/O完成：阻塞态就绪态,引起进程状态转换的典型事件：,84,挂起状态：,有些系统除了进程的三种基本状态外，还有挂起状态。,1）引入挂起状态的原因：,（1）终端用户的请求：,（2）父进程请求：,（3）负荷调节的需要 ：,（4）操作系统的需要 ：,当终端用户在自己的程序运行期间发现有可疑问题时，希望暂停执行。,希望考察和修改子进程，或协调各子进程间的活动时,实时系统中工作负荷较重时，系统可把一些不重要的进程挂起。,操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。,85,2）具有挂起状态系统的进程状态的转换,活动就绪静止就绪,活动阻塞静止阻塞,静止就绪活动就绪,静止阻塞活动阻塞,挂起原语Suspend,激活原语Active,86,为了描述和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块。 进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。,1. PCB作用：,使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发进程进行控制和管理的。,例如：进程调度；现场保护和恢复；进程同步和通信。,PCB是进程存在的唯一标志,2.1.5 进程控制块（PCB）,87,2进程控制块中的信息,PCB中记录了操作系统所需的、用于描述进程当前情况以及控制进程运行的全部信息。具体包括下述四方面的信息：,1）进程标识符：,内部标识符(进程号)；外部标识符(名)； 父进程标识及子进程标识；用户标识,2）处理机状态：,处理机状态信息主要由处理机的各种寄存器中的内容组成的。寄存器包括：通用寄存器、指令计数器、程序状态字（PSW）寄存器、用户栈指针。(保护、恢复现场),当处理机被中断时，这些信息都必须保存到PCB中，以便该进程重新执行时，能从断点继续执行。,88,3）进程调度信息：,在PCB中还存放一些与进程调度和进程对换有关的信息。包括：,进程状态作为调度和对换时的依据。 进程优先级由于描述进程使用处理机的优先级别的一个整数，优先级高的进程优先获得处理机。 进程调度所需的其它信息它们与所采用的进程调度算法有关。 事件即阻塞原因。,89,4）进程控制信息：,程序和数据的地址指程序和数据所在的内存或外存首地址； 进程同步和通信机制如信号量、消息队列指针等，它们可能全部或部分地存放在PCB中； 资源清单是一张列出了除CPU外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链接指针它给出本进程（PCB）所在队列中下一个进程的PCB的首址。,90,3进程控制块的组织方式,常用的组织方式有两种：链接方式和索引方式。,1）链接方式,把具有同一状态的PCB，用其中的链接字链接成一个队列。形成：就绪队列、阻塞队列、空白队列等,91,2）索引方式:,系统根据所有进程的状态建立几张索引表。如， 就绪索引表 阻塞索引表等,索引表的首址记录在专用单元中； 每个索引表的表目中，记录具有相应状态的某个PCB的首址。,92,2.2 进程控制,进程控制是进程管理中最基本的功能。 进程控制包括： 创建进程 终止进程 进程状态转换,进程控制是由OS的内核完成的。,93,2.2.1 进程的创建,1引起创建进程的事件,用户登录 作业调度 提供服务,当用户进程提出某种请求后，系统将专门创建一个进程来提供用户所需的服务。如，文件打印。,上述三种情况，都是由系统内核为它创建一个新进程。,应用请求：,是基于应用进程的需求，由应用进程自己创建一个新进程，以便新进程以并发运行方式完成特定任务。,94,2进程的创建,调用进程创建原语Create（），按下述步骤创建一个进程：,（1）申请空白PCB； （2）为新进程分配资源。主要是内存空间。 （3）初始化PCB。包括：,初始化标识信息 初始化处理机状态信息：,程序计数器，堆栈指针等,进程状态就绪或静止就绪、优先级等。,初始化处理机控制信息：,（4）将新进程插入就绪队列。,Win32中创建进程的API函数是CreateProcess( )；创建线程的API是CreateThread( )函数。详见“OS课内上机实验使用的相关API函数介绍.doc”或MSDN。,95,1引起进程终止的事件,正常结束,外界干预,越界错误 保护错试图访问不允许访问的资源或文件，或者以不适当方式访问 非法指令 特权指令错用户程序试图执行只允许OS执行的指令 运行超时 等待超时 算术运算错被0除 I/O故障, 操作员或操作系统干 预（如发生死锁） 父进程请求 父进程终止,2.2.2 进程的终止,异常结束 常见的异常 结束事件,96,2进程的终止过程,OS调用终止原语，按下述过程终止进程：,根据被终止进程的标识，从PCB集合中找除该进程的PCB，读出该进程状态。 若被终止进程正处于执行状态，应立即终止其执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。若该进程还有子孙进程，应将其所有子孙进程终止，以防止它们成为不可控进程。 将被终止进程的所有资源，或者归还给其父进程，或者归还给系统。 将被终止进程（它的PCB）从所在队列中移出，等待其他进程来搜索信息。,Win32中终止进程的API函数是TerminateProcess( )；终止线程的API函数是TerminateThread( )。详见“OS课内上机实验使用的相关API函数介绍.doc”,97,2.2.3 进程的阻塞和唤醒,1引起进程阻塞和唤醒的事件,请求系统服务,无新工作可做,当执行进程请求OS服务时，由于某种原因，OS并不立即满足该进程的请求时，该进程只能转变为阻塞状态来等待。 如，进程请求打印机，,系统往往设置一些具有特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。 如，系统中发送数据的进程，,启动某种操作,当进程启动某种操作后，如果该进程必须在该操作完成后才能继续执行，则必须先使该进程阻塞，以等待操作完成。 如，启动了某I/O设备，,新数据尚未到达,对于相互合作的进程，如果其中一个进程需要获得另一个（合作）进程提供的数据才能运行以对数据进行处理，则只要其所需数据尚未到达，该进程只有阻塞（等待）。如，,98,2进程阻塞过程,调用阻塞原语block把自己阻塞。（主动行为）,阻塞（block）过程：,立即停止执行； 把PCB中进程状态由“执行”改为“阻塞”； 将PCB插入具有相同事件的阻塞队列； 转进程调度程序，将处理机分配给某个就绪进程，并进行进程切换保留被阻塞进程的处理机状态（在PCB中），再按新进程的PCB中处理机状态设置CPU的环境。,99,3进程唤醒过程,调用唤醒原语wakeup( )，将等待事件的进程唤醒。,唤醒原语执行过程：,将被唤醒进程的PCB从阻塞队列移出； 将其PCB中进程状态由“阻塞”改为“就绪”； 将改PCB插入到就绪队列中。,block（）和wakeup（）是成对的。,100,Win32中线程阻塞的API函数是SuspendThread( )；唤醒线程的API函数是ResumeThread ( )。详见文档“OS课内上机实验使用的相关API函数介绍.doc”或查看MSDN。 Windows中一般没有挂起状态，即线程“挂起”后并不调到外存，而只是阻塞。唤醒也称为释放。 了解为什么在Windows中没有关于进程阻塞(挂起)和唤醒(释放)的系统调用。,101,1进程的挂起,当出现了引起进程挂起的事件时(用户进程请求将自己挂起，或父进程请求将子进程挂起)，系统将用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。,挂起原语的执行过程：,检查被挂起进程的状态：,若处于活动就绪或执行状态，则将其转为静止就绪； 若处于活动阻塞,则将其转为静止阻塞,把该进程的PCB复制到某指定内存区域,为方便用户或父进程考查该进程的运行状态。,若该进程正在执行，则转进程调度程序重新调度。,2.2.4 进程的挂起和激活,102,2进程的激活,当发生激活进程的事件时(如父进程或用户请求激活指定进程，而内存中已有足够空间时)，系统利用激活原语active( )将指定进程激活。,激活过程是：,将进程从外存调入内存；,若是静止就绪，则改为活动就绪； 若是静止阻塞，则改为活动阻塞。,若采用的是抢占式调度策略，则应检查被激活就绪进程的优先级，若其优先级比先行执行进程高，则应将处理机分配给被激活进程。,检查该进程现行状态：,103,2.3 进程同步,由于进程的异步性，尤其是它们竞争临界资源时，可能会给系统造成混乱。 进程同步的主要任务，是使并发执行的进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。,2.3.1 进程同步的基本概念 2.3.2 信号量机制 2.3.3 信号量的应用,104,2.3.1 进程同步的基本概念,1两种形式的制约关系,（1）间接制约关系,间接制约关系源于资源共享。如，共享打印机。,进程互斥,（2）直接制约关系,源于进程间的合作。如，,进程同步,2临界资源,在一段时间内只允许一个进程访问的资源，即仅当一个进程访问完并释放该资源后，才允许另一个进程访问的资源，称为临界资源或独占资源。,如，打印机、磁带机、共享变量、队列、,105,生产者-消费者问题,【例】生产者-消费者问题著名的进程同步问题,共享变量： 临界资源,生产者投放一个产品后，输入指针in加1：in = ( in + 1 ) % n （n是缓冲区个数，整型常量），in初值为0； 消费者每取出一个产品，输出指针out加1：out = ( out + 1 ) % n，out初值为0；,引入一个共享变量counter,初值为0。 生产者投放一个产品，counter加1，counter = n时不能再投放产品 消费者每取一个产品，counter减1，counter = 0时不能再取出产品,前面交通观察站例子亦然。,以下是软件临界资源的例子。,106,process producer： while （condition） produce an item in nextp； while(counter=n) no-op；/no-op表示空操作 bufferin = nextp； in = (in + 1)% n ； counter = counter + 1 ； ,生产者进程算法如下：,107,process consumer： struct item nextc ； while （condition） while （counter = 0）no-op ； nextc = bufferout ； out = （out + 1）% n ； counter = counter 1 ； consume the item in nextc ； ,消费者进程算法如下：,108,上面的生产者程序和消费者程序，在顺序执行时其结果是正确的。但若并发执行时，可能会出现差错，问题在于这两个进程共享变量counter。生产者做counter=counter+1操作，消费者做counter= counter-1操作，这两个操作在机器语言实现时，常可用下面的形式描述：,生产者执行的操作： register1 = counter ； register1 = register1 + 1; counter = register1；,消费者执行的操作： register2 = counter ； register2 = register2 - 1 ； counter = register2；,109,假设某一时刻counter的值为5，生产者和消费者同时对counter操作，按下述顺序执行：,register1 = counter; (生产者取得counter的当前值为5) register1 = register1 + 1; (生产者将该值增1变为6) register2 = counter; (消费者取得counter的当前值为5) register2 = register2 1; (消费者将该值减1变为4) counter = register2; (消费者保存counter的新值4) counter = register1; (生产者保存counter的新值6),最终counter的值为6，正确的值应是5，出现了差错。 学生考虑：什么情况会出现counter最终值为4的情况。,解决此问题的关键，是应将变量counter作为临界资源处理，亦即让生产者进程和消费者进程互斥地访问变量counter。,110,2.3.1 进程同步的基本概念,3临界区（critical section）,每个进程中访问临界资源的那段代码称为临界区。,不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它们访问。,显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界区的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看是否正被访问，如果此刻该资源未被访问，便可进入临界区对该临界资源进行访问，并设置它正被访问的标志；如果此刻它正被访问，则本进程不能进入临界区。,定义：,进程互斥的定义：,进程互斥不允许两个或两个以上进程同时访问同一个临界资源。 进程互斥不允许两个或两个以上进程同时进入相关临界区。,111,因此必须在临界区前增加一段用于上述检查的代码，把这段代码称为进入区(entry section) 相应地，在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。,repeat 非临界区 进入区 临界区 退出区 非临界区 until false,一般结构,“进入区”和“退出区”的不同构成方法，形成了各种不同的同步机制。,112,4同步机制应遵循的原则,为了实现各进程互斥地进入自己的临界区，一般是在系统中设置专门的同步机制来协调各进程间的运行。,所有同步机制都应遵循如下四条准则：,空闲让进,当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以便有效地利用临界资源。,空闲让进、忙则等待、有限等待、让权等待。,113,有限等待,让权等待,对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死锁”状态。不死等。 不互相阻塞。,当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙