[系统运维]操作系统_2

2.1 进程的定义、组成、组织、特征

2.1.1进程的定义

程序：就是一个指令序列

早期的计算机只支持单道程序 --> 引入多道程序技术之后，为了方便操作系统管理，完成各程序并发执行，引入了进程、进程实体的概念

进程实体（进程映像）：由PCB、程序段、数据段三部分构成。一般情况下，我们把进程实体就简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤销进程，实质上是撤销进程实体中的PCB。

注意：PCB是进程存在的唯一标志

2.1.2 进程的组成

进程（进程实体）由程序段、数据段、PCB三部分组成。

2.1.3 进程的组织

2.1.3.1 链接方式

持有不同的指针，不同的指针指向不同的状态

2.1.3.2 索引方式

类似于链接方式，唯一不同是增加了索引表

2.1.4 进程的特征

2.1.5 总结

2.2 进程的状态与转换

2.2.1 进程的状态

另外两种状态：

2.2.2 进程状态的转换

2.2.3 总结

2.3 进程控制

2.3.1 什么是进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

简化理解：反正进程控制就是要实现进程状态转换

2.3.2 如何实现进程控制？

用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。
这种不可被中断的操作即原子操作。
原语采用“关中断指令”和“开中断指令”实现

2.3.3 进程控制相关的原语

2.3.4 总结

2.4 进程通信

2.4.1 什么是进程通信

顾名思义，进程通信就是指进程之间的信息交换。
进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。

但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。

进程通信的例子：逛微博时将内容分享到微信上，那么微信和微博就是有通信的

2.4.2 共享存储

进程一和进程二共享一个空间，操作系统提供共享空间和同步互斥工具，进程一和进程二不可以同时使用共享空间，他们对共享空间的访问是互斥的。

共享存储分为：

• 基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一-种低级通信方式
• 基于存储区的共享:在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制,而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

2.4.3 管道通信

“管道"就是用于连接读写进程的一个共享文件，其实就是在内存中开辟一个大小固定的缓冲区

管道采取半双工通信，如果需要实现双向同时通信，需要设置两个管道；

进程互斥访问管道，进程1写数据写满，进程2读取，取完管道中的数据，进程1才可以接着写入；

管道没写满不准读，没读完不准写，一个数据只能被读取一次

2.4.4 消息传递

进程间的数据交换以格式化的消息( Message)为单位。进程通过操作系统提供的“ 发送消息/接收消息”两个原语进行数据交换。

消息传递的两种方式：

• 直接通信方式：消息直接挂到接收进程的消息缓冲队列上
• 间接通信方式：消息要先发送到中间实体(信箱)中，因此也称“信箱通信方式”。Eg: 计网中的电子邮件系统

2.4.5 总结

2.5 线程、多线程模型

问:什么是线程，为什么要引入线程？

有的进程可能需要"同时"做很多事，即在进程中创建了多个执行流，为此，引入了线程来增加并发度。这些功能显然需要用不同的几段程序才能实现， 并且这几段程序还要并发运行

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

引入线程后，进程之间可以并发，进程内的各线程之间也可以并发，进程只作为除CPU之外的系统资源的分配单元

2.5.1 线程的实现方式

• 用户级线程：用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责(包括线程切换)，”用户级线程“就是从用户视角可以看到的线程，用户可以看到线程的存在，但是操作系统只能看到用户进程
• 内核级线程：必须在核心态下切换，从操作系统内核视角能看到的线程

重点重点：
操作系统只”看得见“内核级线程，因此只有内核级线程才是处理机分配的单位

如上图，假设我们电脑是4核，现在是3个用户，因为只有两个内核级线程，所以只会被分配到两个核心，而不是三个核心。

2.5.2 多线程模型

在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引
出了“多线程模型”问题。

• 多对一：多个用户线程映射到一个内核级线程
  • 优点：用户级线程的切换在用户空间即可完成，线程管理系统开销小，效率高
  • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高

2.6 处理机调度

”调度“研究的问题:资源有限，一堆任务没办法同时处理，必须确定某种规则来决定处理这些任务的顺序

处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

补充知识：挂起态和七状态模型

2.6.1 进程调度（低级调度）

2.6.1.1 进程调度的时机

• 需要进行进程调度与切换的情况：
  • 运行进程主动放弃：正常终止，运行过程发生异常而终止，进程主动请求阻塞
  • 运行进程被动放弃：分给进程的时间片用完，更紧急的事情需要处理，更高优先级的进程进入
• 不能进行进程调度:
  • 处理中断的过程
  • 进程在操作系统内核程序临界区中，普通临界区可以进行调度和切换的
  • 原子操作过程中

2.6.1.2 进程调度的方式

• 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
• 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

2.6.1.3 进程的切换与过程

进程切换的过程主要完成：

对原来运行线程各种数据的保存，对新进程各种数据的恢复

进程的切换过于频繁使得整个系统的效率降低

2.7 调度算法的评价指标

• CPU利用率：指CPU“忙碌”的时间占总时间的比例。
• 系统吞吐量：单位时间内完成作业的数量，公式：总共完成了多少道作业/总共的时间
• 周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔。周转时间=作业完成时间-作业提交时间；平均周转时间 = 各作业周转时间之和 / 作业数

• 等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低
  • 对于进程来说，等待时间是在进程建立后等待被服务的时间之和，在等待I/O完成的期间在被服务，所以不计入等待
  • 对于作业来说，不仅要考虑建立进程后的等待时间，还要家上作业在外存后被队列中等待的时间（未被创建进程）
• 响应时间：指从用户提交请求到首次产生响应所用的时间
  

2.8 调度算法

2.8.1 先来先服务（FCFS, first come first serve）

2.8.2 短作业优先（SJF，shortest Job First）

短作业优先一般默认是非抢占式的，其实抢占式可能平均等待时间更少

2.8.3 高响应比优先（HRRN，highest response ratio next）

问题：先来先服务只考虑了等待时间，短作业优先只考虑了作业时间

小结

2.8.4 时间片轮转（RR，round-robin）

时间片太大，使得每个作业几乎都可以在一个时间片内完成，则会退化为先来先服务算法

时间片太小，使得进程切换过于频繁，导致视机用于进程执行的时间比例减少

2.8.5 优先级调度算法

2.8.6 多级反馈队列调度算法

如果源源不断有短进程，长进程可能会饥饿

小结：

2.9 进程同步和互斥

2.9.1 进程同步

知识点回顾：进程具有异步性的特征，异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2.9.2 进程互斥

临界资源：一个时间段内只允许一个进程使用的资源

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

小结：

2.9.3 进程互斥的软件实现方法

• 单标志法：
  • 算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
  • 问题：如果P0进入临界区但是一直不访问，此刻P1又不允许进入临界区那么临界区就会被空闲，违背了”空闲让进“的原则。
• 双标志先检查法
  • 设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿,
  • 问题：进入区的“检查”（检查其他进程是否想进入临界区）和“上锁”（告诉其他进程我想进入临界区）两个处理不是一 气呵成的，”检查“后和”上锁“前可能发生进程切换，违反了”忙则等待“的原则
• 双标志后检查法
  • 算法思想:先上锁后检查
  • 问题:和先检查法一样不是一气呵成的，可能都不能进入临界区，解决了”忙则等待“，违背了”空闲让进“和”有限等待“原则，各进程可能产生”饥饿“现象
• Peterson算法
  • 算法思想:如果双方谁也不让谁，尝试”孔融让梨“思想，设置flag[]数组表示意愿数组，turn表示优先让哪个进程进入临界区

2.9.4 小结

2.9.4 进程互斥的硬件实现方法

• 中断屏蔽方法
  • 利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)。关中断后即不允许当前进程被中断，也必然不会发生进程切换
  • 简单高效，不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程（危险）
• TestAndSet 指令
  • 用硬件实现的，执行过程不允许中断，将”检查“和”上锁“用硬件的方式变成了一气呵成的原子操作
  • 适用于多处理机，不满足”让权等待“
• Swap指令
  • 用硬件实现的，执行过程不允许中断
    

2.10 信号量机制

用户进程可以通过使用操作系统提供的–对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量：就是一个变量，表示系统中某种资源的数量

一对原语：wait(s)和signal(s),原语是一-种特殊的程序段，其执行只能一气呵成，不可被中断

信号量：

• 整数型变量的信号量：表示系统中某种资源的数量，三种操作：初始化、P操作（wait）、V操作（signal）
  • 存在问题：不满足”让权等待“，发生”忙等“
• 记录型信号量：用记录型数据结构表示的信号量，记录剩余资源数和等待队列，有资源时分配给等待队列的对头进程
  • P操作：进程请求一个单位的该类资源，剩余资源数-1
  • V操作：对系统资源的释放，剩余资源数+1

2.11 信号量机制实现进程互斥、同步、前驱关系

2.11.1 实现进程互斥

• 设置互斥信号量mutex，初值为1
• 在临界区之前执行P(mutex)，使用临界资源前需要加锁
• 在临界区之后执行V(mutex)，使用临界资源后需要解锁

2.11.2 实现进程同步

进程同步:要让各并发进程按要求有序地推进。所以我们必须保证”一前一后“的同步关系

• 设置同步信号量S，初始为0
• 在”前操作“之后执行V(S)
• 在”后操作“之前执行P(S)

2.11.3 实现前驱关系

2.12 生产者 - 消费者问题

实现互斥的P操作一-定要在实现同步的P操作之后。否者出现生产者和消费者出现”死锁“，两个V操作顺序可以交换

总结：

生产者-消费者问题一对互斥、两对同步关系

• 多生产者-消费者问题

如果盘子容量设为2，必须设置互斥变量，否则父亲和母亲可以同时访问盘子，同步关系变为：盘子变空–>放入水果

• 吸烟者问题

• 读者-写者问题

• 哲学家进餐问题

2.13 管程

2.13.1 为什么要引入管程

信号量机制存在的问题:编写程序困难、易出错，能不能设计一种机制，让程序员写程序时不需要再关
注复杂的PV操作，让写代码更轻松呢?

管程：一种高级的同步机制

2.13.2 管程的定义和基本特征

2.14 死锁

2.14.1 什么是死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”发生死锁后若无外力干涉，这些进程都将无法向前推进。

2.14.2 死锁、饥饿、死循环的区别

• 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
• 饥饿:由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先(SPF) 算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”
• 死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。
  

2.14.3 死锁产生的必要条件

• 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
• 不剥夺条件: 进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
• 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

注意!发生死锁时一定有循环等待，但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

2.14.4 什么时候会发生死锁

• 各进程对不可剥夺的资源(如打印机)的竞争可能引起死锁
• 请求和释放资源的顺序不当
• 信号量的使用不当也会造成死锁

总之，对不可剥夺资源的不合理分配，可能导致死锁。

2.14.5 死锁的处理策略

• 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
• 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)
• 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措
  施解除死锁。
  

2.15 死锁的处理策略

2.15.1 预防死锁

• 破坏互斥条件：如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态，比如SPOOLing技术，将独占设备在逻辑上改造成共享设备
  • 缺点：很难破坏这个条件，适用范围不广
• 破坏不剥夺条件：
  • 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要重新申请
  • 方案二：操作系统协助将想要的资源强行剥夺
  • 缺点：
    • 实现复杂
    • 释放已获得的资源可能造成前一阶段工作的失效，只适用于易保存和易恢复状态的资源
    • 反复地申请和释放资源会增加系统开销，降低系统吞吐量
    • 采用方案一，如果一直发生得不到资源的情况，导致进程饥饿
• 破坏请求和保持条件：
  • 可以采用静态分配方法，即进程在运行前-.次申请完它所需要的全部资源，在它的资源未满足前,不让它投入运行。一旦投入运行后，这些资源就一 直归它所有，该进程就不会再请求别的任何资源了。
  • 缺点：
    • 运行时间短的进程一直保持所有资源，造成严重的资源浪费，资源利用率极低
    • 导致某些进程饥饿，比如A进程需要资源1，B进程需要资源2，C进程需要资源1和2，系统中有源源不断地A和B类进程时，导致C进程饥饿
• 破坏循环等待条件：
  • 可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(即编号相同的资源)一次申请完。

原理分析:一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。在任何一个时刻，总有一个进程拥有的资源编号是最大的，那这个进程申请之后的资源必然畅通无阻。因此，不可能出现所有进程都阻塞的死锁现象

缺点：
添加新设备需要重新分配所有地编号
进程实际使用资源的顺序可能和编号递增的顺序不一致，导致资源浪费
必须按规定次序申请资源，用户编程麻烦

2.15.2 避免死锁

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

  • 安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个
    安全序列，系统就是安全状态。当然，安全序列可能有多个。
  • 不安全状态，分配了资源之后，系统中找不出任何一个安全序列，进入不安全状态，意味着之后可能所有进程都无法顺利执行，但是如果有进程提前归还一部分资源，系统有可能重新回到安全状态
  • 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)

• 银行家算法的核心思想：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求

2.15.3 死锁的检测和解除

按照资源分配信息如果最后请求边和分配边都没有完全消除的话，就发生了死锁，最终还连着边的进程就是处于死锁状态的进程

检测死锁的算法：

• 在资源分配图中，找出既不阻塞又不是孤点的进程Pi ，如果系统可以满足其资源请求则消去它所有的请求边和分配边，使之称为孤立的结点
• pi释放资源后可以唤醒某些进程，根据上述方法进行简化，若能消去图中所有的边，则该图是可完全简化的

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

展开阅读全文