操作系统原理总结

对课本知识的概括和总结，来自《操作系统原理》第四版 —— 庞丽萍著

用户环境

操作系统的生成：

• 系统生成

• 根据计算机的硬件配置选择相应的功能模块来组装成一个可利用的操作系统

• 硬件配置信息可通过从文件读取或者系统程序员

• 系统初启

• 引导程序 => 系统核心 => 核心初始化

• 核心初始化：先建立 0# 进程（永远处于核心态，换页），再建立 1# 进程（初始化进程，实现系统初始化，负责为终端建立子进程）

• 用户程序的运行过程

• 编写源程序

• 将源程序记录在某种介质上

• 控制计算机工作，加工，得到计算结果

  • 编译
  • 链接
    • 静态链接：将外部调用函数链接到目标文件中形成一个完整的主存映像文件
    • 动态链接：运行时将动态链接库加载并链接到目标程序中
  • 运行

• 操作系统的用户界面

• 定义：用户和计算机打交道的外部机制。和用户上机类型和操作系统的的类型有关

• 系统提供的用户界面：操作命令、系统功能调用

• 系统功能调用

• 用户程序调用系统例程，由用户态进入管态

• 系统调用的实现：用户程序（用户态） => 发出自愿访管命令 => 访管中断程序保护现场，查找例行子程序入口地址表获取系统例程的入口地址 => 根据入口地址进行系统调用（管态） => 结果返回访管中断程序 => 恢复用户程序现场（用户态）

并发处理

提高计算机的处理能力和机器的利用率，但容易造成错误。

• 并发的特点

• 失去程序的封闭性：计算结果不再和时间无关，依赖于各程序的相对执行速率

• 程序和计算不再一一对应：过个计算可以公用一个程序

• 程序并发执行的相互制约

• 进程

• 进程的定义

  • 一个程序在给定的空间和初始环境下，在一个处理机上的执行过程
  • 进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动

• 进程和程序的区别：

  • 程序是指令的有序集合，其本身没有任何运行的含义，它是一个静态的概念，可永久保存
  • 进程是程序（指令）在处理机上的一次执行的过程，是动态的概念，有生命周期，动态地产生和消亡
  • 进程是独立运行的单位，能与其他进程并行的活动
  • 进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度额基本单位
  • 多任务的操作系统中，活动的最小单位是进程，进程一定包含一个程序，程序是进程应完成的功能的逻辑描述；一个程序可以多应多个进程

• 进程的类型

  • 用户进程：为用户算题任务建立的进程
  • 系统进程：资源管理和控制作用

• 进程的状态

  • 进程的基本状态：等待状态=>就绪状态<=>运行状态=>等待状态

• 进程的描述：进程控制块，是一个和进程对应的实体，记录进程的各种状态信息

• 线程概念及特点

  • 什么是线程
    • 线程是比进程更小的活动单位，它是进程中的一个执行路径。一个进程可以有多条的执行路径，每条路径就是一条线程
    • 线程有自己的堆栈和处理机执行环境（尤其是处理器寄存器）
    • 共享分配给父进程的主存
    • 若系统支持线程运行，那么每个进程至少有一个执行线程

• 线程的特点及状态

  • 线程的特点
    • 开销小，共享进程的程序和全局数据
    • 可以提高系统的并行处理能力
    • 线程拥有私有的指令计数器、私有的栈区、私有的寄存器集合和地址区域

• 线程的状态以及变迁

  • 创建，建立一个新的线程，新生的线程处于新建状态
  • 就绪，线程处于就绪队列中，等待被调度
  • 运行，一个线程正占用 CPU，执行它的程序
  • 等待，一个正在执行的线程如果发生某些事件，如被挂起或者需要执行费时的输入输出操作
  • 终止，线程已经退出，但该信息还没有被其他线程所收集

• 用户线程和内核线程

  • 用户线程是在内核的支持下，在用户层通过线程库来实现的。线程库提供对线程的创建、调度和管理等方面的支持。用户线程对内核来说是透明的，即内核并不知道线程的存在。相当于在单线程的进程中模拟多线程，这种线程不是 CPU 调度的单位，调度单位依然是线程
  • 内核线程是内核可感知的，由操作系统直接支持，在内核空间内执行线程的创建、调度和管理
  • 内核线程的创建、调度以及管理要比用户线程慢

• 进程控制

• 进程的创建（linux 中 fork，vfork，clone 的区别）、撤销、阻塞、唤醒

• 进程的相互制约关系

• 进程竞争与合作

  • 竞争系统资源
  • 进程间合作：信息共享；并行处理

• 进程互斥的概念

  • 临界资源：共享硬件资源、共享公用变量、共享表格等
  • 临界区：各个进程访问临界资源的那段程序
    • 在有限时间内进入临界区
    • 至多有一个进进程处于临界区
    • 进程在临界区内仅逗留有限的时间
  • 互斥：若干进程能够访问和修改的存储单元称为公共变量，公共变量或公共存储区一次只能被一个进程读写

• 进程同步的概念

  • 同步的例子：病人看病，医生开化验单，病人拿化验单去化验，将化验结果交给医生

• 同步机构

• 锁：上锁原语&开锁原语

• 原语的概念：不可分割的一系列操作。在单处理机上，该功能由操作系统提供支持，即软件方法实现，使得某进程在执行某原语所包含的一系列指令执行时不被中断。在多核处理机上必须要由硬件支持。详见 stackoverflow、Linux内核同步原语之原子操作、百度百科-原子操作、并行编程3——内存模型之原子性

  • 单处理器上的原语靠操作系统实现，即使该原语由一系列的指令完成，但只要操作系统不把线程中断（如线程调度）即可保证这一系列指令的原子性；此时其他线程等待的是时间片（处于就绪态）
  • 多处理器上的原语靠硬件实现，如果某原语由一系列的指令完成，即使执行该原语的线程在其运行的 CPU 上不被调度（或者说被中断），其他 CPU 上可能会有线程操作该原语对应的内存区域，此时并不能保证该 “原语” 的原子性，此时就需要 CPU 提供 LOCK 指令使得原语所操作的内存被锁上，那么其他 CPU 上在线程就不能操作该内存了，从而保证了原语的原子性，此时这些线程等待的是 UNLOCK 指令（处于阻塞状态）
  • 总的来说原语就是要保证相同内存只能被一个线程所操作

• 信号灯以及 P、V操作

  • 信号灯：从交通管理应用过来的一个术语，绿灯行（信号量非负），红灯停（信号量小于零）
  • P、V操作：P 操作和 V 操作都为原语
    • P 操作使得信号量减 1，如果信号量此时大于等于 0，那么进程继续；否则进入该信号灯的等待队列中
    • V 操作使得信号量加一，如果此时信号量大于零进程继续；如果小于零，说明有进程处于等待队列中，因此需要从等待队列中唤醒一个进程（原因：该进程由于等待而挂起，并不能自己唤醒自己）

• 进程互斥与同步的实现

• 互斥的实现：1) 上锁原语、开锁原语； 2)信号灯

• 同步的实现：信号灯以及 P、V 操作

  • 生产者消费者问题
  • 病人看病问题

//病人看病
main() {
    int s1 = 0; // 表示有无化验单的信号量，初始值为 0，表示没有
    int s2 = 0; // 表示有无化验结果的信号量，初始值为 0，表示没有
    cobegin             
        labora();          
        diagnosis();        
    coend
}

labora() {
    while(化验为完成) {
        p(s1); // 询问有无化验单，无则等待
        化验;
        V(s2); // 送出化验结果
    }
}

diagnosis() {
    while(看病工作未完成) {
        看病；
        V(s1); // 送出化验单
        P(s2); // 等化验结果
        diagnosis; // 诊断
     }
}

// 生产者消费者
main() {
    int full = 0; // 满缓冲区数目
    int empty = n; // 空缓冲区树木
    int mutex = 1; // 对有界缓冲区进行操作的互斥信号灯
    cobegin
        p1();p2();...;pm(); // 生产
        c1();c2();...;ck(); // 消费
    coend
}

producer() {
    while(生产未完成) {
           .
           .
        生产一个产品；
        P(empty);
        P(mutex);
        送一个产品到有界缓冲区;
        V(mutex);
        V(full);
    }
}

consumer() {
    while(还要继续消费) {
        P(full);
        P(mutex);
        从有界缓冲区中取出产品；
        V(mutex);
        V(empty);
           .
           .
        消费一个产品;
    }       
}

• 进程通信
  • 拷贝消息到另一个进程的地址空间
  • 信箱通信，进程 A 投递消息到进程 B 的信箱中；进程 B 投递从自己的信箱中获取消息。信箱可位于 B 的空间，也可位于系统空间
    • send 原语：可同步可异步，同步需等待对方接受；异步不关心对方是否接受
    • receive 原语：可以阻塞或非阻塞，如果阻塞，信息到来之前接收进程挂起；如果非阻塞，有消息将消息立即返回，无消息返回标志，表示没有消息可用

资源分配与调度

• 资源管理概述
• 资源管理的目的和任务
  • 资源的静态分配和动态分配：运行前一次性分配为静态分配；运行时根据运行情况动态的分配为动态分配
  • 资源分配的目标
    • 保证资源的高利用率
    • 在合理的时间内使所用的用户有获得所需资源的机会
    • 对不可共享的资源实施互斥使用
    • 防止由资源分配不当而引起的死锁
  • 资源管理的任务
    • 资源数据结构的描述：资源物理名、逻辑名、类型、地址、分配状态等
    • 确定请求的分配原则和调度原则：资源分给谁，何时分配，分配数量
    • 资源分配的执行：按需分配资源，回收资源
    • 存取控制和安全保护
• 资源的分类方法
  • 物理资源和程序资源：各种硬件资源为物理资源，系统服务、文件等为程序资源
  • 单一访问入口资源和多访问入口资源：单访问入口资源一次只能一个进程用，多访问入口资源一次允许多个进程用
  • 等同资源：多个资源的实例，如磁盘的各个扇区
  • 虚拟资源：如虚拟主存，虚拟 CPU 等
• 资源分配机制
• 资源描述器：描述资源最小分配单位的信息，如资源名、资源类型、分配标志等
• 资源信息块（rib）
  • 等待队列头指针：指向等待该资源的的进程队列
  • 可利用资源队列头指针：指向资源描述器组成的队列
  • 资源分配程序入口地址：执行分配任务，把对应的资源分配给请求者
• 资源分配策略
• 先请求先服务（先进先出，FIFO）
• 优先调度（针对处理机而言）：优先照顾需要尽快处理的作业或进程
• 针对设备特性的调度：如对磁盘资源的请求会考虑移臂距离和旋转次数
• 死锁
• 同类资源的死锁：A、B 为两个进程，C 资源两个实例，A、B 各自拥有一个 C 资源的实例，它们不释放已有的资源实例，并且继续申请 C 资源，此时产生同类资源的死锁
• 非同类资源的死锁：A、B 为两个进程，C、D 两个资源各有一个实例。A 占有 C 资源，B 占有 D 资源，它们都不释放已有的资源，同时 A 申请 D 资源，B 申请 C 资源，此时产生非同类资源的死锁
• 死锁的原因和条件
  • 产生死锁的根本原因：系统提供的资源数少于申请该资源的数目
  • 产生死锁的必要条件：
    • 互斥条件：资源为非共享的，或者说单一入口资源
    • 不剥夺条件：资源使用完之前，其他进程不能强行剥夺其他进程的资源
    • 占有并等待：进程申请其他资源时，不会释放已占有的资源
    • 环路条件：A 进程需要的资源被 B 进程占有，而 B 进程需要的资源被进程 C 占有 …… * 进程需要的资源被 A 进程占有
• 死锁的解决策略
  • 破坏死锁的必要条件之一
• 死锁的避免：
  • 静态预防：从根源避免死锁，作业在运行前说明所需要的所有资源，如果系统能够提供，那么投入运行，否则不能投入运行
  • 动态避免
    • 有序资源分配法：给资源标序号，一个进程对于同类资源需一次性申请完，对不同类资源需要按序申请。该方法避免死锁的原因：每一时刻，总有一个进程 A 占有已分配资源中序号最高的那一个，此进程继续申请的资源的序号必定更高，这些资源必定处于空闲，因此进程 A 可以推进，在执行完后释放已有资源；进程 A 执行完后，又有一个进程 B 和进程 A 之前的状态一样，占有已分配资源中序号最高的那一个，于是 B 进程也可顺利执行结束；以此类推，所有进程都可顺利执行而不会发生死锁
    • 银行家算法：某个进程将来需要的各类资源当前系统能够满足，则将此进程投入运行。该方法避免死锁的原因：（1）进程 A 在运行时最多需要 5 个资源 B，此时系统拥有 B 的实例有 10 个，满足条件，将 A 投入运行，A 暂时只用到了 2 个 B 资源实例；（2）此时 C 进程想投入运行，它所需资源 B 的最大个数为 7 个，而系统此时有 8 个，故 C 投入运行，C 暂时只用了 6 个；（3）A 此时又想获取 3 个 B 实例，但是 B 资源只有 2 个不够，于是等待；（4）C 再次申请 1 个资源，成功，C 执行完毕并释放所有 B 资源实例；（4）A 获得 2 个资源，执行完毕后释放所有 B 资源实例。该算法成功避免死锁的原因在于后来的申请者一定会释放所申请资源，使得系统所拥有资源量符合对较早申请者的承诺。

处理机调度

• 处理机的多级调度

• 批处理中的处理机调度

  • 先作业调度（宏观调度）：根据一定的策略挑选作业，建作业对应的进程，使其投入运行
  • 后进程调度（微观调度）：对于进入主存的进程的调度，什么时候把处理机分配给该进程

• 多任务操作系统的处理机调度：处理机空闲时，选择一个就绪的进程投入运行

• 多线程操作系统的处理机调度：处理机空闲时，选择一个就绪的线程投入运行

• 作业调度

• 作业的状态：后备状态（进入磁盘队列），执行状态（进入主存执行），完成状态（从完成到善后处理结束并退出）。

• 作业调度的功能：确定数据结构，确定调度算法，资源分配，善后处理

• 作业控制块：记录作业的有关信息，如作业名、作业类型、作业状态、作业对资源的要求等

• 调度算法的衡量：平均周转时间和平均带权周转时间

  • 平均周转时间为各个作业从进入磁盘到完成作业所花时间的平均值
  • 平均带权周转时间为各个作业的周转时间和运行时间（不包括在磁盘队列中的等待时间）的比值的平均值

• 作业调度算法

• 先来先服务（FIFO）：考虑等待时间

• 短作业优先：运行所花时间最短的作业优先执行，考虑运行时间

• 相应比高者优先：（等待时间／运行时间） 最大者优先，同时考虑等待时间和运行时间

• 优先调度算法：给各个作业分配优先数，优先数高者优先执行，优先数 = waiting_time² - running_time - 16 * output

• 进程调度

• 进程调度的功能和准则

  • 功能

主存管理

未完待续。。。