作者：whisper

链接：http://proprogrammar.com:443/article/117

声明：请尊重原作者的劳动，如需转载请注明出处

---

    说明：本章主要讲了进程与线程（进程概念，进程的状态与转换，进程控制，进程组织，进程通信（共享存储系统；消息传递系统；管道通信。），线程概念与多线程模型），处理机调度（调度的基本概念，调度时机、切换与过程，调度的基本准则，调度方法，典型调度算法（先来先服务调度算法；短作业（短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法），同步与互斥（进程同步的基本概念，实现临界区互斥的基本方法（软件实现方法；硬件实现方法。），信号量，管程，经典同步问题（生产者-消费者问题；读者-写者问题；哲学家进餐问题。），死锁（死锁的概念，死锁处理策略，死锁预防，死锁避免（系统安全状态；银行家算法。），死锁检测和解除

    进程与线程

    进程概念

    一个具有一定独立功能的程序对某个数据集合上的一次动态执行过程和资源分配过程

    进程包含的重要元素：

    代码（指令）、数据、进程表（进程控制块）

    Code、Data、PT（PCB）

    进程和程序的区别与联系

    进程是动态的，程序是静态的
    进程是暂时的，程序是永久的
    进程和程序的组成不同
        程序主要包含代码和数据
        进程除了包含代码和数据以外，还有进程表
    进程和程序间有非常紧密的联系
        程序经过多次创建，可以对应不同的进程
        一个进程通过系统调用，可以被多个程序所使用

    进程的状态与转换

    三种基本状态

    就绪(Ready)状态
    执行(Running)状态
    阻塞(Blocking)状态

    四种转换

    执行——阻塞（出事）
    执行——就绪（时间到）
    就绪——执行（调度）
    阻塞——就绪（事毕）

    进程的状态与转换（续）

    五状态模型

    创建（create）
    终止（terminal）

    七状态模型

    就绪挂起（Ready Suspend）
    阻塞挂起（Blocked Suspend）

    注：挂起是程序从内存转向外存

    进程控制

    进程的创建（创建原语）

    进程的创建过程

    申请空白进程表
    为新进程分配资源
    初始化进程表
    将新进程插入就绪队列

    进程控制（续1）

    进程的终止

    正常结束（自愿的）
    异常结束
    ----出现错误控制退出（自愿的）
    ----致命错误被迫退出（非自愿的）
    外界干预（非自愿的）

    进程控制（续2）

    进程的终止过程

    从进程控制块中读出该进程的状态
    若被终止进程正处于执行状态，立即终止该进程的执行
    若该进程还有子孙进程，还应将其所有子孙进程予以终止
    将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统
    将被终止进程的进程控制块移出

    进程控制（续3）

    进程的阻塞与唤醒

    请求系统服务
    启动某种操作
    新数据尚未到达
    无新工作可做

    进程控制（续4）

    进程的挂起与激活

    进程组织（进程表/进程控制块）

    进程表中的信息

    进程表中的信息
        进程管理信息：进程号，处理器寄存器，优先级等
        存储资源分配：代码指针，数据指针，堆和栈的指针等
       文件资源信息：句柄，描述符，设备等

    进程组织（续1）

    链接方式
        就绪队列链表（一般为一个）
        阻塞队列链表（可能依据不同阻塞原因有多个队列链表）
    索引方式
        就绪队列索引
        阻塞队列索引

    进程通信

    Shared memory(共享内存)
    Message(消息机制)
    Pipe(管道)
    Signal(信号)
    Socket(套接字)

    进程通信（续1）

    共享内存
        共享某些数据结构（有名）
        共享内存区域（指针）

    进程通信（续2）

    消息传递（格式化的报文，由原语实现）
        发送原语send（receiver，message）
        接收原语receive（sender，message）
        异步实现

    进程通信（续3）

    管道（内存中的字符流）
    原语自动实现同步
    实现阻塞读，非阻塞读或阻塞写或非阻塞写
    实现方法read/write，不支持lseek

    线程概念与多线程模型

    线程概念（提高并发性）
         进程的实体

    注：由上图可知，线程属于进程，一个进程可以有多个线程

    线程概念与多线程模型（续1）

    线程的属性
    轻型实体（容易创建和撤销）
    独立调度和分派的基本单位
    可并发执行
    共享进程资源
    适应硬件的发展

    线程概念与多线程模型（续2）

    在具有线程OS 中，进程是作为拥有系统资源的基本单位，进程不再作为一个执行的实体。
    具有线程的OS 中的进程有以下属性：
        作为系统资源分配的单位
        可包括多个线程
        进程变为了不是一个可执行的实体

    线程概念与多线程模型（续3）

    线程间的同步和通信

    互斥锁(mutex):互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制
    条件变量
    线程共享同一进程的全局变量

    线程概念与多线程模型（续4）

    内核支持线程
    内核支持线程是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。
    在内核空间还为每一个内核支持线程设置了一个线程控制块， 内核是根据该控制块而感知某线程的存在的，并对其加以控制

    线程概念与多线程模型（续6）

    用户级线程
    用户级线程仅存在于用户空间中。这种线程的创建、 撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。
    对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，无须内核的支持。
    由于切换的规则比进程切换的规则简单，因而使线程的切换速度特别快。

    线程概念与多线程模型（续8）

    混合线程

    注： 单应用的多个用户级线程映射成一些内核级线程

    处理机调度

    调度的基本概念

    作业调度——进入内存（宏观调度/高级调度）

    进程/线程调度——占用处理器（微观调度/低级调度）

    交换调度——位于何处（中级调度）

        与存储关系更多

    注：交换即内外存交换

    调度的基本概念（续1）

    高级、中级和低级调度

    调度的基本概念（续2）

    高级调度(High Scheduling)，宏观调度，作业调度
    在每次执行作业调度时（由外存创建到内存成为进程），都须做出以下两个决定
        接纳多少个作业?

        接纳哪些作业 ?

    调度的基本概念（续3）

    中级调度(Intermediate-Level Scheduling) ，中程调度
    引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量
    中级调度的算法主要由内存管理来实现，与高级调度和低级调度的算法不同，故一般在存储管理中分析，虚拟存储的中级调度即页面调入、置换等实现

    调度的基本概念（续4）

    低级调度(Low Level Scheduling)，微观调度，进程调度，线程调度
    调度的方式（后面还会提到）
    非抢占方式(Non-preemptive Mode)
    抢占方式(Preemptive Mode)

    调度时机、切换与过程

    时机、切换
    什么时候调度？怎么操作？流程是什么？
        调度器（scheduler）/切换器（dispatcher 也称分派器）（均是系统代码级程序）
        策略与机制
        调度队列
        上下文（context）切换

    调度时机、切换与过程（续1）

    过程（举个例子：分时系统）

        时钟中断，响应，时间片到（时机）？
        激活调度器，调度器占用CPU 运行（很少代码很短时间），按照调度算法选出下一个运行的进程
        激活切换器，切换器占用CPU 运行（很少代码很短时间），将原处理器上进程撤下，将新进程装入
        将CPU 交由新进程运行

    调度的基本准则

    基本要求

        公平
        策略执行
        平衡
    系统不同而有差别

    调度方法

    不可抢先方法（非剥夺式调度）
        只在处理机空闲时才激活调度器进行调度
    可抢先式方法（可剥夺式调度）
        只要出现调度时机均激活调度器并依的略可抢夺处理器

    调度算法

    先来先服务调度算法FCFS（适用作业调度和进程调度）
    按到达时刻组织作业/进程队列，每次取最早到达的作业/进程投入运行
    比较有利于长作业/进程，而不利于短作业/进程
    有利于CPU 繁忙的作业/进程，而不利于I/O 繁忙的作业/进程

    调度算法（续1）

    短作业（短进程、短线程）优先调度算法SJF
        预计运行时间最短的作业（进程）优先调度
        优点：
            比FCFS 改善平均周转时间和平均带权周转时间，缩短作业的等待时间
            提高系统的吞吐量

    缺点：
    对长作业非常不利，可能长时间得不到运行，出现饥饿
    未能依据作业的紧迫程度来划分执行的优先级
    难以准确估计作业（进程）的执行时间，从而影响调度性能

    调度算法（续2）

    时间片轮转调度算法(RR: Round Robin )（适用进程调度）
    通过硬件定时器计数，到时发出时钟中断，称为一个时间滴答，若干时间滴答组成一个时间配额（时间片），分配给进程，进程按先来先服务顺序轮流使用

    调度算法（续3）

    优先级调度算法Priority First
    所有影响调度的因素均可以折算为优先级（数）
    非抢占式优先级调度算法
    抢占式优先级调度算法
    优先级的类型
    静态优先级（不变）
    动态优先级（可变）

    调度算法（续4）

    高响应比优先调度算法HRRN(Highest Response Ratio Next)
        响应比R = (等待时间 + 预计运行时间) / 预计运行时间
        不可抢夺
    变形为“最短剩余时间优先”SRT(Shortest Remaining Time)
        允许比当前作业/进程剩余执行时间更短的进程来抢夺
    是“先来先服务”和“短作业优先”的折衷

    调度算法（续5）

    多级反馈队列调度算法
    (Round Robin with Multiple Feedback)
    多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展

    注： 多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成

    同步与互斥

    注：同步即协作，互斥即竞争

    进程同步的基本概念

    两种形式的制约关系
        间接相互制约关系（互斥）
        直接相互制约关系（同步）
    临界资源(Critical Resource)（共享并修改）
    临界区(Critical Section)
        访问临界资源的代码

    一个飞机订票系统（软件相同），两个终端，运行T1、T2 进程

T1：
……
read(x);
if x>=1 then
x:=x-1;
write(x);
……
T2：
……
read(x);
if x>=1 then
x:=x-1;
write(x);
……

    互斥关系：对访问票额数据库互斥
    同步关系：对访问共享数据同步

    进程同步的基本概念（续）

    同步机制应遵循的规则
        空闲让进
        忙则等待
        有限等待
        让权等待

    实现临界区互斥的基本方法

    软件实现方法
        Peterson’s Algorithm

         Pi 进程：

         flag[ i ] = TRUE; turn = j;             //进入区

         while(flag[ j ] && turn == j);        //进入区

         critical section;                            //l临界区

         flag[ i ] = FALSE ;                         //退出区

         remainder section;                    //剩余区

         Pj 进程：

         flag[ j ] = TRUE; turn = i;             //进入区 

         while(flag[ i ] && turn == i);        //进入区

         critical section;                             //临界区

         flag[ j ] = FALSE;                         //退出区

         remainder section;                     //剩余区

    具体如下：考虑进程  Pi ，一旦它设置 flag[ i ] = TRUE ,表示它想要进入临界区，同时 turn = j ,此时如果进程 Pj 已经在临界区中，则符合进程Pi 的while
循环条件，则Pi 不能进入临界区。而如果 Pj 进程没要进入临界区，即  flag[ j ] = FALSE ，循环条件不符合，则  Pi 进程可以顺利进入，反之亦然

    硬件实现方法
        硬件TSL 指令或swap（exchange）指令（略）

    信号量

    信号量机制
        整型信号量：最初由Dijkstra 把整型信号量定义为一个整型量，仅能通过初始化和两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。两个操作被分别称为P、V 操作(原语primitive)

    信号量（续1）

    P 原语wait(s); down(s); P(s)

--s.count; //表示申请一个资源; if (s.count <0) //表示没有空闲资
源;
{
    调用进程进入等待队列 s.queue;
    阻塞调用进程;
}

    信号量（续2）

    V 原语signal(s); up(s); V(s)

if (s.count <= 0) //表示有进程处于阻塞状态；
{
    从等待队列s.queue 中取出一个进程P;
    进程P 进入就绪队列;
}

    信号量（续3）

        用信号量可以实现互斥

type def semaphore；
semaphore S=1；
PROC1                     PROC2
P（S）；                   P（S）；
critical section          critical section
V（S）；                   V（S）；
remainder section         remainder section

    信号量（续4）

        用信号量可以实现同步

type def semaphore；
semaphore S=0；
PROC1                PROC2
                     P（S）；
produce data；       consume data；
V（S）；
remainder section    remainder section

    管程

    管程定义：一个数据结构a 和能为并发进程所运行的一组操作b，这组操作能同步进程和改变管程中的数据。

    管程由三部分组成
        共享数据说明a
        操作的一组过程b
        设置初始值

TYPE monitor_name = MONITOR；
共享变量说明
define 本管程内所定义、本管程外可调用的过程（函数）名字表
use 本管程外所定义、本管程内将调用的过程（函数）名字

PROCEDURE 过程名（形参表）；
过程局部变量说明；
BEGIN
语句序列；
END；

......

FUNCTION 函数名（形参表）：值类型；
函数局部变量说明；
BEGIN
语句序列；
END；

......

BEGIN
共享变量初始化语句序列；
END；

    经典的同步问题

    生产者-消费者问题
        利用信号量解决生产者—消费者问题

    经典的同步问题（续1）

      读者写者问题

    利用信号量解决读者-写者问题

 

    经典的同步问题（续2）

        哲学家进餐问题

    Philosophers eat/think
    Eating needs 2 forks
    Pick one fork at a time
    How to prevent deadlock

    让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。

send(i)
begin
if i mod 2 ==0 then               else
{                                 {
  P(c[i]);                            P(c[i+1 mod 5]);
  P(c[i+1 mod 5]);                    P(c[i]);
  eat;                                eat;
  V(c[i+1 mod 5]);                    V (c[i]);
  V (c[i]);                           V(c[i+1 mod 5]);
}                                 }
end

    死锁

    1.死锁的概念

    死锁定义

    同一进程集中的二个或以上的不同进程都在互相等待对方为自己释放资源因而造成的进程无法推进的现象

    死锁的概念（续1）

    产生死锁的原因
        互斥资源分配不当（造成剩余资源不足，非资源不足）
        进程间推进顺序不当

    死锁的概念（续1）

    产生死锁的四个必要条件
       互斥条件
       请求和保持条件
       不剥夺条件
       环路等待条件

    2.死锁处理策略

    根据系统宽容度和代价的不同而不同
        忽略死锁(鸵鸟算法)
        检测和解除死锁(有向图，矩阵: 剥夺资源)
        避免死锁(银行家算法)
        预防死锁(打破死锁的四个必要条件)

    3.死锁预防

    死锁预防（严格管制，处理在前）
        摒弃互斥条件
        摒弃“请求和保持” 条件
        摒弃“不剥夺” 条件
        摒弃“环路等待”

    4.死锁避免

    放松管制，只在分配资源时进行预测
    预测为安全状态时则分配资源
    预测为不安全状态时则推迟或拒绝分配资源

    4.死锁避免（续1）

    系统安全状态
    某一时刻，系统能按某种顺序，如P1、P2、…、Pn 来为每个进程分配其所需资源，使每个进程都能顺利地完成，则称此时系统处于安全状态。反之，称之为不安全状态。

    4.死锁避免（续2）

    银行家算法

    一个银行家把他的固定资金（capital）贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。
    利用银行家算法可以避免死锁

    5.死锁检测和解除

    放任系统，定期进行检测（2 种方法）
    若没有死锁则忽略
    若出现死锁则调用解除程序进行解除（4 种方法）
    解除时要考虑代价

    5.死锁检测和解除（续1）
    死锁的检测 1（资源有向图）
    出现环路并环路中的进程长时间阻塞

    5.死锁检测和解除（续2）
        死锁的检测 2（资源矩阵）
        资源不够分配
        进程集均阻塞

    5.死锁检测和解除（续3）

    死锁的解除
        剥夺资源
        回溯到还原点（需要编程配合）
        撤消进程
        重启系统 （代价最大）

---

亲爱的读者：有时间可以点赞评论一下