计算机组成原理 学习笔记I 计算机组成原理 学习笔记II
目录系列目录第1章 计算机系统概述1.1 操作系统的基本概念1.1_1 操作系统的定义、功能1.1_2 操作系统的特征 1.2 操作系统的发展与分类1.3 操作系统的运行环境🌟1.3_1 操作系统的运行机制🌟1.3_2 中断和异常1.3_3 系统调用 1.4 操作系统结构1.5 操作系统引导第2章 进程与线程2.1 进程与线程2.1.1 进程的概念、组成、特征2.1.2 进程的状态与转换、进程的组织2.1.3 进程控制2.1.4 进程通信2.1.5 线程的概念2.1.6 线程的实现方式和多线程模型2.1.7 线程的状态与转换 2.2 处理机调度2.2.1 调度的概念、层次2.2.2 进程调度的时机、切换与过程、方式2.2.3 调度器和闲逛进程2.2.4 调度算法的评价指标2.2.5 调度算法 2.3 同步与互斥2.3.1 进程同步、进程互斥2.3.2 进程互斥的软件实现方法🌟2.3.3 进程互斥的硬件实现方法🌟2.3.4 互斥锁2.3.5 信号量机制🌟🌟2.3.6 用信号量实现进程互斥、同步、前驱关系2.3.7 生产者-消费者问题2.3.8 多生产者-多消费者问题2.3.9 吸烟者问题2.3.10 读者写者问题2.3.11 哲学家进餐问题2.3.12 管程 2.4 死锁2.4.1 死锁的概念2.4.2 死锁的处理策略-预防死锁2.4.3 死锁的处理策略-避免死锁2.4.4 死锁的处理策略-检测和解除第3章 内存管理3.1 内存管理概念3.1.1 内存的基础知识3.1.2 内存管理的概念3.1.3 覆盖与交换(408大纲已删)3.1.4 连续分配管理方式3.1.5 动态分区分配算法3.1.6 基本分页存储管理方式3.1.7 基本地址变换机构3.1.8 具有快表的地址变换机构3.1.9 两级页表3.1.10 基本分段存储管理方式3.1.11 段页式管理方式 3.2 虚拟内存管理3.2.1 虚拟内存的基本概念3.2.2 请求分页管理方式3.2.3 页面置换算法3.2.4 页面分配策略、抖动、工作集3.2.5 内存映射文件第4章 文件管理4.1 文件系统基础4.1.1 初识文件管理4.1.2 文件的逻辑结构4.1.3 文件目录4.1.4 文件的物理结构4.1. 5 逻辑结构 VS 物理结构4.1.6 文件存储空间管理4.1.7 文件的基本操作4.1.8 文件共享4.1.9 文件保护 4.2 文件系统4.2.1 文件的层次结构(考纲不要求)4.2.2 文件系统的全局结构(布局)4.2.3 虚拟文件系统第5章 输入/输出管理5.1 I/O管理概述5.1.1 I/O设备的概念和分类5.1.2 I/O控制器5.1.3 I/O控制方式🌟5.1.4 I/O软件层次结构5.1.5 输入输出应用程序接口和驱动程序接口 5.2 设备独立性软件5.2.1 I/O核心子系统5.2.2 假脱机技术5.2.3 设备的分配与回收5.2.4 缓冲区管理 5.3 磁盘和固态硬盘5.3.1 磁盘的结构5.3.2 磁盘调度算法🌟5.3.3 减少磁盘延迟时间的方法5.3.4 磁盘的管理5.3.5 固态硬盘SSD 持续更新～欢迎评论区留言指正如果你是Obsidian用户，可以导入自己的笔记库中，效果最佳⚠️如需转载，请标明出处！第1章 计算机系统概述 1.1 操作系统的基本概念 1.1_1 操作系统的定义、功能 OS的定义(概念)负责管理协调硬件、软件等计算机资源的工作为上层用户、应用程序提供简单易用的服务是一种系统软件(最接近硬件的一层软件) 功能和目标资源的管理者 处理机管理存储器管理文件管理设备管理 向上层提供服务 给普通用户的GUI 用户图形界面命令接口 联机命令接口脱机命令接口 给软件/程序员用的程序接口——即系统调用 对硬件机器的拓展 扩充机器1.1_2 操作系统的特征 操作系统的特征 并发和共享是OS的最基本的两个特征f并发共享 互斥共享方式(如对摄像头设备的共享使用)同时共享方式(如对硬盘资源的共享使用) 虚拟 空分复用技术(如虚拟存储技术)时分复用技术(如虚拟处理器技术) 异步 1.2 操作系统的发展与分类 OS的发展与分类 后面三个不是重点手工操作阶段——缺点：人机速度矛盾批处理阶段 单道批处理系统(引入脱机输入输出技术)优点：缓解人机速度矛盾缺点：资源利用率依然很低 多道批处理系统(OS开始出现)优点：多道程序并发执行，资源利用率高缺点：不提供人机交互功能 分时OS 优点：提供人机交互功能缺点：不能优先处理紧急任务 实时OS 硬实时系统——必须在绝对严格的规定时间内完成处理软实时系统——能接受偶尔违反时间规定优点：能优先处理紧急任务 网络OS分布式OS个人计算机OS 1.3 操作系统的运行环境🌟 1.3_1 操作系统的运行机制🌟 简单了解程序的运行原理高级语言编写代码——>机器指令程序运行的过程就是CPU执行指令的过程 两类程序内核程序用户程序 两类指令特权指令非特权指令 两种处理器状态内核态/核心态/管态——可执行除访管指令外的所有指令用户态/目态——只能执行非特权指令 内核内核(Kernel)是OS最重要最核心的部分由很多内核程序组成OS内核 🌟如何变态？内核态——>用户态：一条修改PSW的特权指令用户态——>内核态：由中断引起，硬件自动完成(硬件中断程序) 1.3_2 中断和异常 中断的作用让OS内核强行夺回CPU的控制权使CPU从用户态变为内核态 中断的分类内中断(又称异常、例外) 陷阱、陷入(trap)故障(fault)终止(abort) 外中断(又称“中断”，狭义上的) 时钟中断I/O中断请求 中断机制的基本实现原理检查中断信号 内中断：CPU在执行指令时会检查是否有异常发生外中断：每个指令周期末尾，CPU都会检查是否有外中断信号需要处理 找到相应的中断处理程序 通过“中断向量表”实现1.3_3 系统调用 系统调用定义：操作系统对应用程序/程序员提供的接口系统调用与库函数的区别 有的库函数对系统调用的进一步封装有的库函数没有使用系统调用 (按功能)分类 凡是与共享资源有关的操作，都需要通过系统调用来实现 设备管理文件管理进程控制进程通信内存管理 系统调用的过程 传参陷入指令/Trap/访管由OS内核程序处理系统调用请求返回应用程序1.4 操作系统结构 操作系统体系结构大内核(宏内核/单内核)——Linux、UNIX 将OS的主要功能模块都作为系统内核，运行在核心态，通常也采用了“模块化”的思想 优点：性能高，内核内部各种功能都可以直接相互调用缺点：内核庞大功能复杂，难以维护大内核中某个功能模块出错，就可能导致整个系统崩溃 微内核——Windows NT 只把中断、原语、进程通信等最核心的功能放入内核，进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态 优点：内核小功能少、易于维护，内核可靠性高内核外的某个功能模块出错不会导致整个系统崩溃 缺点：性能低，需要频繁地在核心态/用户态之间切换用户态下的各功能模块不可直接相互调用，只能通过内核的“消息传递”间接通信 分层结构 内核分多层，每层可单向调用(相邻)更低一层提供的接口 优点：便于调试和验证，自底向上逐层调试验证易扩充和易维护，各层之间调用接口清晰固定 缺点：仅可调用相邻低层，难以合理定义各层的边界效率低，不可跨层调用，系统调用执行时间长 模块化 将内核划分为多个模块，各模块之间相互协作 优点模块间逻辑清晰易于维护，确定模块间接口后即可多模块同时开发支持动态加载新的内核模块(如：安装设备驱动程序、安装新的文件系统模块到内核)，增强OS适应性任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高 缺点：模块间的接口定义未必合理、实用模块间相互依赖，更难调试和验证 外核(exokernel) 内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全 优点：外核可直接给用户进程分配“不虚拟、不抽象”的硬件资源，使用户进程可以更灵活的使用硬件资源减少了虚拟硬件资源的“映射层”，提升效率 缺点：降低了系统的一致性使系统变得更复杂1.5 操作系统引导 操作系统引导(Boot)过程CPU从一个特定主存地址开始，取指令，执行ROM中的引导程序(先进行硬件自检，再开机)将磁盘的第一块——主引导记录PCB 读入内存，执行磁盘引导程序，扫描分区表从活动分区(又称主分区，即安装了OS的分区)读入分区引导记录PBR，执行其中的程序从根目录下找到完整的OS初始化程序(即 启动管理器)并执行，完成“开机”的一系列动作 举例：CPU加电激活后，会从最顶端的主存地址FFFF0H获得一条JMP指令(该地址仅有16字节，放不下一段程序)，以跳到更低地址去执行BIOS程序(BIOS程序在内存最开始的空间构建中断向量表和相应服务程序，以实现后续POST过程中要用到中断调用等功能)==然后进行通电自检POST(Power-on Self Test)以检测硬件是否有故障完成POST后，BIOS需要在硬盘、光驱或软驱等存储设备搜寻OS内核的位置以启动OS(在硬盘逻辑格式化之前，需要先对硬盘进行分区，即创建硬盘分区表。分区完成后，对物理分区进行逻辑格式化，即创建文件系统，为每个分区初始化一个特定的文件系统，并创建文件系统的根目录；另外，如果某个分区采用Unix文件系统，还要在该分区中建立文件系统的索引结点表) 第2章 进程与线程 2.1 进程与线程 2.1.1 进程的概念、组成、特征 概念 程序：静态的，存在在磁盘里的可执行文件，也就是一系列的指令集合 进程(Process)：是动态的，使程序的一次执行过程，同一个成许多次执行会对应多个进程，如：多开qq组成 一个程序开始运行前，需要创建对应的进程，也就需要创建相应的PCB 进程是进程实体的运行过程，使系统进行资源分配和调度的一个独立单位 进程实体(进程映像)的组成PCB PCB,Process Control Block，一种数据结构，是进程存在的唯一标志 当进程被创建时，OS会为其创建PCB；当进程结束时，会回收其PCB OS(进程的管理者)所需的数据都在PCB中 进程描述信息进程标识符PID用户标识符UID 进程控制和管理信息CPU、磁盘、网络流量使用情况统计进程当前状态：就绪态/阻塞态/运行态 资源分配清单正在使用哪些文件正在使用哪些内存区域正在使用哪些I/O设备 处理机相关信息如PSW、PC等等各种寄存器的值(用于实现进程切换) 程序段 包含程序的代码(指令序列) 数据段 包含运行过程中产生的各种数据(如：程序中定义的变量) 特征动态性 动态性是进程最基本的特征进程是程序的一次执行过程，是动态地产生、变化和消亡的 并发性 内存中有多个进程实体，各进程可并发执行 独立性 进程时能独立运行、独立获得资源、独立接受调度的基本单位 异步性 各进程按各自独立的、不可预知的速度向前推进，OS要提供“进程同步机制”来解决异步问题 结构性 每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成2.1.2 进程的状态与转换、进程的组织状态
运行态：CPU✅其他所需资源❌就绪态：CPU❌其他所需资源✅(CPU很忙)阻塞态：CPU❌其他所需资源❌创建态：OS为新进程分配资源、创建PCB终止态：OS回收进程的资源、撤销PCB进程状态间的转换 
线程的状态与转换 ![![[截屏2024-07-12 17.13.35.png]]](https://i-blog.csdnimg.cn/direct/302c82a42dca40b2bcb8e82355dafb82.png)
线程的组织与控制 ![![[截屏2024-07-12 17.13.03.png]]](https://i-blog.csdnimg.cn/direct/631dc09adfa14c93a0f3780a854bd902.png)
![![[截屏2024-07-15 08.33.30.png]]](https://i-blog.csdnimg.cn/direct/48c88e64fba448e4a83a0208e93c9eb1.png)
2.2.2 进程调度的时机、切换与过程、方式 进程调度的时机需要进程调度的时机 主动放弃进程正常终止运行过程中发生异常而终止主动阻塞(如 等待I/O) 被动放弃分给进程的时间片用完有更紧急的事情需要处理(如 I/O中断)有更高优先级的进程进入就绪队列 不能进程调度的时机 在处理中断的过程中进程在OS内核程序临界区中原子操作过程中(原语) 进程调度的切换与过程狭义的“调度”和“切换”的区别切换过程 对原来运行进程各种数据的保存对新的进程各种数据的恢复 重要结论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高 方式非剥夺调度方式(非抢占式) 只能由当前运行的进程主动放弃CPU剥夺调度方式(抢占式) 可由OS剥夺当前进程的CPU使用权 2.2.3 调度器和闲逛进程调度器/调度程序(scheduler) OS内核的一个重要的程序模块 ![![[截屏2024-07-15 08.53.35.png]]](https://i-blog.csdnimg.cn/direct/aff8589357734e80ad2d8290ae51fab0.png)
闲逛进程(idle) 调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程 特性：
优先级最低可能是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)能耗低 2.2.4 调度算法的评价指标 CPU利用率 利用率 =忙碌的时间 总时间利用率=\frac{忙碌的时间}{总时间}利用率=总时间忙碌的时间系统吞吐量 系统吞吐量 =总完成作业数 所花时间系统吞吐量=\frac{总完成作业数}{所花时间}系统吞吐量=所花时间总完成作业数周转时间 周转时间 = 完成时间 − 到达时间 ( 提交时间 ) 周转时间=完成时间-到达时间(提交时间)周转时间=完成时间−到达时间(提交时间)平均周转时间 平均周转时间 =周转时间 运行时间平均周转时间=\frac{周转时间}{运行时间}平均周转时间=运行时间周转时间等待时间 等待时间 = 周转时间 − 运行时间 等待时间=周转时间-运行时间等待时间=周转时间−运行时间响应时间 从用户提交请求到首次产生响应所用的时间 2.2.5 调度算法 典型调度算法分类早期批处理系统(非交互式系统) ![![[截屏2024-07-15 09.05.31.png]]](https://i-blog.csdnimg.cn/direct/afc8d2a13c664bf48703431ef3744e43.png)
交互式系统 ![![[截屏2024-07-15 09.06.20.png]]](https://i-blog.csdnimg.cn/direct/d8158fc1f6384575929104855e0701fe.png)
![![[截屏2024-07-15 09.07.38.png]]](https://i-blog.csdnimg.cn/direct/7deb8d9eb9484ab585d566ab3d0ffb49.png)
2.3 同步与互斥 2.3.1 进程同步、进程互斥 进程同步并发性带来了异步性，有时需要通过进程同步解决这种异步问题有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序 进程互斥 ==临界资源：一次仅允许一个进程使用的资源对临界资源的访问，需要互斥的进行，即同一时间段内只能允许一个进程访问该资源四个部分(临界资源的访问分为) 进入区 检查是否进入临界区，若可进入，需要“上锁”临界区(临界段) 进程中访问临界资源的那段代码退出区 负责“解锁”剩余区 其余代码部分 (进程互斥)需要遵循的原则 空闲让进 临界区空闲时，应允许一个进程访问忙则等待 临界区正在被访问时，其他试图访问的进程需要等待有限等待 要在有限时间内进入临界区，保证不会饥饿让权等待 进不了临界区的进程，要释放处理机，防止忙等2.3.2 进程互斥的软件实现方法🌟 进程互斥的软件实现方法 turn表“谦让”和flag表“意愿”的思想单标志法 公用整型变量turn表“谦让” 在进入区只做“检查”，不“上锁”在退出区把临界区的使用权转交给另一个进程(相当于在退出区既给另一进程“解锁”，又给自己“上锁”)主要问题：不遵循“空闲让进”原则 双标志先检查 flag数组(想要进入临界区)表“意愿” “检查”和“上锁”并不能一气呵成 在进入区先“检查”后“上锁”，退出区“解锁”主要问题：不遵循“忙则等待”原则 双标志后检查 在进入区先“加锁”后“检查”，退出区“解锁”主要问题：不遵循“空闲让进、有限等待”原则，可能导致“饥饿” Peterson算法 单标志法和双标志后检查法的结合 在进入区“主动争取—主动谦让—检查对方是否想进、己方是否谦让”主要问题：不遵循“让权等待”原则，会发生CPU“忙等”2.3.3 进程互斥的硬件实现方法🌟 进程互斥的硬件实现方法中断屏蔽方法 关中断指令只对关中断的特定处理机有用 不适合多处理机系统 使用“开/关中断”指令实现优点：简单高效缺点：只适用于单处理机；只适用于OS内核进程 TestAndSet/TestAndSetLock(TS指令/TSL指令) old记录是否已被上锁；再将lock设为true；检查临界区是否已被上锁(若已上锁，则循环重复前几步)优点：实现简单；适用于多处理机环境缺点：不满足“让权等待”——可能会出现忙等现象 Swap指令(XCHG指令) 逻辑上同TSL 2.3.4 互斥锁 ![![[截屏2024-07-15 09.42.19.png]]](https://i-blog.csdnimg.cn/direct/1374710b1eac434d9ce8cad63c41776a.png)
![![[截屏2024-07-15 09.42.42.png]]](https://i-blog.csdnimg.cn/direct/8f6c3c049920430cb1525975960c2f4a.png)
先V后P ![![[截屏2024-07-15 18.36.02.png]]](https://i-blog.csdnimg.cn/direct/6414b198bfb4437488d690ca3145bdc6.png)
![![[截屏2024-07-15 18.37.07.png]]](https://i-blog.csdnimg.cn/direct/5598e5d1453f4f5b8dc713d084a6d864.png)
![![[截屏2024-07-15 18.39.49.png]]](https://i-blog.csdnimg.cn/direct/21390cdabb9d4545aab41454f99759aa.png)
遇到进程同步问题应参考生产者-消费者问题；而进程互斥问题应参考读者写者问题 ![![[截屏2024-07-15 18.42.04.png]]](https://i-blog.csdnimg.cn/direct/6088f54054654808bfdee501d4b22b85.png)
遇到一个进程需要同时持有多个临界资源的情况这种问题，应参考哲学家问题 ![![[截屏2024-07-15 18.43.33.png]]](https://i-blog.csdnimg.cn/direct/fca4c0b459cc4645a4c0165fffbb7931.png)
解决信号量机制编程麻烦、易出错的问题 类比“类(class)”的概念
组成共享数据结构对数据结构初始化的语句一组用来访问数据结构的过程(函数) 基本特征各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据结构每次仅允许一个进程在管程内执行某个内部过程 补充各进程必须互斥访问管程的特性是由编译器实现的可在管程中设置条件变量及等待/唤醒操作wait()/signal()以解决同步问题 2.4 死锁 2.4.1 死锁的概念定义：各进程相互等待对方手里的资源，导致各进程都阻塞，无法向前推进 对不可剥夺资源的不合理分配，有可能导致死锁
死锁、饥饿、死循环的区别死锁：至少是两个进程一起死锁，死锁进程处于阻塞态饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪死循环：可能只有一个进程发生死循环，死循环的进程可上处理机(可执行)死锁和饥饿由OS解决，而死循环由程序员解决 死锁产生的必要条件互斥条件 对必须互斥使用的资源的争抢才会导致死锁不剥夺条件 进程保持的资源只能主动释放，不可强行剥夺请求和保持条件 保持着某些资源不放的同时，请求别的资源循环等待条件 存在一种资源的循环等待链循环等待不一定死锁，死锁一定有循环等待链 死锁的处理策略预防死锁(静态策略) 不允许死锁发生 破坏互斥条件破坏不剥夺条件破坏请求和保持条件破坏循环等待条件 避免死锁(动态策略) 不允许死锁发生 死锁系统进入不安全状态(银行家算法)死锁的检测和解除 允许死锁发生，系统负责检测出死锁并解除 2.4.2 死锁的处理策略-预防死锁 破坏互斥条件将临界资源改造为可共享使用的资源(如SPOOLing技术)缺点：可行性不高，很多时候无法破坏互斥条件 破坏不剥夺条件方案一，申请的资源得不到满足时，立即释放拥有的所有资源方案二，申请的资源被其他进程占用时，由OS协助剥夺(考虑优先级)缺点：实现复杂；剥夺资源可能导致部分工作实效；反复申请和释放导致系统开销大；可能导致饥饿 破坏请求和保持条件运行前分配好所需的资源，之后一直保持缺点：资源利用率低；可能导致饥饿 破坏循环等待条件给资源编号，必须按编号从小到大的顺序申请资源缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦 2.4.3 死锁的处理策略-避免死锁处于不安全状态未必发生了死锁，但死锁一定发生在不安全状态 银行家算法的核心思想： 在资源分配之前预先预判这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求 ![![[截屏2024-07-15 19.12.09.png]]](https://i-blog.csdnimg.cn/direct/323fb50057d64c92b1d36f045d5927ad.png)
![![[截屏2024-07-15 19.07.58.png]]](https://i-blog.csdnimg.cn/direct/8127944d4e0f45e4a22a77381fce8344.png)
检测
数据结构：资源分配图 本质——图 ![![[截屏2024-07-15 19.16.39.png]]](https://i-blog.csdnimg.cn/direct/42e516aa7f0d4804ac0c306401542b03.png)
死锁检测算法 后期时间充裕可以自己动手实现
依次消除与不阻塞进程相连的边，直到无边可消注：所谓不阻塞进程是指其申请的资源数还足够的进程死锁定理：若资源分配图是不可完全简化的，说明发生了死锁解除 ![![[截屏2024-07-15 19.20.10.png]]](https://i-blog.csdnimg.cn/direct/907ef85a6f1049a19a0ca3b77c680e63.png)