一.操作系统的演进

1.无操作系统

• 人工操作
• 用户独占
• cpu等待人工操作
• 资源利用率很低

2.批处理系统

• 无需人工等待
• 批量输入任务
• 资源利用率提升
• 多道程序设计

3.分时系统

• 人-机交互
• 多用户共享
• 及时调试
• 资源利用率提升

4.多道程序的设计

• 早期批处理系统只能一次处理一个任务
• 多道程序设计使得批处理系统可以一次处理多个任务
• 多道程序设计：
• 多道程序设计是指在计算机内存中间同时存放多个程序
• 多道程序在计算机的管理程序之下相互穿插进行

5.五大功能

• 进程管理
• 存储管理
• 作业管理
• 文件管理
• 设备管理

二.操作系统概览

1.什么是操作系统呢？

• 操作系统是管理计算机硬件和软件资源的计算机程序
• 管理配置内存，决定资源供需顺序，控制输入输出设备等
• 操作系统提供让用户和系统交互的操作界面
• 管理硬件提供用户交互的软件系统

2.操作系统分类

• Android：MIUI，ColorOS，Flyme
• Linux：Centos，Ubuntu
• 华为：鸿蒙

3.操作系统存在原因

• 我们不能直接操作计算机硬件
• 设备种类繁多复杂，需要统一界面
• 操作系统的简易性

4.操作系统的基本功能

• 处理器资源：cpu
• 存储器资源：内存，磁盘
• io资源
• 文件资源

5.操作系统相关概念

• 并发性
• 共享性
• 虚拟性
• 异步性

什么是并发和并行？

• 并行指两个或多个事件可以在同一个时刻发生
• 并发是指两个或多个事件可以在同一个时间间隔发生
• 并行：在8:00时刻张三在学习，李四在洗澡，这个属于同一时刻发生的事
• 并发：在8:00时候李四看了会历史书，8:05时候看了数学书，那么这个属于在一个时间段发生的事
• 在操作系统中实现：
  单处理器：多个程序交替执行，实现并发，单个处理器中只能实现并发
  多个处理器：多个处理器上的程序一起执行，但是对于一个处理器多核的话也可以实现并行，但是对于单核处理器来说还是以并发执行

什么是共享性？

• 共享性表现为操作系统中的资源可供多个并发的程序共同使用
• 这种共同使用的形式称之为资源共享
• 多个程序可以同时使用主存资源
• 资源共享根据属性可分为两种方式：互斥共享形式，同时访问形式

什么是虚拟性？

• 虚拟性表现为把一个物理实体转变为若干个逻辑实体
• 物理实体是真实存在的，逻辑实体是虚拟的
• 虚拟的技术要有时分复用技术和空分复用技术
• 时分复用：资源在时间上进行复用，不同的程序并发使用，多道程序分时使用计算机的硬件资源，提高资源利用率
• 空分复用：空分复用技术用来实现虚拟磁盘，虚拟内存等，提高资源利用率

什么是异步性？

• 在多道程序环境下，允许多个进程并发执行
• 进程在使用资源时可能需要等待或放弃
• 进程的执行并不是一气呵成的，而是以走走停停的形式推进的

为什么需要进程？

• 进程是系统进行资源分配和调度的基本单位
• 进程作为程序独立运行的载体保证程序正常执行
• 进程的存在使得操作系统资源的利用率大幅提升

进程的实体？

• 进程控制块
• 线程和进程区别：
• 

进程管理之五状态模型？

• 就绪状态：当进餐被分配到除cpu之外所有必要的资源后
• 只要再获得cpu的使用权，就可以立即运行
• 其他资源都准备好，只差cpu资源的状态就为就绪状态
• 执行状态：进程获得cpu，其他程序正在执行状态
• 在单处理机中，在某个时刻只能有一个进程是处于执行状态的
• 阻塞状态：进程因某种原因如：其他设备未就绪而无法继续执行
• 从而放弃cpu的状态称为阻塞状态

状态间切换？（还有创建和终止 ）

• 创建进程时拥有PCB但其他资源尚未就绪的状态称为创建状态。
• 进程结束由系统清理或者归还PCB的状态称为终止状态。
  

为什么需要进程间的同步？

• 生产者-消费者模型
  

• 生产者往缓冲区+1

• 消费者往缓冲区-1

• 缓冲区在cache（在高速缓存中）

• 操作缓冲需要三个步骤
  （1）把缓冲区中的数据拿出来到寄存器中
  （2）然后寄存器进行+1
  （3）然后再把寄存器中的值写回到缓冲区

• 哲学家进餐问题

• （1）正常情况：拿起左边筷子，发现右边筷子被拿了。等待右边筷子释放，拿起右边筷子，进餐

• （2）假设五个哲学家同时拿起左边的筷子（造成死锁 ）

这两个问题根源：

• 彼此间没有通信
• 需要进程间的同步

进程同步原则？

• 空则让进：资源无占用，允许使用
• 忙则等待：资源有占用，请求进程等待
• 有限等待：保证有限等待时间能够使用资源
• 让权等待：等待时，进程需要让出CPU
• 进程间同步的方法：消息队列，共享存储，信号量

线程同步？

• 线程同步方法：
• （1）互斥量
• （2）读写锁
• （3）自旋锁
• （4）条件变量

linux进程的相关概念？

• 进程类型：
• （1）前台进程：优先级高需要和用户交互
• （2）后台进程：优先级低
• （3）守护进程：守护进程是特殊的后台进程，很多守护进程在系统引导时候就启动，一直运行到系统关闭。（crond sshd httpd mysqld）

进程的标记？

• 进程ID是进程的唯一标记，每个进程拥有不同的ID
• 进程ID表现为一个非负整数，最大值由操作系统限定

---

linux进程相关命令？

• ps命令：ps命令常用于显示当前进程的状态，ps命令常配合aux参数或ef参数和grep命令检索特定进程
• top命令；操作系统使用内存状态
• kill命令： kill -9 进程id关闭信号，给特定的线程发送信号，kill -l可以查看操作系统支持的信号，使用9信号无条件终止

作业管理之进程的调度？

• 进程调度概述：进程调度是指计算机通过决策决定哪个就绪进程可以获得cpu使用

• （1）保留就进程的运行信息，请出旧进程

• （2）选择新进程，准备运行环境并分配cpu

• 调度机制：
  （1）就绪队列的排队机制：按照一定方式排成队列，以便调度程序可以最快找到就绪进程
  （2）选择运行进程的委派机制：调度程序以一定的策略选择就绪进程，将cpu资源分配给它
  （3）新老进程的上下文切换机制：保存当前进程上下文信息，装入被委派执行进程的运行上下文

• 非抢占式调度：
  （1）处理器一旦分配给某个进程，就让该进程一直使用下去
  （2）调度程序不以任何原因抢占正在被使用的处理器
  （3）直到进程完成工作或因为IO阻塞才会让出处理器。

• 抢占式调度
  （1）允许调度程序以一定的策略暂停当前运行的进程
  （2）保存好旧进程的上下文信息，分配处理器给新进程

• 进程调度算法
  （1）先来先服务调度算法：优先取出来的进程
  （2）短进程优先调度算法： 调度程序优先选择就绪队列中估计运行时间最短的进程，不利于长进程使用
  （3）高优先权优先调度算法：进程附带优先权，调度程序优先选择权重高的进程，高优先权优先调度算法使得紧迫的任务可以优先处理。
  （4）时间片轮转调度算法： 按先来先服务的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行，是相对公平的调度算法，但不能及时响应用户。

作业管理之死锁？

• 死锁产生？

  • 竞争资源
    （1）共享资源数量不满足各个进程需求
    （2）各个进程之间发生资源争抢导致死锁
    

• 进程调度顺序不当

• 死锁产生的必要条件？
  （1）互斥条件：进程对资源的使用是排他性的使用，某资源只能由一个进程使用，其他进程需要使用只能等待
  （2）请求保持条件：进程至少保持一个资源，又提出新的资源请求。新资源被占用，请求被阻塞。被阻塞的进程不释放自己保持的资源。
  （3）不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺。获得的资源只能由进程自身释放
  （4）环路等待条件：发生死锁时，必然存在进程-资源环形链。

• 预防死锁的方法？
  （1）摒弃请求保持条件，系统规定进程运行之前，一次性申请所有需要的资源。
  进程在运行期间不会提出资源请求，从而摒弃请求保持条件。
  （2）摒弃不可剥夺的条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源。
  进程运行时占有的资源可以被释放，意味着可以被剥夺。
  （3）摒弃环路等待条件，可用资源线性排序，申请必须按照需要递增申请。
  线性申请不再形成环路，从而摒弃环路等待条件。

• 银行家算法？
  （1）是一个可操作的著名的避免死锁的算法
  （2）以银行借贷系统分配策略为基础的算法。

（3）需要三个表已分配的表，所需表，可分配表

什么是原子性？

• 原子性是指一系列操作不可被中断的特性

• 这一系列操作要么全部执行完成，要么全部没有执行

• 不存在部分执行部分执行的情况

  线程同步之互斥量？

• 互斥量是最简单的线程同步方法

• 互斥量（互斥锁），处于两态之一的变量：解锁和加锁

• 两个状态可以保证资源访问的串行

• 操作系统提供了API完成资源的加锁，解锁操作，c语言提供的是pthread_mutex_t

线程同步之自旋锁？

• 

线程同步之自旋锁的优点？

• 自旋锁避免了进程和线程上下文开销
• 操作系统内部很多地方使用的是自旋锁
• 自旋锁不适合在单核cpu使用

线程同步之读写锁？（适用多读少写）

• 读写锁是一种特殊的自旋锁
• 允许多个读者同时访问资源以提高读性能
• 对于写操作则是互斥的

线程同步锁？

• mutex lock（互斥锁）
• rwlock_rdlock(读写锁)

线程同步之条件变量？

• wait-notify

线程同步方法总结？

使用fork创建进程？

fork函数返回两次

进程同步的方法？

• 进程中的线程是共享进程中的资源
• 进程是共享计算机资源的
• 共享内存

使用共享内存的步骤？

进程同步之Unix域套接字？

服务端和客户端

存储管理之内存分配与回收

• 单一连续分配
  （1）单一连续分配是最简单分配方式。
  （2）只能在单用户，单进程的操作系统中使用

• 固定分区分配
  （1）固定分区是支持多道程序的最简单存储分配方式。
  （2）内存空间被划分为若干固定大小的分区
  （3）每个分区提供给一个程序使用，互不干扰。

• 动态分区分配？
  （1）动态分区空闲表数据结构
  （2）动态分区空闲链数据结构（双向链表）动态分区是把临近节点和起来，节点需记录可存储的容量。
  
  （3）动态分配算法：（考点）
  - 首次适应算法（FF）
  - 最佳适应算法（BF）
  - 快速适应算法（QF）

首次适应算法：
- 分配内存时从开始顺序查找适合内存区
- 若没有合适的空闲去，则该次分配失败
- 每次从头部开始，使得头部地址空间被划分。（缺点）
- 改善：使用循环适应算法，可以从当前节点继续检索
最佳适应算法：将空闲区先排序，避免大才小用
- 最佳适应算法要求空闲区链表按照容量大小排序。
- 遍历空闲区链表找到最佳合适空闲区。

快速适应算法？快速找到适合进程的分区
- 快速适应算法要求有多个空闲区链表
- 每个空闲区链表存储一种容量的空闲区

• 内存回收过程
  （1）回收区在空闲区下面
  - 不需要新建空闲链表节点
  - 只需要把空闲区1的容量增大为空闲区

（2）回收区在空闲区上面
- 将回收区与空闲区合并
- 新的空闲区使用回收区的地址

（3）回收区位于两个空闲区之间
- 将空闲区1，空闲区2和回收区合并
- 新的空闲区使用空闲区1的地址

（4）回收区 自己
- 为回收区创建一个节点
- 插入到相应的空闲区链表中去

存储管理之段页式存储管理？

1.页式存储管理
2.段式存储管理
3.段页式存储管理

- 页式存储管理？

（1）将进程逻辑空间等分成若干大小的页面
（2）相应的把物理内存空间分成与页面大小的物理块
（3）以页面为单位把进程空间装进物理内存中分散的物理块。

注意：（1）页面大小应该适中，过大难以分配，过小内存碎片过多。（在空闲链表中）
（2）页面大小通常是512b-8k

页表：记录进程逻辑空间与物理空间的映射。（每个页面对应一个物理块，对应一个物理块号）（多级页表）

地址：页号+页面偏移
缺点：有一段连续的逻辑分布在多个页面中，将大大降低执行效率。
- 段式存储管理

（1）将进程逻辑空间划分成若干段（非等分）
（2）段的长度由连续逻辑的长度决定
（3）主函数main，子程序x，子函数y等。

段表：记录进程逻辑和物理空间的映射。根据段号去锁定
段地址：段号+段内偏移地址。

段适和页式的区别？

相同点：段式存储和页式存储都离散地管理了进程的逻辑空间。
不同点：
（1）页是物理单位，段是逻辑单位。
（2）分页是为了合理利用空间，分段是满足用户要求。
（3）页大小由硬件固定，段长度可动态变化
（4）页表信息是一维的，段表信息是二维的。

- 段页式存储管理？

（1）页式优点：分页可以有效提高内存利用率。
（2）分段可以更好满足用户需求。

（1）先将逻辑空间安段式存储分成若干段
（2）再把段内空间按页式管理等分成若干页

段页地址：段号+段内页号+页内地址

存储管理之虚拟内存？

• 虚拟内存？（把程序使用内存划分，将部分暂时不使用的内存放置在辅存，将进程的逻辑空间加载到物理空间，将不用的空间暂时放到磁盘）

（1）有些进程实际需要很大内存，超过物理内存的容量
（2）多道程序设计，使得每个进程可用物理内存更加稀缺
（3）不可无限增加物理内存，物理内存总有不够的时候。

程序的局部性原理？
（1）程序运行时，无需全部装入内存，装载部分即可。
（2）如果访问页不在内存，则发出缺页中断，发起页面置换
（3）从用户层面看，程序有很大的空间，即是虚拟内存。
虚拟内存：实际是对物理内存的补充，速度接近于内存，成本接近于辅存。

虚拟内存的页面置换算法？
[1]替换策略发生在Cache-主存层次，主存-辅存层次
[2]Cache-主存层次的替换策略主要是为了解决速度问题
[3]主存-辅存层次主要是为了解决容量问题

（1）先进先出算法（fifo）
（2）最不经常使用算法（lfu）
（3）最少使用算法（lru）

高速缓存的替换时机？

主存页面的替换时机？
主存缺页时

Linux的存储管理？

• Buddy内存管理算法？
  （1）Buddy算法是经典的内存管理算法
  （2）算法基于计算机处理二进制的优势具有极高的效率
  （3）算法主要是为了解决内存外碎片的问题

页内碎片：内部碎片是已经被分配出去（能明确指出属于哪个进程）的内存空间大于请求所需的内存空间，不能被利用的内存空间就是内部碎片。
页外碎片：外部碎片指还没有分配出去（不属于任何进程），但是由于大小而无法分配给申请内存空间的新进程的内存空闲块。

内存分配原则：向上取整为2的幂大小
伙伴系统：
（1）“伙伴”指的是内存的伙伴
（2）一片连续内存的“伙伴”是相邻的另一片大小一样的连续内存。

算法流程：创建一系列空闲块链表，每一种都是2的幂。1kb，2kb，4kb。。

存储空间1mb
分配100k

100k向上取整2的幂=128k
分配1m，然后拆分512，然后拆分256，然后128合格。

回收刚才分配的内存？

• Linux交换空间？（速度慢）

（1）交换空间（Swap）是磁盘的一个分区
（2）LInux物理内存满时，会把一些内存交换至Swap空间
（3）Swap空间是初始化系统时配置的

作用：
（1）冷启动内存依赖
（2）系统睡眠的依赖
（3）大进程空间依赖

交换空间和虚拟内存比较？

交换空间时存于磁盘，虚拟内存存在于磁盘
交换空间与主存发生置换，虚拟内存与主存发生置换。
交换空间是操作系统概念，虚拟内存是进程概念
交换空间解决系统物理内存不足问题，虚拟内存解决进程物理内存不足问题

操作系统的文件管理？

（1）逻辑结构的文件类型：有结构文件，无结构文件
（2）顺序文件：顺序文件是指按顺序存放在存储介质中的文件，磁带的存储特性使得磁带文件只能存储顺序文件，顺序文件是所有逻辑文件中存储效率最高的。（增删效率低）
（3）索引文件：可变长文件不适合使用顺序文件格式存储。索引文件是为了解决可变长文件存储而发明的一种文件格式，索引文件需要配合索引表完成存储的操作

• 辅存的分配方式？
  （1）连续分配：顺序读取文件内容非常容易，速度很快。
  对存储要求高，要求满足容量的连续存储空间。
  （2）链接分配：可以将文件储存在离散的盘块中，需要额外的存储空间储存文件的盘块链接顺序。
  （3）索引分配：把文件的所有盘块集中存储（索引），读取某个文件时，将文件索引读取进内存即可。

Linux文件基本操作？

• Linux目录

bin：执行的命令
etc：配置文件
home：主目录
usr/local：管理员的目录

相对路径：全路径
绝对路径：…/

linux的常见操作：
创建文件：touch file
编辑文件：vim file
查看文件内容：cat file
删除文件：rm file
创建文件夹：mkdir dir4
删除文件夹：rm -r dir4 递归删除
df-T 磁盘挂在信息

• 文件类型
  （1）套接字（s）
  （2）普通文件（-）
  （3）目录文件（d）
  （4）符号链接（l）
  （5）设备文件（b，c）
  （6）FIFO（p）

Linux文件系统？

• 文件系统的概览

（1）FAT：（File Allocation Table）FAT16，FAT32等，微软DOS/Windows使用的文件系统，使用一张表保存盘块的信息。
（2）NTFS：windowsnt环境的文件系统，NTFS对FAT进行了改进。
（3）EXT：扩展文件系统，linux文件系统，EXT2/3/4数字代表几代。

操作系统设备管理？

• 广义的IO设备：对CPU进行数据输入的都是输入设备，对CPU进行数据输入的都是输出设备。

• IO设备的缓冲区：减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性。
  

• SPOOLing技术