操作系统-进程与线程

操作系统 进程与线程
操作系统
发布日期:   2024-01-19
更新日期:   2024-01-29
文章字数:   6.3k

进程的概念

为了让使参与的每个程序都能独立地运行，为之专门配置的一个数据结构就称为进程块（Process Control Block, PCB）。而由程序段、相关数据段和PCB三部分构成了进程实体（又称进程映像）。

PCB是进程存在的唯一标识，当进程被创建时，操作系统会为其创建PCB，结束后会回收其PCB。

若执行相同的三个程序，此时会将三个程序载入进程，它们的PCB、数据段各不相同，但程序段的内容都是相同的。

进程的状态与转换

进程通常有以下几种状态：

  1. 运行态。进程正在处理机上运行。
  2. 就绪态。进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。
  3. 阻塞态。又称等待态，进程正在等待某一事件（不是在等待CPU处理完成）而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使根据阻塞原因的不同，可设置多个阻塞队列。
  4. 创建态。进程正在被创建，尚未转到就绪态。
  5. 终止态。进程正从系统中小时，可能是进程正常结束或其他原因推出运行。

由于进程的整个生命周期都在运行态、就绪态、阻塞态三种状态，所以也称这三状态为基本状态。

进程控制

进程控制主要是对系统中的所有进程实施有效的管理，可为了保证进程连续，一般进程控制会用原语（即运行时不可被中断，通过关中断指令和开中断指令实现）来实现。

进程的创建

进程创建需要使用创建原语，即：

  1. 申请空白PCB。
  2. 为新进程分配所需资源。
  3. 初始化PCB。
  4. 将PCB插入就绪队列

当用户登录、作业调度（把外存中的应用运行到CPU上）、提供服务、应用请求时会引起进程创建。

进程的终止

在进程结束前需要使用撤销原语来撤销事件，即

  1. 从PCB集合中找到终止进程的PCB
  2. 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程。
  3. 终止其所有子进程
  4. 将其进程拥有的所有资源归还给父进程或操作系统。
  5. 删除PCB

使用撤销原语能使就绪态/阻塞态/运行态来转为终止态。

进程的阻塞和唤醒

进程的阻塞就是主动将进程从运行态转变到阻塞态。

阻塞原语的步骤为：

  1. 找到要阻塞进程对应的PCB。
  2. 保护进程运行现场（CPU通过栈顶和栈底寄存器来执行），将PCB状态信息设置为“阻塞态”，暂时停止进程运行。
  3. 将PCB插入相应事件的等待队列。

进程的唤醒就是被动地被CPU从阻塞态改为就绪态。

唤醒原语的步骤为：

  1. 在事件等待队列中找到PCB
  2. 将PCB从等待队列移除，设置进程为就绪态。
  3. 将PCB插入就绪队列，等待被调度。
进程的切换

进程切换就是将运行态切换为就绪态或把就绪态切换为运行态。

切换原语的步骤为：

  1. 将运行环境信息存入PCB
  2. PCB移入相应队列
  3. 选择另一个进程执行，并更新其PCB
  4. 根据PCB恢复新进程所需的运行环境。

进程的通信

由于进程与进程不能访问相互的地址空间，所以得通过进程通信来实现交互。

共享存储

共享存储时在内存中开辟一个共享存储区，所有进程都可以对其进行访问。

为了保证可靠性，要求进程进行访问的操作是互斥的，即当一个进程访问该空间时，其他进程在此时无法访问。

基于存储区的共享方式是一种高级通信方式。

而基于数据结构（通过开辟数组等操作）的共享方式是低级通信方式。

消息传递

消息传递就是将进程要传递的数据进行格式化为消息头和消息体两部分，通过操作系统的发送和接受原语来实现。

消息传递分为两种通信方式。

  1. 直接通信方式

    直接将消息通过发送原语来发到接收方的消息队列中，然后接收方通过接受原语来从消息队列取数据。

  2. 间接通信方式

    通过一个中间实体“信箱”来实现消息传递。发送方通过发送原语来将数据发送到操作系统所开辟的“信箱”中，然后接收方通过接受原语来将对应“信箱”中的数据取走。

    多个进程可以往同一个信箱发送消息，也可以多个进程从同一个信箱中接受消息。

管道通信

管道通信就是在发送方和接受方建立一个“管道”（FIFO，采用队列的方式实现），发送方只能在管道的一端写，而接收方只能在管道的另一方读。

管道只采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

并且各进程需要互斥地访问管道。

线程概念和多线程模型

线程的基本概念

为了更好的并发执行多道程序，引入了线程概念，线程相对于微量型进程，作为基本的CPU执行单元，也是程序执行流的最小单位。

一个进程中会蕴含多个线程。而当CPU进行一个进程时可以并发调用多个线程，从而提高计算机的并发性。

线程的实现方式

线程实现可以分为两类：用户级线程（User-Level Thread, ULT），和内核级线程（Kernel-Level Thread, KLT）。

  1. 用户级线程

    1. 是程序员自己通过代码来创建一个线程库来实现，从代码角度看，线程就是一段代码逻辑，通过线程库来实现对线程的管理工作。

    优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。

    缺点：当一个用户级线程被阻塞后，整个线程都会被阻塞，并发度不高。多个线程不可再多核处理器上并行运行。

  2. 内核级线程

    内核级线程的管理工作由操作系统内核完成。

    线程内核级切换需要在核心态下才能完成。

    并且操作系统内核视角可以“看到”线程。

    优点：当一个线程被阻塞后，别的线程还可以继续执行。

    缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型

在支持内核级线程的系统中，根据用户和内核级线程的映射关系，可以划分为多种多线程模型。

  1. 一对一模型。一个用户级线程映射一个内核级线程。

    优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理器上并行执行。

    缺点：线程管理成本高，开销大。

  2. 多对一模型。多个用户线程映射一个内核级线程。

    优点：用户级线程切换不需要切换到核心态，线程管理系统开销小，效率高。

    缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发性不高。

  3. 多对多模型。n个用户级线程映射到m个内核级线程（用户级线程数量大于等于内核级线程数量，即n>=m）。每个用户进程对应m个内核级线程。

处理机调度

调度的基本概念

调度就是当有一堆任务要处理，但由于资源有限，这些事情没法同时处理时候就需要根据某种规则来调整这些任务的顺序，这就是调度研究的问题。

调度的层次

调度往往需要经历三个层次。

高级调度（作业调度）

按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

中级调度（内存调度）

由于内存不够时，CPU可将某些进程的数据调出外存，当内存空闲或进程需要运行时再重新调入内存。

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列。

将挂起队列中的进程重新调入到内存就称内存调度。

低级调度（进程调度）

进程调度就是按照某种策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高。

三层调度的联系、对比

调度的算法评价指标

CPU利用率

CPU利用率指CPU“忙碌”的时间占总时间的比例。
$$
利用率=\frac{忙碌的时间}{总时间}
$$

系统吞吐量

系统吞吐量是指单位时间内完成作业的数量。
$$
系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间}
$$

周转时间

周转时间是指作业被提交给系统开始道作业完成为止过程所需要花费的时间。

包括四个部分：

  1. 作业再外存后备队列上等待作业调度（高级调度）的时间
  2. 进程在就绪队列上等待进程调度（低级调度）的时间
  3. 进程在CPU上执行的时间
  4. 进程等待I/O操作完成的时间

$$
周转时间=作业完成时间 - 作业提交时间
$$

$$
带权周转时间=\frac{作业周转时间}{作业实际运行的时间}
$$

由上可得带权周转时间越小，用户满意度越高。
$$
平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}
$$

等待时间

等待时间指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

响应时间

响应时间是指从用户提交请求道首次产生响应所用的时间。

调度算法

先来先服务（FCFS）

先来先服务算法是根据作业的先后顺序进行服务，为非抢占式算法。

作业/进程调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。

优点：公平、算法实现简单。

缺点：FCFS算法对长作业有利，对短作业不利。

短作业优先（SIF）

短作业优先是将最短的作业/进程优先得到服务。短作业优先即可用于作业调度也可用于进程调度。当用于进程调度时称为“短进程优先”（SPF）。

优点：可以获得一个很短的平均等待时间、平均周转时间。

缺点：对短作业有利，对长作业不利，可能产生饥饿现象。若长作业一直得不到服务会产生“饿死”现象。

高响应比优先（HRRN）

高响应比是根据响应比来将响应比最高的作业/进程来为其服务。
$$
响应比=\frac{等待时间+要求服务时间}{要求服务时间}
$$
高响应比即可用于作业调度，也可用于进程调度。

优点：综合考虑了等待时间和运行时间，既有SIF的优点，也有FCFS的优点，且避免了长作业饥饿的问题。

时间片轮转（RR）

时间片轮转算法就是可以公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。

算法具体是按照各进程到达就绪队列的顺序，轮流让每个进程执行一个时间片（如100ms），若进程未在一个时间片内执行完，则剥夺处理机重新排队。因此时间片轮转属于抢占式算法。

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转算法将会退化成先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

由于进程调度、切换是有时间代价的，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的实际比例减少。

优点：公平；响应快，适用于分时操作系统；

缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。

优先级调度

优先级调度算法就是根据任务的紧急程度来决定处理顺序。

该算法会给每个作业设置各自的优先级，调度时选择优先级最高的作业。

优先级调度算法会根据优先级是否可以动态改变又分为静态优先级和动态优先级两种。

  • 静态优先级：创建进程时确定，之后一直不变。
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
多级反馈队列调度算法

多级反馈队列调度算法是前几种算法的折中权衡。

该算法会设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

进程到达时候先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。

只有第k级队列为空时，才会从k+1级队头的进程分配时间片用于进程调度。

该算法属于抢占式算法，在k级队列进程运行过程中，1~k-1级队列中进入一个新进程就会进行抢占。

同步与互斥

同步就是让进程之间有直接制约关系，它是为了某些进程需要在某些为止上协调它们的工作次序而产生的制约关系。

进程互斥是因为有临界资源（要求一个时间段内只允许一个进程使用）必须互斥的访问，即不能同时访问同个临界资源，此时产生了间接制约关系，因此称为进程互斥。

对于临界资源的访问可分成四部分：

  • 进入区。负责检测是否可以进入临界区。
  • 临界区。访问临界资源的那段代码。
  • 退出区。负责解除正在访问临界资源的标志。
  • 剩余区。做其他处理。
do{
    entry selection;		//进入区
    critical selection;		//临界区
    exit selection;			//退出区
    remainder selection;	//剩余区
}while(true)

注：进入区和退出区是负责实现互斥的代码段。

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

软件实现

单标志法

该算法会设置一个公用变量turn，用于指示被允许进入临界区的进程编号。

如下面有p0和p1两个进程。

P0:
while(turn!=0);			//进入区
critical selection;		//临界区
turn = 1;				//退出区
remainder slection;		//剩余区
P1:
while(turn!=1);			//进入区
critical selection;		//临界区
turn = 1;				//退出区
remainder slection;		//剩余区

若turn==0时进入P0进程，turn==1时进入P1进程。

仅当退出的时候会修改turn的值。

双标志检查法

该算法会设置一个布尔型数组flag[]，数组中存放标记各进程想进入临界区的意愿。只有当对方为false时才能使用临界区。

如下面有p0和p1两个进程。

P0:
while(flag[1]);			//进入区
flag[0] = true;			//进入区
critical selection;		//临界区
flag[0] = false;		//退出区
remainder slection;		//剩余区
P1:
while(flag[0]);			//进入区
flag[1] = true;			//进入区
critical selection;		//临界区
flag[1] = false;		//退出区
remainder slection;		//剩余区

若flag[1]==false时进入P0进程，flag[0]==false时进入P1进程。

仅当退出的时候会修改flag的值。

由于双标志先检查法在并发环境进入区的“检查”和“上锁”不是同时完成，有可能会违法“忙则等待”原则。

双标志后检查法是先上锁后检查。但在并发环境下会出现饥饿现象，导致谁都无法使用临界区

Peterson算法

Peterson算法就是结合双标志法、单标志法的思想，设置turn和flag两变量实现。

如下面有p0和p1两个进程。

P0:
flag[0] = true; turn = 1;						//进入区
while(flag[1] && turn==1);						//进入区
critical selection;								//临界区
flag[0] = false;								//退出区
remainder slection;								//剩余区
P1:
flag[1] = true; turn = 0;						//进入区
while(flag[1] && turn==0);						//进入区
critical selection;								//临界区
flag[1] = false;								//退出区
remainder slection;								//剩余区

仅有当flag[0]==true且turn==1时才执行P0进程，很好的防止并发情况下会卡在while循环的情况，但仍然未能解决其他未能进入临界区的进程退出进入区的情况。

硬件实现

中断屏蔽方法

通过开关中断来实现互斥，即进程进入临界区后关中断，退出临界区再开中断。

优点：简单、高效。

缺点：由于开关中断指令只能在内核态中运行，因此不适用于多处理机。

互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock），当进程进入临界时候会获得锁；退出后释放锁。

互斥锁的主要缺点就是忙等待，当有一个进程在临界区，其他任何进程进入临界区必须进行等待。

而需要连续循环忙等待的互斥锁就称为自旋锁（spin lock）。

优点：等待期间不需要切换进程上下文，多核处理器系统中，若上锁时间段，则等待代价很低。

信号量

信号量机制是可以很好的用来解决互斥和同步问题的机制，它只能被两个标准原语wait(S)和signal(S)访问，也可以记作P(S)、P(S)。

信号量实际就是一个变量（可以为整数，也可以是更复杂的记录型变量）。

整型信号量

对于整型信号量只有三种操作，即初始化、p操作、v操作。

C语言模拟实现信号量的wait(s),signal(s)

void wait(int S){		//wait原语，相对于“进入区”
    while(S<=0);		//如果资源数不够。就一直循环等待
    S = S-1;			//如果资源数够，就占用一个资源
}
void signal(int S){		//signal原语，相对于“退出区”
    S = S+1;			//使用完资源后，在退出区释放资源
}
记录型信号量

记录型信号量使用一个记录型的数据结构来表示。

//记录型信号量的定义
typedef struct{
    int value;			//剩余资源数
    struct process *L;	//等待队列
} semaphore;

相应的wait(S)和signal(S)操作。

void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L);//若资源数不够将进程从运行态进入阻塞态
    }
}
void signal(semaphore S){
    S.value++;
    if(S.value <= 0){
        wakeup(S.L); //释放资源后若等待队列中还有进程，则将该进程从阻塞态变为就绪态
    }
}
信号量机制实现进程互斥

实现进程互斥只需在临界区使用一个互斥信号量mutex即可实现，初值为1.

semaphore mutex = 1; //初始化信号量

P1(){
    ...
    P(mutex);		//使用临界资源前需要加锁
    临界区代码段...
    V(mutex);		//使用临界资源后需要解锁
    ...
}
信号量机制实现进程同步

通过设置同步信号量S，初始为0，在“前操作”之后执行V(S)（来唤醒后操作），在“后操作”之前执行P(S)（确保前操作没执行完前block）。

semaphore S=0;

P1(){
    代码1;
    代码2;
    V(S);	//S++，并唤醒等待队列中进程
    代码3;
}

P(2){
    P(S);	//S--，若此时P1未执行导相应代码则进入阻塞态
    代码4;
    代码5;
    代码6;
}

死锁

死锁的定义：

死锁就是指当多个进程并发执行时因竞争资源而产生的一种僵局（互相等待），导致各进程都阻塞，无法向前推进的现象。

死锁、饥饿、死循环的区别和共同点

死锁产生的的必要条件

  • 互斥条件。只有当对必须互斥使用资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。
  • 不剥夺条件。进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
  • 请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞。
  • 循环等待条件。存在一种进程资源的循环等待链。

处理死锁总共有三种方法：

  1. 死锁预防。设置某些限制条件，破环产生死锁的4个必要条件中的一个或多个。
  2. 避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态。
  3. 死锁的检测及解除。允许进程发生死锁，但发生死锁后会采取措施解除死锁。

死锁预防

  1. 破环互斥条件

    将只能互斥使用的资源改造未共享使用。如SPOOLing技术。

  2. 破环不剥夺条件

    方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是即使某些资源尚未使用完，也需要主动释放。

    方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种一般需要考虑各个进程的优先级。

  3. 破环请求和保持条件

    可以采用静态分配资源，即进程在运行前一次申请完它所需要的全部资源，在它资源未满足前，不让它投入运行。

  4. 破环循环等待条件。

    可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。

避免死锁

避免死锁就是在进程运行之前会施加一些限制条件来避免使用资源后会进入死锁状态。

安全序列、不安全状态、死锁的联系

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配资源后，系统中找不出任何一个安全序列，系统就进入了不安全状态，就意味着之后如果分配了资源之后可能所有进程都无法顺利的执行下去。

若系统处于安全状态，就一定不会发生死锁。

若系统进入不安全状态，就可能会发生死锁。

安全性算法

安全性算法即每一轮都从编号较小的进程开始检测，通过循环来获得安全序列，从此达到避免死锁。

文章作者: LsWorld
文章链接: http://example.com/2024/01/19/cao-zuo-xi-tong-jin-cheng-yu-xian-cheng/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 LsWorld !
操作系统 进程与线程
评论
  目录