进程与线程

进程

进程是资源分配的基本单位，在某一个瞬间，一个物理CPU核心只能运行一个进程。

进程模型

计算机上所有可运行的软件，通常包括操作系统，被组织成若干顺序进程，称为进程

202031162023

程序与进程的关系：模板与实例

进程的创建

导致进程创建的4种主要事件：

守护进程：停留在后台的线程

写时复制：UNIX中fork出来的子进程的内存是父进程的一个拷贝，为了避免不必要的开销，操作系统通过让二者共用一份物理内存，当内存发生变化时，才进行复制。

进程的终止

终止的条件：

进程的层次结构

UNIX中，进程创建一个新进程后，该进程称为其的父进程，它与它的所有后代组成一个进程组。 但在Windows中，进程之间没有层次关系，除了父进程在创建子进程时，会获得其的句柄，除此之外，没有任何联系。

进程的状态

stateDiagram-v2
  运行 --> 就绪: 调度程序选择另一个进程
  就绪 --> 运行: 调度程序选择这个进程
  运行 --> 阻塞: 等待输入而阻塞
  阻塞 --> 就绪: 出现有效输入

这些状态很像线程

调度程序：负责切换进程的执行

进程的实现

为实现进程模型，操作系统维护一张表：进程表，每个进程维护如下的一些字段

进程管理 存储管理 文件管理
寄存器 正文段指针 根目录
程序计数器 数据段指针 工作目录
程序状态字 堆栈段指针 文件描述符
堆栈指针 用户ID
进程状态 组ID
优先级
调度参数
进程ID
父进程
进程组
信号
进程开始时间
使用的CPU时间
子进程的CPU时间
下次定时器时间

操作系统通过进程表每个进程的状态，当中断发生（IO发送数据），一个称为中断向量的位置：中断服务程序的入口地，就会执行一段中断程序，中断完成后回来继续该进程:

  1. 硬件压入堆栈程序计数器等。
  2. 硬件从中断向量装人新的程序计数器。
  3. 汇编语言过程保存寄存器值。
  4. 汇编语言过程设置新的堆栈。
  5. C中断服务例程运行(典型地读和缓冲输入)。
  6. 调度程序决定下一个将运行的进程。
  7. C过程返回至汇编代码。
  8. 汇编语言过程开始运行新的当前进程。

多道程序设计模型

CPU利用率 = 1-P^n

n称为多道程序设计的道数 P为CPU空转的概率

线程

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

202031162222

线程的使用

使用线程的理由：

如果不使用多线程，在程序中手动维护多个多个工作的状态，是一种称为有限状态机的技术，这种方式其实知识一种以更加困难的方式来模拟线程以及堆栈

每个计算机都有一个被保存的状态，存在一个会发生且使得相关状态发生改变的事件集合

经典的线程模型

每个线程都有自己的栈：每个线程会调用不同的过程，所以需要维护自己的栈

每个进程中的内容 每个线程中的内容
地址空间 程序计数器
全局变量 寄存器
打开文件 栈
子进程 状态
即将发生的定时器
信号与信号处理程序
账户信息

一些常见的线程调用：

线程给程序设计带来了更多的复杂性，父子进程之间线程是否可共享？

POSIX线程

一种线程标准，定义的线程包叫做pthread

在用户空间中实现线程

优点

局限性

在内核中实现线程

创建代价很大，所以需要考虑线程的回收复用

混合实现

部分线程由内核实现，这些线程会给用户级线程多路复用

调度程序激活机制

上行调用

弹出线程

一个消息的到达导致系统创建一个处理该消息的线程

使单线程代码多线程化

进程与线程的区别

进程间通信

竞争条件

两个或多个进程读写某些共享数据，得到的结果取决于进程运行的精确时序

临界区

通过互斥来组织多个进程同时读写共享数据 把对共享内存进行访问的程序片段称为临界区

临界区互斥

同步与互斥

忙等待的互斥

睡眠与唤醒

从生产者-消费者问题中发现消费者与生产者之间需要一系列的睡眠-唤醒操作

信号量

信号量（Semaphore）是一个整型变量，可以对其进行原子操作，并且可以用来实现同步。

互斥量

信号量的一个简化版本，值只能取0或者1

管程

一个管程由过程、变量、数据结构等组合成的一个集合，是一种编程语言概念

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

管程的原语确定：在一个时刻只能有一个进程使用管程，管程被JAVA中的synchronized所实现了

进程可以在任何时候通过管程间接获取数据，但是不能直接获取数据

消息传递

send(目的,&msg);
receive(源,&msg);

用消息传递解决生产者-消费者问题 消息传递接口

这种接口是建立在计算机网络、互斥量、同步等上的一个高级接口

屏障

当一个进程到达屏障时，就会被阻拦，直到所有进程都到达屏障为止，CyclicBarrier

屏障

避免锁：读-复制-更新（RCU）

最快所的就是没有锁

要么读取旧版本，要么读取新版本

调度

调度程序使用调度算法完成调度

进程的行为分为IO活动与CPU计算，也就是IO密集型和计算密集型

进程行为

何时进行调度：

调度算法

调度算法分为两种：

在对响应时间有要求的情况下，抢占式是很有必要，这能保证计算资源不会一直被某个进程占着

目标

批处理系统

在该系统中，调度算法目标是保证吞吐量和周转时间

FCFS

有个问题就是对段任务不够公平，时间片会大量被长任务进程所占用

SJF

可能导致长任务一直得到不到执行，产生饥饿

和 SJF 差不多，但是放回队列的时候按照作业剩余时间排序，优先调度剩余完成时间最短的任务

SRTN

交互式系统

在该系统中调度算法的目标是快速地进行响应

每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程，该算法效率与时间片大小有关，时间片过于小，会造成进程切换频繁，过大实时性无法得到保证

为每个进程分配一个优先级，按优先级进行调度 为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级

它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列，在这种情况下，就能有效避免一个进程需要执行连续多个时间片而造成的切换频繁问题

202031164556

实时系统

静态的调度算法在系统运行之前就已确定好如何调度，结果肯定是可预测的

动态的调度算法则运行时完成

策略和机制

使用策略模式分离调度机制与调度策略

线程调度

经典进程同步问题

哲学家就餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子

20203117217

一种解法是哲学家发现与其他人冲突时，放弃操作，等待随机的一段时间，这种方式很有效，在以太网中有二进制指数回退，在raft协议中有随机的竞选超时时间

读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生 这一般需要两把锁来完成，也就是通过读写锁

进程通信

为了能够达到进程同步的目的，需要让进程进行通信

管道

202031171046

FIFO(命名管道)

202031183319

有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信

消息队列

信号量

用于为多个进程提供共享对象的访问

共享存储

多个进程可以使用一个给定的存储区进行通信

可以使用文件或者内存

套接字

用于不同机器之间的进程通信