进程与线程（一）

一、进程

1.进程是在系统中能独立运行并作为资源分配的基本单位。

Tips:并行是指在同一时刻多个事件一起执行，并发是指在同一时间间隔中多个事件一起执行。

2.进程控制块（process control block，PCB）：用于描述进程的基本信息和运行状况。

  • 进程控制块（PCB）、程序段和相关数据段构成了进程实体，也就是我们常说的进程。

  • 通常我们所说的创建进程和撤销进程实质上是对进程实体中的进程控制块进行创建和撤销。

  • 进程控制块PCB包含：

    • 进程描述信息：进程标识符PID，用户标识符UID。

    • 进程控制和管理信息：进程当前状态，进程优先级等。

    • 资源分配清单：代码段指针、堆栈段指针、数据段指针等，鼠标键盘也是。

    • 处理机相关信息：各种寄存器的值。

  • 进程的特性：

    • 并发性

    • 动态性

    • 独立性

    • 异步性

3.进程的基本状态

  • 就绪状态：进程已经准备好了除CPU以外的所有资源，等待调度。通常将这些进程按照一定策略（优先级策略）排成队列，称为就绪队列。

  • 运行状态：进程获取CPU，程序处于执行状态。

  • 阻塞状态：进程由于发生了某件事（I/O请求，申请缓冲区失败等）而无法继续执行处于暂停状态。同时这些进程也被排成一个阻塞队列，等待资源。


    图片1.png

Tips：只有就绪状态和执行状态可以互相转换。

  • 创建状态：通常指创建一个空白的PCB，然后往其中写入控制和管理进程的信息。然后申请到满足运行所需的资源后将其加入就绪队列中。

  • 结束状态：当进程自然结束或者是被操作系统终结，会将PCB清空，然后返还空间给系统。

后两个状态不一定加。

二、线程

1.线程是独立调度的基本单位。

  • 一个进程中有多个线程共享资源。

  • 线程具有多种进程的特点，因此也称为轻型进程。

  • 引入进程是为了让程序能够并发执行，提高资源利用率。（所以是资源分配的基本单位）

  • 引入线程是为了减少程序并发执行过程中的时空开销，使OS具有更好的并发性。（所以是调度和分派的基本单位）

2.线程状态与进程3大状态一样，包括转换。

三、进程与线程的区别

1.调度

  • 传统操作系统中，进程是独立调度和拥有资源的基本单位。在引入线程的操作系统中，线程是独立调度的基本单位，进程是资源分配的基本单位。

  • 同一个进程中的线程切换不会引起进程切换，但是从一个进程中的线程切换到另外一个进程中的线程时，会引起进程切换。

2.拥有资源

  • 进程是资源分配的基本单位，拥有资源。

  • 线程本身不拥有系统资源，仅有一些必不可少，保证独立运行的资源（TCB，计数器，局部变量，寄存器和堆栈）。但是线程可以访问隶属进程的系统资源。

ps：如果线程也可以拥有资源，那么线程切换的开销也就很大了，引入线程就没有太大的意义了。

3.系统开销

  • 在创建或撤销进程的时候，系统要为其分配或回收进程控制块、内存空间和I/O设备等资源，开销远大于创建或撤销线程所需的开销。

  • 切换进程的时候涉及到上下文切换（当前进程的CPU运行环境和新调度进程的CPU运行环境的切换），所以开销很大，但是切换线程的时候仅需要保存和设置少量寄存器内容，开销极小。

4.通信方式

  • 进程间通信(IPC)需要使用进程同步和互斥的手段辅助。

  • 线程之间可以直接读写同一个进程的数据来进行通信。

四、线程的实现

1.内核级线程（Kernel Level Threads）

  • 内核级线程是在内核空间实现的，线程的创建、撤销、切换和阻塞等都是由内核完成的，应用程序是没有线程管理的代码的，只有一个到内核级线程的接口。

  • 对于内核级线程而言，调度的基本单位是线程。

  • 缺点：对于用户的线程切换而言，模式切换的开销较大。在同一个进程中，当从一个线程切换到另外一个线程时，需要从用户态转到核心态进行，因为用户的线程是在用户态运行的，但是线程的调度和管理是在内核实现的。

2.用户级线程（User Level Threads）

  • 用户级线程是在用户空间实现的，线程的创建、撤销、阻塞和切换都无需内核的支持，用户级线程是和内核无关的。

  • 缺点：对于用户级线程而言，由于内核意识不到线程的存在，所以调度的基本单位还是进程，这样对各进程中的线程是不公平的。比如：A进程有1个用户级线程，B进程有100个用户级线程，采用轮转调度算法的时候，A中线程运行时常是B中的100倍。但如果采用内核级线程，那么直接分给B的时间片就是分给A的100倍了。

3.组合方式的实现（多线程模型）

  • 用户级线程和内核级线程组合实现。

  • 多对一模型：将多个用户级线程映射到一个内核级线程上，线程管理在用户空间完成，此模式中用户级线程对操作系统来说是不可见的。

    • 优点：线程管理在用户空间进行，效率较高。

    • 缺点：当一个线程使用内核服务的时候被阻塞，内核进程也会被阻塞。多个线程不能并行的运行在多处理机上。

  • 一对一模型：每个用户线程映射到一个内核级线程上。

    • 优点：当一个线程被阻塞的时候，其他线程继续执行，并发能力强。

    • 缺点：每创建一个用户级线程都要创建一个内核级线程对应，开销较大。

  • 多对多模型（m>=n）：将m个用户级线程映射到n个内核级线程上。

    • 克服了多对一并发低的缺点，也克服了一对一创建线程开销大的缺点，同时拥有两种模型的优点。

五、进程调度算法

进程调度又称低级调度，主要任务是按照某种方法和策略从就绪队列中选择一个进程分配处理机。

进程调度方式可以分为：

  • 非抢占式：一旦处理机分配给了进程，只有当进程完成或者因为其他原因阻塞才会将处理机分配给其他进程。

  • 抢占式：基于一定原则，允许进程抢占正在运行的进程的处理机，以防一个进程占用太久处理机，原则有：

    • 优先级

    • 短进程优先：当新到进程的执行时间比正在运行进程剩余时间短的话，就允许抢占。

    • 时间片原则：时间片结束就重新调度。

1.先来先服务(first come first serverd，FCFS)调度算法

  • 是一种非抢占式的调度算法，FCFS调度算法每次从就绪队列中选择最先进入队列的进程，并将处理机分配给它。

  • 特点是算法简单，但是效率低，对长作业有优势，对短作业不友好，短作业需要等到长作业完全结束才能运行，造成短作业等待时间过长。因此实际使用的时候结合其他调度策略，比如优先级调度策略，对于优先级相同的进程采用先到先服务处理。

2.短作业优先(short job first，SJF)调度算法

  • 短作业（进程）优先算法，是一种非抢占式的调度算法，从就绪队列中选择一个预估运行时间最短的进程，给其分配处理机。

  • 特点是利于短作业，一旦就绪队列中有长作业，很可能因为总是优先调度短作业，导致长作业长期不被调度，处于饥饿状态。对于作业的紧迫程度并未考虑。

3.最短剩余时间优先（short remaining time next，SRTF）调度算法

  • 是短作业优先调度算法的抢占式调度算法，当有新进程到达，将其运行时间与正在运行的进程的剩余时间相比，如果较短，就将正在运行的进程挂起，运行新进程；如果较长就将新进程放入等待队列中。

4.高响应比优先调度算法

  • 是FCFS和SJF调度算法的结合，同时考虑每个进程的服务时间和等待时间。响应比=（要求服务时间+等待时间）/要求服务时间。

  • 根据公式我们可知，如果等待时间相同，要求服务时间越短的响应比越高，优先级越高，利于短进程。

  • 如果要求服务时间相同，等待时间越长，响应比越高，实现了先到先服务的思想。

  • 对于长作业，只要等待时间足够久，响应比足够高就能克服饥饿状态。

5.时间片轮转调度算法

  • 时间片轮转调度算法用于分时系统，根据先来先服务原则，根据进程到达时间排成就绪队列，将处理机分配给队首进程，队首进程执行完一个时间片后，计时器发出时钟中断，调用程序停止该进程，并将它放到就绪队列的末尾，继续把处理机分配给就绪队列队首进程。

  • 如果时间片太大，将导致所有进程都在时间片结束前完成，退化成FCFS。

  • 如果时间片太小，所有进程都只能执行一部分就被调用程序停止放到队尾，处理机的频繁切换使得花在切换上的时间太多，处理机真正用于进程的时间变少。

  • 时间片设置一般取决于：响应时间，队列中的进程数目，系统处理能力等。

6.优先级调度算法

  • 按抢占进程可以分为：

    • 抢占式优先级调度：如果有优先级更高的进程进入等待队列，立即暂停正在执行的进程，将处理机分配给新来的进程。

    • 非抢占优先级调度：即便有新到的优先级更高的进程，依然等待当前进程执行结束或者被阻塞才可以获得处理机。

  • 按可否改变可以分成：

    • 静态优先级调度：优先级一旦赋予将无法改变。

    • 动态优先级调度：就绪队列里进程的优先级可以根据进程情况改变，改变的依据主要有进程占有处理机时间，进程等待处理机的时间等。

7.多级反馈队列

  • 是时间片轮转和优先级调度算法的结合。有多个就绪队列，每个就绪队列的优先级不同，且使用的时间片长短也不同。从上往下时间片越来越大，优先级越来越低。比如第1级队列的进程如果时间片结束之前未完成，会被放入第2级队列，只有等到一级队列全空才会去调用下一级队列。但是一旦有优先级高的队列进入新进程，会被抢占处理机。被抢占的进程会放到当前队列的队尾。

  • 优势

    • 短作业优先

    • 周转时间较短，即时间片大小不相同，处理机不会频繁切换（针对时间片轮转调度算法中时间片太短问题）

    • 不会使长作业饥饿

六、进程同步

多道程序的情况下进程是并发执行的，为了协调进程间制约关系，引入进程同步概念。比如1+2*3，分为加法进程和乘法进程，如果不进行协调就可能发生加法发生在乘法之前。

1.临界资源

  • 一次仅允许一个进程访问的资源称为临界资源，打印机等物理设备是临界资源，还有些变量啥的也是临界资源。存放临界资源的代码称为临界区。

  • 为了互斥访问临界资源，分为三部分

entry section   //进入区，检查能否访问临界区，可以就设置正在访问的标志阻止其他进程访问
critical section //临界区
exit section  //离开区 ，离开后清除正在访问标志，允许其他进程访问

2.同步

  • 进程间的直接制约关系，有工作次序。比如A通过缓冲区向B提供数据，如果缓冲区空，B拿不到数据被阻塞，A传入数据B被唤醒。缓冲区满，A无法写入数据被阻塞，B取走数据，唤醒A。

3.互斥

  • 进程间的间接制约关系。比如访问临界资源。有以下4个要点：

    • 空闲让进

    • 忙则等待

    • 有限等待，保证请求资源的进程在有限时间内能访问到。

    • 让权等待，当进程不能进入临界区的时候就释放处理机，防止忙等待。（可能是设置了访问标志，但是还没访问就被阻塞，其他进程没办法访问，以上为个人理解）

4.信号量

信号量是一个整型变量，可以进行wait()，signal()操作（P，V或者down,up）操作。

  • wait：如果信号量大于0，执行-1操作，如果信号量=0，进程被阻塞，进入就绪队列等待唤醒（信号量>0）。用资源来理解就是拿走了资源或者消费了资源。

  • signal：对信号量执行+1操作，如果信号量为0，执行后可以唤醒被阻塞的进程。用资源来理解就是释放了资源或者生产了资源。

如果信号量只能取0，1那么就是互斥量，0表示临界区加锁，1表示临界区解锁。

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

5.管程

使用信号量访问资源的时候要进行同步操作，大量的同步操作就被分散在各个进程中，而且可能因为同步进程使用不当造成死锁，于是使用管程将控制管理的代码独立出来，不仅不容易出错，也更容易管理了。

管程：由一组数据以及定义在这组数据上的操作组成的一种软件模块，这组操作能够初始化管程中的数据和同步进程。

  • 局部于管程的数据只能被局部于管程内的过程所访问。

  • 一个进程只有通过管程的过程才能进入管程访问管程中的共享数据。

  • 每次仅允许一个进程在管程内执行某个内部过程。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

七、经典同步问题

1.生产者消费者问题

生产者消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的 数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

2.读者写者问题

  1. 允许多个读者同时读文件

  2. 只允许一个写者往文件中写入

  3. 写者在写入的时候禁止读者和写者操作

  • 可以分析，写者进程和任何进程是互斥的，读者和写者是互斥的但是读者和读者是同步的。因此读者和读者需要个计数器来计算有多少读者在读。
int count=0; //计数器
semaphore mutex=1;  //计数器互斥量
semaphore rw=1;  //读写互斥量
writer(){
    while(true){
        P(rw);
        write;
        V(rw);
    }
}
Reader(){
    while(true){
        P(mutex);
        if(count==0)
            P(rw);
        count++;
        V(mutex);
        read;
        P(mutex);
        count--;
        if(count==0)
            V(rw);
        V(mutex);
    }
}

3.哲学家问题

五个哲学家坐在桌子上，两人之间有一个筷子，要同时拥有两个筷子才能进餐，那么就有可能造成饥饿或者死锁。

解决办法：

  • 同时拿起左右筷子

  • 按一定策略拿

    • 必须同时拿起左右两根筷子。

    • 只有在两个邻居都没有进餐的情况下才允许进餐。

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,589评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,615评论 3赞 396
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 165,933评论 0赞 356
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,976评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,999评论 6赞 393
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,775评论 1赞 307
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,474评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,359评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,854评论 1赞 317
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,007评论 3赞 338
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,146评论 1赞 351
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,826评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,484评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,029评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,153评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,420评论 3赞 373
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,107评论 2赞 356