计算机操作系统¶

概述¶

操作系统是一门很神奇的学科，他在我们进行计算机学习中占据着重要的地位，现在主流有很多操作系统，比如大家所熟知的Window操作系统，Linux操作系统，Harmony操作系统，IOS操作系统。可以说是百家齐放。今天我们就来学习一下操作系统这个有趣的内容。

定义和目标¶

定义：操作系统是控制管理计算机系统的硬软件，分度调配资源的系统软件

目标：方便性，有效性，可拓展性，开放性

基本功能¶

统一管理计算机资源，实现对于计算机资源的抽象，提供用户和计算机之间的接口

特征¶

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

并发：指俩个或多个事件可以同时发生，多核CPU可以实现并行 指俩个或多个时间可以同一时间间隔发生，看起来是每个程序都在运行，但是实际上是交替运行

共享：操作系统中的资源可以提供多个并发程序共同使用，资源共享

虚拟：把一个物理实体转变为若干个虚拟实体（时分复用技术，空分复用技术）

异步：在多道程序环境下，允许多个程序并发执行，运行 暂停 速度 完成

操作系统的发展历程¶

1. 手工操作阶段 - 程序员直接操作计算机硬件 - 无操作系统，效率低下

2. 批处理系统 - 单道批处理系统：一次只处理一个作业 - 多道批处理系统：内存中同时存放多个作业

3. 分时系统 - 将CPU时间分成时间片，轮流分配给各终端用户 - 特征：交互性、及时性、多路性

4. 实时系统 - 确保在规定时间内完成任务 - 分为硬实时（严格时间要求）和软实时（偶尔超时可接受）

中断处理¶

中断产生：

• 发生中断时，CPU立马切换到管态，开展管理工作；（管态又叫特权态，系统态或核心态，是操作系统管理的程序执行时，机器所处的状态。）
• 发生中断后，当前运行的进程回暂停运行，由操作系统内核对中断进行处理；
• 对于不同的中断信号，会进行不同的处理。

中断的分类： - 内中断：来自CPU内部，如程序错误、系统调用 - 外中断：来自外部设备，如I/O完成、时钟中断

进程管理¶

进程的基本概念¶

进程管理实体进程

为什么要用进程：

• 进程是系统进行资源分配和调度的基本单位

• 进程作为程序独立运行的载体保证程序的正常执行

• 进程的存在使得操作系统资源的利用大幅提升

进程控制块（PCB）：用于描述和控制进程运行的通用数据结构，记录进程状态和控制进程运行的全部信息，是进程存在的唯一标识。

PCB的内容： - 进程标识符（PID） - 处理机状态（程序计数器、寄存器等） - 进程调度信息（状态、优先级等） - 进程控制信息（程序地址、I/O资源等）

进程与线程¶

进程和线程的区别：线程是操作系统运行调度的最小单位，进程是系统进行资源分配和调度的基本单位

区别和联系：

• 一个进程可以有一个或者多个线程

• 线程包含在进程里面，是进程中实际运行的工作单位

• 进程的线程共享进程资源

• 一个进程可以并发多个线程，每个线程执行不同的任务

线程的优点： - 创建和切换开销小 - 通信方便（共享内存） - 并发度提高

线程的缺点： - 一个线程崩溃可能导致整个进程崩溃 - 不适合多核CPU的负载均衡

进程的状态转换¶

进程管理的五个状态有就绪状态，执行状态，阻塞状态，创建状态，终止状态

• 就绪状态：其他资源都准备好，但是CPU没有准备好

• 执行状态：进程获得CPU，程序正在执行

• 阻塞状态：进程因为某种原因放弃CPU的状态，阻塞进程队列的形式存在

• 创建状态：创建进程拥有PCB，但是其他资源没有就绪

• 终止状态：进程结束由系统清理或者归还PCB状态

状态转换： - 创建 → 就绪：分配资源完成 - 就绪 → 执行：获得CPU - 执行 → 就绪：时间片用完 - 执行 → 阻塞：等待I/O - 阻塞 → 就绪：I/O完成 - 执行 → 终止：正常结束或异常

进程同步¶

进程同步的作用：对竞争资源在多进程间进行使用次序的协调，使得并发执行的多个进程之间可以有效使用资源和相互合作。

进程间同步的四原则：

空闲让进：资源无占用，允许使用； 忙则等待：资源被占用，请求进程等待； 有限等待：保证有限等待时间能够使用资源； 让权等待：等待时，进程需要让出CPU。

经典同步问题：

1. 生产者-消费者问题：有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费，生产者进程和消费者进程可以并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程需要将所生产的产品放到缓冲区中（+1操作），消费者进程可以从缓冲区取走产品消费（-1操作）。

产生问题：当两者并发执行时可能出差错，导致预期的结果与真实的结果不相符：当执行生产者+1和消费者-1操作之后，缓冲区的值从10变为了11

解决方案：使用信号量机制

// 伪代码
semaphore mutex = 1;  // 互斥信号量
semaphore empty = n;  // 空闲缓冲区数量
semaphore full = 0;   // 已用缓冲区数量

// 生产者
producer() {
    while(1) {
        produce_item();
        P(empty);      // 申请空闲缓冲区
        P(mutex);      // 进入临界区
        put_item();
        V(mutex);      // 离开临界区
        V(full);       // 增加已用缓冲区
    }
}

// 消费者
consumer() {
    while(1) {
        P(full);       // 申请已用缓冲区
        P(mutex);      // 进入临界区
        get_item();
        V(mutex);      // 离开临界区
        V(empty);      // 释放空闲缓冲区
        consume_item();
    }
}

2. 哲学家进餐问题：有5个哲学家，他们的生活方式是交替的思考和进餐，哲学家们共同使用一张圆桌，分别坐在5张椅子上，圆桌上有5只碗和5只筷子。平时哲学家们只进行思考，饥饿时则试图取靠近他们的左右两只筷子，只有两只筷子都被拿到的时候才能进餐，否则等待，进餐完毕后，放下左右筷子进行思考。

这会导致以下的问题，筷子就相当于临界资源：

临界资源指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。

解决方案： - 限制同时进餐的哲学家数量（最多4人同时） - 奇数号哲学家先拿左边筷子，偶数号先拿右边筷子

内存管理¶

内存管理的基本概念¶

内存管理的功能： - 内存的分配与回收 - 地址转换 - 内存保护 - 内存扩充

内存分配方式¶

1. 连续分配方式

• 单一连续分配：将内存分为系统区和用户区，只能用于单用户单任务系统
• 固定分区分配：将内存划分为若干固定大小的分区
• 动态分区分配：根据进程的实际需要动态地划分内存

动态分区分配算法： - 首次适应算法：从头开始找第一个满足的空闲区 - 最佳适应算法：找最小的能满足的空闲区 - 最坏适应算法：找最大的空闲区 - 邻近适应算法：从上次结束位置开始找

2. 离散分配方式

• 分页存储管理：将进程的逻辑空间分成若干页面，内存分成若干块，页面大小与块大小相等
• 分段存储管理：将程序的地址空间划分为若干段，每段有独立的逻辑意义
• 段页式存储管理：结合了分页和分段的优点

分页与分段的比较：

虚拟存储器¶

虚拟存储器的定义： 虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

虚拟存储器的实现方式： - 请求分页存储管理：进程开始时只装入部分页面，需要时再调入 - 请求分段存储管理：只装入部分段，需要时再调入 - 请求段页式存储管理：结合请求分页和请求分段

页面置换算法¶

1. 最佳置换算法（OPT） - 淘汰以后永不使用的，或者在最长时间内不再被访问的页面 - 理论上最优，但无法实现，只能作为评价其他算法的标准

2. 先进先出置换算法（FIFO） - 淘汰最早进入内存的页面 - 实现简单，但性能较差，可能出现Belady异常

Belady异常：增加分配的物理块数，缺页率反而上升

3. 最近最久未使用置换算法（LRU） - 淘汰最近最久未被访问的页面 - 性能接近OPT，实现较复杂

LRU的实现方法： - 计数器法：为每个页面添加访问时间戳 - 栈方法：用栈记录最近访问的页面

4. 时钟置换算法（Clock） - LRU的近似算法，实现简单，性能较好 - 使用访问位（reference bit）

改进的时钟算法：考虑访问位和修改位

5. 最不常用置换算法（LFU） - 淘汰访问次数最少的页面 - 需要维护访问计数器

页面置换算法比较¶

文件管理¶

文件系统¶

文件的定义： 文件是具有文件名的一组相关信息的集合，是操作系统管理信息的基本单位。

文件的分类： - 按用途：系统文件、库文件、用户文件 - 按数据形式：源文件、目标文件、可执行文件 - 按保护级别：只读文件、读写文件、可执行文件

文件的逻辑结构¶

1. 有结构文件 - 顺序文件：记录按某种顺序排列 - 索引文件：建立索引表，提高查找效率 - 索引顺序文件：结合顺序文件和索引文件的优点

2. 无结构文件 - 字符流形式，由字符序列组成

文件的物理结构¶

1. 连续分配 - 文件占用的磁盘块是连续的 - 访问速度快，但容易产生外部碎片

2. 链接分配 - 隐式链接：每个磁盘块中包含指向下一个块的指针 - 显式链接：使用文件分配表（FAT）或索引表

3. 索引分配 - 为每个文件建立索引块 - 支持直接访问，适合大文件

文件存储空间管理¶

1. 空闲表法 - 使用一个表格记录空闲块

2. 空闲链表法 - 空闲盘块链：将所有空闲盘块链接成链表 - 空闲盘区链：将连续的空闲盘区链接成链表

3. 位示图法 - 使用二进制位表示磁盘块的状态（0空闲，1占用）

4. 成组链接法 - 结合空闲表和空闲链表的优点

目录管理¶

目录的功能： - 实现"按名存取" - 提高文件检索速度 - 允许文件重名 - 实现文件共享

目录结构： - 单级目录结构：所有文件都在同一目录中 - 两级目录结构：主目录和用户文件目录 - 树形目录结构：多级目录，支持层次结构 - 图形目录结构：允许文件有多个父目录

设备管理¶

I/O系统层次结构¶

用户层I/O软件
    ↓
设备独立性软件
    ↓
设备驱动程序
    ↓
中断处理程序
    ↓
硬件

I/O控制方式¶

1. 程序I/O方式 - 由用户进程直接控制 - CPU利用率低

2. 中断驱动I/O方式 - 使用中断机制 - 提高了CPU利用率

3. DMA方式 - 直接存储器访问 - 数据传输不经过CPU

4. 通道控制方式 - 使用独立的I/O处理器 - CPU几乎不参与I/O操作

设备分配¶

设备分配的数据结构： - 设备控制表（DCT） - 控制器控制表（COCT） - 通道控制表（CHCT） - 系统设备表（SDT）

设备分配的算法： - 先请求先服务 - 优先级高者优先

缓冲技术¶

缓冲的目的： - 缓和CPU与I/O设备速度不匹配的矛盾 - 提高设备利用率 - 实现设备间的并行操作

缓冲的类型： - 单缓冲 - 双缓冲 - 循环缓冲 - 缓冲池

调度算法¶

调度的层次¶

1. 高级调度（作业调度） - 从后备队列中选择作业调入内存 - 创建进程，分配资源

2. 中级调度（内存调度） - 将暂时不能运行的进程调至外存 - 提高内存利用率

3. 低级调度（进程调度） - 从就绪队列中选择进程分配CPU - 频率最高

进程调度算法¶

1. 先来先服务（FCFS） - 按进程到达的先后顺序进行调度 - 简单，但可能导致"护航"效应

2. 短作业优先（SJF） - 选择估计运行时间最短的进程 - 平均等待时间最短，但难以准确估计

3. 优先级调度 - 为每个进程分配优先级 - 优先级高的进程优先执行

4. 时间片轮转 - 给每个进程分配一个时间片 - 时间片用完后，进程切换 - 适合分时系统

5. 多级反馈队列调度 - 设置多个就绪队列 - 不同队列有不同的时间片和优先级 - 综合了多种调度算法的优点

死锁¶

死锁的定义¶

死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

死锁产生的必要条件¶

1. 互斥条件 - 资源在某一时刻只能由一个进程使用

2. 请求和保持条件 - 进程已经保持了至少一个资源，但又提出了新的资源请求

3. 不可抢占条件 - 资源不能被抢占，只能在使用完后释放

4. 循环等待条件 - 存在一个进程资源的循环等待链

注意：这四个条件必须同时满足才会发生死锁。

死锁的预防¶

1. 破坏互斥条件 - 允许资源共享 - 但有些资源必须互斥使用

2. 破坏请求和保持条件 - 实行静态分配，进程在运行前一次性申请所有资源

3. 破坏不可抢占条件 - 允许进程抢占资源

4. 破坏循环等待条件 - 实行资源有序分配策略

死锁的避免¶

银行家算法： - 每次分配资源前，先判断系统是否安全 - 如果系统安全，才进行分配 - 如果系统不安全，进程等待

死锁的检测¶

资源分配图： - 用节点表示进程和资源 - 用边表示分配和请求关系 - 如果图中存在环路，则可能存在死锁

学习建议¶

理解重点： - 进程与线程的区别 - 虚拟内存的实现原理 - 文件系统的组织方式 - 死锁的产生条件和处理方法

实践建议： - 学习Linux操作系统的使用 - 阅读简单的操作系统源代码 - 编写简单的系统调用程序 - 模拟实现基本的调度算法

操作系统是计算机科学的核心课程，掌握操作系统的原理对于成为一名优秀的程序员至关重要！