Sean's Blog
0%

OS-进程

发表于 更新于 分类于 ，

参考教材：《操作系统——精髓与设计原理》（第八版）

chp3进程描述与控制

简答

一、进程概念

  • 概念：进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位。进程就是程序的执行过程。
  • vs程序
    • 进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时存在的；而程序则是一组代码的集合，他是永久存在的，可长期保存。
    • 进程具有并发性，而程序没有；
    • 一个程序可对应多个进程； 一个进程可以执行一个程序或多个程序

二、进程控制块PCB

  • 内容：
    • 标识符：进程的唯一标识符
    • 状态：阻塞态/运行态
    • 进程控制信息
  • 重要性：是操作系统为支持多线程并提供多重处理技术的关键工具。可以在中断后恢复进程的执行。

三、操作系统为进程提供了哪些支持

  • 操作系统维护了一组队列，表示系统中所有进程的当前状态。简单来说，每个进程的PCB都根据它的状态加入到相应的队列中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另一个队列。
  • 创建进程、调度

四、程序如何变成进程的，及其在内存中的状态

  1. 操作系统将程序读入内存，为程序映射分配内存空间；
  2. 操作系统向内核数据结构中添加了适当的信息，并为运行程序代码分配了必要的资源之后，程序就变成了进程。
  3. 跳转到入口函数，OS将CPU控制权交给新创建的进程，进程获取到CPU后就可以执行了。
  4. 程序在内存中的状态：img
  5. 进程映像在虚存中的结构：PCB+用户栈+进程专用地址空间（程序、数据）+内核栈+共享地址空间

五、进程控制的相关系统调用

系统调用：此时CPU为内核态

在这里插入图片描述

  • 创建：Fork创建一个新的进程并分配pid；
  • 销毁：Exit终止运行中的进程，变为退出状态；
  • 切换：Wait导致进程由运行态变为等待态，操作系统根据调度算法将CPU交给下一个进程

六、进程创建

以Fork为例

  • Fork创建一个继承的子进程：
    • 分配标识符、PCB
    • 复制父进程的变量和内存
    • 将进程设为就绪态，放入就绪队列
  • 调用一次，返回两次：子进程返回0，父进程返回子进程标识符

*七、五状态模型

img

传统的五状态模型

  • 创建态：PCB已创建但还未加载到内存中的新进程→
  • 就绪态：进入就绪队列，等待CPU的调度
  • 运行态：进程正在处理器上执行
  • 阻塞/等待态：进程因正在等待某些事件而暂停执行，如等待IO操作完成；
  • 退出态：操作系统释放进程

八、进程/上下文切换

  • 从OS的角度看：操作系统从就绪队列中选出下一个进程并把CPU控制权交给它；
  • 从cpu的角度看：寄存器先把当前进程的命令位置记录下来，然后保存起来，接着把当前进程的命令位置替换成内核态的指令的新位置，然后跳转到内核态执行任务，当系统调用结束后，还要切换回用户态继续执行
  • 从任何一个进程的角度：？？？

九、模式/态(mode)的切换

进程切换与模式切换 - xd_xumaomao - 博客园 (cnblogs.com)

  • 用户模式到内核模式由中断/异常(如缺页故障)/系统调用 中断用户进程执行而触发
  • 内核模式到用户模式由OS执行中断返回指令将控制权交还用户进程而触发

选择

  • CPU的mode
    • 当执行应用程序(用户程序时)：user mode
  • 进程的五状态模型
    • 点，边
    • 导致新建态的产生：新的批处理作业提交、新的用户登录、现有进程创建子进程
    • 导致退出态：执行了无效指令、系统管理员终止了它、父进程终止
  • 新进程的创建步骤：
    • 为新进程分配新的内存地址空间
    • 为新进程分配唯一的进程标识符
    • 初始化新进程的进程控制块PCB
  • 进程切换必须在操作系统内核模式下完成，这就需要模式切换。即有进程切换，一定有处理器态的切换。
  • 进程切换可能发生在：时钟中断、系统调用、缺页故障
  • 一些中断/异常不会引起进程状态转换，不会引起进程切换，只是在处理完成后把控制权交回给被中断进程
  • 进程两状态模型：运行态、非运行态
  • 多道环境下：
    • 单个进程的行为，可由单个进程的轨迹来进行描述；
    • CPU的行为可由多个进程轨迹交替执行来描述

others

七状态模型

增加了挂起状态

状态模型

chp4线程

简答

*一、线程的概念，与进程的关系

  • 线程是进程的一条执行流程。是操作系统调度和分派的单位；
  • vs进程：
    • 进程是资源分配的单位，线程是调度的单位。
    • 一个进程有一个或多个线程；
    • 线程有就绪、阻塞、执行状态及状态转换
  • 是轻量级进程：线程创建，终止时间比较短；同样具有就绪，阻塞和执行三种基本状态，同样具有状态之间的转换。

二、？？？

*三、线程的实现方式&四、ULT和KLT的优缺点

[线程的实现方式 - 云+社区 - 腾讯云 (tencent.com)](https://cloud.tencent.com/developer/article/1350257#:~:text=一、线程的三种实现方式 1 使用内核线程实现,2 使用用户线程实现 3 使用用户线程加轻量级进程混合实现)

  1. 内核线程KLT，一对一线程模型
    img
  2. 用户线程ULT，一对多线程模型
    img
  3. 用户线程加轻量级进程混合实现，N:M线程模型img
实现方式 描述 优点 缺点
内核线程实现
KLT		 直接由操作系统内核支持的线程，由内核来完成线程切换，内核通过操纵调度器（Scheduler）对线程进行调度，并负责将线程的任务映射到各个处理器上。程序一般不会去直接使用内核线程，而是去使用内核线程的一种高级接口——轻量级进程（Light Weight Process，LWP） 内核线程保证了每个轻量级进程都成为一个独立的调度单元，即使有一个轻量级进程在系统调用中阻塞了，也不会影响整个进程的继续工作。 1.系统调用代价高，需要在用户态和内核态来回切换；
2.轻量级进程要消耗一定的内核资源，一个系统支持轻量级进程的数量是有限的
用户线程实现
ULT		 完全建立在用户空间的线程库上，系统内核不能感知线程存在的实现。用户线程的建立、同步、销毁和调度完全在用户态中完成 不需要切换内核态，效率非常高且低消耗；
可以支持规模更大的线程数量		 由于没有系统内核的支援，阻塞处理等问题的解决十分困难
混合 用户线程与轻量级进程的数量比是不定的，线程创建完全在用户空间完成，线程的调度和同步也在应用程序中进行；一个程序中的多个用户级线程会被映射到内核级线程 应用程序可以使用内核提供的线程调度功能及处理器映射；
同一个用户程序中的多个线程可以在多个处理器上并行，某一线程阻塞不会阻塞整个进程

五、Linux线程的系统调用机制

  • pthread_create创建线程
  • pthread_exit退出线程
  • pthread_join阻塞回收子线程
  • pthread_cancel杀死线程

选择

  • 资源所有权for进程，调度/执行for线程
  • 创建线程、线程切换、终止线程都比直接操作进程花费的时间更少
  • 线程包含CPU线程，可以独立执行程序
  • 线程共享进程的地址空间
  • Linux中，线程:进程=M:1
  • 与线程状态改变的4种基本操作
    • 派生：线程可在同一进程中派生另一个线程
    • 阻塞：线程需要等待一个事件时
    • 解除阻塞：事件发生，移到就绪队列
    • 结束
  • 线程同步：使线程访问同一进程的共享资源时不产生冲突
    • 线程有各自的PCB（进程控制块）

chp5互斥和同步

简答

*一、互斥和同步的解决办法&二、硬件方法解决

操作系统（三）—进程管理 - 知乎 (zhihu.com)

  • 软件方法

    • Dekker算法-2个进程
    • Peterson算法-N个进程

  • 硬件方法

    • 关中断/中断禁用：（单处理器机器）处理器只能交替执行并发进程，不能重叠；让硬件将中断处理延迟到中断启用后。在临界区内，没有中断，没有上下文切换，因此没有并发。
    • 特殊指令：（多处理配置）保证原子性，将两个动作结合到一个指令周期。

      • testset：进入临界区之前，首先用TS指令测试lock，如果为false，则表示空闲，将lock赋为true，关闭临界资源；如果TestAndSet返回true，则一直循环测试，直到返回false，跳出循环，进入临界区。基于这个指令，我们可以实现获取资源和释放资源的操作。

      • exchange/swap

        1
        2
        3
        4
        5
        6
        void exchange_swap(int register, int memory) { 
            int temp; 
            temp = memory; 
            memory = register; 
            register = temp; 
        }

  • OS/开发语言提供的机制

    • 信号量：互斥+条件同步，容易造成死锁
    • 管程=共享资源数据结构+对数据结构的操作，利用少量的共享数据结构抽象的表示系统中共享资源，并且讲对该共享数据结构的特定操作定义为一组过程。对于共享资源的访问必须通过这组过程，每次只有一个进程进入管程。

三、条件竞争

  • 发生在多个进程或线程读写数据时，其最终结果取决于多个线程的指令执行顺序
  • 举例
    • 输入-赋值-输出
      image-20220601224853485
    • 算术运算

*四、信号量解决生产者/消费者问题

1.使用二元信号量解决无限缓冲区：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n;
binary_semaphore s=1,delay=0;//定义s只能为01来实现互斥（存商品和取商品之间），delay用于迫使消费者在缓冲区为空的时候等待
void producer(){
    while(true){
        produce();	//生产商品不属于共享资源
        semWaitB(s);
        append();	//将商品存入仓库属于临界资源
        n++;
        if(n==1) semSignalB(delay);	//当n=1表示这是仓库为空后存入的第一个商品
        semSignalB(s);
    }
}
void consumer(){
    int m;
	semWaitB(delay);	//仓库不为空后唤醒消费者
    while(true){
        semWaitB(s);
        take();	//取商品属于临界资源
        n--;
        m=n;
        semSignalB(s);
        consume();	//消费商品不属于临界资源
        if(m==0) semWaitB(delay);	//n=0表示仓库为空了
    }
}
void main(){
    n=0;	//初始化仓库内有n个产品
    parbegin(producer,consumer);
}

2.使用一般/计数信号量实现无限缓冲区:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
semaphore n=0,s=1;
void producer(){
    while(true){
        produce();
        semWait(s);
        append();
        semSignal(s);
        semSignal(n);
    }
}
void consumer(){
    while(true){
        semWait(n);
        semWait(s);
        take();
        semSignal(s);
        consume();
    }
}

3.使用信号量解决有限缓冲区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int sizeofbuffer="缓冲区大小";
semaphore s=1,n=0,e=sizeofbuffer;
void producer(){
    while(true){
        produce();
        semWait(e);
        semWait(s);
        append();
        semSignal(s);
        semSignal(n);
    }
}
void consumer(){
    while(true){
        semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e);
        consume();
    }
}

*五、并发的四个问题及解决办法

【Linux】—互斥与同步、死锁与饥饿、实现生产者消费者模型、常见锁类型_想去吹吹海风的博客-CSDN博客_互斥死锁饥饿

问题 描述 解决
互斥 为了保证多个线程或进程访问同一份资源时，保证不产生数据二义性，用原子性的操作，去限制一部分线程的访问。 1.软件方法（Dekker，Peterson）；2.硬件方法（关中断，专用指令）
同步 为了保证各个线程之间互斥访问共享资源的顺序合理且高效，用条件变量和信号量（原子性操作）去安排访问顺序。 信号量
饥饿 由于竞争条件不平等，与其他进程或线程竞争访问共享资源运行期间，被调度器无限忽视，无法访问共享资源的情况，称为饥饿。 哲学家就餐问题
死锁 两个或两个以上的进程（LWP）都在等待互相释放自己的资源，导致进程都不能继续执行的情形 1.死锁预防；2.死锁避免；3.死锁检测与解除（

选择

  • 为了实现互斥：
    • 同一时间只允许一个程序进入程序的临界区
    • 一个进程驻留在临界区中的时间是有限的
    • 对进程执行速度无要求
  • 临界区指并发进程中访问共享变量的代码段
  • 生产者和消费者同时是读者和写者

chp6死锁和饥饿

可重用资源：可被多个进程多次使用
（1）可抢占资源（处理器CPU）与不可抢占资源（打印机）
（2）处理器、I/O部件、内存、文件、数据库、信号量
可消耗资源：只可以使用一次、可创建和销毁的资源
（1）信号、中断、消息

简答

一、死锁的概念和举例

  • 概念：当一组进程中的每个进程都在等待某个事件（如等待释放所请求的资源），而仅有这组进程中被阻塞的其他进程才可触发该事件时，就称这组进程发生了死锁。
  • 举例：
    • 独木桥。A，B都要过独木桥，但是互不退让，僵死。
    • 十字路口。A，B，C，D四辆车各占据一个资源，且由于所需要的第二个资源被另一辆汽车占有，因此他们都不能通行。

二、数学方法描述死锁

三、死锁的条件

  • 互斥。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。
  • 占有且等待。当一个进程等待其他进程时，继续占有已分配的资源。
  • 不可抢占。不能强行抢占进程已占有的资源。
  • 循环等待。存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

*四、死锁的解决办法

死锁的产生、防止、避免、检测和解除 - 知乎 (zhihu.com)

  • 死锁预防：破坏死锁的四个条件，但是都会导致低效的资源使用和低效的进程执行。
    • 互斥：使资源同时访问而非互斥使用，就没有进程会阻塞在资源上，从而不发生死锁。比如可以同时多个读访问，但是写访问必须互斥，因此很多操作不能破坏该条件。
      • 一般来说，第一个条件不可能禁止。
    • 占有且等待：要求进程一次性地请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足。
      • 低效：1.可能被阻塞很久；2.请求满足后占有该资源但是可能在很长时间内不使用，此时其他进程也不能使用
      • 该进程可能事先并不知道它所需要的所有资源
    • 不可抢占：
      • 若请求资源被拒绝，则释放之前占有的资源（必要时可再次请求）
      • 请求被其他进程占用的资源时，操作系统可以根据优先级进行抢占。（俩进程优先级必须不同）
      • 适用情况：资源状态可以很容易地保存和恢复的情况下。
    • 循环等待：定义资源类型的线性顺序。
      • 低效：1.使进程执行速度变慢；2.可能在没有必要的情况下拒绝资源访问。
  • 死锁避免：允许前三个条件，通过选择确保不会到达死锁点。需要知道未来进程资源请求的情况。
    • 若一个进程的请求会导致死锁，则不启动该进程；
    • 若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。
  • 死锁检测和恢复
    • 检测-进程资源分配图
      • 无环路：无死锁
      • 有环路
        • 每种资源类中仅有一个资源，则系统发生了死锁。
        • 每种资源类中有多个资源，则环路的存在只是产生死锁的必要不充分条件，系统未必会发生死锁。
    • 恢复
      • 资源剥夺
      • 进程回退
      • 进程撤销：1.CPU消耗时间最少者 2.产生的输出量最小者 3.预计剩余执行时间最长者 4.分得的资源数量最少者 5.优先级最低者
      • 系统重启

*五、银行家算法

操作系统——银行家算法（Banker’s Algorithm） - 王陸 - 博客园 (cnblogs.com)

  • 安全状态：至少有一个资源分配序列不会导致死锁。
  • 不安全状态：不一定是死锁状态
  • 系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态。

img

银行家算法是死锁避免算法。实质是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。

两个向量：

  • Resource：资源总数
  • Available：分配后还剩的

两个矩阵：

  • Claim：进程需要的资源数
  • Allocation：已分配的资源数

计算

有进程P1,P2,P3,P4,P5, 资源R1,R2,R3,R4, 当前可用资源数Available(R1,R2,R3,R4)=(2,1,0,0), 已分配情况如下：

image-20220623001456593

  1. 分别计算仍然需要=最大需求-当前分配
    image-20220623001756750
  2. 选择可以分配资源且不造成死锁的进程
    1. 选择P1后，P1顺利执行完毕并释放已占有资源，即Available=(2 1 0 0) + (0 0 1 2) =(2,1,1,2)
    2. 选择P4,顺利结束后 Available=(2 1 1 2) + (2 3 5 4) = (4 4 6 6)
    3. 选择P5，Available=(4 4 6 6) + (0 3 3 2) = (4 7 9 8)
    4. 选择P2，Available=(4 7 9 8 ) + (2 0 0 0) = (6 7 9 8)
    5. 选择P3，Available=(6 7 9 8 ) + (0 0 3 4 )= (6 7 12 12)

ps：1.如果所拥有的可用资源可支持多个进程，选其一；2.如果没有满足条件的，则为不安全状态

选择

  • 可消耗资源：可以创建和销毁，如消息？
  • 死锁恢复中选择特定进程中止或回滚
    • 已分配的总资源最少
    • 最低优先级
    • 预计剩余时间最长