第四章 并发处理 (一)并发程序及特点 (二)进程的基本概念 (三)进程控制 (四)进程互斥 (五)进程同步 (六)线程的基本概念.

Slides:



Advertisements
Similar presentations
2 和 5 的倍数的特征 运动热身 怎样找一个数的倍数? 从小到大写出 2 的倍数( 10 个): 写出 5 的倍数( 6 个) 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 5 , 10 , 15 , 20 , 25 , 30.
Advertisements

高校教师、高级项目经理 任铄 QQ : 第一章 操作系统引论 1.1 操作系统的目标和作用 1.2 操作系统的发展过程 1.3 操作系统的基本特性 1.4 操作系统的主要功能 1.5 OS 结构设计.
Edu.51cto.com 高校教师、高级项目经理 任铄 QQ : edu.51cto.com 第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 进程通信 2.6 线程.
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
3.2 进程的描述 进程的特征 1 .动态性 动态性是进程最基本的特征。 动态性是进程最基本的特征。 2. 并发性 这是指多个进程实体,同存于内存中,能在一段时 间内同时运行。并发性是进程的重要特征,同时也成 为 OS 的重要特征。引入进程的目的也是为了使该进 程的程序能和其它进程的程序并发执行。
Linux 系统. 操作系统发展需求 1 没有操作系统 2 简单批处理操作系统 3 多道程序设计的批处理 4 多道程序设计的分时操作系统 5 多处理机并行系统 6 网络操作系统 7 分布式操作系统.
计算机操作系统 第二章 进程管理 高校教师、高级项目经理 任铄 QQ:
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
操作系统 年级:2003春 专业:计算机应用专业.
实用操作系统概念 张惠娟 副教授 1.
Oracle数据库 Oracle 子程序.
Lab2 syscall 参数问题 参数check在当前代码框架下并不具有任何含义, 它就只是个参数而已 参数不超过四个: 系统调用号
全国计算机等级考试 二级基础知识 第二章 程序设计基础.
在PHP和MYSQL中实现完美的中文显示
陈香兰 助教:陈博、李春华 Spring 2009 嵌入式操作系统 陈香兰 助教:陈博、李春华 Spring 2009.
Kvm异步缺页中断 浙江大学计算机体系结构实验室 徐浩.
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
Hadoop I/O By ShiChaojie.
OpenMP简介和开发教程 广州创龙电子科技有限公司
计算机软件技术基础 操作系统(3).
管理信息结构SMI.
实践演练 广州创龙电子科技有限公司 01 广州创龙电子科技有限公司
走进编程 程序的顺序结构(二).
辅导课程六.
网络常用常用命令 课件制作人:谢希仁.
临界区软件互斥软件实现算法.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第十章 IDL访问数据库 10.1 数据库与数据库访问 1、数据库 数据库中数据的组织由低到高分为四级:字段、记录、表、数据库四种。
操作系统原理 Operating System Principles
本节内容 模拟线程切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
动态规划(Dynamic Programming)
CPU结构和功能.
作业调度系统常用命令.
Windows 7 的系统设置.
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
第二章 登录UNIX操作系统.
内容摘要 ■ 课程概述 ■ 教学安排 ■ 什么是操作系统? ■ 为什么学习操作系统? ■ 如何学习操作系统? ■ 操作系统实例
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
微机系统的组成.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
实验四、TinyOS执行机制实验 一、实验目的 1、了解tinyos执行机制,实现程序异步处理的方法。
Process Concept & Process Control
进程概念.
姚金宇 MIT SCHEME 使用说明 姚金宇
分裂对象模型 C++ otcl.
Web安全基础教程
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
信号量(Semaphore).
实验三 16位算术逻辑运算实验 不带进位控制的算术运算 置AR=1: 设置开关CN 1 不带进位 0 带进位运算;
iSIGHT 基本培训 使用 Excel的栅栏问题
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
Visual Basic程序设计 第13章 访问数据库
魏新宇 MATLAB/Simulink 与控制系统仿真 魏新宇
临界区问题的硬件指令解决方案 (Synchronization Hardware)
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
本节内容 Windows线程切换_时钟中断切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
φ=c1cosωt+c2sinωt=Asin(ωt+θ).
本节内容 动态链接库 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第8章 创建与使用图块 将一个或多个单一的实体对象整合为一个对象,这个对象就是图块。图块中的各实体可以具有各自的图层、线性、颜色等特征。在应用时,图块作为一个独立的、完整的对象进行操作,可以根据需要按一定比例和角度将图块插入到需要的位置。 2019/6/30.
本节内容 进程 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第四章 UNIX文件系统.
位似.
《偏微分方程》第一章 绪论 第一章 绪论 1.1.
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
本节内容 SEMAPHORE 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
Presentation transcript:

第四章 并发处理 (一)并发程序及特点 (二)进程的基本概念 (三)进程控制 (四)进程互斥 (五)进程同步 (六)线程的基本概念

(一)并发程序及特点 一、顺序程序及特点 1. 什么是程序的顺序执行 一个程序由若干个程序段组成,而这些程序段的执行必须按照严格的先后次序顺序的执行。程序的顺序执行也称为顺序程序设计。 顺序环境: 在单道计算机系统中只有一个程序在运行,这个程序独占系统中所有资源,其执行不受外界影响.

2. 程序顺序执行的特点 (1)程序执行的顺序性(大多数程序都具有) 处理机的操作严格按照程序所规定的顺序执行。 (2)程序执行的封闭性 独占资源,执行过程中不受外界影响(由执行环境保证) (3)程序执行结果的可再现性(确定性) 程序执行的结果与初始条件有关,而与执行时间无关。即只要程序的初始条件相同,它的执行结果是相同的,不论它在什么时间执行,也不管计算机的运行速度。(由封闭性保证)

在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态,并且次序不是事先确定的 二. 并发程序及特点 1.并发环境: 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态,并且次序不是事先确定的 B A

例:用下图说明在多道批处理系统中,大量操作执行的先后次序。 I1 I2 I3 I4 C1 C2 C3 P1 P2 讨论: (1)哪些程序段的执行必须是顺序的?为什么? (2)哪些程序段的执行是可并行的?为什么?

2. 什么是程序的并发执行 程序并发执行 (定义) 若干个程序段同时在系统中运行,这些程序的执行在时间上是重迭的,一个程序段的执行尚未结束,另一个程序段的执行已经开始,即使这种重迭是很小的,也称这几个程序段是并发执行的。 例:三个并发执行的程序段

cobegin 3. 并行语句的表示 程序并发执行的描述 S1;S2;S3;...;SN coend; 提问:

假设有一个程序由S0~Sn+1个语句,其中 S1~Sn语句是并发执行的,程序如下: cobegin S1;S2;S3;...;SN coend; Sn+1;

4. 实例: a 一个循环程序顺序执行的誊抄 由这个程序完成誊抄工作是不会出错的。 算法1: 输入:f 输出:g { while (f 不为空) input ; output ; } 由这个程序完成誊抄工作是不会出错的。

实例: b 两个程序并发执行完成誊抄 设有一台标准输入设备(键盘),和一台标准输出设备(显示器或打印机),输入程序负责从标准设备中读取一个字符,送缓冲区中。输出程序从缓冲区中取数据,送标准设备输出。 f g 输出程序 输入程序 缓冲区

算法:2 { cobegin while (不为结束符)/* 输入程序段 */ { input; /* 从标准输入设备读入一个数据 */ send; /* 将读入的数据送到bufferf */ } while(buffer不为空) /* 输出程序段 */ { receive; /* 从bufferf中取数据 */ output; /* 送打印机输出 */ coend ?存在什么问题?

这两个程序段并发执行时可能出现如下情况: 1、输出程序运行的速度比输入程序快时,有些输出会重复; 2、输入程序执行的速度比输出程序快时,有些数据会丢失。

实例: c 三个并发执行程序的誊抄 copy g f put get get程序负责从输入序列f中读取字符并送到缓冲区s中; copy程序把缓冲区s中的数据复制到缓冲区t中去; put程序从缓冲区t中取出数据打印。

算法中的: copy≡t=s put ≡ put(t,g) get ≡ get(s,f) 假定f系列中有记录 f=(R1,R2,...,Rn) g=() 在誊抄完成后: f=() g=(R1,R2,...,Rn) 算法中的: copy≡t=s put ≡ put(t,g) get ≡ get(s,f)

与时间有关的错误 若程序错写成: while(誊抄未完成){ cobegin copy; put; get; coend } 初始状态: f=(R1,R2,...,Rn) s=() t=() g=() 首先执行了get(s,f) s=R1,t=(),g=()

然后,copy,put,get三个程序段并发执行,就有六种组合: 1、copy;put;get 导致结果:g=(R1,R2)  2、copy;get;put 导致结果:g=(R1,R2)  3、put;copy;get 导致结果:g=(R1,R1)  4、put;get;copy 导致结果:g=(R1,R1)  5、get;copy;put 导致结果:g=(R1,R3)  6、get;put;copy 导致结果:g=(R1,R1)  这就是与时间有关的错误: 程序并发执行时,若共享了公共变量,其执行结果与各并发程序的相对速度有关,即给定相同的初始条件,若不加以控制,也可能得到不同的结果,此为与时间有关的错误。

5. 并发程序的特点 (1)失去了程序的封闭性(程序结果的不可再现性) 如果程序执行的结果是一个与时间无关的函数,即具有封闭性。 若一个程序的执行可改变另一个程序的变量,程序执行的结果不仅依赖于程序的初始条件,还依赖于程序执行时的相对速度,在这种情况下结果是不确定的,即失去了程序的封闭性。 例:讨论共享公共变量的两个循环程序,它们执行时可能产生的不同结果。 设:程序A每执行一次都要做n加1的操作 程序B每隔一段时间打印出n的值,并将n重新置为零

(3)程序并发执行的相互制约 (2)程序与计算不再一一对应 一个程序可以对应多个计算:多用户共享使用同一个程序,但处理(计算)的对象却是不同的。 例1: 例2: L1 编译; 输入程序段 L2 C编译程序 编译; … … Ln 编译。 (3)程序并发执行的相互制约 直接的相互制约关系——公共变量 间接的相互制约关系——资源共享

6. 进程的引入 并发活动--进程的引入 操作系统的特性之一是并发与共享,这就会引起一系列的问题,包括:对资源的竞争、运行程序之间的通信、程序之间的合作与协同等。 操作系统的第三个特性:不确定性* 要解决这些问题,用程序的概念已经不能描述程序在内存中运行的状态,必须引入新的概念——进程。

(二) 进程的基本概念 一、进程定义 在多道程序设计的环境下,为了描述程序在计算机系统内的执行情况,必须引入新的概念--进程。 程序并发执行时,新的活动规律: 执行  暂停  执行 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360,在IBM的OS/360/370系统中也曾叫过任务(task)。 1. 什么是进程 所谓进程,就是一个程序在给定活动空间和初始环境下,在一个处理机上的执行过程。

2. 进程与程序的区别与联系: 1、程序是指令的集合,是静态的概念; 进程是程序在处理机上的一次执行的过程,是动态的概念。 进程有生命周期,有诞生有消亡,短暂的;而程序是相对长久的 2、进程是一个独立的运行单位,能与其它进程并行活动。而程序则不是。 进程更能真实地描述并发,而程序不能 3、进程是竞争计算机系统有限资源的基本单位,也是进行处理机调度的基本单位。 4、一个程序可以作为多个进程的运行程序,一个进程也可以运行多个程序。 进程具有创建其他进程的功能,而程序没有

3. 进程的类型 在系统中同时有多个进程存在,但归纳起来有两大类: 1、系统进程 系统进程起着资源管理和控制的作用。 或者:执行操作系统核心代码的进程。 2、用户进程 执行用户程序的进程。 (系统进程优先于用户进程)

系统进程与用户进程的区别: 1、系统进程被分配一个初始的资源集合,这些资源可以为它独占,也能以最高优先权的资格使用; 2、用户进程不能做直接I/O操作,而系统进程可以做显示的、直接的I/O操作。 3、系统进程在核态下活动,而用户进程则在用户态下活动。

二、进程的状态 1. 进程的基本状态 进程在系统中的活动规律是: 执行 暂停 执行 进程的三种基本状态: 运行状态 就绪状态 等待状态(又称阻塞、挂起、睡眠)

(1)运行状态 (Running) 该进程已获得运行所必需的资源,它的程序正在处理机上执行。(在系统中,总只有一个进程处于此状态) (2)等待状态 (Wait) 进程正在等待某个事件的发生而暂停执行。这时,即使给它CPU时间,它也无法执行,则称该进程处于等待状态。 (3)就绪状态(Ready) 进程已获得除CPU之外的运行所必需的资源,一旦得到CPU控制权,立即可以运行。(有多个进程处于此状态)

在进程运行过程中,由于进程自身进展情况及外界环境的变化,这三种基本状态可以依据一定的条件相互转换:  就绪—运行  运行—就绪  运行—等待  等待—就绪

运行 就绪 等待 2. 进程状态的变迁 进程的状态不是固定不变的,而是在不断变换,它随着自身的推进和外界条件的变换而发生变化。 等待某事件的发生 时间片到 服务完成/ 事件发生 进程调度

例1. 设有3个排序程序 程序A:采用冒泡排序算法,在屏幕的左1/3处开设一个窗口显示其排序过程。 程序B:采用堆排序算法,在屏幕的中1/3处开设一个窗口显示其排序过程。 程序C:采用快速排序算法,在屏幕的右1/3处开设一个窗口显示其排序过程。 (1)在不支持进程运行环境的操作系统下运行 (2)在支持进程运行环境的操作系统下运行

运 行 过 程 (1)在不支持进程运行的环境下: 依次运行程序A、程序B、程序C。 (2)在支持进程运行的环境下: 建立进程A、B、C,分别对应进程A、B、C。 若系统按时间片轮转的调度策略调度这3个进程,则在屏幕上有3个窗口,同时显示3个程序的排序过程。 实际上,这3个程序是轮流的占用CPU的时间执行。由于CPU的高速度,使我们看到好像是这3个程序在同时执行。

例2:设有2个程序,程序C是打印工资报表的程序,程序D是计算1000以内所有素数并显示最后结果程序。 (1)在不支持进程运行环境的操作系统下运行。 (2)在支持进程运行环境的操作系统下运行。

运 行 过 程 (1)在不支持进程运行的环境下: 依次执行程序C,程序D。可以看到,先是打印机不停的打印工资报表,打完后,接着运行程序C,不停的计算,最后显示所计算的结果。 (2)在支撑进程运行的环境下: 创建进程C和进程D。 由于进程C是I/O量较大的进程,而进程D是计算量较大的进程,故在系统进程调度的控制下,两个进程并发执行。 可以看到打印机不断打印工资报表,而处理机不停的计算,最后屏幕显示计算的结果。

三、进程描述 1. 什么是进程控制块 描述一个进程在各个不同时期所处的状态,与其他进程及系统资源的关系的数据结构称为进程控制块pcb(process control block),也称为进程描述器(process descriptor)。 系统为了管理进程而设置的一个专门的数据结构,用它来记录进程的外部特征,描述进程的运动变化过程。 系统利用PCB来控制和管理进程,所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的

描述进程的动态特征,该进程与其他进程和系统资源的关系。 2. 进程的组成 程序与数据: 描述进程本身所应完成的功能; PCB: 描述进程的动态特征,该进程与其他进程和系统资源的关系。 进程 控制块 PCB 程 序 与 数 据

在系统中一个进程存在: 进程的执行程序(一个可执行文件) 进程控制块(数据结构) 进程总是位于某个队列(就绪、等待某事件队列) 处于某种状态(运行、就绪、等待) 占用某些系统资源(内存,打开某些文件、处理机、外设) 进程标识信息 进程状态信息 进程控制信息 用户堆栈 共享地址空间 用户私有地址空间 (代码、数据) 进 程 控 制 块

3. PCB的主要内容 (1)进程标识符: 进程符号名或内部id号。 (2)进程当前状态: 本进程目前处于何种状态(运行、就绪、等待)。 (3)当前队列指针next: 该项登记了处于同一状态的下一个进程的pcb地址。 (4)总链队列指针all_q_next: 该项登记了在系统总链队列中,下一个进程的pcb地址。

系统中的进程是很多的,状态也不一样。为了调度和管理进程,需将各进程的PCB用适当的方法组织起来,以下有三种方法:

all_q _next next PCB 总链队列结构

3. PCB的主要内容 (5)程序开始地址: 该进程的程序将从此地址开始执行。 (6)进程优先级: 反映了进程要求CPU的紧迫程度。 当进程由于某种原因释放处理机时,CPU现场信息被保存在pcb的该区域中。 (8)通信信息: 进程间进行通信时所记录的有关信息。 (9)家族联系: 指明本进程与家族的联系。 (10)占有资源清单

(三)进程控制 进程控制包括: 一. 进程控制的概念 进程控制的职责是对系统中全部进程实施有效的管理,它是处理机管理的部分(另一部分是进程调度),当系统允许多进程并发执行时,为了实现共享、协调并发进程的关系,处理机管理必须提供对进程实行有效的管理。 进程控制包括: 进程创建、进程撤消、进程阻塞、进程唤醒 改变优先数、 调度进程、进程延迟 这些操作都要对应地执行一个特殊的程序段(操作系统核心程序),同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语(一种特殊的系统调用)。

进程撤消 运行 就绪 等待 时间片到 进程调度 进程创建 进程阻塞 进程唤醒

二. 进程创建 1. 进程创建原语的形式: create(name,priority,start-addr) 入口参数 name:被创建进程的标识符 priority:进程优先级 start-addr:某程序的开始地址。 2. 进程创建原语的功能: 创建一个指定标识符的进程(形成该进程的进程控制块pcb)。 UNIX系统: fork()

3. 进程创建原语的实现 创建一个PCB 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 设置相应的链接 从PCB池中申请一个空的PCB结构: -1 => x 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 许多默认值 (如: 状态为 New,无I/O设备或文件...) 设置相应的链接 如: 把新进程加到就绪队列的链表中

••• ••• ••• 进程创建后相应数据结构变化 next ∧ next next ∧ Ready-q-start all-q-start PCB[3] PCB[11] PCB[2] ∧ PCB[n] Ready-q-start ••• next PCB[k] ••• next PCB[67] PCB[22] PCB[34] ∧ PCB[m] all-q-start

三. 进程撤消 当进程完成任务后希望终止自己时使用进程撤销原语。 1. 进程撤销原语的形式: Kill(或exit) 该命令没有参数,其执行结果也无返回信息。 2. 进程撤销原语的功能: 撤销当前运行的进程。将该进程所占用的资源归还给父进程,从总链队列中摘除pcb结构,归还到pcb资源池,然后转进程调度程序。 UNIX系统:exit()

3. 进程撤消原语的实现 根据撤销进程标识号,从相应队列中找到它的PCB 将该进程拥有的资源归还给父进程或操作系统 若该进程拥有子进程,应先撤销他的所有子孙进程,以防它们脱离控制 被撤销进程出队,将它的PCB归还到PCB池 调用进程调度程序

当进程需要等待某一事件完成时,它可以调用等待原语把自己挂起。 四. 进程挂起 当进程需要等待某一事件完成时,它可以调用等待原语把自己挂起。 1. 进程等待原语的形式: susp(chan) 入口参数chan:进程等待的原因。 2. 进程等待原语的功能: 中止调用进程的执行,并加入到等待chan的等待队列中,最后使控制转向进程调度。 UNIX:sleep(chan, pri)

3. 进程等待原语的实现 算法 susp(chan) 输入:chan 等待的原因 输出:无 { 进程现场信息→PCB; 进程状态置为“阻塞”; 插入到等待 “chan”等待队列; 调用进程调度程序; }

••• ••• next ∧ next next wait-lpt-q-start PCB[3] PCB[11] PCB[2] PCB[n] PCB[j] ∧

当处于等待状态的进程所期待的事件来到时,由发现者进程使用唤醒原语叫唤醒它。 五. 进程唤醒 1. 进程唤醒原语的形式: 当处于等待状态的进程所期待的事件来到时,由发现者进程使用唤醒原语叫唤醒它。 wakeup(chan) 入口参数chan:进程等待的原因 2. 进程唤醒原语的功能: 当进程等待的事件发生时,唤醒等待该事件的所有进程或等待该事件的首进程。

3. 进程唤醒原语的功能 从相应的等待进程队列中取出进程控制块 修改进程控制块的有关信息,如进程状态等 把修改后进程控制块加入有关就绪进程队列 进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。