《计算机操作系统》重点知识总结1（1-4章）

📢注意：

   这篇总结文档参考的配套书籍为《计算机操作系统》(第四版) 相关知识点关联的页码可能只与本书配套。

📓说明：

    由于时间关系，该总结的部分知识点可能有所疏落或存在错误，请认真研读不要盲目学习，读者如有补充或问题更正请联系作者[1712229564@qq.com]，作者将会表示感谢！

   最后，希望尊重作者劳动成果，该文档仅供学习交流使用，请大家转载时注明出处，Thanks！😄

第一章 操作系统引论

1 操作系统的定义（P9）：

操作系统是一组能有效的组织和管理计算机硬件和软件资源，合理的对各类作业进行调度，以及方便用户使用的程序的集合。

2 操作系统的基本特征（P14）：

并发、共享、虚拟、异步

3 并发和并行（P14）：

并发：两个或多个事件在同一时间间隔内发生。

并行：两个或多个事件在同一时刻发生。

4 操作系统的五大功能（P18）：

（1）处理机管理功能

（2）存储器管理功能

（3）设备管理功能

（4）文件管理功能

（5）提供与用户之间的接口

第二章 进程的描述与控制

1 程序并发执行时的特征（P38）:

(1)间断性

(2)失去封闭性

(3)不可再现性

扩展：

程序顺序执行时的特性：①顺序性 ②封闭性 ③可再现性

2 进程的定义（P39）：

进程实体 = 程序段 + 相关数据段 + 进程控制块（PCB）

（1）进程是程序的一次执行

（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动

（3）进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

总结：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

扩展：

进程的特性：①动态性 ②并发性 ③独立性 ④异步性 ⑤结构性 (可不写)

3 进程的基本状态和转换（P40）：

进程的三种基本状态：就绪（Ready）状态、执行（Running）状态、阻塞（Block）状态

常见问题:

当n个进程并发执行时，在单处理机中：

处于就绪状态的最多n-1个，最少0个

处于阻塞状态的最多n个，最少0个

处于执行状态的最多1个，最少0个

4 进程间的制约关系（P52）：

（1）直接制约（同步关系）：

某些应用程序，为了完成某个任务而建立了两个或多个进程（源于进程间的合作）。

关于直接制约关系的举例：

（2）间接制约（互斥关系）：

多个程序并发执行时，由于共享系统资源（如CUP、I/O设备等）而导致这些并发执行的程序之间形成相互的制约的关系。

关于间接制约关系的两个举例：

5 *同步机制遵循的原则（P55）：

（1）空闲让进

（2）忙则等待

（3）有限等待

（4）让权等待

6 信号量—记录型信号量（P58）：

记录型信号量是一种不存在“忙等”现象的进程同步机制。

typedef struct{
    int value; //资源个数
    struct process_control_block *list;  //阻塞队列
}semaphore;
wait(semaphore *S){  
    S->value--; //S->value初值表示系统中某类资源的数目，称为资源信号量
    if(S->value<0){
        //自我阻塞
        block(S->list);
    }
}
signal(semaphore *S){
    S->value++;
    if (S->value <= 0){
        //唤醒，将S->list链表的第一个等待线程唤醒
        wakeup(S->list);
    }
}
复制代码

有兴趣看代码实现的同学可以读下这篇文章：blog.csdn.net/Mr_YanMingX…

7 信号量—互斥信号量（P61）：

A用完B用，A和B就是互斥

semaphore mutex = 1;
Pa(){
    while(1){
        wait(mutex);
        临界区;
        signal(mutex);
        剩余区;
    }
}
Pb(){
    while(1){
        wait(mutex);
        临界区;
        signal(mutex);
        剩余区;
    }
}
复制代码

8 信号量的（应用）—实现前驱关系（P61）：

设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2，我们希望在S1执行之后再执行S2，为实现这种前驱关系，只需进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal（S）操作放在语句S1的后面，而在S2语句的前面插入wait（S）操作，即

在进程P1中，用S1；signal（S）

在进程P2中，用wait（S）；S2

由于S被 初始化为0，这样若先执行S2必为阻塞，只有在进程P1执行完S1；signal（S）操作后使S变为1是，P2进程才能成功执行语句S2。

9 线程（P81）：

引入线程后：资源分配还是进程，但是资源调度变为了线程

前言:

引入进程–>为了多个程序并发执行，提高资源利用率和吞吐量。

引入线程–>为了减少程序在并发执行时所付出的时空开销，使系统具有更好的并发性。

定义：

线程是进程的一个实体，是独立调度的一个基本单位。

第三章 处理机调度与死锁

1 三级调度（P92）：

（1）低级调度：

[最基本的调度，在多道批处理、分时和实时的三种类型的OS中必须配置] 又称为进程调度或短程调度，调度对象为进程，主要功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。

（2）中级调度：

又称为内存调度，主要目的是提高系统内存的利用率和系统的吞吐量，实际上就是存储管理器中的对换功能。

（3）高级调度：

[主要用于多道批处理系统] 又称为长程调度或作业调度，调度对象为作业，主要功能是根据某种算法，决定将外存中处于后备队列中的哪几个作业调入内容，为他们创建进程、分配必要的资源，并将其放入队列。

小扩展:

运行频率 ： 低级调度 > 中级调度 > 高级调度

2 调度算法（P96）：

（1）先来先服务（FCFS）：

最简单的调度算法，可用于作业调度和进程调度，主要思想就是按照作业到达的先后顺序来进行调度。

（2）短作业优先（SJF）：

根据作业的时间长短来决定作业的优先级，时间越短优先级越高，作业的长短是指作业要求的运行时间决定，从后背队列中选择时间短的优先执行。

• 优点
  提高系统吞吐量，有效降低平均等待时间。
• 缺点
  必须预知作业的时间；对长作业不利；无法实现人机交互；未考虑作业的紧急程度；

（3）优先级调度算法（PSA）：

核心在于确定作业的优先级，可用于进程调度和作业调度，使用该算法进行作业调度时需要事先在外部定义好该作业的优先级。

（4）高响应比调度算法（HRRN）：

既考虑作业的运行时间，又考虑作业的等待时间，设置优先级为动态，规律为：

3 死锁（P112）：

产生死锁的必要条件：

（1）互斥条件

（2）请求和保持条件

（3）不可抢占条件

（4）循环等待条件

预防死锁：

（1）破坏“请求和保持条件”

（2）破坏“不可抢占”条件

（3）破坏“循环等待”条件

4 *银行家算法（P120）

银行家算法—避免死锁(P122)：

什么是银行家算法？

[百度百科] ：在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行.

银行家算法的数据结构：

（1）可利用资源向量Available

是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有R类资源K个。

（2）最大需求矩阵Max

这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要R类资源的最大数目为K。

（3）分配矩阵Allocation

这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得R类资源的 数目为K。

（4）需求矩阵Need

这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要R类资源K个，方能完成其任务。

如图所示：

避免死锁的核心方法和流程图：

Need [ i, j ] = Max [ i , j ] - Allocation [ i , j ]

解释一下：就是让需求等于已经分配的加上再向操作系统请求的，比如对于P0进程，该公式换算后的结果就是

0 0 1 2 = 0 0 4 4 - 0 0 3 2 就可以根据任意两个变量计算出第三个变量