（一）

1. 操作系统的概念和定义

1.1. 操作系统的层次结构

从上至下，用户——应用程序——操作系统——裸机（纯硬件）。
image.png
操作系统OS(Operating System)是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配（从当前层次结构中间往两边看），提供用户和其他软件方便的接口和环境（当前层次结构从下往上看），同时它是计算机系统中最基本的系统软件（层次结构从上往下看）。

1.2.操作系统的功能和目标

image.png
（1） 系统资源的管理者image.png
（2）作为用户与计算机硬件之间的接口
image.pngimage.png联机命令接口又称为交互命令接口，给一句指令执行一句；脱机命令接口，给一堆命令执行一堆命令。
image.png程序接口等于系统调用。
（3） 作为最接近硬件的层次
image.png

1.3. 操作系统的四个基本特征

1.并发、共享、虚拟、异步。
image.png
（1）并发
并发:两个或多个事件同一时间间隔内发生，这些事件宏观上同时发生，微观上交替发生。
（易混淆概念 并行：指两个或多个事件在同一时刻同时发生）
操作系统的并发性是指计算机系统中同时存在着多个运行着的程序。
image.png
image.png
（2）共享
共享即资源共享，是指系统中资源可供内存众多个并发执行的进程共同使用。
image.png
并发和共享关系（互为存在条件）
image.png
（3）虚拟
虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体实际存在，而逻辑对应物使用户感受到的。
空分复用技术image.png时分复用技术image.png
image.png
（4）异步
异步是指多到程序环境下，允许多个程序并发执行，但资源有限，进程的执行不是一贯到底，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
image.png

1.4.操作系统的发展和分类

image.png
手工操作阶段：用户独占全机，人机速度矛盾导致资源利用率极低
批处理阶段：脱机输入/输出技术 （用磁带完成） 监督程序负责控制作业的输入、输出
image.png
多道批处理系统：
image.png
分时操作系统
image.png
实时操作系统image.png
image.png

1.5.操作系统的运行机制 体系结构

image.png
（1）两种指令
指令就是处理器（cpu）能是别的执行的最基本的命令
image.png
（2）两种处理器状态
image.png
（3）两种程序image.png
（4）操作系统的内核
image.png
内核是计算机上配置的底层软件，是操作系统最基本最核心的部分。实现操作系统内核功能的那些程序就是内核程序。
image.png
image.pngimage.png

1.6.中断和异常

image.png
(1) 中断机制的诞生
早期计算机个程序只能串行执行，系统资源利用率低，为了解决该问题，人们发明了操作系统，引入了中断机制，实现了多道程序并发执行。
发生中断就意味着需要操作系统介入，开展管理工作
中断是CPU从用户态进入核心态的唯一途径
image.png
（2）中断的分类
image.png
image.png
（3）外中断的处理过程
image.png

1.7.系统调用

image.png
image.png

系统调用与库函数
image.png
image.png

总结

（1）操作系统总结

image.png

（2）操作系统四个特征总结

image.png

（3）操作系统的发展和分类的总结

image.png

（4）操作系统的运行机制 体系结构 总结

image.png

（5）中断和异常总结

image.png

（6）系统调用

image.png

（二）

2.1 进程与线程

image.png

2.1.1 进程

（1）定义
程序：就是一个指令序列
早期的计算机（只支持单道程序） 程序的代码放在程序段内，程序运行过程处理的数据放在数据段内（如变量）
引入多道程序技术后：
image.png
程序段、数据段、PCB三部分组成进程实体（进程映像） 进程实体简称进程。
PCB是进程存在的唯一标志。
进程是系统进行资源分配和调度的基本单位。
image.png
（2）组成
程序段、数据段、PCB
进程的管理者（操作系统）所需要的数据都在PCB中，程序本身运行所需的数据在程序段和数据段中。
image.png
== PCB==image.png
（3）组织
进程的组织是多个进程之间的组织方式问题
image.png
链接方式
image.png
索引方式
image.png
（4）特征
image.png

2.1.2.进程的状态和转换

image.png
（1）进程的三种基本状态
image.png
进程的另外两种状态（创建态 终止态）
image.png
（2）进程状态的转换
image.png

2.1.3.进程控制

image.png
（1）进程控制的概念
进程控制就是实现进程状态的转换
image.png
原语 运行在核心态（在操作系统内核中）
image.png
关/开中断指令的权限非常大，只允许在核心态下执行的特权指令
进程控制一定会导致进程状态的转换
创建原语
image.png

撤销原语
image.png
阻塞原语和唤醒原语
image.png
== 切换原语==
image.png

2.1.4.进程通信

image.png
（1）进程通信概念
进程通信就是进程之间的信息交换。进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。为保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现，操作系统提供一些方法实现。
image.png
（2）共享存储
共享空间 对共享空间的访问是互斥的
image.png
（3）管道通信
半双工通信 若想双工 需要设置两个管道 各进程互斥的访问管道
image.png
（4）消息传递
进程中的数据交换以格式化的消息为单位 进程通过操作系统提供的 发送消息/接受消息 两个原语进行数据交换。
image.png

2.1.5.线程 多线程模型

image.png
（1）线程的引入
有的进程可能要同时做很多事，而传统的进程智只能串行地执行一列程序 为此引入线程来增加并发度。
传统的进程是程序执行流的最小单位
引入线程后：

  1. 线程可以理解为“轻量级进程” ，线程是一个基本的CPU执行单元，也是程序执行流的最小单位。
  2. 引入线程后，不仅是进程之间可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（qq视频 文字聊天 传文件）。
  3. 进程只作为除CPU外的系统资源的分配单元（如打印机 内存空间都是分配给进程的）

（2）引入线程机制的变化 image.png
（3）线程的属性
image.png
（4）线程的实现方式

  1. 用户级线程（user-Level Thread，ULT）
    image.png
    2. 内核级线程（Kernel-Level Thread KLT 又称为内核支持的线程）
    image.png
    3. 同时指挥用户级线程和内核级线程
    image.png
    （5）多线程模型多对一
    image.png
    一对一
    image.png
    多对多
    image.png

    总结

    （1）进程总结

    image.png

    （2）进程的状态和转换 总结

    image.png

    （3）进程控制 总结

    image.png

    （4）进程通信 总结

    image.png

    （5）线程 多线程模型 总结

    image.png

    2.2 进程的调度

    2.2.1.处理机调度

    image.png

  2. 概念
    当有一堆任务要处理，由于资源有限，事情没法同时处理。需要确定某种规则来决定处理这些任务的顺序，这就是调度研究的问题。
    image.png

  3. 调度的三个层次

（1）高级调度
image.png
（2）中级调度
image.png
挂起态与七状态模型
image.png
（3）低级调度
image.png
（4）三种调度的练习与对比image.png

2.2.2.进程调度的时机 切换与过程 调度方式

image.png
（1）进程调度的时机
image.png
image.png
image.png
（2） 进程调度的方式
非剥夺调度方式 剥夺调度方式image.png
（3）进程的切换与过程
image.png

2.2.3.调度算法的评价指标

image.png
（1）cpu利用率
忙碌时间/总时间=利用率
（2）系统吞吐量
单位时间内完成作业的数量 总共完成作业数/总共花的时间=系统吞吐量
（3）周转时间
从作业被提交给系统开始，到作业完成为止的时间间隔。image.png
作业完成时间-作业提交时间=周转时间 平均周转时间=各作业周转时间之和/作业数
带权周转时间
image.png
（4）等待时间
进城作业处于等待处理机状态时间之和image.png
（5）响应时间
用户从提交请求到首次产生响应的时间。

2.2.4.调度算法

先来先服务 最短作业优先 最高响应比优先
（1）先来先服务（FCFS first come first serve）
image.png
（2）短作业优先（SJF Shortest Job First）
抢占式、非抢占式
image.png
（3）高响应比优先算法（HRRN Highest Response Ratio Next ）
image.png
（4）总结
image.png
image.png
（1）时间片轮转调度算法（RR round-robin）
时间片太大，退化为先来先服务调度算法
时间片太小，进程切换频繁，系统花费时间更多image.png
（2）优先级调度算法
image.png
（3）多级反馈队列调度算法
image.png
（4）总结image.png

2.2.5.进程同步 进程互斥

image.png
（1）什么是进程同步
image.png
（2）什么是进程互斥
image.png
image.png
image.png

2.2.6.进程互斥的软件实现方法

image.png
（1）单标志法
image.png
image.png
（2）双标志先检查法
image.png
（3）双标志后检查法
image.png
（4）Peterson算法
image.png
image.png

2.2.7. 进程互斥的硬件实现方法

image.png
（1）中断屏蔽方法
image.png
不适用多处理机 关中断指令只对当前的处理机起作用
（2）TestAndSet指令（TS指令）
image.png
将检查和上锁的操作变为原子操作 防止异步带来的逻辑漏洞
（3）Swap指令
image.png

2.2.8. 信号量机制

image.png
（1）信号量机制
image.png
wait和signal操作简称P、V操作（荷兰语缩写 proberen verhogen）
（2）整型信号量
image.png
（3）记录型信号量
image.png
image.png
image.png

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

（1）信号量机制实现进程互斥
image.png
（2）信号量机制实现进程同步
image.png
image.png
（3）前驱关系
前操作之后执行V操作
后操作之前执行P操作
image.png

2.2.10. 生产者消费问题

image.png
image.png
image.png
image.png
image.png
总结
image.png

2.2.11. 多生产者多消费者（多类）

image.png
image.png
image.png
如果缓冲区大小为1，有时可以不设置互斥信号量（根据具体问题分析）
image.png
缓冲区为2或以上，如果不设置互斥信号量可能会导致数据覆盖问题
image.png
总结
image.png

2.2.12. 吸烟者问题（单生产者 多消费者）

image.png
image.png
缓冲区（桌子）大小为1，不需要设置互斥信号量
image.png
总结
image.png

2.2.13. 读者-写者问题

image.png
image.png

image.png
image.png
总结
image.png

2.2.14. 哲学家进餐问题

image.png

  1. //leetcode 1226
  2. class DiningPhilosophers {
  4.     private final ReentrantLock[] locks = {new ReentrantLock(),
  5.       new ReentrantLock(),
  6.       new ReentrantLock(),
  7.       new ReentrantLock(),
  8.       new ReentrantLock()};
  10.       private Semaphore eatLimit = new Semaphore(2);
  12.     public DiningPhilosophers() {
  14.     }
  16.     // call the run() method of any runnable to execute its code
  17.     public void wantsToEat(int philosopher,
  18.                            Runnable pickLeftFork,
  19.                            Runnable pickRightFork,
  20.                            Runnable eat,
  21.                            Runnable putLeftFork,
  22.                            Runnable putRightFork) throws InterruptedException {
  23.         int le = philosopher;
  24.         int re = (philosopher+1)%5;
  25.         eatLimit.acquire();
  27.         locks[le].lock();
  28.         locks[re].lock();
  30.         pickLeftFork.run();
  31.         pickRightFork.run();
  32.         eat.run();
  33.         putLeftFork.run();
  34.         putRightFork.run();
  36.         locks[le].unlock();
  37.         locks[re].unlock();
  39.         eatLimit.release();
  40.     }
  41. }


总结
image.png

2.2.15.管程

image.png
（1）为什么引入管程
image.png
（2）管程的定义和基本特征
管程类似于面向对象的类
特征1、2： 类似于类中的private变量 特征3：进程访问缓冲区互斥（对共享数据的访问只能有一个）
image.png
（3）用管程解决生产者消费者问题
image.png
封装思想
image.png
image.png

2.2.16.死锁

image.png
（1）什么是死锁image.png
（2）死锁 饥饿 死循环
image.png
（3）死锁产生的必要条件
image.png
（4）什么时候发生死锁
image.png
（5）死锁的处理策略
image.png

2.2.17. 预防死锁

image.png
（1）破坏互斥条件
image.png
（2）破坏不可剥夺条件
image.png
（3）破坏请求和保持条件
image.png
（4）破坏循环等待条件
image.png

2.2.18. 避免死锁

image.png
（1）什么是安全序列
image.png
image.png
（2）安全序列 不安全状态 死锁的联系
image.png
银行家算法
image.png
寻找安全序列的情况
image.png
找不到安全序列的情况
image.png
实现
image.png

2.2.19. 死锁的检测和解除

image.png
（1）死锁的检测
image.png
不能消除所有边 发生死锁
image.png
image.png
（2）死锁的解除
image.png

总结

（1）处理机调度 总结

image.png

（2）进程调度的时机 切换与过程 调度方式 总结

image.png

（3）调度算法的评价指标 总结

image.png

（4）进程同步 进程互斥 总结

image.png

（5）进程互斥的软件实现方法 总结

image.png

（6） 进程互斥的硬件实现方法 总结

image.png

（7）信号量机制 总结

image.png

（8） 信号量机制实现互斥、同步、前驱关系 总结

image.png

（9）管程 总结

image.png

（10）死锁 总结

image.png

（11） 预防死锁 总结

image.png

（12） 避免死锁（银行家算法） 总结

image.png

（13）死锁的检测和解除 总结

image.png

（三）

3. 内存

3.1 内存的基础知识

image.png
image.png
image.png
image.png
image.png
image.png
image.png

image.png

3.2 内存管理的概念

image.png
image.png
image.png

3.3 覆盖与交换

image.png

覆盖技术

image.png
image.png

交换技术

image.png

image.png

image.png

3.3 内存空间的分配和回收

image.png

3.3.1 连续分配管理方式

1.连续分配管理方式 系统为用户分配的必须是一个连续的内存空间
（1）单一连续分配
image.png
（2）固定分区分配
image.png
image.png
（3）动态分区分配
image.png
image.png
image.png
image.png
2.非连续分配管理方式

3.3.2 内存空间的扩充

（1）覆盖技术
image.png
image.png
（2）交换技术
image.png

3.3.3 动态分区分配算法

image.png
（1）首次适应算法
image.png
（2）最佳适应算法
image.png
image.png
（3）最坏适应算法
image.png
image.png
（4）邻近适应算法
image.png
image.png

3.3.4 非连续分配管理方式

image.png

（1）基本分页存储管理

image.png
image.png
image.png
image.png
（2）基本地址变换机构
image.png
image.png
image.png
（3）具有快表的地址变换机构
image.png

  • 局部性原理
    image.png
  • 什么是快表 TLB 联想寄存器
    image.png

image.png
（4）两级页表
image.png
单级页表存在的问题：
问题1：需要一段较大的连续页来存储页表项，当页表很大时，需要占用多个连续的页框，又违背了离散存储的优点。
问题2：没必要让整个页表常驻内存，因为进程一段时间可能只访问特定几个页面，造成内存空间的浪费。
image.png

  • 问题1解决办法 ： 两级页表
    image.png
    image.png
  • 问题2解决办法 ： 虚拟存储
    image.png
    -各级页表的大小不能超过一个页面
    image.png
    -多级页表访问内存需要更多的时间
    image.png
    （2）基本分段存储管理方式
    image.png
    分段
    image.png
    image.png
    段表

    总结

    （1）内存的基础知识

    image.png

    （2）内存管理的概念

    image.png

    （3）覆盖与交换

    image.png

    （4）连续分配管理

    image.png

    （5）动态分区算法

    image.png

    （6）基本分页存储管理

    image.png

    （7）基本地址变换机构

    image.png

    （8）具有快表的地址变换机构

    基本地址变换机构两次访问内存：
    第一次访问内存————查页表
    第二次访问内存————访问实际目标内存单元
    image.png

    （9）两级页表

    image.png