1.操作系统是对计算机资源进行管理的软件
2.操作系统的基本功能：控制和管理系统内的各种资源
3.操作系统最基本的两个特征：并发和共享
4.并发：在同一时间间隔发生 并行：在同一时刻发生
5.用户可以通过命令接口和系统调用两种方式来使用计算机
6.系统调用是由操作系统提供给用户的，只能通过用户程序间接使用
7.系统调用的目的是：请求系统服务
8.操作系统提供了命令接口和图形接口。 命令接口包括：联机用户接口，脱机用户接口
9.单处理机系统中，同一时刻只有一个进程占用CPU
1.提供单机资源利用率的关键技术：多道程序设计技术
2.批处理系统的主要缺点：无交互能力
3.多道程序设计的基本特征：制约性，间断性，共享性。
4.操作系统的基本类型：批处理操作系统，分时操作系统，实时操作系统
5.分时系统中每个任务依次轮流使用时间片，响应时间好，是一种多用户操作系统。
6.分时系统追求的目标是：比较快速的响应用户。
7.分时系统中，时间片一定，用户越多，响应时间越长。
8.实时操作系统必须在规定时间内处理完来自外部的事件。
9.批处理系统分为单道批处理系统和多道批处理系统
10.中断技术始得多道批处理系统的IO设备可以与CPU并行工作。
11.多道程序系统的优点：CPU利用率高，系统吞吐量大，IO设备利用率高
2.管理计算机系统资源是操作系统关心的主要问题
3.批处理的主要缺点是缺少交互性
4.输入/输出指令必须在核心态下执行
5.采用多道程序设计技术的最主要原因是提高系统利用率和吞吐率
6.操作系统中，通道技术是一种硬件技术
7.用户程序使用系统调用命令，该命令经过编译后形成若干参数和陷入指令
8.程序设计无法形成屏蔽中断指令
9.用户程序创建一个新进程，需要使用操作系统提供的系统调用接口
10.当操作系统完成用户请求的调用功能后，应使CPU从内核态转到用户态
11.中断处理是操作系统必须要提供的功能，各种错误都需要中断处理
12.在用户态下使用指令会引起访管中断（陷入中断）
13.指令：只能在核心态下执行的指令
14.计算机通过硬件中断机制完成由用户态到核心态的转换
15.可以在核心态执行的指令：屏蔽中断，设置中断，停机指令
16.系统调用的调用：可能发生在用户态 系统调用的执行：一定发生在核心态
17.外部中断是由CPU外部事件引起：I/O设备请求，时钟信号
18.内部中断：也叫异常，由CPU内部事件引起：访管指令，缺页异常
19.库函数运行在用户态，系统调用运行在内核态
20.使用库函数开销较小，使用系统调用开销较大
21.库函数方便被替换，系统调用不方便被替换
22.库函数可以很方便的调试，系统调用很麻烦
23.命令解释程序是面向用户的，在用户态下执行
24.执行系统调用的过程：传递系统调用函数->执行陷入指令->执行相应服务程序->返回用户态
25.操作系统不同，底层逻辑，实现方法均不同
26.在执行系统调用服务程序过程中，CPU处于内核态
27.常见的指令：有关对I/O设备操作的指令，有关访问程序状态的指令，存取特殊寄存器的指令，其他指令
28.由硬件完成：保存断点和程序状态字，将CPU模式改为内核态
29.由操作系统完成：保存通用寄存器的内容，执行系统调用服务例程
1.分层结构
特性：内核分多层，每层可以单向调用更低一层提供的接口
优点：1.便于调试和验证，自底向上逐层调试验证
2.易扩充和易维护，各层之间接口清晰固定
缺点：1.仅可以调用相邻低层，难以合理定义各层的边界
2.效率低。不可以跨层调用，系统调用执行时间长
2.模块化
特性：将内核划分为多个模块，各个模块之间相互协作 内核 = 主模块 + 可加载内核模块
主模块：只负责核心功能：进程调度，内存管理
可加载模块：可以动态加载新模块到内核，而无需重新变易整个内核
优点：1.支持动态加载新的内核模块
2.任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高
缺点：1.模块间的接口定义未必合理
2.模块间相互依赖，更难调试和验证
3.大内核
特性：所有系统功能都在内核里面
优点：性能高，内核内部各种功能都可以直接相互调用
缺点：1.内核庞大功能复杂，难以维护
2.大内核中某个功能模块出错，可能导致整个系统崩溃
4.微内核
特性：只把中断、原语、进程通信等最核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态
优点：1.内核小功能少，易于维护，内核可靠性高
2.内核外的某个功能模块出错不会导致整个系统崩溃
缺点：1.性能低，需要频繁切换 用户态/核心态 用户态下的各功能模块不可以直接相互调用，只能通过内核的“消息内核”来通信
2.用户态下的各功能模块不可以直接相互调用，只能通过内核的“消息传递”来间接通信
5.外核
特性：内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全。
优点：1.外核可以直接给用户进程分配“不虚拟、不抽象”的硬件资源，使用户进程可以更灵活的使用硬件资源
2.减少了虚拟硬件资源的“映射层”，提升效率
缺点：1.降低了系统的一致性
2.使系统变得更复杂
操作系统的引导过程：
1.激活CPU： 激活的CPU读取ROM中的boot程序，将指令寄存器置为BIOS的第一条指令，即开始执行BIOS指令
2.硬件自检： BIOS程序在内存最开始的空间创建中断向量表
3.加载带有操作系统的硬盘： 通电自检BIOS开始读取Boot Sequence，将控制权交给启动顺序排在第一位的存储设备，将存储设备引导扇区内容加载到内存
4.加载主引导记录（MBR）
5.扫描硬盘分区表，并加载硬盘活动分区
6.加载分区引导记录（PBR）
7.加载启动管理器
8.加载操作系统
1.进程影响 = 进程实体 = PCB（进程控制模块）+ 程序段 + 数据段
2.CPU调度的基本单位：线程
3.PCB是进程存在的唯一标志
5.一个进程可以创建多个线程
6.线程之间的通信可以通过共享存储空间，使用系统调用函数
7.进程之间交换数据可以通过：共享文件，消息传递，访问共享存储区进行通信
8.进程和程序的根本对比：
进程：动态的 程序：静态的
9.并发进程相互竞争，制约，且运行结果具有不可再现性
10.并发进程执行的相对速度是与进程调度策略有关
11.进程创建原语能够实现：
申请PCB并初始化
为进程分配内存空间
将进程插入就绪队列
12.一个进程在其生命周期中可以执行多个程序。
13.一个程序的多次运行可以形成多个不同的进程
14.一个程序的一次执行可以产生多个进程
15.导致创建新进程的操作：用户登录、高级调度发生、操作系统响应用户提出的请求、用户打开了一个浏览器程序
16.操作系统是根据进程控制块来对并发执行的进程进行控制和管理
17.一个进程释放了一台打印机，他可能会改变另一个等待打印机的进程的状态
18.系统进程所请求的一次I/O操作完成后，将使进程状态从阻塞态变为就绪态 I/O前为阻塞态，完成后为就绪态
19.在分时系统中，通常处于就绪态的进程最多，用于抢夺CPU使用权
20.并发进程失去封闭性，是指并发进程共享变量，其执行结果与速度有关
21.进程在处理器上执行时，进程之间可能是无关的，但也有可能是有交互性的。 进程可能有相关性，也可能相互
22.不管系统中是否有进程，进程都是拥有资源的单位
23.在多对一的线程模型中，当一个多线程进程中的某个线程被阻塞后，整个进程都将阻塞
24.用信箱实现的通信机制包括：发送原语和接受原语
25.速度最快的进程通信方式：共享内存 Socket：不同机器之间进程通信
26.进程可以有程序段，数据段和PCB进行描述 线程是一种特殊的进程 进程是程序在一个数据集合上的运动过程，它是系统进行资源分析和调度的一个单元
27.PCB包括：PID、进程状态、程序计数器、栈指针、内存分配情况、文件描述符、优先符、调度信息
28.各个进程在某一时间段内并发运行，CPU和I/O设备间并行工作
29.对进程的管理和控制使用原语
30.同一进程中，线程的切换不会引起进程切换 当从一个进程中的线程切换到另一个进程中线程中时，才会引起进程的切换
31.线程是比进程更小的能运行的基本单位，不可以脱离进程运行
32.引入线程可以提高程序并发执行的速度，可以进一步提高系统效率
33.线程引入会减少程序执行时的时空开销
34.同一进程或不同进程内的线程都可以并发执行
35.线程的优点：提高系统并发性，节约系统资源，便于进程通信
36.多线程技术具有明显的优越性：速度快，通信简便，设备并行性高
37.两个合作进程无法利用高级语言程序设计中的全局变量交换数据
38.一个进程从运行态变为就绪态必会引起进程切换
39.进程处于等待操作系统分配CPU时间时，处于非阻塞态
40.一个进程被唤醒，意味着该进程可以重新竞争CPU
41.采用轮转调度算法，进程中设置内核级线程和用户级线程的效果完全不同
42.跨进程的用户级线程调度需要内核参与，控制简单
43.用户级线程可以在任何操作系统中运行
44.若系统中只有用户级线程，则CPU的调度对象是进程
45.同一进程中的线程切换，系统开销小
46.当内核线程阻塞时，CPU将调度同一进程中的其他内核线程执行
47.内核级线程的程序实体可以在内核态运行
48.对多处理器系统，核心可以同时调度同一进程的多个进程并行运行
49.用户级线程的优点：
线程切换不需要切换到内核态
支持不同的应用程序采用不同的调度算法
在不同操作系统上不经修改就可以直接运行
50.用户级线程创建和调度都是在用户态下完成的
51.用户及线程由线程库进行管理
52.操作系统无法直接调度用户级线程
53.线程库中线程切换不回导致进程切换
54.并发性较好的多线程模型：一对一模型 多对多模型
55.多对一的线程切换不会导致进程切换
56.创建进程的原因：
用户登录
高级调度
系统处理用户程序的请求
用户程序的应用请求
57.进程是资源分配的基本单位 线程是CPU调度的基本单位
高级调度（作业调度）：按一定的原则从外存的作业后备队列挑选一个作业调入内存，并创建进程。
每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB
低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
其中进程调度也是最基本的调度，在一般的操作系统中都必须配置进程调度。 且进程调度的频率很高，几十毫秒一次
中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能被多次调入、调出内存
中级调度发生频率比高级调度高。 暂时被调到外存等待的进程为挂起状态，被挂起的PCB会被组织成挂起队列
暂时调到外存等待的进程状态为挂起状态
挂起态分为：就绪挂起、阻塞挂起
CPU利用率：指CPU“忙碌”的时间占总时间比例
利用率 = 忙碌时间 / 总时间
系统吞吐量：单位之间内完成作业的数量
系统吞吐量 = 总共完成的作业 / 总共花的时间
周转时间：指从作业被提交给系统开始到作业完成位置的这段时间间隔（高级调度的时间、低级调度的时间、进程在CPU执行时间、进程等待I/O操作完成时间）
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业实际运行时间 = （作业完成时间 - 作业提交时间） / 作业实际运行时间
带权周转时间与周转时间都是越小越好
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
等待时间：进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低
对进程来说：等待时间即进程建立后等待被服务的时间之和
对作业来说：等待时间即建立进程后的等待时间 + 作业在外村后备队列中等待的时间
响应时间：用户提交请求到首次产生响应所用时间
进程调度：按照某种算法从就绪队列中选择一个进程为其分配处理机。
需要进行进程调度和切换的情况：
当前运行的进程主动放弃处理机（有的系统，只允许进程主动放弃处理机）
进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞
当前运行的进程被动放弃处理机（有的系统进程可以主动放弃处理机，当有更紧急的任务需处理，也会强行剥夺处理机 ）
分给进程的时间片用完
有更紧急的事需要处理（I/O中断）
有更高优先级的进程进入就绪队列
不能进行进程调度与切换的情况：
在处理中断过程中，中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
进程在操作系统内核程序临界区
原语中，原子操作不可中断，要一气呵成
实现简单，系统开销小但是无法及时处理紧急任务。适用于早期的批处理系统
剥夺调度方式（抢占方式）：当有更紧急的任务需处理，会强行剥夺处理机，将处理机分配给更重要更紧急的进程
②、③由调度程序引起，调度程序决定，调度程序决定：
让谁运行 ---- 调度算法
运行多长时间 ---- 时间片大小
调度时机：
创建新进程
进程退出
运行进程阻塞
I/O中断发生
闲逛进程特性：
优先级最低
能耗低
学习思路：
算法思想
算法规则
这种调度算法是用于 作业调度 还是 进程调度
抢占式 非抢占式
优点 缺点
是否会导致饥饿（某进程/作业长期得不到服务）
算法一：先来先服务（FCFS First Come First Serve）
算法思想：主要从“公平”的角度考虑 （平常排队买菜）
算法规则：按照作业/进程到达的先后顺序进行服务
这种调度算法是用于 作业调度 还是 进程调度：
用于作业调度时，考虑的是哪个作业先到达后备队列
用于进程调度时，考虑的是哪个进程先到达就绪队列
属于非抢占式的算法
优点：公平、算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业不利。
是否会导致饥饿（某进程/作业长期得不到服务）：不会
例题:
算法二：短作业优先（SJF Shortest Job First）
算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
算法规则：最短的作业/进程先得到服务（所谓“最短”，是指要求服务时间最短）
这种调度算法是用于 作业调度 还是 进程调度：
可以用于作业调度
可以用于进程调度，用于进程调度时称为“短进程优先” （SPJ Shortest Process First）算法
SJF和SPF是非抢占式算法，但是也有抢占式版本----最短剩余时间优先算法（SRTN Shortest Remaining Time Next）
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，不一定真实，不一定能够做到真正的短作业优先
是否会导致饥饿（某进程/作业长期得不到服务）：会，如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿现象”。如果一直得不到服务，则称为“饿死”。
例题：
算法三：高响应比优先（HRRN Highest Response Ratio Next）
算法思想：要综合考虑作业/进程的等待时间和要求服务时间
算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
响应比 = （等待时间 + 要求服务时间） / 要求服务时间
这种调度算法是用于 作业调度 还是 进程调度：既可以用于作业调度，也可以用于进程调度
非抢占式算法。因此只有当前运行的作业/进程主动放弃处理机时候，才需要调度，才需要计算响应比
优缺点：综合考虑了等待时间和运行时间（要求服务时间）
等待时间相同时，要求服务时间短的优先（SJF的优点）
要求服务时间相同时，等待时间长的优先（FCFS的优点）
对于长作业来说，随着等待时间越来越久，响应比也越来越大，从而避免了长作业饥饿的问题
是否会导致饥饿（某进程/作业长期得不到服务）：不会
例题：
算法四：时间片轮转（RR，Round-Robin）
算法思想：公平的、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到相应
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机。将进程重新放在就绪队列队尾重新排队
这种调度算法是用于 作业调度 还是 进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
抢占式算法：若进程没能在时间片内运行完，将强行剥夺处理机使用权。 由时钟装置发出时钟中断来通知CPU时间片已到
优点：公平，响应快，适用于分时操作系统
缺点：由于高频率的进程切换，因此有一定开销，不区分任务的紧急情况
是否会导致饥饿（某进程/作业长期得不到服务）：不会
时间片过大：时间片轮转算法会退化未先来先服务调度算法，并且会增大进程响应时间。
时间片过小：导致进程切换过于频繁，系统会花大量时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。
例题：
算法五：优先级调度算法
算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多应用场景需要根据任务的紧急程度来决定处理顺序
算法规则：调度时选择优先级最高的作业/进程
这种调度算法是用于 作业调度 还是 进程调度：既可以用于作业调度，也可以用于进程调度。 还会用于在之后的I/O调度中
非抢占式：只需要在进程主动放弃处理机时进行调度即可
抢占式：在非抢占式基础上，还需要在就绪队列变化时，检查是否会发生抢占
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，可以灵活调整对各种作业/进程的偏好程度
缺点：若源源不断地有高优先级的进程到来，可能导致饥饿
是否会导致饥饿（某进程/作业长期得不到服务）：会
根据优先级是否可以动态改变，分为静态优先级和动态优先级：
静态优先级：创建进程时确定，之后一直不变
动态优先级：创建进程时有一个初始值，之后会根据情况动态调整优先级
通常：系统进程优先级高于用户进程 前台进程优先级高于后台进程 操作系统更偏好I/O型进程
如果从追求公平，提升资源利用率的角度考虑：
若某进程在就绪队列中等待了很久，可以适当提升其优先级
若某进程占用处理机运行了很长时间，可以适当降低其优先级
若发现一个进程频繁地进行I/O操作，可以适当提升其优先级
例子：
算法六：多级反馈队列调度算法
算法思想：对其他调度算法的这种权衡
算法规则：
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第一级队列，按照FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，进程进入下一级队列队尾。若此时已经是在最下级的队列。则重新放回该队列队尾
只有第k级队列为空时，才会为k+1级对头进程分配时间片
这种调度算法是用于 作业调度 还是 进程调度：进程调度
抢占式算法
优点：
对各类型进程相对公平（FCFS优点）
每个新到达的进程都可以很快的得到相应（RR优点）
短进程只用较少的时间就可以完成（SPJ优点）
不必实现估计进程的运行时间（避免用户作假）
可以灵活的调整对各类进程的偏好程度（如CPU密集型进程、I/O密集型进程）
是否会导致饥饿（某进程/作业长期得不到服务）：会
例题：
总结：
进程具有异步性的特征。 异步性指：各并发执行的进程以各自的、不可预知的速度向前推进
操作系统要提供“进程同步机制”来解决异步问题
进程同步即解决异步问题 同步也叫直接制约关系
进程的“并发”需要“共享”的支持。 各个并发执行的进程不可避免的需要共享一些系统资源（如内存，打印机）
两种资源共享方式：
互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源
同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对他们进行访问
临界资源：一个时间段内，只允许一个进程使用的资源 许多物理设备（摄像头，打印机）都属于临界资源 还有许多变量、数据、内存缓冲区都属于临界资源
对于临界资源，需要互斥进行。 互斥也叫间接制约关系
进程互斥：当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放资源后，另一个进程才能去访问临界资源。
对于临界资源的互斥访问，在逻辑上分为如下四个部分：
临界区：进程中访问临界资源的代码段
进入区和退出区：负责实现互斥的代码段
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循：
空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
算法一：单标志法（谦让）
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。即每个进程进入临界区的权限只能被另一个进程赋予
该算法可以实现“同一时刻最多只允许一个进程访问临界区”
单标志法问题：违背空闲让进的原则
算法二：双标志先检查法（表达意愿）
算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿。 如：“flag[0] = true”意味着0号进程P0现在想要进入临界区。 每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区。若没有 把自身对应标志flag[i]设为true，之后开始访问临界区
双标志先检查法问题：违反忙则等待原则
原因：进入区的“检查”和“上锁”两个处理不是一气呵成的。 “检查”后，“上锁”前可能发生进程切换
算法三：双标志后检查法
算法思想：双标志检查法的改版。 前一个算法问题是：先“检查” 后“上锁” 但是两个操作无法一气呵成 导致了两个进程同时进入临界区的问题。 所以双标志后检查法为先“上锁”后“检查“
双标志后检查法问题：违反了空闲让进 和 有限等待的原则 会因各进程都长期无法访问临界资源产生”饥饿“现象
原因：两个进程都争着想进入临界区，但是谁都不让谁，最后谁都无法进入临界区
算法四：Peterson算法
算法思想：结合双标志法、单标志法的思想。若双方都争着想进入临界区，可以让进程尝试”孔融让梨“的方法
Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则。 但是未遵循让权等待
总结：
方法一：中断屏蔽方法
利用”开/关中断指令“ （与原语实现思想相同 在某进程开始访问临界区到结束访问位置都不允许被中断 无法发生进程切换 因此不能发生两个同时访问临界区的情况）
优点：简单、高效
缺点：不适用于多处理机 只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态）
方法二：TestAndSet指令
简称为TS指令，也称TSL指令 （TestAndSetLock指令）
TSL指令是用硬件实现的，执行过程不允许被中断，只能一气呵成
相比软件实现方法，TSL指令把”上锁“和”检查“操作用硬件的方式变成一气呵成的原子操作
优点：实现简单，无需像软件实现方法那样严格检查使用都有逻辑漏洞 适用于多处理机环境
缺点：不满足”让权等待“原则 暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致”忙等”
方法三：Swap指令
也叫Exchange指令 或者为XCHG指令
Swap指令是用硬件实现的 执行的过程不允许被中断，只能一气呵成
优点：实现简单，无需像软件实现方法那样严格检查使用都有逻辑漏洞 适用于多处理机环境
缺点：不满足”让权等待“原则 暂时无法进入临界区的进程会占用CPU并循环执行Swap指令，从而导致”忙等”
总结：
互斥锁：解决临界区最简单的工具 一个进程在进入临界区时应该获得锁 退出时释放锁 缺点：忙等待
acquire（） 和 release（）的执行必须是原子操作 因此互斥锁通常采用硬件机制实现
自旋锁：需要连续循环忙等的互斥锁 如：TSL指令 swap指令 单标志法
锁的特性：
需忙等，进程时间片用完才下处理机，违反“让权等待”
优点：等待期间不用切换进程上下文，多处理机系统中，若上锁时间短，则等待代价很低
常用于多处理机系统，一个核忙等，其他核照常工作，并快速释放临界区
不太适用于单处理机系统，忙等的过程不可能解锁
信号量机制：一种卓有成效的实现进程互斥、同步的方法
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作 从而方便的实现进程互斥、进程同步
信号量：一个变量（可以是整数，也可以是更复杂的记录型变量） 可以用一个信号量表示系统中某种资源的数量
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。 原语由关中断/开中断指令实现
一对原语：wait（S）原语和signal（S）原语 可以把原语理解为自己的函数 函数名分别为wait和signal 信号量S是函数调用时传入的一个参数
wait、signal（value+1）原语简称为P、V操作 wait（S）原语和signal（S）原语分别写为P（S）、V（S）
整型信号量：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
记录型信号量：用记录型数据结构表示的信号量 （由于整型信号量的缺陷是存在“忙等”问题）
在考研中：wait（S）、signal（S）可记为P（S）、V（S） 可以用于实现系统资源的“申请”和“释放”
对信号量S的一次P操作意味着进程请求一个单位的该类资源 value-1操作 当S.value<0 表示资源分配完毕 此时进程调用block原语进行自我阻塞（从运行态 ----> 阻塞态） 主动放弃处理机，并插入该类资源的等待队列S.L
对信号量S的一次V操作意味着进程释放一个单位的该类资源 value+1操作 若加1后还是S.value <= 0 表示依然有进程在等待该类资源 因此应调用wakeup原语唤醒等待队列中的第一个进程 （从阻塞态 ----> 就绪态）
p（S） ----- 申请一个资源S，如果资源不够就阻塞等待
V（S） ----- 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程
①：信号量机制实现进程互斥
用信号量机制实现进程互斥：
分析并发进程的关键活动，划定临界区
设置互斥信号量mutex 初值为1
在进入区P（mutex） ---- 申请资源
在退出区V（mutex） ---- 释放资源
对不同的临界资源需要设置不同的互斥信号量 P、V操作必须成对出现 缺少P（mutex）就不能保证临界资源的互斥访问 缺少V（mutex）会导致资源永不被释放，等待进程永不被唤醒
②：信号量机制实现进程同步
进程同步：要让各并发进程按照要求有序推进 让本来异步并发的进程互相配合，有序推进
用信号量实现进程同步：（前v后p）
分析什么地方需要实现“同步关系” 即必须保证“一前一后”执行的两个操作
设置同步信号量S 初始0
前操作执行V（S）
后操作执行P（S）
③：信号量机制实现前驱关系
要为每一对前驱关系各设置一个同步信号量
在“前操作”之后对相应的同步信号量执行V操作
在“后操作”之前对相应的同步信号量执行p操作
总结：
系统中有一组生产者进程和一组消费者进程 生产者进程每次生产一个产品放入缓冲区 消费者进程每次从缓冲区取除一个产品并使用
生产者、消费者共享一个初始为空、大小为n的缓冲区
只有缓冲区未满时，生产者才能把产品放入缓冲区，否则必须等待 缓冲区未满 ---> 生产者生产
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待 缓冲区没空 ----> 消费者消费
缓冲区时临界资源，各进程必须互斥访问 （互斥关系）
PV操作题目分析步骤：
关系分析。 找出题目中描述的各个进程，分析他们之间的同步、互斥关系
整理思路。 根据进程的操作流程确定P、V操作顺序
设置信号量。 并根据题目条件确定信号量初值 （互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）
先申请一个空闲缓冲区P（empty） 增加一个产品资源V（full） 由于是互斥关系，所以添加p（mutex） v（mutex）
先申请消耗一个产品P（full） 增加一个空闲缓冲区位置 V（empty） 由于互斥关系，所以添加p（mutex） v（mutex）
实现互斥的p操作一定要在实现同步的p操作之后（谨防死锁问题） v操作不会导致进程阻塞，两个v操作顺序可以交换
前v后p
互斥关系：（mutex = 1） 对缓冲区（盘子）的访问要互斥进行
同步关系：（一前一后）
父亲将苹果放入盘子中，女生才能取苹果
母亲将句子放入盘子中，儿子才能取橘子
只有盘子为空时，父亲或母亲才能放入水果（盘子为空可以由儿子或者女儿触发 事件发生后才允许父亲或者母亲放水果）
对于父亲母亲来说：p（plate） 表示请求放入水果 V（apple） 表示放入苹果到缓冲区 并通知孩子有水果放入缓冲区
对于孩子来说： p（apple）表示检查苹果数量是否足够 v（plate）表示通知父母进程 缓冲区已经没有水果
当缓冲区大小为1时，即使不设置专门的互斥变量mutex 也不会出现多个进程同时访问盘子的现象
当缓冲区大小大于1时，必须专门设置一个互斥信号量mutex来保证互斥访问访存区
注：实现互斥的p操作一定要在实现同步的p操作之后，否则可能引起死锁
两类进程：写进程、读进程
互斥关系：写进程-写进程 、 写进程-读进程 读进程与读进程不存在互斥问题
如何防止死锁的发生（三种方法）
可以对哲学家进程加一些条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有哦一个哲学家可以拿到左右两只筷子
要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞，这样避免了占有一支后在等待另一只的情况
仅当一个哲学家左右两支筷子都可用时才允许他拿起筷子
引入管程：信号量机制存在问题（编写程序困难、易出错） 管程中程序源不再需要关注复杂的PV操作
管程是一种特殊的软件模块，有这些部分组成：（相当于类）
局部于管程的共享数据结构说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句
管程有一个名字
管程的基本特征：
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
临界区：进程中用于访问临界资源的那段代码
信号量是一个特殊的整型变量，只有初始化和PV操作才能改变其值。 信号量分为互斥量和资源量 互斥量初值一般为1，表示临界区只允许一个进程进入，从而实现互斥 互斥量等于0时，表示临界区已经有一个进程进入，临界区外尚无进程等待 互斥量小于0时，表示临界区中有一个进程，互斥量的绝对值表示在临界区外等待进入的进程数 资源信号量的初始值可以是任意整数，表示可用的资源数， 当资源量小于0时，表示所有资源已经全部用完。等待进程=资源量的绝对值
临界区指并发进程访问共享变量段的代码程序
同步机制的四个准则：空闲让进、忙则等待、让权等待、有限等待
PV操作是一种低级进程通信原语
P操作就是wait操作，表示等待某种资源直至可用为之。若资源不可用，那么进程进入阻塞态。注意，执行P操作时的进程处于运行态
只有就绪进程能够获得处理器资源，被唤醒的进程并不能直接转换成运行态
互斥信号量初始值设置为1，p操作成功则减少1，禁止其他进程进入，V操作成功则加1，允许等待队列中的进程进入
可重入代码：即纯代码，允许多个进程同时访问的代码
互斥锁可用于多线程或多进程之间，但是只有对他加锁的进程或线程才能解锁。 如果一个进程或者线程试图解锁一个不属于他的互斥锁，会返回错误码（谁加锁，谁解锁）
S.value>0,表示某类可用资源的数量，每次p操作，意味着请求分配一个单位的资源 S.value<=0,表示某类资源已经没有，或者说还有因请求该资源而被阻塞的进程，S.value的绝对值表示等待进程数目
PV操作是一种低级进程通信原语，且是由两个不可被中断的过程组成
并发进程之间可能是无关的，可能是有交往的
在Peterson算法中 flag数组用于标记各个线程想要进入临界区的意愿。当一个线程想要进入临界区时，将flag值置为true 退出时，置为false turn变量用于指示允许进入临界区的线程编号。当一个线程想要进入临界区，它将turn置为对方的编号，表示优先让对方先进入。turn等于自己的编号，表示轮到自己进入。如果turn等于对方编号，表示轮到对方进入。
生产者消费者问题用于解决多个进程之间同步互斥问题
死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象
饥饿：由于长期得不到想要的资源，进程无法向前推进的现想
死循环：某进程执行过程中一直挑不出某个循环的现象。有时是因为程序逻辑bug导致的 有时是程序员故意为之
死锁产生的必要条件：只要其中任意条件不成立，死锁不发生
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
请求和保持条件：进程已经保持了至少一个资源，但是又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放（我有对象，但是我还喜欢你，我又不想放弃我现在的对象，但是你还不答应我）
循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被下一个进程所请求
注：发生死锁时一定循环等待，但是发生循环等待时未必死锁
什么时候发生死锁：
对系统资源的竞争 对不可剥夺资源竞争可能导致死锁 对可剥夺资源不会引起死锁
进程推进顺序非法 请求和释放资源的顺序不当
信号量的使用不当 生产者-消费者问题，是实现互斥的p操作在实现同步的p操作前可能导致死锁
死锁的处理策略：
预防死锁：破坏死锁产生的四个必要条件之一或几个
避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
死锁的检测和解除：允许死锁的发生，不过os会负责检测出死锁的发生，然后采取某种措施解决死锁
方法一：破坏互斥条件
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态 如SPOOLing技术
操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备 比如，用SPOOLing技术将打印机改造成共享设备
缺点：并不是所有的资源都可以改造成可以共享使用的资源。并且为了系统安全，很多地方必须保护这种互斥性。所以很多时候无法破坏
方法二：破坏不剥夺条件
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
方案一：当某个进程请求新的资源得不到满足时，他必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有时，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级，（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
缺点：
实现起来较复杂
释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于已保存和恢复状态的资源，如cpu
反复申请和释放资源会增加系统开销，降低系统吞吐量
若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后在重新申请。如果一直发生这种情况，会导致进程饥饿
方案三：破坏请求和保持条件
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己己有的资源保持不放。
可以采用静态分配方法：进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，可以不让他投入运行。一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求别的任何资源。
优点：实现简单
缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。此外，该策略也可能导致某些进程饥饿
方案四：破坏循环等待条件：
循环等待条件：存在一种进程资源的循环等待链，链中的每个进程已获得的资源同时被下一个进程所请求
可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按照编号递增的顺序请求资源，同类资源一次申请完
缺点：
不方便增加新的设备，因为可能需要重新分配所有的编号
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
必须按照规定次序申请资源，用户编程麻烦
总结：
安全序列：指如果系统按照这种序列分配资源，则每个进程都能够顺利完成 只要能找出一个安全序列，系统就是安全状态 安全序列可能有多个。
不安全状态：分配了资源之后，系统找不出任何一个安全序列，系统进入了不安全状态 意味着之后可能所有进程都无法顺利的执行下去
重回安全状态：在不安全状态下，有进程提前归还了一些资源。 但是在分配资源之前要考虑最坏的情况
如果系统处于安全状态，就一定不会发生死锁
如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但是发生死锁时一定是在不安全的状态下）
银行家算法的核心思想：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，一次决定是否答应资源分配请求
银行家算法步骤：
检查此次申请是否超过了之前声明的最大需求数
检查此时系统剩余的可用资源是否还能满足此次请求
试探着分配，更改各数据结构
用安全性算法检查此次分配是否会导致系统进入不安全状态
安全性算法步骤：
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列
把该进程持有的资源全部回收
不断重复上述过程，看最终是否能让所有进程都加入安全序列
系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。
如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。这种情况下，系统提供两个算法：
死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来
死锁的检测：为了能对系统是否已经发生了死锁进行检测，必须：
用某种数据结构来保存资源的请求和分配信息
提供一种算法，利用上述信息来检测系统是否已进入死锁状态
若系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺序地执行下去。
若这个进程执行结束了把资源归还系统，就可能使某系正在等待资源的进程被激活，并顺序执行下去。
相应地，这些被激活地进程执行完了之后又会归还一些资源，这样可能又会激活另一些阻塞的进程
按上述过程分析：
若最终能消除所有边，就称这个图是可以完全简化，此时一定没有发生死锁（相当于找到一个安全序列）
若最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程。
死锁的解除：一旦检测出死锁的产生，就应该立即解除死锁
补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程
解除死锁的主要方法：
资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
撤销进程法：（或叫终止进程法）强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束，一旦被终止功亏一篑，以后还要重新来
进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置为原点。
内存：可以存放数据，程序执行之前，需要先放到内存中才能被CPU处理 ---- 缓和CPU与硬盘之间的速度矛盾
思考：在多道程序环境下，系统中会有多个程序并发执行，即会有多个程序的数据需要同时放到内存中。如何区分各个程序的数据是放在什么地方？
内存中也有一个一个的小房间，每个小房间就是一个”存储单元“
如果计算机”按字节编址“，则每个存储单元大小为1字节，即1B，即8个二进制位 一字节=八比特
如果字节为16位的计算机”按字编址“，则每个存储单元大小为1个字，每个字的大小为16个二进制位
手机有4GB，指内存中可以存放4*2^30个字节。按字节编址 会有2^32个”小房间“
2^10 = 1K 2^20 = 1M 2^30 = 1G
装入的三种方式：
编译：将高级语言翻译成机器语言
链接：由连接程序将编译后形成的一组目标模块，以及所需库函数连接到一起，形成一个完整的装入模块
装入：由装入程序将装入模块装入内存运行
链接的三种方式：
静态链接：在程序运行之前，先将各目标模块以及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不在拆开
装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享
总结：
操作系统作为系统资源的管理者，当然也需要对内存进行管理，要管些什么？
操作系统负责内存空间的分配与回收
操作系统需要提供某种技术从逻辑上对内存空间进行扩充
操作系统需要提供内存保护功能。保护各进程在各自存储空间内运行，互不干扰
三种装入方式：
内存保护的方法：
总结：
覆盖技术：用于解决”程序大小超过物理内存总和“的问题
覆盖技术的思想：将程序分为多个段（多个模块） 常用的段常驻内存，不常用的段在需要时调入内存。
内存中分为固定区和若干个覆盖区
需要常驻内存的段放在”固定区“中，调入后就不在调出（除非运行结束）
不常用的段放在”覆盖区“，需要用到时调入内存，用不到时调出内存
覆盖技术：必须由程序员生命覆盖结构，操作系统完成自动覆盖。 缺点：对用户不透明，增加了用户编程负担
交换技术：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已经具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。 文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式 对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度。因此通常对换区采用连续分配方式 对换区的I/O速度比文件区的更快
交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。
可优先换出阻塞进程，可换出优先级低的进程
（PCB会常驻内存，不会被换出外存）
总结：
内存空间的分配与回收：
连续分配管理方式
单一连续分配
固定分区分配
动态分区分配
非连续分配管理方式
连续分配：指为用户进程分配的必须是一个连续的内存空间
1）单一连续分配：
在单一连续分配方式中，内存被分为系统区和用户区
用户区用于存放用户进程相关数据
优点：实现简单，无外部碎片。可以采用覆盖技术扩充内存，不一定需要采取内存保护
缺点：只能用于单用户、单任务的操作系统中 有内部碎片，存储器利用率极低 内部碎片：分配给某进程的内存趋于中，有些部分没用上
2）固定分区分配
固定分区分配：
分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分
操作系统需要建立一个数据结构 --- 分区说明表 来实现各个分区的分配与回收。 每个表对应一个分区，通常按照分区大小排列。
说明表优点：实现简单，无外部碎片
缺点：
当用户程序太大时，可能所有分区都不能满足需求，此时不得不采用覆盖技术解决，但是又回降低性能
会产生内部碎片，内存利用率低
3）动态分区分配（可变分区分配）
这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态建立分区，并使分区的大小正好适合进程需要。
动态分区分配没有内部碎片，但有外部碎片。
回收内存分区时，可能遇到的情况：
回收区的后面有一个相邻的空闲分区 两个相邻的空闲分区合并为一个
回收区的前面有一个相邻的空闲分区 两个相邻的空闲分区合并为一个
回收区的前后各有一个相邻的空闲分区 三个相邻的空闲分区合并为一个
回收区的前后都没有相邻的空闲分区 新增一个表项
动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择那个分区分配
首次适应算法
最佳适应算法
最坏适应算法
邻近适应算法
1）首次适应算法：
2）最佳适应算法：
算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证“大进程”到来时能有连续的大片空间，可以尽可能多的留下大片的空闲区，优先使用更小的空闲区。
实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
优点：会有更多的大分区被保留下，更能满足大进程的需求
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片
3）最坏适应算法：
算法思想：为了解决最佳适应算法的问题 ---- 留下了太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，方便使用。
实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足的第一个空闲分区。
优点：可以减少难以利用的小碎片
缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程“到达，就没有内存分区可用了。
4）临界适应算法：
5）基于索引搜索的分配算法：
快速适应算法：空闲分区的分类根据进程常用的空间大小进行划分
首先根据进程的长度，在索引表中找到能够容纳他的最小空闲分区链表
从链表中找到第一块进行分配
优点：查找效率高、不产生内部碎片
缺点：回收分区时，需要有效合并分区，算法较复杂，系统开销大
伙伴系统：规定所有分区大小均为2的k次幂 当需要为进程分配大小为n的分区时，在大小为2^i的空闲分区链中查找
哈希算法：根据空闲分区链表的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针。分配时，根据所需分区大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链表
连续分配：为用户进程分配的必须是一个连续的内存空间
非连续分配：为用户进程分配的可以使一些分散的内存空间
页框（也可以叫页帧，内存块，物理块，物理页面）：将内存空间分为一个个大小相等的分区，每个分区就是一个页框
页框号（也可以叫页帧号，内存块号，物理块号，物理页号）：每个页框有一个编号，页框号从0开始
注：页，页面是表示进程的 页框是表示内存的
操作系统以页框为单位为各个进程分配内存空间. 进程的每个页面分别放入一个页框中。 即进程的页面与内存的页框一一对应
各个页面不必连续存放，可以放到不相邻的各个页框中
注：进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片。因此页框不能太大，否则可能产生过大的内部碎片造成浪费
页表：为了能够知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表
页表通常存放在PCB中
1）一个进程对应一张页表
2）进程的每个页面对应一个页表项
3）每个页表项由“页号”和“块号”组成
4）页表记录进程页面和实际存放的内存块之间的映射关系
5）每个页表项的长度是相同的
问题一：每个页表项占多少字节？
例：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？
内存块大小 = 页面大小 = 4KB = 2^12B
4GB内存总共会呗分为2^32 / 2^12 = 2^20个内存块
内存块号范围为0 ~ 2^20 - 1
内存块号至少要用20bit表示
由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要3*（n+1）B
重要重要重要重要考点！！！！：计算机中内存块的数量 -----> 页表项中块号至少占多少字节
页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）
特点：虽然进程的各个页面是离散存放，但是页面内部是连续存放
页号 = 110/50 = 2
页内偏移量 = 110 % 50 = 10
问题三：为什么页面大小要取2的整数幂
好处:
进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会放在页表寄存器中。
计算页号P和业内偏移量W（P = A / L W = A % L）
比较页号P和页表长度M 若P>=M 则产生越界中断，否则继续执行（注：页号是从0开始的，而页表长度至少是1，因此P=M时也会越界）
计算页号、页内偏移量 页号：P = A / L = 2500 / 1024 = 2 W = A % L = 452
未越界 存放的内存块号b = 8
因为局部性原理，一般来说快变动而命中率可以达到90%以上。
（1+100）*90% + （1+100+100） * 10% = 111us
有的系统支持快表和慢表同时查找，这样平均耗时应为（1+100）*90% + （100 + 100） * 10% = 110.9us
时间局部性：如果执行了程序中的某条指令，那么不久之后这条指令可能会再次执行，如果某个数据被访问，不久之后该数据可能再次被访问（因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（因为很多数据在内存总都是连续存放的）
单级页表的问题：
页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
没有必要让整个页表常驻内存，因此进程在一段时间内可能只需要访问某几个特定的页面
根据二级页号查二级页表，找到最终想访问的内存块号
问题二：没有必要让整个页表常驻内存，因此进程在一段时间内可能只需要访问某几个特定的页面
解决方法：可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存 若想要访问的页面不在内存中，则产生缺页中断（内中断/异常），然后将目标页面从外存调入内存
注：若分为两级页表后，页表依然很长，则可以采用更多级的页表，一般来说各级页表的大小不能超过一个页面
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻
段表：程序分多个段，各段离散地装入内存，为了保证程序能够正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。因此，需要为每个进程建立一张段映射表，简称“段表”
每个段对应一个段表项，其中记录了该段在内存中的起始位置（也叫”基址“）和段的长度
各个段表项的长度是相同的 段号可以隐含，不占存储空间
判断段号是否越界。若S>=M，则产生越界中断，否则继续执行（注：段表长度至少是1，而段号从0开始）
访问目标内存单元
分页、分段管理的对比：分段比分页更容易实现信息的共享和保护
分页管理：
优点：内存空间利用率高，不会产生外部碎片，只会有少量的业内碎片
缺点：不方便按照逻辑模块实现信息的共享和保护
分段管理：
优点：很方便按照逻辑模块实现信息的共享和保护
缺点：如果段长过大，为其分配很大的连续空间回很不方便。另外，段式管理会产生外部碎片
段页式管理 = 分段 + 分页
段号的位数决定了每个进程最多可以分为几个段
页号位数决定了每个段最大有多少页
业内偏移量决定了页面大小、内存块大小是多少
页表：每个页对应一个页表项。各页表项长度相同，由页号（隐含）、页面存放的内存块号组成
2.内存管理的主要功能：
内存空间的分配和回收（os负责内存空间的分配和管理 并回收已结束进程所占用的内存空间）
内存空间的扩充（利用虚拟技术从逻辑上扩充内存）
内存共享（允许多个进程访问内存的同一部分）
存储保护（保证各个进程在各自的存储空间内运行，互不打扰）
3.提高内存的物理存储速度由硬件机构决定
6.固定分区分配：分区大小是在系统启动时就确定。不会随着作业的长度而变化。 分区大小可以不同，也可以相同，但是一旦确定，就不会改变。
7.将上邻空闲区、下邻空闲区、回收区合并为一个空闲区，因此空闲区少了一个。而只有上邻空闲区或者下邻空闲区，空闲区数不会减少
8.最佳适配算法：空闲区大小递增 在每次为作业分配内存空间时，找到满足空间大小需要的最小分区给作业。
9.
10.动态重定位允许程序在内存中移动，系统中只有一个重定位寄存器。每次切换进程时，需要保存和恢复该寄存器的值。不会为每个进程分配一个重定位寄存器。
12.对于重定位存储管理方式，应该在整个系统中设置一个重定位寄存器
13.分页式存储管理有内部碎片，分段式存储管理有外部碎片
14.不管进程有多少个段，系统都为每个进程建立一张段表，每个段表项对应进程中的一段
17.在段式存储管理中，程序分段是指在用户编程时，将程序按照逻辑划分为几个逻辑段
18.分段存储管理方法有利于程序的动态链接
20.可重入程序是通过减少对换数量方法来改善系统性能
21.实现分页、分段和段页式存储管理需要特定的数据结构支持，如页表、段表。代价较高。分区存储管理的代价最小
22.动态分区是在作业装入时动态建立的
23.段式存储管理方式满足：方便编程、分段共享、分段保护、动态链接、动态增长
25.单用户连续分配管理方式只适用于单用户、单任务的操作系统，不适用于多道程序设计
26.段式分配中，CPU每次从内存中去一次数据需要2次访存 段页式分配中，CPU每次从内存中去一次数据需要3次访存
29.分页存储管理中，要求每个进程拥有一张页表，且进程的页表驻留在内存中
30.分段存储管理方式中，以段为单位，每段是一个连续存储区
31.段是逻辑结构上相对的程序块，因此段是可变长的
32.按程序中实际的段来分配主存，所以分配后的存储块是可变长的
33.每个段表项必须记录对应段在主存的起始位置和端的长度
34.分段方式对低级程序员和编译器来说是可见的
内存空间的扩充：覆盖技术，交换技术，虚拟存储技术（在传统存储管理方式的基础上引入了交换技术、覆盖技术，使内存利用率有所提升，并且能从逻辑上扩充内存容量）
传统存储管理（很多暂时用不到的数据也会长期占用内存，导致内存利用率不高）：
连续分配
单一连续分配
固定分区分配
动态分区分配
非连续分配
基本分页存储管理
基本分段存储管理
基本段页式存储管理
存在的问题：
一次性：作业必须一次性全部装入内存才能开始运行 导致：①作业很大时不能全部装入内存，导致大作业无法运行 ②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量可以运行，导致多道程序并发度下降
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源
以上问题可以用虚拟存储技术解决
局部性原理：
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；若某个数据被访问过，不久后数据可能再次被访问
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也可能被访问。（因为很多数据在内存时连续存放，且指令也是顺序的在内存中存放）
快表机构：将近期常访问的页表项副本存放到更高速的联想寄存器中
高数缓冲技术：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中
基于局部性原理，在程序装入时，可以将程序中很快就会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
在程序执行过程中，当访问的信息不在内存中时，由操作系统 负责将所需信息从外存调入内存，然后继续执行程序
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
在操作系统的管理下，再用户看来似乎有一个比实际内存大得多的内存，即虚拟内存（os虚拟性的体现，物理内存大小不变，在逻辑上进行扩充）
虚拟内存的实际容量 = min（内存和外存容量之和，CPU寻址范围）
虚拟内存有以下主要特征：
多次性：无需再作业运行时一次性全部装入内存，而是允许被分成多次调入内存
对换性：再作业运行时无需一直常驻内存，而是允许再作业运行过程中，将作业换入、换出
虚拟性：从逻辑上扩充了内存的容量，始得用户看到的内存容量远大于实际容量
虚拟内存的实现需要建立在离散分配的内存管理方式基础上
虚拟内存的实现：
请求分页存储管理
请i去分段存储管理
请求段页式存储管理
传统的非连续分配存储管理：
基本分页存储管理
基本分段存储管理
基本段页式存储管理
主要区别：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序（操作系统要提供请求调页功能）。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存（操作系统要提供页面置换的功能）
请求分页存储管理与基本分页存储管理的主要区别：
在程序执行过程中，当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序（os提供请求调页功能，将缺失页面从外存调入内存）
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存（os要提供页面置换的功能，将暂时用不到的页面换出外存）
请求分页管理方式：
页表机制
缺页中断机构
页表机制：与基本分页管理相比，请求分页管理中，为了实现“请求调页”，os需要知道每个页面是否已经调入内存；若还没调入们也需要知道该页面在外存中存放的位置
当内存空间不够时，要实现“页面置换”，os需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，需要将外存的旧数据覆盖。
在请求分页系统中，每当要访问的页面不在内存时，便会产生一个缺页中断，然后由os的缺页中断处理程序处理中断
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
若内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
若内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存
缺页中断：因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断
一条指令在执行期间，可能产生多次缺页中断
请求分页存储管理与基本分页存储管理的主要区别：
在程序执行过程中，当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序（os提供请求调页功能，将缺失页面从外存调入内存）
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存（os要提供页面置换的功能，将暂时用不到的页面换出外存）
新增步骤1：请求调页（查到页表项时进行判断）
新增步骤2：页面置换（需要调入页面。但没有空闲内存块时进行）
新增步骤3：需要修改请求页表中新增的表项
请求分页存储管理与基本分页存储管理的主要区别：
在程序执行过程中，当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序（os提供请求调页功能，将缺失页面从外存调入内存）
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存（用页面置换算法决定应该换出哪个页面）
页面置换算法：页面的换入、换出需要磁盘I/O，会有较大开销，因此好的页面置换算法应该追求更少的缺页率
最佳置换算法（optimal replacement OPT）
先进先出置换算法（first in first out FIFO） Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象
最近最久未使用置换算法（least recently used LRU）
时钟置换算法（CLOCK） 最近未用算法
改进型的时钟置换算法
驻留集：指请求分页存储管理中给进程分配的物理块的集合
在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小
若驻留集太小，会导致缺页频繁，系统会花大量时间来处理缺页，实际用于进程推进的时间很少
若驻留集太大，会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程进行期间不再改变。即，驻留集大小不变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可以根据情况做适当的增加或者减少。即，驻留集大小可变
局部置换：发生缺页时，只能自己选进程自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程（意味着我一个进程拥有的物理块数量必然会改变，因此不可能是固定分配）
固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存的页面中选出一页换出，然后再调入需要的页面。 缺点：很难再刚开始就确定应为每个进程分配多少个物理块才算合理
可变分配全局置换：刚开始为每个进程分配一定数量的物理块。os会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程。若没有空闲物理块，则选择一个未锁定的页面患处外村，再将该物理块分配给缺页的进程。
注：只要某进程发生缺页都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度;反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
可变分配全局置换：只要缺页就给分新物理块
可变分配局部置换：要根据发生缺页的频率来动态的增加或减少进程的物理块
何时调入页面：
预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入页面大多是都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但是目前预测成功率只有50%左右。所以这种策略主要用于进程的首次调入（运行前调入，由程序员指出应该先调入哪些部分）
请求调页策略：进程再运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大
何处调入页面：
系统拥有足够的对换区空间:页面的调入、调出都是在内存与对换区之问进行，这样可以保证页面的调入、调出速度很快。在进程运行前需将进程相关的数据从文件区复制到对换区。
系统缺少足够的对换区空间:凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入
UNIX方式:运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
对换区：采用连续存储方式、速度更快
文件区：采用离散存储方式、速度更慢
抖动（颠簸）：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为
产生抖动的主要原因：进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
工作集：指再某段时间间隔里，进程实际访问页面的集合
注：驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页
文件：一组有意义的信息/数据集合
文件的属性：
标识符：一个系统内的各文件标识符唯一，对用户毫无可读性。因此标识符只是操作系统用于区分各个文件的一种内部名称
类型：指明文件的类型
大小：文件的大小
创建时间、上次修改时间、文件所有者信息
保护信息：对文件进行保护的访问控制信息
文件内部数据如何组织：
无结构文件（如文本文件）：由一些二进制或者字符流组成，也称“流式文件”
有结构文件（如数据库表）：由一组相似的记录组成，也叫“记录式文件”
数据项是文件系统中最基本的数据单位
记录是一组相关数据项的集合
操作系统向上提供的基本功能：
创建文件（create调用）
删除文件（delete调用）
读文件（read调用）
写文件（wirte调用）
打开文件（open调用）
关闭文件（close调用）
文件应该如何存放到外存中（文件的物理结构）
操作系统如何管理外存中的空闲块（存储空间的管理）
操作系统需要提供的其他文件管理功能（文件共享，文件保护）
逻辑结构分为：
无结构文件
有结构文件
顺序文件
索引文件
索引顺序文件
所谓逻辑结构：指在用户看来，文件内部数据应该是如何组织起来的。
所谓物理结构：在操作系统看来，文件的数据如何存放在外存中的
按文件是否有结构分类 分为无结构文件、有结构文件
无结构文件：文件内部的数据是单纯的一系列二进制流或者字符流组成。也叫流式文件。如“txt”文件
有结构文件：由一组相似的记录组成，也叫做记录式文件。每条记录由若干个数据项组成。如：数据库表文件。一般来说，每条记录由一个数据项可以作为关键字。根据各条记录的长度（占用的存储空间）是否相等。又可以分为定长记录和可变长记录两种。
定长记录:
可变长记录：
根据有结构文件中的各条记录在逻辑上如何组织，可以分为三类：顺序文件，索引文件，索引顺序文件
顺序文件：文件中的记录一个接一个的顺序排列（逻辑上），记录可以是定长的或者是可变长的。各个记录在物理上可顺序或者链式存储
顺序存储：逻辑上相邻的记录物理上也相邻（类似于顺序表）
链式存储：逻辑上相邻的记录物理上不一定相邻（类似于链表）
顺序文件：
串结构：记录之间的顺序于关键字无关（通常按照记录存入的时间决定记录的顺序）
顺序结构：记录之间的顺序按关键字顺序排列
链式存储：无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次向后查找
顺序存储：
可变长记录：无法实现随机存取，只能从第一个记录开始一次往后查找
定长记录：
可以随机存取，记录长度为L，则第i个记录存放的相对位置是i*L
若采用串结构，无法快速找到某关键字对应的记录
若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
结论：定长记录的顺序文件，若物理上用顺序存储，则可以实现随机存储。若能再保证记录的顺序结构，则可实现快速检索
注：考试中的顺序文件指：物理上顺序存储的顺序文件
顺序文件缺点：增加/删除一个记录相对困难（如果是串结构简单一些）
索引文件：索引表本身是一个定长记录的顺序文件。可以快速找到第i个记录对应的索引项 主要用于：对信息处理及时性要求较高的场合
可以用不同的数据项建立多个索引表（SQL支持根据某个数据项建立索引的功能）
索引文件缺点：每个记录对应一个索引表项。因此索引表可能会很大。如：文件的每个记录平均只占8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，存储空间利用率较低
索引顺序文件：索引文件和顺序文件思想结合。同样会为文件建立一张索引表，但是不同的是，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项
多级索引顺序文件：提高检索效率，可以为顺序文件建立多级索引表
操作系统对磁盘块进行哪些管理：
对非空闲磁盘块的管理（存放了文件数据的磁盘块）
对空闲磁盘块的管理
文件的物理结构（文件分配方式即文件数据应该怎么样存放在外存中）：
连续分配
链接分配
隐式链接
显式链接
索引分配
连续分配：要求每个文件在磁盘上占有一组连续的块
物理块号 = 起始块号 + 逻辑块号
同时需要检查用户提供的逻辑块哈哦是否合法（逻辑块号 >= 长度不合法）
可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）
读取某个磁盘块时，需要移动磁盘，访问的两个磁盘块相隔越远，移动磁头所需时间越长
结论：连续分配的文件在顺序读/写时速度最快
结论：物理上采用连续分配的文件不方便拓展
结论：物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片 可以用紧凑来处理碎片，但是需要耗费很大时间代价
连续分配总结：
优点：支持顺序访问和直接访问（即随机访问），连续分配的文件在顺序访问时速度最快
缺点：不方便文件拓展，存储空间利用率低，会产生磁盘碎片
链接分配：以离散分配的方式，可以为文件分配离散的磁盘块，分为隐式链接、显式链接两种方式
结论1：采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量存储空间
结论2：采用隐式链接的链接分配方式，很方便文件拓展。另外， 所有空闲磁盘块都可以被利用，不会有碎片问题，外村利用率高
优点：很方便文件拓展，不会有碎片问题，外存利用率高
只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间
显式链接：把用于链接文件各物理块的指针显式存放在一张表中。即文件分配表中（FAT）
注：一个磁盘仅设置一张FAT。开机时，将FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以隐含
总结：把用于链接文件各物理块的指针显式存放在一张表中。即文件分配表中（FAT） 一个磁盘只会建立一张文件分配表。开机时，文件分配表放入内存，并常驻内存
缺点：文件分配表需要占用一定的存储空间
索引分配：允许文件离散的分散在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块
索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表即可）但是索引表需要占用一定的存储空间
链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块连接起来存放
多层索引：进阿里多层索引（原理类似于多级页表）使第一层索引块指向第二层的索引块。则可根据文件大小的要求再建立第三层、第四层索引块（若采用多级索引，则各层索引表大小不能超过一个磁盘块）
要会根据多层索引、混合索引结构计算出文件的最大长度（KEY：各级索引表最大不能超过一个块）
要能自己分析访问某个数据块所需的都磁盘次数（KEY：FCB中会有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作）
逻辑结构：
用户（文件创建者）的视角看到的样子
文件内部的信息组织完全由用户自己决定，操作系统并不关系
物理结构：
由操作系统决定文件采用什么物理结构存储
文件系统的层次结构：
索引节点（对文件控制块的优化）
FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除节点请求时，只是删除该用户的FCB、并使共享计数器-1，并不会直接删共享结点 只有共享计数器减为0时，才删除结点
索引结点：
除了文件名之外的所有信息都放到索引节点中，每个文件对应一个索引结点
操作系统需要对磁盘进行的管理：
对非空闲磁盘块的管理（存放了文件数据的磁盘块） --- “文件的物理结构/文件分配方式”要讨论的问题
对空闲磁盘块的管理 ---“文件存储管理”要探讨的问题
文件存储管理：
存储空间的划分与初始化
文件卷（逻辑卷）的概念
几种管理方法
空闲表法
空闲链表法
空闲盘块链
空闲盘区链
位示图法
成组链接法
存储空间的划分与初始化：在安装windows操作系统的时候，一个必经步骤是为磁盘分区（C D E盘）
文件区用于存放文件数据
存储空间管理：空闲表法：适用于“连续分配方式”
如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可以采用首次使用、最佳适应、最坏适应等算法来决定要为文件分配哪个区间
如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况
回收区的前后都没有相邻空闲区
回收区的前后都是空闲区
回收区前面是空闲区
回收区后面是空闲区
总之：回收时需要注意表项的合并问题
空闲链表法：
空闲盘块链 ----- 以盘块为单位组成一条空闲链
空闲盘区链 ----- 以盘区为单位组成一条空闲链
操作系统保存着链头、链尾指针
如何分配：若某文件申请K个盘块、则从链头开始一次摘下K个盘块分配，并修改空闲的链头指针
如何回收：回收的盘块一次挂到链尾，并修改空闲链的链尾指针
操作系统保存着链头、链尾指针
如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据
如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘曲中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾（离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高）
位示图法：连续分配、离散分配都适用
位示图：每个二进制位对应一个盘块
如何分配：若文件需要K个块
顺序扫描位示图，找到K个相邻或不相邻的“0”
根据字号、位号算出对应的盘块号，将相应盘块分配给文件
将相应位设置为“1”
如何回收：
根据回收的盘块号计算出相应的字号、位号
将相应二进制位设为“0”
成组链接法（很难作为考题）：适用于大型文件系统 因为空闲表或者空闲链表可能过大 UNIX系统中采用了成组链接法对磁盘空闲块进行管理
向上提供的基本功能：
创建文件（create系统调用）
删除文件（delete系统调用）
读文件（read系统调用）
写文件（write系统调用）
打开文件（open系统调用）
关闭文件（close系统调用）
创建文件：
进行create系统调用时，需要提供的几个主要参数：
所需的外存空间大小（如一个盘块，即1KB）
文件存放路径（D：/Demo）
文件名（这个地方默认为“新建文本文档.txt”）
操作系统在处理Create系统调用时，主要做了两件事：
在外存中找到文件所需的空间
删除文件：
进行Delete系统调用，需要提供的几个主要参数：
文件存放路径（D：/Demo）
文件名（test.txt)
操作系统在处理Delete系统调用时，主要做了几件事：
打开文件：
很多操作系统中，在对文件进行操作之前，要求用户先使用open系统调用“打开文件”，需要提供几个主要参数：
文件存放路径（D：/Demo）
文件名（test.txt)
要对文件的操作类型（如：r只读，rw读写等）
操作系统在处理open系统调用时，主要做了几件事：
关闭文件：
进程使用完文件后，要“关闭文件”
操作系统在处理Close系统调用时，主要做了几件事：
将进程的打开文件表相应表项删除
回收分配给该文件的内存空间等资源
系统打开文件表的打开计数器count减1，若count = 0 则删除对应表项
读文件：根据读指针、读入数据量、内存位置将文件数据从外存读入内存
写文件：根据写指针、写出数据量、内存位置将文件数据从内存写出外存
文件共享：操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件
基于索引结点的共享方式（硬链接）
基于符号链的共享方式（软链接）
注：多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化 若是多个用户都复制了同一个文件，那么系统中会有好几份文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并无影响
硬链接：
索引节点中需要有链接计数count
只有count == 0时才能真正删除文件数据和索引结点，否则会导致指针悬空
软连接（符号链接）：
在一个Link型的文件中记录共享文件的存放路径（Windows快捷方式）
文件保护：保护文件数据的安全
口令保护
加密保护
访问控制
口令保护：为文件设置一个“口令”，用户请求访问该文件时必须提供“口令”
注：口令一般存在文件对应的FCB或索引节点中，用户访问文件前需要先输入口令，操作系统会将用户提供的口令与FCB中存储的口令进行对比，若正确，则允许该用户访问文件
优点：保存口令的空间开销不多，验证口令的时间开销也很小
缺点：正确的“口令”存放在系统内部，不够安全
加密保护：使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密
优点：保密性强，无需再系统中存储“密码”
缺点：编码/以嘛，或者说加密/解密要花费一定时间
访问控制：在每个文件的FCB（或索引结点）中增加一个访问控制列表，该表中记录了各个用户可以对该文件执行哪些操作
精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作
当某个用户想要访问文件时，系统会检查该用户所属分组是否有相应的访问权限
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- huatuo0.cn 版权所有 湘ICP备2023017654号-2
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务