操作系统-进程

A9ia

操作系统

发布于：2021年12月26日

次浏览

进程

[TOC]

进程概念

进程的定义

我对进程定义的理解是：一个运行中的程序的控制信息和占用的资源的集合

由进程控制块（PCB）、数据段和代码段组成

进程控制块

操作系统用于管理进程的信息，在程序运行时创建，进程结束时销毁。

包含许多与特定进程相关的信息：

• 进程 id
• 进程状态
  • new
  • running
  • waiting
  • ready
  • terminated
• CPU 寄存器信息，用于中断时保存现场
• CPU 调度信息，调度优先级等
• 内存管理信息，指向分配的内存地址
• 记账信息，记录 CPU 时间，使用 CPU 期限等
• IO 状态信息，分配给进程的 IO 设备、打开的文件等信息

进程占用的内存空间

在 32 位 Linux 系统中，当程序运行时，操作系统除了会创建一个 PCB，还为这个进程分配 4G 的虚拟内存地址空间，其中 1G 分配给内核使用（所有的进程共享以及操作系统本身使用，当用户进程陷入内核态时使用。），3G 分配给用户使用。

分配给用户的 3G 又要分为：

• 堆空间

  由用户管理，用内存动态分配指令来使用

• 栈空间

  由系统管理，存放局部变量，形参，自动变量等

• 数据段

  • bss：未初始化的字段，占用一个占位符表示。
  • rodata：常量，只读。
  • .data：初始化后的数据。

• 代码段：实际程序代码文本（只读），可以多个进程公用一个

图源：https://zhuanlan.zhihu.com/p/141590426

进程运行

进程运行中存在三种队列：

• 等待 CPU 的就绪队列
• 等待某种 IO 设备的设备队列
• 所有进程队列

进程操作和状态变化

• Process creation

  1. 申请 PCB
  2. 分配内存
  3. 初始化 PCB
  4. 插入就绪队列

• Process Termination：运行完

• Process blocking：阻塞

• Process wakeup：从阻塞态中唤醒为准备态

• Process suspend：暂停

• Process activate：开始运行

进程创建

在 Linux 中，通过 fork 函数来创建子进程。系统初始化是会创建一个系统进程作为根节点，当创建其他进程时，操作系统会自动把他连到 init 进程下。

相应的一个进程本身有创建子进程的能力。

父子进程不共享资源，采用写时复制技术（未修改时父子复用同一个，修改时子进程会创建新的地址空间存放这个信息），值得注意的是：当父子进程指向同一个文件时，因为指向的是同一个文件的结构，文件访问的指针会被复用，访问文件信息时会互相干扰，即子进程修改后，父进程也会相应修改。

进程阻塞和中断

进程阻塞和中断时需要保存当时进程运行中的寄存器等状态，然后进入相应队列。

多线程

每个进程都必须有一个线程。

在进程的用户空间中实现的线程创建、调度和管理。内核无感知。当运行线程时必须将用户线程映射到内核线程上。也就是说，真正能够被分配 CPU 等资源运行的只有内核线程，用户线程只是逻辑上的。

进程内线程共用代码段和数据段。堆部分共享，栈线程私有。

通过时间片或者多处理器实现并行执行代码。

内核线程和用户线程映射

1. 一对一

   每个用户线程独享一个内核线程

2. 多对一

   多个用户线程共享一个内核线程

3. 多对多

   多个用户线程轮流使用多个内核线程

进程调度

调度概念

进程的运行需要在占用 CPU 运行和等待 IO 之间交替进行，调度就是充分发挥 CPU 的作用，利用多道程序轮换来避免等待 IO 时 CPU 空闲。这在短期主要是通过 CPU 调度来实现的。

分类

调度类型可以分为三类：

• 长期调度：控制 ready 队列中进程的数量，控制 IO 密集型和 CPU 密集型进程混合运行，提高效率。
• 短期调度：又叫 CPU 调度，控制目前使用 CPU 的进程
• 中期调度：将进程从 CPU 竞争中短暂从内存移出到辅存中，减少多道程序复杂度

上下文切换

调度时需要进行上下文切换：

1. 用户级上下文：进程用户地址空间，包括用户正文段、数据段和栈
2. 寄存器级别上下文：程序计数器、程序状态寄存器、栈指针、通用寄存器的值
3. 系统级上下文：PCB和资源表格；核心栈（调用核心时使用的不同核心栈）

抢占调度

根据是否允许当一个程序在运行态，一个优先级更高的程序就绪时进行调度，分为抢占式和非抢占式。

调度程序（dispatcher）

负责完成：

• 切换上下文
• 跳转到用户程序的合适位置，以便重启程序
• 切换到用户模式

这个程序会有一定的调度延迟

调度算法有不同的衡量准则：

• 吞吐量：单元时间内，进程完成的数量
• 周转时间：进程从提交到完成的时间
• 响应比：周转时间除以运行时间

调度算法

先到先服务（FCFS）

一个 FIFO 队列，非抢占式。

容易产生护航效果（convoy effect）：大 CPU 密集型占用 CPU 导致剩余全部进程等待其完成的问题

最短作业优先调度（SJF）

最先执行当前就绪队列中 CPU 作业短的进程

因为没办法知道进程 CPU 执行长度，所以说很难实现。

可以通过预测 CPU 执行时间来避免这个问题，定义预测时间为：下次时间 = a * 上次长度 + (1 - a) * 上次时间

SJF 既可以是抢占的，也可以是非抢占的。

抢占式 SJF 一般称为最短剩余时间优先调度

优先级调度（PS）

按照优先级进行调度，优先级越小，越先被执行。

会有无穷阻塞或者说饥饿的问题。

可以通过老化：随着时间使等待着的进程优先级减小来避免饥饿。

既可以是抢占的，也可以是非抢占的。

时间片轮转制度（RR）

为分时系统设计，基础是 FCFS，把一个较小时间单元定义为时间量（time quantum），就绪队列为循环队列，每次为进程提供不多于一个时间量的 CPU。如果执行完则执行下一个，如果时间片耗尽则将其中断放到队尾，执行下一个。

需要时间片远大于调度耗费时间。

多级队列调度（multilevel queue）

进程通常分为前台进程和后台进程。前台进程需要更高的优先级。在这种业务场景下使用多级队列调度。

队列内进行 RR 调度。

mq 调度不同优先级的队列进程有两种办法

• 只有当优先级更高的队列为空时，才能进行优先级较低的队列调度。
• 划分优先级更高的队列更长时间的时间片，优先级较小的队列较小时间片，两个队列总体上进行 RR 调度。

多级反馈队列调度

基于多级队列调度，新来的程序先进入到优先级最高的队列中，执行一个较短的时间片，若未执行完成，则放到低一级的队列队尾。最后一级队列采用 FCFS 调度。

多线程调度

用户线程由线程库进行调度，内核无感知。CPU 实际上调度的是内核线程或者轻量级进程（LWP）。

需要研究的是多对一和多对多模型下如何进行调度

多处理器调度

可以分为两种

1. 非对称多处理器：只让一个处理器处理所有调度、IO以及其他系统活动，剩下的处理器都用来处理用户进程。
2. 对称多处理器（SMP）：每个处理器自我进行调度、IO以及其他系统活动，分别处理队列中（或公有、或私有）进程。

为了避免在进程在一处理器上运行时，切换处理器带来的开销。进程会优先试图选择同一个处理器进行运行，这被称为处理器亲和性（processor affinity）。系统尽量为之称为软亲和性，确保为之称为硬亲和性。

实时操作系统进程调度

因为实时操作系统要求更好的实时性，所以调度算法也有一定的不一样。要对实时性要求高的进程优先服务。分为软实时系统和硬实时系统。软实时系统只保证进程会优先于非关键进程，硬实时系统在时间期限后完成相当于没有完成。

从事件发生到进行中断并对其进行服务的过程时间为：事件延迟。包括两类延迟：

• 完成当前正在执行的指令，然后保存现场，执行中断程序的中断延迟（以及调度完关中断的延迟
• 从一个程序结束，加载另一个进程并运行的调度延迟

实时系统要尽量减少这个延迟

优先级调度

当一个实时进程需要 CPU 时立刻相应。

通过抢占的，基于优先级的调度算法，给实时进程最高的优先级。这只是实现了软实时性。但还是需要其他算法来保证硬实时。

以下讨论的几种算法来保证硬实时。

单调速率调度

采用抢占式，静态优先级的策略来调度周期性的任务。

即周期越长的实时性任务，优先级越低。高优先级会抢占低优先级。

该算法被认为是最优的，如果一组进程不能被该算法调度，那么不能被其他分配静态优先级的策略来调度。

但是静态优先级算法有上线，即调度 N 个进程的情况下，CPU的利用率最坏不能高于：

N (2^(1/N) - 1)

否则静态优先级算法就会失效。

最早截止期限优先调度（EDF）

动态分配优先级

截止期限越早，优先级越高；截止期限越晚，优先级越低。

这个算法不要求进程应该是周期的，也不要求 CPU 执行长度固定。

该算法是理论上最佳的。

比例分享调度

调度程序在应用程序之间分配 T 股。如果一个应用程序接受 N 股的时间，那么确保它拥有 N / T 的比例的总的处理器时间。采用准入控制，如果一个进程需要的股多于剩余股，那么进制其进入。

进程通信（IPC）

通信方式

通信方式模型

通信方式有两种基本模型：

• 共享内存
• 消息传递
• 管道

共享内存和消息传递两者之间的区别在于缓存区是否为所有进程仲裁使用，管道则像是两者的结合。

共享内存通过两个进程共同的地址空间来实现通信。

消息传递则是封装了公共的地址空间，只给进程提供发送和接受两个接口。

共享内存

通过相同的内存地址，两个进程进行通信。

消息传递

通过公有的消息传递队列进行消息传递。

操作系统提供创建邮箱，通过邮箱发送、接收信息和释放邮箱机制。

进程通过 send(mailbox_A, message)和receive(mailbox_B, message)来通信。

为了实现收发进程同步，提供了同步\异步两种收发方式。（也叫阻塞/非阻塞）

同步、阻塞：直到对方接受或者发送则停止行为

异步、非阻塞：执行行为并返回，不等待。

根据缓存区的大小进行同步或者异步的选择。当缓存区长度为 0 时，直接把消息发送给目的进程。

管道

普通管道用于父子进程之间的通信，命名管道用于任意进程之间的通信。两者之间的区别是，命名管道多了一个名称以标识该共享内存。

管道是划分了一部分内存区域用于存储信息（一般是一个文件），开始时写指针和读指针在同一位置。当写入时会环型写入，直到与读指针再次重合，此时写缓冲满，等读指针移动后才可以继续写入。

一般来说，读写是不能同时进行的（互斥）。这是为了确保每次读都是在读入写入的内容。

远程进程通信

通过网络中的传输层，进行远程进程之间的通信。

操作系统为其提供的方式有：

• Socket
• RPC

Socket 是一个用于通信地址的概念。基于 TCP / UDP，Socket 系列函数对 Socket 文件进行操作，并通过协议进行与远程主机的通信，完成进程到端口的最后一步。

RPC 是远程过程调用，基于 TCP 或者 HTTP。通常也使用 Socket 函数封装一些操作。用于进程调用远程进程的方法。

同步

为了保证 IPC 或者存储数据的可靠性，我们需要避免多个进程同时操作缓冲区对数据造成影响。也就是使得进程之间的操作的影响互相同步。

我们把共有缓冲区称为临界区。把实现多进程在临界区同步的问题称为临界区问题。

1
2
3
4
5
6

do {
	进入区（请求进入临界区）
		临界区
	退出区（确保退出临界区）
		剩余区（剩余操作）
}

临界区问题需要实现三个功能：

• 互斥：当有进程在临界区执行时，其他进程无法执行
• 有限等待：当进程请求进入临界区直到这个请求允许前，不能有无限个进程被允许进入临界区
• 进步：没有进程在执行，并且有进程请求进入临界区时，从不在剩余区的进程中选择进程，这种选择不能被无限推迟

死锁

更新于：2023年3月22日

操作系统