第2章 进程和线程 内容提要: 2.1 进 程 概 念 2.2 进程的状态和组成 2.3 进 程 管 理 2.4 线 程.

Slides:



Advertisements
Similar presentations
作者 : 陳鍾誠 單位 : 金門技術學院資管系 URL : 日期 : 2016/7/21 行程的同步 註:本章學術性較重,但考試常考。
Advertisements

Linux 环境及 Shell 程序 操作系统实验 1. 二、 Shell 编程与进程通信 常用 shell 命令 文件及文件属性操作 ls 、 cp 、 mv 、 rm ln 、 ln –s 、 chmod 、 groupadd 、 useradd 输入输出操作 echo 、 cat >> 、
第 3 章操作系统基础 3.1 操作系统概述 3.2 操作系统的功能模块 3.3 典型操作系统概述.
进 程. “ 程序 ” 和 “ 进程 ” 进程是 OS 对 CPU 执行的程序的运行过程的一种抽象。进程有自 己的生命周期,它由于任务的启动而创建,随着任务的完成(或 终止)而消亡,它所占用的资源也随着进程的终止而释放。 Linux 内核中通常把进程称为任务,每个进程主要通过一个称为进程描 述符(
进程管理习题 设有一个可以装 A 、 B 两种物品的仓库,其 容量无限大,但要求仓库中 A 、 B 两种物品 的数量满足下述不等式: -M ≤ A 物品数量 -B 物品数量 ≤N 其中, M 和 N 为正整数。试用信号量和 P 、 V 操作描述 A 、 B 两种物品的入库过程。
投資 & 購屋置產 報告 ( 課程 : 個人理財規劃 ) 授課老師 : 許秀鶴 授課老師 : 許秀鶴 報告學生 : 報告學生 : 許文耀 學號 : 許文耀 學號 : 張慧珍 學號 : 張慧珍 學號 : Next 個人簡介.
南山中學 102學年度 性別平等教育週性別教育 性騷擾防治.
C语言程序设计 主讲教师 :张群燕 电话:
2013届 计算机科学与技术专业 毕业设计(论文) 启动报告
第7章 樹與二元樹 (Trees and Binary Trees)
行程(process).
第二章 进程的描述与控制管理.
Next 三個士兵,拖著腳步,走在陌生鄉下的路上。他們剛打完仗從戰場走路回家。他們很累,肚子又餓。實際上,他們已經兩天沒有吃東西了。
作業系統 第六章 同步與死結.
计算机操作系统.
进程管理习题 图书馆有100个座位,有一张登记表,要求: 用P、V原语描述一个读者的使用过程 阅读者进入时登记,取得座位号; 出来时,注销;
多核体系结构与并行编程模型 计算机科学导论第八讲
第二章 进程管理.
第二章 进程、线程与作业 多道程序设计 Multi-programming 进程的引入 Process 线程与轻进程
第三章 鏈結串列 Linked List.
第五章 资源分配与调度 (一) 资源管理功能 (二) 资源分配的机构和策略 (三) 死锁概念.
PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY
第四章 网络营销战略 战略计划是企业的生命线,是企业一切工作都必须遵循的总纲。我们经常说,做对的事情比把事情做对更重要,就是这个道理。美国一位总裁曾说:每天我总要花部分时间来思考的事情是企业未来10年的事情。在日本的一次调研中,90%的企业家认为:最占 时间、最为重要、最为困难的事情就是制定战略计划。可见,企业需要战略,没有战略计划指导的企业是很容易迷路的,迷了路的企业很难不误入歧途,误入歧途的企业,失败则是必然的。
Chapter 6 同步 (Synchronization)
中央广播电视大学计算机课程 操 作 系 统.
Operating System Process Management - 4 Monday, August 11, 2008.
操作系统 (并发进程) 徐锋 南京大学计算机科学与技术系 2018年9月18日3时52分.
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
第三章 堆疊與佇列的基本應用 3-1 簡介堆疊(Stack) 3-2 迷宮問題研究 3-3 佇列(queue)的介紹
Operating System Concepts 作業系統原理 Chapter 3 行程觀念 (Process Concept)
Linked List Operations
中国科学技术大学计算机系 陈香兰 2013Fall 第五讲 进程同步和通信(part II) 中国科学技术大学计算机系 陈香兰 2013Fall.
多线程编程基本概念 2008.
chapter 1-Introduction
佇列 (Queue).
第7章 Linux环境编程.
第四讲 MPI并行程序设计 课程网站:CourseGrading buaa.edu.cn 主讲教师: 赵长海
经典同步问题.
作業系統 第六章 同步與死結.
Chapter 3 行程觀念 (Process Concept)
Function.
第三章 C++中的C 面向对象程序设计(C++).
进程及进程管理 第4章 进程及进程管理.
计算机操作系统 第二章 进程管理 高校教师、高级项目经理 任铄 QQ:
第三章 进程互斥与同步.
第三章 进程互斥与同步 进程通信 Communication.
进程操作.
Process management(程序管理)
操作系统原理 Operating System Principles
李元金 计算机与信息工程学院 第 4 讲 进程管理(2) 李元金 计算机与信息工程学院 1/
第六章. 系统调度,COW Fork和IPC (lab4)
多核结构与程序设计 杨全胜 东南大学成贤学院计算机系.
李元金 计算机与信息工程学院 第 3 讲 进程管理(1) 李元金 计算机与信息工程学院 1/
实验一、进程控制 一、实验目的 1、加深对进程的理解,进一步认识并发执行的实质; 2、分析进程争用资源现象,学习解决进程互斥的方法;
第2章 进程管理 2.1 进程概念 2.2 线程 2.3 进程管理 2.4 进程间通信 2.5 经典进程同步问题 2.6 管程
第1章 概述 本章要点: C语言程序结构和特点 C语言程序的基本符号与关键字 C语言程序的编辑及运行 学习方法建议:
第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.
Operation System(OS).
青少年常見犯法行為.
作業系統 第四章 行程.
第7章 樹與二元樹(Trees and Binary Trees)
3.5 线程 问题的提出 进程的引入使操作系统得以完成对并发执行的多道程序动态特征的描述和资源共享的管理,因而进程既是调度的基本单位又是资源分配的基本单位。进程所具有的这两个特点构成了程序并发执行的基础,但同时又导致进程切换过程中由于进程映像过大而带来的时空开销。因此,如果系统中创建的进程过多,或进程切换的频率过高,则会使系统效率下降,限制了并发度的进一步提高。
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
挑戰C++程式語言 ──第9章 函數.
Computer Science & Information Management
2017 Operating Systems 作業系統實習 助教:陳主恩、林欣穎 實驗室:720A Lab4.
Race Conditions and Semaphore
2019 Operating Systems 作業系統實習 助教:林欣穎 實驗室:720A Lab10 1.
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
《操作系统设计与实现》 Linux系统编程.
Presentation transcript:

第2章 进程和线程 内容提要: 2.1 进 程 概 念 2.2 进程的状态和组成 2.3 进 程 管 理 2.4 线 程

2.1 进 程 概 念 2.1.1 多道程序设计 1.顺序程序活动的特点 顺序性 封闭性 可再现性 2.多道程序设计

2.1.1 多道程序设计 3.程序并发执行的特征 ① 失去封闭性。 ② 程序与计算不再一一对应。 ③ 并发程序在执行期间相互制约。

2.1.2 进程概念 1.引入:用程序这个静态概念已经不能如实反映程序并发执行过程中的这些特征。 2.进程概念 2.1.2 进程概念 1.引入:用程序这个静态概念已经不能如实反映程序并发执行过程中的这些特征。 2.进程概念 进程最根本的属性是动态性和并发性。 进程定义为:程序在并发环境中的执行过程

2.1.2 进程概念 进程和程序的区别 : (1)动态性 (2)并发性 (3)非对应性 (4)异步性

2.1.2 进程概念 3.进程的基本特征 (1)动态性 (2)并发性 (3)调度性

2.2 进程的状态和组成 2.2.1 进程的状态及其转换 1.进程的基本状态 运行状态(Running) 就绪状态(Ready) 2.2 进程的状态和组成 2.2.1 进程的状态及其转换 1.进程的基本状态 运行状态(Running) 就绪状态(Ready) 阻塞状态(Blocked 新建状态(New) 终止状态(Terminated)

运行状态 分到CPU 等待某事件发生 时间片到 (如等待I/O) 就绪 状态 阻塞状态 所等待事件发生 (如I/O完成)

2.进程状态的转换 图2-2 进程的5种基本状态及其转换

2.2.2 进程描述 1.进程映像 进程映像由它的(用户)地址空间内容、硬件寄存器内容和与该进程有关的核心数据结构组成。 2.2.2 进程描述 1.进程映像 进程映像由它的(用户)地址空间内容、硬件寄存器内容和与该进程有关的核心数据结构组成。 图2-3 进程映像模型

2.2.2 进程描述 2.进程控制块的组成 进程控制块(PCB)有时也称进程描述块(Process Descriptor),它是进程组成中最关键的部分,其中含有进程的描述信息和控制信息,是进程动态特性的集中反映,是系统对进程施行识别和控制的依据。

进程控制块的组成 进程名 特征信息 进程状态信息 调度优先权 通信信息 现场保护区 资源需求 进程实体信息 族系关系 其他信息

2.2.2 进程描述 3.进程控制块的作用 每个进程有惟一的进程控制块

2.2.3 进程队列 1.线性方式 图2-4 PCB线性队列示意图

2.2.3 进程队列 2.链接方式 图2-5 PCB链接队列示意图

2.2.3 进程队列 3.索引方式 图2-6 PCB索引结构示意图

2.3 进 程 管 理 2.3.1 进程图 进程图(Process Graph)是描述进程族系关系的有向树 图2-7 进程创建的层次关系

2.3.2 进程创建 引发创建进程的事件通常是调度新的批作业,交互式用户登录,操作系统提供服务和现有进程派生新进程。 2.3.2 进程创建 引发创建进程的事件通常是调度新的批作业,交互式用户登录,操作系统提供服务和现有进程派生新进程。 创建新进程时要执行创建进程的系统调用(如UNIX/Linux系统中的fork),其主要操作过程有如下四步: (1)申请一个空闲的PCB (2)为新进程分配资源 (3)将新进程的PCB初始化 (4)将新进程加到就绪队列中

下面这个C程序展示了UNIX系统中父进程创建子进程及各自分开活动的情况 #include <stdio.h> void main(int argc,char *argv[]) { int pid; /* fork another process */ pid = fork(); if (pid < 0) { /* error occurred */ fprintf(stderr, "Fork Failed"); exit(-1); } else if (pid == 0) { /* child process */ execlp( "/bin/ls", "ls",NULL); else {/* parent process */ /* parent will wait for the child to complete */ wait(NULL); printf( "Child Complete" ); exit(0);

2.3.3 进程终止 (1)正常终止 (2)异常终止 (3)外部干扰

2.3.3 进程终止 终止进程的主要操作过程如下: 找到指定进程的PCB 终止该进程的运行 回收该进程所占用的全部资源 2.3.3 进程终止 终止进程的主要操作过程如下: 找到指定进程的PCB 终止该进程的运行 回收该进程所占用的全部资源 终止其所有子孙进程,回收它们所占用的全部资源。 将被终止进程的PCB从原来队列中摘走

2.3.4进程阻塞 进程阻塞的过程如下: 立即停止当前进程的执行 现行进程的CPU现场保存 现行状态由“运行”改为“阻塞” 转到进程调度程序

2.3.5 进程唤醒 唤醒原语执行过程如下: ① 把阻塞进程从相应的阻塞队列中摘下。 2.3.5 进程唤醒 唤醒原语执行过程如下: ① 把阻塞进程从相应的阻塞队列中摘下。 ② 将现行状态改为就绪状态,然后把该进程插入就绪队列中。 ③ 如果被唤醒的进程比当前运行进程的优先级更高,则设置重新调度标志。

2.4 线 程 2.4.1 线程概念 现代操作系统中,进程只作为资源拥有者,而调度和运行的属性赋予新的实体——线程。 2.4 线 程 2.4.1 线程概念 现代操作系统中,进程只作为资源拥有者,而调度和运行的属性赋予新的实体——线程。 线程(Thread)是进程中实施调度和分派的基本单位

2.4.1 线程概念 1.线程的组成 每个线程有一个thread结构,即线程控制块,用于保存自己私有的信息,主要由以下4个基本部分组成: 2.4.1 线程概念 1.线程的组成 每个线程有一个thread结构,即线程控制块,用于保存自己私有的信息,主要由以下4个基本部分组成: 图2-8 thread结构示意图

2.4.1 线程概念 线程必须在某个进程内执行 一个进程可以包含一个线程或多个线程 图2-9 单线程和多线程的进程模型

2.4.1 线程概念 2.线程的状态 运行状态: 就绪状态: 阻塞状态: 终止状态:

2.4.1 线程概念 3.线程的管理 线程创建 线程终止 线程等待 线程让权

2.4.1 线程概念 4.线程和进程的关系 ① 一个进程可以有多个线程,但至少要有一个线程;而一个线程只能在一个进程的地址空间内活动。 2.4.1 线程概念 4.线程和进程的关系 ① 一个进程可以有多个线程,但至少要有一个线程;而一个线程只能在一个进程的地址空间内活动。 ② 资源分配给进程,同一进程的所有线程共享该进程的所有资源。 ③ 处理机分配给线程,即真正在处理机上运行的是线程。 ④ 线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。

2.4.1 线程概念 5.引入线程的好处 ① 易于调度。 ② 提高并发性。 ③ 开销少。 ④ 利于充分发挥多处理器的功能。

2.4.2 在用户空间实现线程 把线程库整个地放在用户空间,核心对线程一无所知。 图2-10(a) 在用户空间实现线程

2.4.2 在用户空间实现线程 1.在用户空间实现线程的优点 ① 线程切换速度很快。 ② 调度算法可以是应用程序专用的。 2.4.2 在用户空间实现线程 1.在用户空间实现线程的优点 ① 线程切换速度很快。 ② 调度算法可以是应用程序专用的。 ③ 用户级线程可以运行在任何操作系统 上,包括不支持线程机制的操作系统。

2.4.2 在用户空间实现线程 2.用户级线程的主要缺点 ① 系统调用的阻塞问题。 2.4.2 在用户空间实现线程 2.用户级线程的主要缺点 ① 系统调用的阻塞问题。 ② 在单纯用户级线程方式中,多线程应用程序不具有多处理器的优点。

2.4.3 在核心空间实现线程 核心知道线程存在,并对它们实施管理 ①在多处理器系统中,核心可以同时调度同一进程的多个线程; 2.4.3 在核心空间实现线程 核心知道线程存在,并对它们实施管理 ①在多处理器系统中,核心可以同时调度同一进程的多个线程; ② 如果一个进程的某个线程阻塞了,核心可以调度同一个进程的另一个线程。 优点是,核心线程本身也可以是多线程的。 缺点,主要是控制转移开销大。 图2-10(b) 在核心空间实现线程

2.4.4 组合方式 1.多对一模型 图2-11 在核心级线程上有多个用户级线程 图2-12 多对一模型

2.4.4 组合方式 2.一对一模型 图2-13 一对一多模型

2.4.4 组合方式 3.多对多模型 图2-14 多对一多模型

2.4.5 线程池

2.5 进程的同步和通信 ① 互斥 ② 同步 ③ 通信

2.5.1 进程的同步与互斥 1.同步 同步进程通过共享资源来协调活动,在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字,但知道对方的存在和作用。在协调动作的情况下,多个进程可以共同完成一项任务。 2.互斥 在逻辑上这两个进程本来完全独立,毫无关系,只是由于竞争同一个物理资源而相互制约。 它们的运行不具有时间次序的特征 竞争条件(Race Condition),即两个或多个进程同时访问和操纵相同的数据时,最后的执行结果取决于进程运行的精确时序。

2.5.2 临界资源和临界区 1.临界资源和临界区 一次仅允许一个进程使用。我们把这类共享资源称为临界资源(Critical Resource)。 在每个进程中访问临界资源的那段程序叫做临界区(Critical Section),简称CS区。

2.5.2 临界资源和临界区 2.进程的一般结构 图2-15 典型进程的一般结构

2.5.2 临界资源和临界区 3.临界区进入准则 ① 如果若干进程要求进入空闲的临界区,一次仅允许一个进程进入。 2.5.2 临界资源和临界区 3.临界区进入准则 ① 如果若干进程要求进入空闲的临界区,一次仅允许一个进程进入。 ② 任何时候,处于临界区内的进程不可多于一个。 ③ 进入临界区的进程要在有限时间内退出。 ④ 如果进程不能进入自己的临界区,则应让出CPU,避免进程出现“忙等”现象。

2.5.2 临界资源和临界区 图2-16 互斥使用临界区

2.5.3 互斥实现方式 1.利用硬件方法解决进程互斥问题 (1)禁止中断 (2)专用机器指令 2.原语 2.5.3 互斥实现方式 1.利用硬件方法解决进程互斥问题 (1)禁止中断 (2)专用机器指令 2.原语 是机器指令的延伸,往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”(atomic action),即一个操作中的所有动作要么全做,要么全不做。 执行原语操作时,要屏蔽中断,以保证其操作的不可分割性。

2.5.3 互斥实现方式 3.利用软件方法解决进程互斥问题 可为每类临界区设置一把锁,该锁有 打开和关闭两种状态。 2.5.3 互斥实现方式 3.利用软件方法解决进程互斥问题 可为每类临界区设置一把锁,该锁有 打开和关闭两种状态。 关锁原语lock (W): while (W==1); W=1; 开锁原语unlock (W): w=0;

2.5.3 互斥实现方式 进程A …… lock(W); 打印信息S; }CS区 unlock(W); 进程B …… lock(W); 2.5.3 互斥实现方式 进程A …… lock(W); 打印信息S; }CS区 unlock(W); 进程B …… lock(W); 打印信息S; }CS区 unlock(W);

2.5.4 信号量 1.整型信号量 P操作最初源于荷兰语proberen,表示测试;V操作源于荷兰语verhogen,表示增加。 2.5.4 信号量 1.整型信号量 P操作最初源于荷兰语proberen,表示测试;V操作源于荷兰语verhogen,表示增加。 在有些书上将P操作称做wait或者DOWN操作,将V操作称做signal或者UP操作。 P和V操作都是原语

2.5.4 信号量 2.结构型信号量 结构型信号量一般是由两个成员组成的数据结构。其中一个成员是整型变量,表示该信号量的值;另一个是指向PCB的指针。 typedef struct{ int value; struct PCB *list; } semaphore;

2.5.4 信号量 信号量的值与相应资源的使用情况有关 对信号量的操作有如下严格限制: 1. 信号量可以赋初值,且初值为非负数。 2.5.4 信号量 信号量的值与相应资源的使用情况有关 图2-17 信号量的一般结构及PCB队列 对信号量的操作有如下严格限制: 1. 信号量可以赋初值,且初值为非负数。 2. 信号量的值可以修改,但只能由P和V操作来访问

2.5.4 信号量 P操作的定义如下: void P(semaphore S) { S.value--; if(S.value<0) 2.5.4 信号量 P操作的定义如下: void P(semaphore S) { S.value--; if(S.value<0) 把这个进程加到S.list队列; block( ); }

2.5.4 信号量 在具体实现时应注意,P, V操作都应作为一个整体实施,不允许分割或相互穿插执行 V操作的定义如下: 2.5.4 信号量 V操作的定义如下: void V(semaphore S) { S.value++; if(S.value<=0) 从S.list队列中移走进程Q; wakeup(Q); } 在具体实现时应注意,P, V操作都应作为一个整体实施,不允许分割或相互穿插执行

2.5.4 信号量 3.二值信号量

2.5.5 信号量的一般应用 1.用信号量实现进程互斥 Pa: Pb: … … P(mutex) P(mutex) 分配打印机 释放打印机 2.5.5 信号量的一般应用 1.用信号量实现进程互斥 Pa: Pb: … … P(mutex) P(mutex) 分配打印机 释放打印机 (读写分配表) (读写分配表) V(mutex) V(mutex) … …

2.5.5 信号量的一般应用 利用信号量实现互斥的一般模型是: 进程P1 进程P2 … 进程Pn 2.5.5 信号量的一般应用 利用信号量实现互斥的一般模型是: 进程P1 进程P2 … 进程Pn … … … P(mutex); P(mutex); P(mutex); 临界区 临界区 临界区 V(mutex); V(mutex); V(mutex); … … …

2.5.5 信号量的一般应用 使用P, V操作实现互斥时应注意两点: 2.5.5 信号量的一般应用 使用P, V操作实现互斥时应注意两点: ① 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现,即先做P,进入临界区;后做V,退出临界区。 ② 互斥信号量mutex的初值一般为1。

2.5.5 信号量的一般应用 2.用信号量实现进程简单同步 图2-18 简单供者和用者对缓冲区的使用关系

2.5.5 信号量的一般应用 供者和用者间要交换两个消息:缓冲区空和缓冲区满的状态。 设置两个信号量: 2.5.5 信号量的一般应用 供者和用者间要交换两个消息:缓冲区空和缓冲区满的状态。 设置两个信号量: S1表示缓冲区是否空(0表示不空,1表示空)。 S2表示缓冲区是否满(0表示不满,1表示满)。 规定S1和S2的初值分别为1和0

2.5.5 信号量的一般应用 供者进程 用者进程 L1: P(S1) L2: … 启动读卡机 P(S2) ; 2.5.5 信号量的一般应用 供者进程 用者进程 L1: P(S1) L2: … 启动读卡机 P(S2) ; … 从缓冲区取出信息 收到输入结束中断 V(S1); V(S2); 加工并且存盘 goto L1; goto L2;

2.5.5 信号量的一般应用 用P和V操作实现同步时应注意如下三点: ① 分析进程间的制约关系,确定信号量种类。 2.5.5 信号量的一般应用 用P和V操作实现同步时应注意如下三点: ① 分析进程间的制约关系,确定信号量种类。 ② 信号量的初值与相应资源的数量有关,也与P, V操作在程序代码中出现的位置有关。 ③ 同一信号量的P, V操作要“成对”出现,但是,它们分别出现在不同的进程代码中。

2.6 经典进程同步问题 1.生产者-消费者问题 如果一个进程能产生并释放资源,则该进程称做生产者;如果一个进程单纯使用(消耗)资源,则该进程称做消费者。 问题可以表述如下:一组生产者进程和一组消费者进程(设每组有多个进程)通过缓冲区发生联系。生产者进程将生产的产品(数据、消息等统称为产品)送入缓冲区,消费者进程从中取出产品。假定缓冲区共有N个,不妨把它们设想成一个环形缓冲池。

1.生产者-消费者问题 它们应满足如下同步条件: ① 任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量(N)。 ② 所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。 图2-19 生产者-消费者问题环形缓冲池

1.生产者-消费者问题 1.设缓冲区的编号为0~N-1,in和out分别是生产者进程和消费者进程使用的指针,指向下面可用的缓冲区,初值都是0。 2.设置三个信号量: full:表示放有产品的缓冲区数,其初值为0。 empty:表示可供使用的缓冲区数,其初值为N。 mutex:互斥信号量,初值为1,表示各进程互斥进入临界区,保证任何时候只有一个进程使用缓冲区。

1.生产者-消费者问题 生产者进程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.6 经典进程同步问题 2.读者-写者问题 读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如,一个航班预订系统有一个大型数据库,很多竞争进程要对它进行读、写。允许多个进程同时读该数据库,但是在任何时候如果有一个进程写(即修改)数据库,那么就不允许其他进程访问它—— 既不允许写,也不允许读。

2.读者-写者问题 设置两个信号量:读互斥信号量rmutex和写互斥信号量wmutex。另外设立一个读计数器readcount,它是一个整型变量,初值为0。 rmutex:用于读者互斥地访问readcount,初值为1。 wmutex:用于保证一个写者与其他读者/写者互斥地访问共享资源,初值为1。

2.读者-写者问题 读者Readers: 写者Writers: while(TRUE) while(TRUE){ P(rmutex); { P(wmutex); 执行写操作 V(wmutex); } 这个算法隐含读者的优先级高于写者。 读者Readers: while(TRUE){ P(rmutex); readcount=readcount+1; if(readcount==1) P(wmutex); V(rmutex); 执行读操作 readcount=readcount-1; if(readcount==0) V(wmutex); 使用读取的数据 }

2.6 经典进程同步问题 3.哲学家进餐问题 图2-20 哲学家进餐问题

3.哲学家进餐问题 =========================================== #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 state[N]; semaphore mutex=1; /* 互斥进入临界区 */ semaphore s[N]; /* 每位哲学家一个信号量 */

3.哲学家进餐问题 void philosopher(int i) { while(TRUE){ think(); /* 哲学家在思考问题 */ take_chopstick(i); /* 拿到两根筷子或者等待 */ eat(); /* 进餐 */ put_chopstick(i); /* 把筷子放回原处 */ } void take_chopstick(int i) P(mutex); state[i]=HUNGRY; test(i); /* 试图拿两根筷子 */ V(mutex); P(s[i]);

3.哲学家进餐问题 void put_chopstick(int i) { P(mutex); state[i]=THINKING; test(LEFT); /* 查看左邻,现在能否进餐 */ test(RIGHT); /* 查看右邻,现在能否进餐 */ V(mutex); } void test(int i) if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING) state[i]=EATING; V (s[i] ); ===============================================

2.6 经典进程同步问题 4.打瞌睡的理发师问题 图2-21 打瞌睡的理发师

4.打瞌睡的理发师问题 理发师和每位顾客都分别是一个进程。 =============================== #define CHAIRS 5 typedef struct{ int value; struct PCB *list; } semaphore; semaphore customers=0; semaphore barbers=0; semaphore mutex=1; int waiting=0;

4.打瞌睡的理发师问题 void barber(void) { while(TRUE){ P(customers); /*如果没有顾客,则理发师打瞌睡*/ P(mutex); /*互斥进入临界区*/ waiting--; V(barbers); /*一个理发师准备理发*/ V(mutex); /*退出临界区*/ cut_hair(); /*理发(在临界区之外)*/ }

4.打瞌睡的理发师问题 { P(mutex); /*互斥进入临界区*/ if(waiting﹤CHAIRS){ waiting++; void customer(void) { P(mutex); /*互斥进入临界区*/ if(waiting﹤CHAIRS){ waiting++; V(customers); /*若有必要,唤醒理发师*/ V(mutex); /*退出临界区*/ P(barbers); /*如果理发师正忙着,则顾客打瞌睡*/ get_haircut(); }else V(mutex); /*店里人满了,不等了*/ }

2.7 管 程 管程概念的定义是:一个管程定义一个数据结构和能为并发进程在其上执行的一组操作,这组操作能使进程同步和改变管程中的数据。 2.7 管 程 管程概念的定义是:一个管程定义一个数据结构和能为并发进程在其上执行的一组操作,这组操作能使进程同步和改变管程中的数据。 一个管程由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。

2.7 管 程 图2-22 管程的结构

2.7 管 程 管程具有以下三个特性: ① 管程内部的局部数据变量只能被管程内定义的过程所访问,不能被管程外面声明的过程直接访问。 2.7 管 程 管程具有以下三个特性: ① 管程内部的局部数据变量只能被管程内定义的过程所访问,不能被管程外面声明的过程直接访问。 ② 进程要想进入管程,必须调用管程内的某个过程。 ③ 一次只能有一个进程在管程内执行,而其余调用该管程的进程都被挂起,等待该管程成为可用的。即管程能有效地实现互斥。

2.7 管 程 定义两个条件变量x和y: condition x , y; 2.7 管 程 定义两个条件变量x和y: condition x , y; 操作wait(x):挂起等待条件x的调用进程,释放相应的管程,以便供其他进程使用。 操作signal(x):恢复执行先前因在条件x上执行wait而挂起的那个进程。 管程的职责与信号量的职责不同。

2.8 进 程 通 信 进程通信是指进程间的信息交换。 上述进程的互斥和同步机构因交换的信息量少,被归结为低级进程通信。 2.8 进 程 通 信 进程通信是指进程间的信息交换。 上述进程的互斥和同步机构因交换的信息量少,被归结为低级进程通信。 高级进程通信方式有很多种,大致可归并为共享存储器、消息传递和管道文件三类。 1.共享存储器方式 共享存储器方式是在内存中分配一片空间作为共享存储区。需要进行通信的各个进程把共享存储区附加到自己的地址空间中,然后,就像正常操作一样对共享区中的数据进行读或写。

2.8 进 程 通 信 2.消息传递方式 消息传递方式以消息(Message)为单位在进程间进行数据交换。 ① 直接通信方式。 2.8 进 程 通 信 2.消息传递方式 消息传递方式以消息(Message)为单位在进程间进行数据交换。 ① 直接通信方式。 ② 间接通信方式。

2.8 进 程 通 信 3.管道文件方式 管道文件也称管道线,它是连接两个命令的一个打开文件。一个命令向该文件中写入数据,称做写者;另一个命令从该文件中读出数据。

2.8 进 程 通 信 2.8.1 消息传递系统 send和receive的一般格式是: send (destination, message) receive (source, message)

2.8.1 消息传递系统 同步: 发送方——阻塞,不阻塞 接收方——阻塞,不阻塞,测试消息到来 格式: 内容 长度——定长,变长 寻址: 2.8.1 消息传递系统 同步: 发送方——阻塞,不阻塞 接收方——阻塞,不阻塞,测试消息到来 格式: 内容 长度——定长,变长 寻址: 直接——发送,接收 ( 显式,隐式) 间接——静态,动态,属主关系 排队规则: FIFO 优先级 表2-3 消息传递系统设计要点

2.8.2 客户-服务器系统中的通信 常用的进程通信方式有socket和远程过程调用。 1.socket 2.8.2 客户-服务器系统中的通信 常用的进程通信方式有socket和远程过程调用。 1.socket socket好像一条通信线两端的接插口—— 只要通信双方都有插口,并且中间有通信线路相连,就可以互相通信了。 一对进程通过网络进行通信要用一对socket,每个进程一个。一个socket在逻辑上有网络地址、连接类型和网络规程三个要素。

2.8.2 客户-服务器系统中的通信 网络地址表明一个socket用于哪种网络 2.8.2 客户-服务器系统中的通信 网络地址表明一个socket用于哪种网络 连接类型表明网络通信所遵循的模式,主要分为“有连接”和“无连接”模式。 网络规程表明具体网络的规程。一般来说,网络地址和连接类型结合在一起就基本上确定了适用的规程。

2.8.2 客户-服务器系统中的通信 图2-25 socket通信流程

2.8.2 客户-服务器系统中的通信 2.远程过程调用 远程过程调用(Remote Procedure Call, RPC)是远程服务的一种最常见的形式。

Bye! 下一章(NEXT): == 第3章-死锁