进程基础

进程基本概念

<font color = #0099ff> 进程组：只包括祖先进程，子孙进程，兄弟进程
进程树：所有进程
僵尸进程：在父进程中经常会调用waitpid来等待子进程终止，如果在父进程调用waitpid之前子进程就终止了，那么子进程就会成为僵尸进程，（因为这个时候子进程必须要等到父进程waitpid之后才能真正结束）
孤儿进程：父进程在子进程终止之前自己先终止了</font>

• 进程间通信只能在同一个进程组之间通信

进程的状态

进程诞生（此时进程还没有准备好）
进程init （进程初始化）
Active （活跃区）
僵尸态 （进程结束，开始收尸）

Active

在 Active中，存在三中不同的状态

• Running 运行态，当进程已获得处理机，其程序正在处理机上执行，此时的进程状态称为执行状态。
• Blocked 这个进程不具备继续运行下去的条件
• Ready 当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行，这时的进程状态称为就绪状态。（进程准备好了，但是缺少资源
  running 和 ready 两种状态统称为runnable
  在操作系统进行中，通过scheduler 控制进程在ready 和 running之间转换 执行 1 2 操作
  当程序发现自己运行不下去了的时候，进程会主动去睡觉，执行 3
  当其他进程使用完资源，叫醒sleep的线程，完成过程 4

进程的生命周期

进程创建

• 所有的进程的公共父进程是init，所有进程都直接或者间接被init进程创建
• 子进程通过父进程调用fork()函数创造，此时子进程享有的数据空间和指令指针和父亲完全一样，但是调用一次fork函数，有两个返回值，一个返回给父亲，如果创建成功返回子进程的pid，创建失败返回错误码。另一个返回给子进程，直接返回0。子进程继承到了父亲的大部分资源，但也不是全部继承，子进程不继承附近的子进程，但是父进程的堆栈，内存环境等都会继承。

进程结束

• 当一个父进程结束的时候，他的子进程也会被同时杀死

结束的可能情况

• 正常死亡 （自愿）完成任务之后死亡
• 出错退出 （自愿）遇到问题，程序自行结束生命
• 严重错误 （非自愿）出现严重错误，直接死亡
• 被杀死 （非自愿）一般是被族亲进程杀死或者root进程杀死

中断 （待完善）

进程的实现 （待完善）

维护了一张进程表（通过数组实现）在这个进程表当中保存了进程的重要信息

管理进程 （待完善）

shell

<font color = #0099ff>shell 是用户和计算机内核交互的接口</font>

前台进程和后台进程

前台进程主要和用户交互，优先级高些，后台进程基本不用和用户交互，优先级低一些。

进程调度

一 背景知识

调度策略

• 进程响应时间尽可能快
• 后台作业的吞吐量尽可能高
• 尽可能避免进程的饥饿现象
• 低优先级和高优先级进程的需要尽可能调和

进程饥饿

<font color= "#0099ff">进程饥饿：等待时间给进程推进和响应带来明显影响
饥饿死亡：饥饿到一定程度，使得进程即使完成了它本该完成的任务也无实际意义的时候称为饥饿死亡</font>

产生饥饿的主要原因

当资源分配不公平，无法保证等待时间上界的存在，即使系统没有发生死锁，但是有些进程仍需长时间等待，举个例子，当有多个进程需要打印文件时，如果系统分配打印机的策略是最短文件优先，那么长文件的打印任务将由于短文件的源源不断到来而被无限期推迟，导致最终的饥饿甚至饿死。

二 进程分类

进程分类

第一种

第二种

实时进程与普通进程

普通进程

上面表格当中的交互式进程和批处理进程统称为普通进程。普通进程的调度策略较为复杂

实时进程

实时进程采用FIFO的调度策略

调度器设计

进程调度器框架

两个调度器

可以用两种方法来激活调度

• 直接的，比如进程打算睡眠或者其他原因放弃CPU
• 通过周期性机制，以固定的频率运行，不时的检测是否有必要

linux的调度程序目前由两个调度器组成：主调度器，周期性调度器，两者统称为通用调度器或核心调度器
并且每个调度器都包含两个内容：调度框架，调度器类

六种调度策略

五个调度器类

依据不同的调度策略实现了五个调度器类，一个调度器类可以用一种或者多种调度策略调度某一类进程

所属进程的优先级为
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

三个调度实体

调度器不只限于调度进程，还可以实现组调度：可用的CPU时间现在进程组之间分配，再由进程组在组内二次分配
这就要求调度器不直接操作进程，而是处理可调度实体
这个调度实体可以是一个进程，也可以是一个进程组，用一个通用的数据结构来描述这个调度实体，下面是三种用于描述的调度实体

竞争条件和实现方式讨论

<font color= "#0099ff">
临界资源：该资源同一时间只能由一个进程使用（进程间不共享，如打印机）但是是共享资源，其他进程也可以用，只是不能同时用
临界区：访问临界资源的一段代码
竞争条件：两个进程访问同一个共享资源区，当一个进程先占用该资源区之后，其他进程无法访问该资源区。
</font>

进程间关系

• 互斥 不能同时使用，两个毫不相关的进程可能会因为抢占同一资源而发生关系
• 同步 两个进程之间在逻辑上存在先后关系，一个进程由于逻辑上等待另一个进程而发生关系

进程间其实就这两种基本关系，之后我们在考虑IPC问题的时候，首先就要分析进程之间是这两种关系当中的哪一种，然后再设计金成问题的解决方案。

实现方案讨论

解决方案应该满足的原则

• 任何两个进程不能同时处于临界区
• 不应对CPU的速度和数量做任何假设
• 临界区外的进程不得阻塞其他进程
• 不得使进程无限期的等待进入临界区

屏蔽中断

首先我们要清楚什么是中断，中断是cpu产生的用于暂停一个进程的运行，并且开启另一个线程的运行的指令。
屏蔽掉中断之后一个进程就会持续运行而不受CPu的管制，直到该进程放弃对CPu的占用。
通常情况下我们都不会屏蔽掉中断，我们也不会把屏蔽中断的权利交给普通的用户进程，因为这样可能会导致用户持续占用CPU。
但是在这里，我们假设我们的普通进程也可以屏蔽中断。这样我们就可以完美解决资源同时使用的问题。
但是把屏蔽中断的能力交个普通进程简直就是傻屌操作。

锁变量

这个时候我们想到我们用一个变量a，来表示该资源是否被占用，这样我们只需要在需要使用资源的时候查询a变量的状态就可以了。
看起来天衣无缝，但是我们考虑一下情况。
进程1先查询了锁变量，锁变量显示无人使用资源，
突然CPU开始执行进程2，进程2也开始查询，锁变量显示资源无人使用，然后进程2把锁变量置为1，并且使用了资源。
在进程2还没有放弃使用资源的时候，cpu开始执行了进程1，进程一并不知道自己刚才睡着了，直接就去使用了资源。
在这种情况下虽然设置了锁变量，但是还是存在两个进程同时使用资源的情况。

严格轮转法

上面的尝试解决方法因为没有明确谁可以使用资源，谁不能使用资源产生了冲突。
严格轮转法维护了一个数组，需要使用该资源的进程pid存入数组，使用完资源的进程pid移除数组。
之后锁变量按照数组中的pid严格轮转，如何严格轮转呢？
假如说数组中的进程有，1，2，3，资源的使用顺序就按照1，2，3循环，每个进程使用一段时间，直到有进程执行完他要执行的任务。
但是！
这种方法也有他的缺点，假如说轮到2进程使用资源，但是2进程在等待另外一个资源的释放，结果2进程就等着另一个资源，这个时候1，3进程也得跟着一起等，因为2进程不用，也轮不到他俩用，于是违反了** 临界区外的进程不得阻塞其他进程 **的规则。导致这个资源虽然
很抢手，但是也一直没人能使用该资源。
<font color = "#0099ff">补充两个定义
忙等待：连续测试一个变量值知道某个值出现为止，例如上面出现的1，3进程一直在查询锁变量是否到他们可以用的时候了。
自旋锁：用于忙等待的锁，称为自旋锁</font>

最终解决方案

信号量

信号量S表示一个资源被使用的情况，一个资源的份数是S的最大值，S的实际值表示现在有多少资源剩余.
而且信号量当中维护了一个存储等待使用资源的队列。当V原语唤醒的时候就会从这个队列中寻找激活谁。
对信号量的操作只有PV原语可以
当我们不需要信号量表示资源数量的功能的时候，即资源只有一份的时候我们使用互斥信号量。

PV原语

P原语和V原语
P原语是阻塞原语：当调用P原语时，如果信号量还有空闲，那么继续执行，如果信号量没有空闲，那么阻塞，直到V原语通知有新的资源可用。
V原语是唤醒原语：如果调用V原语之后，信号量不为满，即还有空位置可以放资源，那么唤醒一个P原语，如果全部占满，那么阻塞
其实PV原语本质是代码执行单元，在P原语和V原语的内部，在执行过程中是不会被打断的，所以这弥补了上面尝试的方法中锁变量的缺点。
PV原语代码。

P (Semaphore s)
{
    s=s-1;
    if (s<0)
    {
        added to the semaphore's queue and sleep;
    }
}

V (Semaphore s)
{
    s=s+1;
    if (s<=0)
    {
        wakeup the waiting process in the semaphore's queue;
    }
}

PV原语的使用

实现过程：
P(resource); // resource的初始值为该资源的个数N
使用该资源；
V(resource);
非临界区

IPC问题

我们上面讨论了一堆如何解决进程间同步和使用互斥资源的解决方案，但是我们在实际当中都会遇到哪些问题呢？
接下来这部分我们讨论的是如何解决IPC问题即（I）进程间通信问题

生产者消费者问题

问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。

问题分析

生产者和消费者不能同时访问临界区，这是互斥关系
只有当生产者生产出来产品之后，消费者才能购买，这说明两者之间还有同步关系。

解决代码

用两对PV原语去解决问题，一组申请临界区资源，一组申请单独访问权限

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer () { //生产者进程
    while(1){
        produce an item in nextp;  //生产数据
        P(empty);  //获取空缓冲区单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //满缓冲区数加1
    }
}

consumer () {  //消费者进程
    while(1){
        P(full);  //获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从缓冲区中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空缓冲区数加1
        consume the item;  //消费数据
    }
}

哲学家就餐问题

问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭，如图所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、 右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

同一个哲学家必须同时有能拿到左右两侧的筷子的权限，再拿起，如果只有一侧，那么先不拿起。
下面的这种实现方法在同一时间只有一个哲学家在尝试拿筷子。虽然造成了一定程度上的性能浪费。
哲学家的左右筷子具有同步性，哲学家与哲学家之间具有互斥性。

解决代码

semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=1; //设置取筷子的信号量
Pi(){ //i号哲学家的进程
while(1)
{
P (mutex) ; //在取筷子前获得互斥量 通过这一步使取左右筷子时不会被其他人打断，如果只有取左右筷子的代码，很容易发生死锁。
P (chopstick [i]) ; //取左边筷子
P (chopstick[ (i+1) %5]) ; //取右边筷子
V (mutex) ; //释放取筷子的信号量
eat; //进餐
V(chopstick[i] ) ; //放回左边筷子
V(chopstick[ (i+l)%5]) ; //放回右边筷子
think; // 思考
}
}

读者写者问题

问题描述

一个作者在写的时候，读者不能读，其他作者不能写
读者在读的时候作者不能写，但是其他读者也可以读。

问题分析

作者和读者以及作者和作者之间都是互斥且同步的关系.
读者和读者之间没有关系。

解决代码

Semaphore mutex, wrt=1,1;
int readcount=0;
void Writer(void)
{
    Down(wrt);
    Perform writing;
    Up(wrt);
}
void Reader(void)
{
    Down(mutex);    //这个防止了两个Reader同时给wrt加锁的问题。
    readcount=readcount+1;
    if(readcount == 1)
        Down(wrt);    //这解决了与读者之间的互斥关系。
    Up(mutex);
    Perform reading;
    Down(mutex);
    readcount=readcount-1;
    if(readcount == 0)
        Up(wrt);
    Up(mutex);
}

睡眠的理发师问题

问题描述

1、5把供顾客等候的椅子
2、一个理发师同时只能给一个顾客理发
3、没有顾客，理发师进入睡眠状态。

问题分析

顾客和顾客之间是互斥的
只有一个理发师，理发师的资源是1
理发师和顾客的关系是同步。

解决代码

int waiting=0 ； //等候理发的顾客数
int chairs=n； //为顾客准备的椅子数
semaphore customers=0, barbers=0,mutex=1;
barber()
{
while(TRUE); //理完一人,还有顾客吗?
P(cutomers); //若无顾客,理发师睡眠
P(mutex); //进程互斥
waiting := waiting – 1; //等候顾客数少一个
V(barbers); //理发师去为一个顾客理发
V(mutex); //开放临界区
cut-hair( ); //正在理发}
customer()
{
P(mutex); //进程互斥
if (waiting)
{ waiting := waiting+1; // 等候顾客数加1
V(customers); //必要的话唤醒理发师
V(mutex); //开放临界区
P(barbers); //无理发师, 顾客坐着养神
get-haircut( ); //一个顾客坐下等理/ }
else
V(mutex); //人满了,走吧!}