操作系统学习笔记_02

什么是进程？

📌所谓进程，就是运行中的程序。

​ 在计算机发展的早期，处理器往往只有一个核心，因此就产生了伪并行（pseudoparallelism）即宏观上多线程同时运行，而微观上，各进程轮流使用 CPU,实际上任意一个时刻，只有一个进程在使用 CPU.

随着计算机技术的不断发展，真正的并行已经可以实现了，现代 CPU 有多个核心，能够同时运行多道进程。

❗ 由于 CPU 不停地在不同进程之间进行切换，每个进程的执行速度往往不确定，所以在编程的时候不能对时序做固定的假设。

进程与程序之间的关系

• 一个进程是某种类型的一个活动，它具有不可再现性
• 一个程序则是用适当形式描述的算法

计算机科学家做蛋糕例子

​ 想像一位有一手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，做蛋糕的食谱就是程序(即用适当形式描述的算法)，计算机科学家就是处理机(CPU)，而做蛋糕的各种原料就是输入的数据。进程就是厨师阅读食谱、取来各种原料以及烘制蛋糕的一系列动作的总和。
​ 现在假设汁算机科学家的女儿哭着跑了进来，说她被一只蜜蜂蛰了。计算机科学家就记录下自己照着食谱做到哪儿了(保存进程的当前状态)，然后拿出一本急救手册，按照其中的指示处理蜇伤。这里，我们看到处理机从一个进程(做蛋糕)切换到另一个高优先级的进程(实施医疗救治)，每个进程加有各自的程序(食谱和急救指示)。当蜜蜂蛰伤处理完之后，计算机科学家回来做蛋糕，从他离开时的那一步继续做下去(继续执行做蛋糕程序)。

进程与程序的主要区别：

（1）程序是永存的；进程是暂时的，是程序在数据集上的一次执行，有创建有撤销，存在是暂时的；

（2）程序是静态的观念，进程是动态的观念；

（3）进程具有并发性，而程序没有；

（4）进程是竞争计算机资源的基本单位，程序不是。

（5）进程和程序不是一一对应的： 一个程序可对应多个进程即多个进程可执行同一程序； 一个进程可以执行一个或几个程序

进程创建

进程创建一般有以下四种情况：

1. 系统初始化
2. 正在运行的一个进程执行了创建进程的系统调用
3. 用户请求创建一个新进程
4. 批处理作业的初始化

系统调用 Fork

​ 简单来讲，调用fork函数后会产生一个新的子进程，父子进程共享相同的内存映像和环境字符串和相同的打开的文件。

fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：

1）在父进程中，fork返回新创建子进程的进程ID；
2）在子进程中，fork返回0；
3）如果出现错误，fork返回一个负值；

详细讲解可以看👉fork函数详解

进程终止

一个进程被终止可能有以下原因：

​ 1. 正常退出（自愿）

​ exit系统调用
2. 出错退出（自愿）

​ 如打开一个不存在的文件

3. 严重错误（非自愿）

   ​ 产生异常，比如除了零

4. 被其他进程杀死（非自愿）

   ​ kill系统调用

进程层次结构

​ 进程只有一个父进程，但可以有多个子进程。子进程本身也可以创建它自己的子进程，这样也就组成了一个进程的层次结构。

进程状态

一个进程有下面三种状态：

• 运行态Running
  • 该时刻实际占用处理机
• 就绪态Ready
  • 可运行，但因为其他进程正在运行而暂时被挂起
• 阻塞态Blocked
  • 除非某种外部事件发生，否则不能运行

他们之间的关系与转换如下图：

• 当某个进程在逻辑上不能继续运行时，它就会被阻塞
  • 等待使用别的输入
  • 另一个进程占用处理机
• 2、3两关系是由进程调度器引起的，它是操作系统的一部分
• 某进程等待的外部事件发生时，发生转换4

线程 thread

📌某些情况下在同一个地址空间中由多个控制流并行运行，像是单独进程，但是它们共享相同的地址空间

举个很简单的例子😉

​ Office Word 是一个进程，而在这个进程里需要许多细分的小进程来处理你对 Word 的各种操作，比如改变字号、改变颜色、定时保存…这些小进程处理同一个 Word 文件，也就是说，他们共享同一片内存空间，我们就称这样的小进程为线程threads!

😶线程和进程一样，都可以处于运行、就绪或阻塞态。

进程间通信问题

Inter Process Communication (IPC)进程间通信

通信需要解决的问题

• 如何给其他进程发消息
• 如何确保通信时不访问临界区
• 进程间如果存在依赖关系，如何设计他们合适的运行顺序

竞争条件

​ 两个多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，就称为竞争条件race condition

临界区

• 互斥mutual exclusion
  • 以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作
• 临界区critical region
  • 对共享内存进行访问的程序片段

几种解决方案

无论如何都要做到

!! 任意两个进程不能在同一时间都存在临界区中；
!! 不能对CPU的数量和执行速度做任何的猜测和假设；
!! 临界区外的进程不能阻塞其他进程的执行；
!! 不能让进程在临界区外一直等待；

基于忙等待的互斥

忙等待：进程不断地读turn的值，只是他没有做任何有意义的事（等待），而且浪费了cpu的时间（忙）。故称作忙等待 busy waiting

关闭中断

进程进入临界区后先关中断，离开前开中断。

评价：

• 不应将关中断的权力交给用户
• 中断响应关闭后，系统就完全失去控制了
• 多处理的系统中，该方案无效，因为其他CPU也会响应中断的。

锁变量

一种软件解决方案

定义一个变量，当作一把锁，进临界区后锁上，出临界区开锁

评价：

• 有纰漏，如果某进程检查锁，发现是开的，但在它准备进入时且还没上锁时，另一个进程进行检测，发现锁是开的，这样就会造成冲突。

严格轮换法

几个进程轮换进入某一临界区，且顺序不能紊乱

评价：

• 轮流进入临界区在一个进程比另一个进程慢很多的情况下不适用

Peterson解决方案

​ 基于Dekker 算法（将轮换法和锁变量以及警告变量的思想相结合）Dijkstra 提出了新的解决方案，它是有效的，可用的，且应用广泛。😍

TSL指令

​ 这是一种需要硬件支持的方法

• 优点
  • 适用于任意数目的进程，在单处理器或多处理器上
  • 简单，容易验证其正确性
  • 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量
• 缺点
  • 等待要耗费CPU时间，不能实现”让权等待”
  • 可能”饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上
  • 可能死锁

Peterson 和 TSL 都是正确的解决方法，但都存在忙等待的缺点，浪费 CPU 的资源，进程的优先级也有区别。因此我们引入新的解决方案。

睡眠与唤醒|生产者消费者

睡眠sleep、唤醒wakeup

利用这两个系统调用，我们引入生产者消费者问题

• “生产者”进程不断写入，而”消费者”进程不断读出；
• 共享缓冲区共有N个；
• 任何时刻只能有一个进程可对共享缓冲区进行操作。

信号量

​ E.W.Dijkstra在 1965 年提出，它使用一个整型变量来累计唤醒次数，引入一种新的变量类型，称作信号量semaphore。

​ 信号量被广泛使用！

• 信号量为0
  • 表示没有积累下的唤醒操作
• 信号量为正值
  • 表示有一个或多个积累下的唤醒操作

有这样两个原子操作：

• down相当于 sleep 操作
• up相当于 wakeup 操作

​ 信号量mutex用于互斥，用于保证任一时刻只有一个进程读写缓冲区和相关变量。

管程

管程是对信号量的一种封装，提供一种实现互斥的简便途径。

来自知乎陈龙的解释👉链接

打一个相对形象的比喻：

人们到一家叫做计算机的银行取钱，这个银行里面就一个空窗口。最早之前，每个人需要从这个窗口爬进去取钱。

这里，银行里面每一个需要取钱的人看作进程，而银行里面的钱可以看做计算机的共享资源，一般是硬件设备或一群共享变量。

每个人都向窗口拥挤，场面混乱不堪。

后面计算机银行不断改进，发明了一种叫ATM的机器（管程），ATM（管程）封装了钱和对外开放了一些存取钱的操作。

这样一来，ATM（管程）在计算机银行的钱和客户之间担任了中介服务的角色。

在一个相对封闭的屋子里面，一次只能服务一个人（让进程互斥使用）。ATM屋子里面有人的时候，其他需要依次排队使用。

一个人（进程）在ATM使用的时间太长也不行，所以需要一个条件变量（condition）来约束他。条件变量可以让一个线程等待时让另一线程进入管程，这样可以有效防止死锁。

管程使并行编程比用信号量更容易保证正确性。

弊端：

• 支持管程的编程语言太少，而且它要求编译器的支持

所以，我们需要新的解决办法！

经典 IPC 问题

哲学家进餐

是一类多进程访问有限资源的问题

读者写者问题

是一类数据库的访问模型

进程调度

几种分类

按调度层次

• 宏观调度
  • 作业
• 中级调度
  • 内外存交换
• 微观调度
  • 进程或线程

按时间周期

• 长期
  • 进程投入进程缓冲池
• 中期
  • 将进程的部分或全部加载到内存中
• 短期
  • 选择某个进程在处理机上执行

按 OS 分类

• 批处理
  • 使用与大中型主机几种计算
• 分时、实时
  • 没有专门的作业调度
• 多处理机

调度的性能准则

面向用户

• 周转时间
• 相应时间
• 截止时间
• 公平性
• 优先级

面向系统

• 吞吐量
• 处理机利用率
• 各种设备的均衡利用

算法

• 易于实现
• 执行开销比

合适的调度算法需要遵守的原则：

1. 公平——每个进程有合理的 CPU 份额
2. 有效——CPU 百分百忙碌
3. 响应时间——使得交互用户的响应时间尽可能短
4. 周转时间——使批处理用户等待的输出时间尽可能短
5. 吞吐量——使每小时处理的作业数最多

调度算法

先来先服务

FCFS First Come First Serve

• 有利于长作业不利于短作业
• 有利于 CPU 繁忙的作业，不利于 I/O 繁忙的作业

时间片轮转

Round Robin

其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；

优先级调度

本算法平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成静态和动态两种方式

静态优先级调度

创建进程时就确定优先级，直到进程终止前都不改变。通常是一个整数

动态优先级调度

在创建进程时赋予其优先级，但在进程运行过程中可以自动改变，以便获得更好的调度性能。

多重队列

引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标。

短作业优先

对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢正在执行中的作业,只对队列中就绪的进程进行调整。

算法优点：

• 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；

• 提高系统的吞吐量；

算法缺点：

• 对长作业非常不利，可能长时间得不到执行；

• 未能依据作业的紧迫程度来划分执行的优先级；

• 难以准确估计作业（进程）的执行时间，从而影响调度性能。