Post

操作系统--进程通信与调度

Posted
By SmallC
21 min read
操作系统--进程通信与调度

1 进程Process

如何定义process：（process的几个定义特点）

  1. Sequence Execution 程序的顺序执行：一个有独立功能的程序独占处理器直至最终结束的过程
  2. Concurrency Execution：并发执行，进程具有并发性，多个进程互不干扰，同时运行。

The Process Model

  • Multiprogramming of four programs（one PC）
  • Conceptual model of 4 independent，sequential processes
  • Only one program active at any instant

Process Concept

进程：一个具有一定独立功能的程序关于某个数据集合的一次活动。

进程和程序之间的区别：

  1. 程序是命令的集合，是一个静态的概念；进程可以描述并发的过程，是一个动态的概念。
  2. 进程包含程序，数据，pcb（进程控制块）
  3. 进程是暂时的，有关闭的时刻；程序是永久的，一旦写好就一直存在。
  4. 一个程序可以调用多个进程来运行各个部分；一个进程可以运行多个程序；
  5. 进程也可以创造其他的进程；

何时创建进程

  1. 系统初始化时：创建两种进程：
    • Foreground Process：与用户交互提供服务
    • Background Process：处理用户调用的调用，又称为daemon（守护进程）
  2. fork（）系统调用
  3. 用户请求
  4. Initiation of a batch job

1.1何时终止进程

终止进程的条件：

  • Normal exit
  • Error exit
  • Fatal error
  • Killed by another process

1.2进程层次

父进程、子进程形成的层级结构；window没有进程的层次结构的概念

1.3进程状态

  • Running
  • Ready
  • Blocked

进程状态之间的相互转换：

Process blocks for input ：running -> blocked Scheduler picks another process: running -> ready Scheduler picks this process: ready -> running Input becomes available: blocked -> running

1.4进程实现

先考虑一个进程由什么组成：

  • User program
  • User data
  • stack 变量储存的地方
  • PCB
  • Process Context
    • 对整个执行进程的最基本的描述
    • 分为：User Context、Register Context、System Context
  • Context Switch （CPU的进程切换，也就是进程调度）
    • 由系统的schedule来执行
    • 保存旧进程的pcb，加载新进程的pcb
    • 刷新memory cache
    • 转换虚拟内存映射（memory mapping）
    • 进程的切换是非常cost的
  • PCB Table
    • OS维护的进程表，每一项就是该进程的pcb
    • PCB table的大小可以衡量系统的并发性
    • 两种组织形式：Link、Index

2 线程 Thread

2.1 Thread concept

线程可以理解为进程的进程。

  • 原进程PCB的内容分成两部分：
    • 描述进程资源和空间的部分；
    • 描述执行现场、状态及调度的部分。

将第二部分内容作为线程控制块TCB的内容，且一个进程内允许多个 线程存在。

  • 新进程描述为：
    • 一个独立的进程空间，可装入进程映像；
    • 一个独立的进程相关联的执行文件；
    • 进程所用的系统资源；
    • 一个或多个线程。（进程在创建时一般同时创建好第一个线程， 其他线程按需要由用户程序请求创建）

线程不拥有系统资源，这是线程与进程不一样的地方，线程只需要保证其运行的基本数据结构：TCB，pc，a register set and a stack，它与该进程的其他线程共享该进程中的资源

2.2 重点：进程和线程的区别

  1. 进程是资源分配的基本单位，所有与该进程有关的资源分 配情况，如打印机、I/O缓冲队列等，均记录在进程控制块 PCB中，进程也是分配主存的基本单位，它拥有一个完整 的虚拟地址空间。而线程与资源分配无关，它属于某一个 进程，并与该进程内的其它线程一起共享进程的资源。
  2. 不同的进程拥有不同的虚拟地址空间，而同一进程中的多 个线程共享同一地址空间。
  3. 进程调度的切换将涉及到有关资源指针的保存及进程地址 空间的转换等问题。而线程的切换将不涉及资源指针的保 存和地址空间的变化。所以，线程切换的开销要比进程切 换的开销小得多。
  4. 进程的调度与切换都是由操作系统内核完成，而线程则 既可由操作系统内核完成，也可由用户程序进行。
  5. 进程可以动态创建进程。被进程创建的线程也可以创建 其它线程。
  6. 进程有创建、执行、消亡的生命周期。线程也有类似的 生命周期。

2.3 Thread Advantage

  1. 线程的创造，切换，结束的开销小
  2. 线程通信非常简单，因为共享资源，公用一块虚拟内存

2.4 Thread Usage

为什么要使用thread呢？

  • 响应性：多个活动同时进行
  • 资源共享
  • 开销小：创造和销毁的开销小
  • 在多处理器结构的系统中非常好用

2.5 Thread的实现

三种架构

  • 用户空间
  • 内核空间
  • 两者混合

2.5.1 User Threads

  • 线程打包在用户态，内核完全不知道线程
  • 线程切换不需要内核的权限，切换开销小且快速
  • 问题：如果内核是单线程的，任何用户态线程调用了一调正在阻塞的系统调用，就会导致整个进程进入阻塞状态。线程的阻塞会导致进程的阻塞

2.5.2 Kernel Threads

  • 内核负责管理线程，负责线程的创造、调度、销毁
  • 没有线程库，内核提供线程相关的api
  • 内核保持着进程和线程的context
  • 线程切换需要内核，所以线程是调度器的基本单位，调度器调度的是线程
  • 缺点是high cost

3 考试重点：进程通信（IPC）

这部分重点讨论以下issue：

  • 进程间如何传递信息
  • 资源共享
  • 进程同步（process synchronization）

在资源共享中存在一个重要的认识：竞争（Race）

存在竞争的条件：

  • 多个进程访问临界区的data，并且进程运行的结果需要多步访问临界区

  • 避免竞争的方法是避免多个进程对临界区的data同时进行读写。

  • 临界资源 Critical Resource：一次只允许一个进程访问
  • 临界区 Critical Region：访问临界资源的代码段

3.1 互斥访问资源 Mutual Exclusion

造成互斥排斥的四个条件：

  1. 没有两个进程同时存在在临界区（互斥）
  2. 没有对CPU的速度和数量进行假设
  3. 没有在临界区外运行的进程可以锁住另一个进程（非抢占式）
  4. 没有进程必须永远的等待进入临界区

如何实现资源互斥排斥访问，也就是能够让多个进程同时在临界区运行

  1. 禁用中断
    • 进入临界区后，禁用所有的中断直到进程离开临界区
    • 时钟中断不会发生时，进程切换不会发生，这样在进程完成临界区访问前都不会被打断。
    • 禁用中断后，所有的程序都会按照顺序运行，这样临界区的data就能被正确的修改访问。
    • 只会在OS系统内使用
  2. 锁变量🔒
    • 常见的有互斥锁Mutux Lock
  3. Strict Alternation 严格变更
  4. Peterson’s 使用turn和interested[i]，当一个进程打算进入临界区时，会检查当前turn是不是自己的进程和另一个进程的是否对临界区感兴趣，如果turn不是自己的或者另一个进程不感兴趣，才可以访问；如果turn是自己的并且另一个进程感兴趣，会卡在循环中。

turn的作用：防止两个进程同时把interested设置为true，导致两个进程卡在while循环

  1. 硬件方法 TSL

3.1.1 Mutual Exclusion with Busy Waiting

方法四、方法五需要进程进行忙等待，就是卡while循环，进程没有进入block状态。

这会导致一个问题：优先级反转问题：优先级低的进程在blocking优先级高的进程。

解决：sleep and wakeup 让进程进入block状态，而不是busy waiting；当能够进入临界区后再唤醒wakeup

3.2 重点：消费者生产者问题

3.2.1 信号量必考中的必考 Semaphores

Semaphores = 0：no wakeups were saved; some value: one or more wakeups were pending

由两部分组成：

  • an integer counter，COUNT
  • a queue of pids of blocked processes，Q

对信号量的操作分为两种：

  • P() or wait() or down() ：申请资源，减少信号量
  • V() or signal() or up() : 释放资源，增加信号量

信号量为正时表示当前资源可以被多少进程访问；信号量为负时表当前有多少进程在等待。

3.2.2 Mutex 互斥信号量

为什么不使用Mutex？

缓冲区大小为1，任何时刻，apple、orange和plate三个同步信号量中最多只有一个是1 。因此，在任何时刻，最多只有一个集成的P操作不会被阻塞。

对于缓冲区大小大于1（信号量允许的值大于1）的代码：

P(plate);
P(mutex);
对plate临界区中的事物进行操作；
V(mutex);
V(plate);

Semaphores大于1时，就必须设定一个mutex来保证互斥访问缓冲区。

PV操作题的解题思路：

  1. 关系分析：找出题目中描述的各个进程；分析他们之间的同步、互斥关系。找到不能同时发生的事情就是临界区。不能同时发生的事情可能有多个。
  2. 设置信号量: 互斥信号量初始值为1，同步信号量初值要看对应资源的初始值是多少。

issue

  • P（S）表示申请资源；V（S）表示释放一个字眼
  • P、V操作必须成对出现，申请意味着未来一定会释放。当为互斥操作时，出现在同进程；当为同步操作时，不在同进程出现；
  • 如果一个同步P和互斥P操作在一起时，同步P在互斥P前面

4 Monitors

程序、变量和数据结构在一个package的集合，可以理解为一个只能被一个进程访问的代码块。

访问Monitor的规则:

  • 进程和线程调用程序访问Monitor
  • 互斥访问Monitor
  • 不能直接访问Monitor的变量
  • Monitor可以只可以访问它的局部变量

monitor如何实现进程同步访问：

  • 使用condition 变量。
  • 使用wait（x）来等待有人使用了condition变量，会是condition+1，使用signal（x）来使用condition变量，会使condition-1

使用monitor解决生产者消费者问题：

  • 需要使用count，一般表示缓冲区的数目。
  • 当count=1时，就要signal（empty），发出空信号，说明已经不空了，让wait empty 的进程得以访问count了；当count=N-1时，就要signal（full），发出满信号，说明现在count已经不满了。

5 Message passing

进程通信的方法：

  • 共享memory
  • 共享file mode
  • Message passing：
    • send and Receive
    • send（addr，msg）；
    • recv（addr，msg）；

6 Barrier

Barrier的使用：

  • 进程们靠近Barrier
  • 所有的进程到达是才允许所有的进程通过Barrier

7 其他的IPC问题

7.1 Dining Philosophers问题

7.2 Reader And Writer 问题

8 调度问题 scheduling

8.1何时调度

  • 新进程被创建
  • 存在运行进程
  • 运行进程被block
  • io中断
  • 时钟中断

抢占式和非抢占式调度

好的调度算法的判断标准：

  • Fair
  • Priority
  • Efficiency
  • Encourage good behavior
  • Support heavy loads
  • Adapt to different environments

不同的系统的侧重点不同：

  • All Systems
    • Fairness
    • Efficiency
    • Policy Enforcement
  • Batch
    • Throughput
    • Turnaround Time
    • Waiting Time
    • Processor Utilization
  • Interactive system
    • Response Time
    • Proportionality
  • Real-Time system
    • meeting deadlines
    • predictability

8.2 调度算法

8.2.1 First Come First Served算法 先进先出
  • 非抢占式
  • 在Batch System中使用

简单不过多描述

问题：convoy问题

8.2.2 Shortest Job First 最短作业优先
  • 有抢占式和非抢占式的
  • 需要提前知道进程工作完成所需时间，这是很困难的
  • 要求进程同时进入就绪态，这也是非常困难的

抢占式SJF

有进程到达时，比较当前执行进程剩余运行时间和到达进程的运行时间

8.2.3 Round-robin 时间片轮转算法

时间片的大小的选择很重要，一般是10 to 100 ms

8.2.4 优先级调度

同级别是FCFS，这是抢占式的。

8.2.5 Multi-Queue Scheduling 多级队列调度算法

一个进程只能永久性进出一个队列，每个队列执行不同的调度算法。

多级队列：该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。

多级队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。

高优先级的队列执行完成后低优先级的队列才能开始执行

8.2.6 Multi-level Feedback 多级反馈调度算法（改进）

基本和上一个算法一样，不同的地方在与高优先级的队列进程弹出后如果没有执行完就对推入下一个优先级的队列

8.2.7 Guaranteed Scheduling

为每个进程分配一个公平的时间份额或优先级，这个份额或优先级会根据进程的行为和需求动态调整。如果一个进程没有使用它的全部时间份额，这个未使用的份额可能会被其他需要更多处理器时间的进程利用。相反，如果一个进程超过了它的时间份额，它的优先级或时间份额会在下一个调度周期中被降低，以给其他进程更多的执行机会。

8.2.8 Lottery Scheduling

很常用！

Probability-based ：

  • 系统为每个进程分配一定数量的彩票，而进程获得CPU时间的机会与它持有的彩票数量成正比。当系统需要选择下一个要执行的进程时，它会进行一次“抽奖”，随机选择一个彩票，拥有该彩票的进程获得执行机会。
  • 给高优先级或者短任务的进程更多的彩票

优点：

8.2.9 Fair-Share Scheduling

分为两种：进程公平调度，也就是之前讨论的时间片轮转；用户公平调度，给每个用户程序同等的CPU访问时间权限。

8.3 Scheduling in Real-Time systems

操作系统
This post is licensed under CC BY 4.0 by the author.