操作系统笔记

 第一章、

①操作系统的四个特征：并发、共享、虚拟、异步。（并发和共享是最基本的特征，二者互为存在条件）（没有并发和共享，就没有虚拟和异步）

1.并发：宏观上是同时发生的，微观上是交替发生的。

操作系统的并发性：计算机系统“同时”运行着多个程序，宏观上看是同时运行着的，微观上看是交替运行的。

考点：单核CPU同一时刻只能执行一个程序，各个程序只能并发的执行；而多核CPU中，多个程序可以并行的执行。

2.并行：同一时刻同时发生

3.共享：指系统中的资源供内存中多个并发执行的进程共同使用。

• 互斥共享方式
• 同时共享方式：往往宏观上“同时”，微观上是交替地对资源进行访问的。（但有时微观上也确实是同时发生的）

4. 虚拟：将一个物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上的对应物是用户感受到的。

5.虚拟存储器技术：比如，我的电脑只有4GB内存，而GTA5需要4GB的运行内存、QQ需要256MB内存，网易云需要256MB的内存.......但是他们还可以在电脑上同时运行，这就是虚拟存储器技术，实际上只有4GB内存，在用户看来远远大于4GB。

6.虚拟处理器技术：比如，在某单核CPU中，用户打开了QQ、网易云、微信等软件，实际上只有一个单核CPU，在用户看来，有多个CPU在同时为自己服务。

②操作系统的运行机制：

1. CPU上会运行两类程序：内核程序、应用程序
2. 分为两类指令：特权指令（只能由内核程序执行）、非特权指令
3. 分为两种处理器状态：内核态（又名核心态、管态）、用户态（又名目态）

• 内核态--->用户态：执行一条特权指令，修改PSW的标志位变为“用户态”，这个动作意味着操作系统主动让出CPU使用权
•   用户态--->内核态：触发中断信号，意味着操作系统强行夺回CPU使用权

③中断和异常

1. 中断的作用（没有中断就没有并发）：让用户态变回内核态的唯一方式，让操作系统强行的夺回CPU的控制权
2. 中断的分类：分为内中断（又名异常）、外中断（又名中断--狭义上的）
3. 如何区分内中断外中断：是否与当前执行的指令有关
4. 中断机制的基本实现原理：

• 检查中断信号：内中断是在执行每条指令的时候就会检查是否有异常会发生、外中断是在每个指令周期末尾，CPU都会检查是否有外中断信号待处理
  • 找到相应的中断处理程序：通过“中断向量表”中查找对应的 ①②③.....

内中断：陷入（trap），故障（fault），终止（abort）

• 陷入trap：有时候应用程序想请求操作系统内核的服务，此时会执行一条特殊的指令---陷入指令（不是特权指令），也会引发一个内部中断信号，这个动作意味着应用主动地将CPU控制权还给操作系统内核
• 故障fault：由错误条件引起，可能被内核程序修复。例如缺页故障。
• 终止abort：由致命错误引起，无法被内核程序修复。在用户态下执行了特权指令或者执行了一条非法指令（例如：整数除以0），就会引发中断信号

外中断：时钟中断、I/O中断请求

• 例如时钟中断，时钟部件每隔一个时间片（如50ms），会给CPU发送一个时钟中断信号，此时CPU在执行应用程序1的指令，会转而执行中断的内核程序，然后开始执行应用程序2的指令，然后又过去了50ms，又中断，然后又换了一个程序执行指令。

 ④系统调用

1. 凡是对共享资源的访问，都必须通过系统调用的方式向操作系统提出服务请求（如存储分配、I/O操作、文件管理等）       
2. 系统调用的过程：应用程序先给传参指令，然后给陷入指令（trap），CPU转为内核态开始执行中断程序， 以及后续的对传过来的参数的相关指令，执行完毕后，再转为用户态，继续执行用户程序的指令。需要注意的是：陷入指令是特殊的指令，是在用户态下执行的，执行陷入指令后，会立即引发一个内中断，使CPU进入核心态。陷入指令==trap指令==访管指令

⑤操作系统的体系结构

ps ：CPU状态的转换是需要消耗不少的时间，

1.大内核：除了硬件关系最紧密的：原语、时钟管理、中断处理 ，还将进程管理、存储管理、设备管理放在内核中

        优点

• 高性能：因为应用程序请求内核服务时，CPU状态转换的次数较少

        缺点

• 内核代码庞大，结构混乱，不易维护

2.微内核：只将与硬件关系最紧密的：原语、时钟管理、中断处理 放在内核。

        优点

• 内核功能少，结构清晰，易于维护

        缺点

• 性能低：需要频繁地在用户态和核心态之间切换

3.分层结构：一层一层的结构，最底层是硬件，最高层是用户接口，每层只可以调用更低一层。（如：层1只能调用层0，也就是硬件层；层3只能调用层2）

        优点

• 便于调试和验证，自底向上逐层调试验证

        缺点

• 效率低，不可以跨层调用，比如用户想要直接调用层2，结果还需要从5->4->3->2，太慢了

4.模块化：将内核分为多个模块，各模块之间相互协作 

          优点

• 可以动态加载新的内核模块
• 各个模块之间可以直接相互调用，无需采用消息传递进行通信，效率高

        缺点

• 各个模块相互调用，难以调试

5.外核 

⑥ 操作系统引导

磁盘分为几个分区：主引导记录（MBR）、C盘、D盘、E盘。

• 主引导记录（MBR）中包含磁盘引导程序和分区表：分区表就是一个数据结构，告诉这个磁盘当中，每个分区分别占多大空间，以及地址范围。
• C盘：是活动分区，安装了操作系统相关程序。C盘可以细分为：引导记录（PBR）、根目录、其他。

主存分为：RAM、ROM（BIOS：Basic Input/Output System）。平时我们所说的手机内存、电脑内存就是RAM

• RAM芯片里面的数据只要一断电、关机，就会被清空；而ROM芯片里的数据不会因为关机而丢失。
• ROM包含ROM引导程序，即自举程序 

操作系统引导（开机过程）：

1. CPU先从特定的主存地址开始，取指令，执行ROM中的引导程序，即自举程序（先进行硬件检查：比如检查有没有插磁条、插内存条，再开机）
2.  然后将磁盘的第一块---主引导记录（MBR）读入内存，执行磁盘引导程序，扫描分区表（分区表会告知活动分区的起始地址，即C盘在哪里）
3. 找到了活动分区后，开始读活动分区的第一个部分：引导记录（PBR）到内存中，执行其中的程序
4. 最后，从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列操作。

 ⑦虚拟机（VM--Virtual Machine）

有两类用户管理程序（VMM--Virtual Machine Monitor）

第一类VMM

• 直接运行在硬件之上，能够直接控制和分配物理资源
• 在安装Guest OS时，VMM要在原本的硬盘上面自行分配存储空间，类似于“外核”的分配方式，分配未经抽象的物理硬件
• 性能更好
• 可以支持更多的虚拟机数量

第二类VMM

• 运行在Host OS之上，依赖于Host OS为其分配物理资源
• GuestOS拥有自己的虚拟磁盘。该盘实际上是Host OS文件系统中的一个大文件。Guest OS分配到的内存实际上是虚拟内存。
• 性能较差，但是虚拟机的可迁移性更好，只需要导出虚拟机镜像文件即可迁移到另外一台Host OS上。
• 只能支持更少的虚拟机数量

第二章、

①进程的概念、组成、特征

• 程序：是静态的，是存放在磁盘里面的可执行文件（.exe）,就是一系列指令的集合
• 进程：是动态的，是程序的一次执行过程。例如：点击执行一次QQ程序，任务管理器中便会多一个QQ的进程，再执行一次，又会多一个QQ的进程。
  • Q：那么如何将这些进程区分呢？         A：操作系统在创建这些进程的时候，会为该进程创建一个唯一的、不重复的PID（Progress ID）
• PCB（Progress Control Block）：操作系统要记录PID，进程所属用户（UID），还要记录给进程分配了哪些资源、运行情况，这些都要被保存在一个数据结构PCB，即进程控制块
  • PCB是进程存在的唯一标志，进程被创建时，操作系统会为其创建PCB，进程结束时，会回收其PCB。
• 进程实体的组成：PCB、程序段、数据段

 ②进程的状态与转换、进程的组织

进程的状态：创建态（又称：新建态）、就绪态、运行态、阻塞态（又称：等待态）、终止态（又称：结束态）

进程的转换：

                                                                王道考研

其中，

1. 就绪态、运行态、阻塞态是三种基本状态
2. 进程PCB中，会有一个变量state来表示当前进程的状态。如：1表示创建态、2表示就绪态、3表示运行态......

 进程的组织：

• 链接方式
  • 按照进程状态将PCB分为多个队列
  • 操作系统持有指向各个队列的指针                                                              

 

•  索引方式
  • 根据进程状态的不同，建立几张索引表
  • 操作系统持有指向各个索引表的指针

③进程控制

 

④进程通信

1.共享存储

需要互斥的访问共享控件（由通信进程自己负责实现互斥）

2.消息传递

•  直接通信：表明  谁发出的   以及  发给谁的
• 间接通信：进程将信息发送到操作系统内核中的信箱中，然后别的进程从信箱里接收信息

3.管道通信：在内存中开辟一个大小固定的内存缓冲区，数据只能单向的（像水流一样）从一个进程通过管道流向另一个进程

• Q：与共享内存那种方式有何区别？          A：共享内存方式：可以向共享区域内任何地区写数据读数据，然而管道通信方式，要写数据，只能靠着“顶部”写。
• 若管道写满了，写进程将阻塞，直到读进程将管道中的数据读走，即可唤醒写进程。
• 若管道没有数据，则读进程将堵塞，直到写进程写入数据，即可唤醒读进程

⑤线程的概念        

⑥线程的实现方式和多线程模型

①调度的概念、层次

②进程调度的时机、切换与过程、方式

• 进程调度的方式：非剥夺调度方式（又称：非抢占方式）、剥夺调度方式（又称：抢占方式）
  • 非剥夺调度方式：只允许进程主动的放弃处理机
  • 剥夺调度方式：当一个进程在处理机上执行时，如果来了一个优先级更高的进程，那么就会立即暂停当前正在执行的进程，将处理机分配给那个进程
• 进程切换的过程主要完成了：

1. 对原来运行的进程各种数据进行保存
2. 对新的进程各种数据进行恢复

③闲逛进程

CPU不可能空闲下来，如果没有进程执行的话，就执行闲逛进程。因此，闲逛进程就是进程调度的备胎。

④调度算法的评价指标

1. CPU利用率：指CPU“忙碌”时间占总时间的比例
2. 系统吞吐量：单位时间内完成作业的数量
3. 周转时间：作业的提交到完成花费了多少时间
4. 平均周转时间：各作业的周转时间之和 / 总作业数量
5. 带权周转时间：作业周转时间 / 作业实际运行时间。   ps：带权周转时间越小，用户满意度越高
6. 等待时间：进程/作业等待被服务的时间之和
7. 响应时间：从用户提交请求到首次产生响应所用的时间

⑤调度算法

单处理机调度算法

多处理机调度算法

单队列

维护一个全局就绪队列，为所有CPU共享。注意：CPU在挑选进程的时候，需要上锁，以防各个CPU调度了相同的进程

多队列

每个CPU都有自己单独的调度队列，

进程同步、进程互斥

一个时间段只允许一个进程访问的资源叫做临界资源；而对临界资源的访问，必须互斥地进行

进程互斥的软件实现方法

1. 单标志法：违背了“空闲让进”的原则。利用一个变量turn标志谁可以使用，配合一个while循环，控制是否可以接下来的语句
2. 双标志先检查法：违背了“忙则等待”的原则。先检查再“上锁。”利用一个bool型数组，在进入区通过while循环判断对方进程是否想要进入临界区，如果不想进入，那就自己进入，并且改动自己的bool类型
3. 双标志后检查法：违背了“空闲让进”和“有限等待”，会产生“饥饿”现象。先“上锁”后检查。
4. Peterson算法：未遵循让权等待的原则。结合单标志法和双标志法的思想。

• 所谓让权等待：即当进程进入不了临界区时，应立即释放CPU资源，而此时一直在while循环里，并没有释放CPU资源

进程互斥的硬件实现方法

1. 中断屏蔽方法：利用“关/开中断指令”实现
2. TestAndSet指令：又称TS指令、TSL指令。TSL指令是由硬件实现的，执行的过程不允许中断。
3. Swap指令：又称Exchange指令、XCHG指令。与TSL指令一样，由硬件实现的，执行的过程不允许中断。

互斥锁

锁：其实可以理解为一个bool型变量

信号量机制

• 信号量其实就是一个变量（可以是一个整数，也可以是一个更复杂的记录型变量），可以用信号量来表示系统中某种资源的数量         

一对原语：wait(S)原语和signal(S)原语，做题时候通常把这两个操作简称为P(S)、V（S）

1. 信号量机制----整型信号量：只有三种操作：初始化、P操作、V操作

   存在的问题：不满足“让权等待”，会出现“忙等”

2. 信号量机制----记录型信号量：为了解决整型信号量的“忙等”问题。

   /*记录型信号量的定义*/
   typedef struct{
       int value;//剩余资源数    
       struct process* L;//等待队列
   }semaphore;
    
   void wait(semaphore S){//wait 原语
       S.value--;
       if(S.value < 0){//说明此时没有可用资源，将该进程从运行态变为阻塞态
           block(S.L);//让他进入等待队列
       }
   }
    
   void signal(semaphore S){//signal原语
       S.value++;  
       if(S.value <= 0){//说明此时还有进程在等待该资源
           wakeup(S.L);//唤醒等待队列中的一个进程，将该进程从阻塞态变为就绪态
       }
   }
   

   

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

1.信号量实现进程的互斥：通过semaphore 一个变量 mutex（互斥信号量，初始值为1），然后通过P、V操作完成

2.信号量实现                进程的同步：让各并发的进程按照要求有序地推进。（比如，进程2的代码需要在进程1代码的基础上实现）

信号量机制实现进程同步：前V后P、且同步信号量需要初始化为0

3.信号量机制实现进程前驱：设置多个同步信号量

总结：

生产者-消费者问题

                

注意：

• 实现互斥的P操作，一定要在实现同步的P操作之后，否则可能会引起“死锁”操作
• 在多消费者问题中，正确的分析方法应该从“事件”的角度来考虑，而不是从“进程”的角度。

吸烟者问题

系统一共有四种进程，三个抽烟者进程和一个供应者进程。

我们将桌子抽象为容量为1 的缓冲区，需要互斥访问。

读写者问题

• 如何实现 ：可让多个读者同时读？        答：由第一个读者上锁，最后一个读者解锁。其中，对count++操作需要一个互斥信号量来控制访问

但是上图，如果 有源源不断的 读进程来访问，那么count会一直++++++，从而造成信号量rw一直没有被解锁，进而造成写进程的“饿死”。  此时可以再增加一个信号量，来实现“写优先”

管程

死锁

定义：多个进程在执行过程中，因为争夺同类资源且资源分配不当而造成的相互等待的现象，若无外力作用，它们都将永远无法继续执行，这种现象叫死锁。

1.必要条件

1. 互斥条件：只有对必须互斥使用的资源进行争抢，才会导致死锁
2. 不剥夺条件：进程所获得的资源在未使用完之前，不可被其他进程强行占领，只能主动释放
3. 请求和保持条件：进程已经保持了至少一个条件，又提出新的资源请求，而该资源正被其他进程占用，此时请求进程堵塞，但又对自己已有的资源保持不放
4. 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

ps:循环等待  未必  会死锁   ，死锁  必定  循环等待3

2.预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

3.避免死锁

银行家算法

4.检测和解除

上图中，如何决定对谁动手呢？

1.进程优先级

2.进程已进行了多长时间

3.进程还要多久完成

4.进程已经使用了多少资源

5.进程是交互式的还是批处理式的。

第三章、

3.1.1内存的基础知识

内存可存放数据。程序 原本存放在外存（磁盘）中，但是磁盘的读写速度很慢，而CPU的处理速度很快，因此程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬盘之间的速度矛盾

内存地址从0开始，每个地址对应一个存储单元，如果计算机是“按字节编制”，则每个存储单元大小为1字节，即1B，即8个二进制位

装入的三种方式：

绝对装入：知道装入模块在内存中的实际起始地址100，再加上逻辑地址79，就成为了绝对装入（直接将地址为179的数据读入寄存器）

可重定位装入（静态重定位）：编译、链接后的装入模块的地址都是从0开始，将装入模块装入的内存的合适位置时候，装入时，对里面的所有地址“重定位” ，将逻辑地址全部变成物理地址（地址变换是在装入时一次完成的）。     注意：在静态重定位中，作业一旦进入内存中，在运行期间是不可以移动的，也不能够再申请空间

动态重定位（动态运行时装入）：需要借助一个重定位寄存器（存放装入模块存放的起始位置），在读取其中的指令时，每次会将读取到的逻辑地址  加上 重定位寄存器里面存放的起始地址，从而形成绝对地址

从写程序到程序运行：

①每个源文件（.c）   经过编译   成为目标文件(.o)（编译就是把高级语言翻译为机器语言）

②将所有目标文件    经过链接   形成一个大的  准入模块(.exe)

3.1.2内存管理的概念 

3.1.3覆盖与交换  

1.覆盖技术（用于早期的操作系统，现在已成历史）

        人们引入覆盖技术，用来解决“程序大小超过计算机物理内存总和”的问题。

覆盖技术的原理：将一个程序分为多个程序段，然后一些常用的段放在固定区，不常用的段放在覆盖区。有一个固定区，及若干个覆盖区。（不可能同时访问的程序段可以共享一个覆盖区）        

操作系统不知道哪些是可以覆盖、哪些是常用，因此需要程序员声明覆盖结构。

缺点：对用户不透明，增加了用户的编程负担，

2.交换技术

        内存紧张时，换出某些进程到外存上，以腾出内存空间，再换入某些进程；磁盘分为对换区和文件区，换出的进程放在对换区（对换区的I/O速度相对来说更快）

被暂时换出外存（磁盘）等待的进程为挂起状态（挂起态，suspend）

注意：PCB是常驻内存的，不会被换出外存。

问：为什么不把PCB也换出外存呢？   因为进程被换出外存，需要记录存放到外存的哪块地址上，这些信息可以存放到进程自己的PCB中，因此PCB常驻内存。

3.覆盖技术与交换技术的区别

        覆盖是在同一个进程中的，而交换是在不同进程（作业）之间的

3.1.4连续分配管理方式

1.单一连续分配

• 内存被分为系统区和用户区，系统区通常位于内存的低地址部分。
• 系统区，存放操作系统相关数据
• 用户区，存放用户进程相关数据
• 内存中，只能有一道用户程序，用户程序独占整个用户区的
• 优点：实现简单，无外部碎片
• 缺点：只能用于单用户、单任务的操作系统；有内部碎片（内部碎片就是分配给进程的空间中，没用上的内存空间）；存储区利用率极低

2.固定分区分配

• 用户空间划分成若干个固定大小的分区，每个分区只能装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式
• 有两种分法：分区大小相等、分区大小不等
• 优点：实现简单、无外部碎片
• 缺点：a.如果有一个程序太大了，任一分区都无法满足需求，此时不得不采取覆盖技术，而覆盖技术是耗时的，从而造成性能降低；b.会产生内部碎片，内存利用率低

3.动态分区分配（可变分区分配）

• 在进程装入内存时，根据进程的大小动态地建立分区
• 要求作业完整调入，并且连续存放
• 支持多道程序
• 优点：无内部碎片
• 缺点：有外部碎片
• 外部碎片可以通过“紧凑”技术来解决

考点：采用可变分区分配管理主存时，无法实现虚拟存储器。

4.内部碎片和外部碎片

        内部碎片：分配给进程的内存区域中，有些部分没有用上

        外部碎片：内存中，某些空闲分区太小了，进而难以将其分配给进程

3.1.5.动态分区分配算法

        当多个休闲分区都能满足需求时，选择哪一个分区呢？

首次适应算法

        算法思想：每次从低地址开始查找第一个能够满足要求的空闲分区。

最佳适应算法

        算法思想：优先使用更小的空闲分区 

        如何实现：空闲分区按照容量递增次序链接，每次分配内存时，顺序查找空闲分区链，找到第一个能够满足要求的分区

        缺点：会留下越来越多的难以利用的小的分区，因此这种算法会产生很多外部碎片        

最坏适应算法（最大适应算法）

        算法思想：优先使用更大的空闲分区

        如何实现：空闲分区按照容量                                                                递减次序链接，每次分配内存时，顺序查找空闲分区链，找到第一个能否满足要求的分区

        缺点：会不断地将大分区划分成小分区，最后突然来一个内存需求大的进程，可能没有能够满足这个进程的空闲分区存在了

临近适应算法

        算法思想：首次适应算法每次都要从链头开始查找，增加了查找的开销。如果每次从上次结束查找的位置开始检索，就可以解决上述问题。

        如何实现：空闲分区以地址递增的顺序排列，每次分配内存的时候，从上次结束的位置开始查找空闲分区链（或者空闲分区表），找到第一个能够满足要求的分区

注意：a.因为首次适应算法和邻近适应算法中，空闲分区是按照低地址到高地址的顺序排列，当空闲分区的大小发生变化的时候，无需对整个链表重新排序，因此这两种算法比最佳适应算法和最坏适应算法开销要小 b.综合来看，首次适应算法是最优的

3.1.6☆基本分页存储管理（页式管理）

• 将内存空间分成一个个大小相等的分区，每个分区就是一个“页框”（页框=页帧=内存块=物理块=物理页面）
  • 每个页框都有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），且页框号从0开始
• 将进程的逻辑地址空间分成与页框大小相等的一个个部分，每个部分称为“页”或“页面”
  • 每个页面也有编号，即“页号”，且页号从0开始
• 进程的页面与内存的页框有着一一对应的关系，通过页表来记录
  • 操作系统会给每个进程都建立一张页表，页表通常存储在PCB中                
  • 页表由一个个页表项组成，页表项由页号、内存快号构成
  • 内存快号占存储空间、而页号不占空间
• 在分页存储管理中，如何通过逻辑地址，找到物理地址？
  • 答：先通过逻辑地址，找到页号和页内偏移量，然后通过页表，找到对应的快号，进而求出实际的物理存储地址。
• 注意：页内偏移量=页面大小
• 最好将页面大小，设置成2的整数幂

3.1.7基本地址变换机构

1. 系统中会有页表寄存器（PTR），用来存放页表在内存中的 起始地址和页表长度（有多少页） 。
2. 进程没有执行的时候，页表的起始地址和页表长度都是存放在PCB中的，只有当进程被调度的时候，操作系统内核才会将他们放入页表寄存器中   
3. 页式管理中地址是一维的，即将逻辑地址转换成物理地址，只需要给一个信息：逻辑地址的值即可。因为页面大小是固定的，根据逻辑地址便可以知道页号、页内偏移量
4. 页内偏移量大小  =  页面大大小               
5. 一个页框大小为4KB,也就是4096B，如果每个页表项的大小为3B，那么每个页框都会剩余1B，这样不优，通常设置页表项的大小为4B，这样一个页框内可以放整数个页表项                                                                    

3.1.8具有快表的地址变换机构

        快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓存（不是内存），用来存放最近访问的页表项的副本。与之对应的，就是内存中的页表，也称为慢表。

        注意：快表是一个硬件，当进程切换的时候，快表中的数据也要对应的清空

3.1.9两级页表

• 单级页表存在的问题
  • 页表需要连续存放，当页表很大的时候，需要占用很多个连续的页框

两级页表的逻辑地址的结构：（一级页号、二级页号、页内偏移量）

为离散分配的页表再建立一张页表，成为页目录表、外层页表、顶层页表。

3.1.10基本分段存储管理

1.分段存储和分页存储的一大差异：分页是每页大小固定，分段是每段的大小不固定，

2.分段存储管理中，每段都有一个段名，每段从0开始编址。每个段在内存中占用连续空间，但是各段之间可以不相邻

3. 段号的位数决定了每个进程最多可以分几个段；段内地址的位数决定了每个段的最大长度是多少                                          

4.各个段在内存中是离散存储的，因此也需要“段表”：段表项中包含   段号、段长、基址

        

3.1.11段页式管理方式

一个进程先按照逻辑模块分段，再将各段分页。

在此管理方式中，一个进程对应一个段表，段页表中存放段号、页表长度、页表存放快号。即一个进程对应一个段表，也意味着对应多个页表

3.2.1虚拟内存的基本概念

虚拟内存技术的提出是  基于  局部性原理

• 时间局部性：如果执行了程序的某条指令，那么不久后这条指令很有可能再次执行的；如果某条数据被访问过，那么不久后这条数据很有可能再次被访问的
• 空间局部性：一旦程序访问了某片内存区域，在不久之后，其附近的内存区域也很有可能被访问

虚拟内存的由来：

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的留在外存，就可以让程序执行。

在程序执行过程，当所访问的信息不在内存的时候，操作系统就从外存上调入内存。

若内存空间不够用时，就将内存上暂时用不到的信息换出到外存上。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

虚拟内存的三个主要特征：

多次性：无需在作业运行时一次性装入内存

对换性：在作业运行时，无需一直常驻内存，而是允许作业在运行过程中，将作业换入、换出

虚拟性：在逻辑上扩充了内存大小，让用户看起来内存比实际上大很多

虚拟内存的实现：

• 请求分页存储管理
• 请求分段存储管理
• 请求段页式存储管理

3.2.2请求分页存储管理

拿到逻辑地址，找到对应页表项后，发现对应页面未调入内存，则产生缺页中断，引发一个内中断，如若此时内存不够，则需要根据页面置换算法，选择页面换出到外存；页面调入内存后，需要修改相应的页表项

注意：缺页中断是内中断，属于内中断中的“故障”

3.2.3页面置换算法

最佳置换算法（OPT）

        每次选择淘汰的页面是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

        但是操作系统无法预知页面访问序列，因此，最佳置换算法是无法实现的。

先进先出置换算法（FIFO）

        每次选择淘汰最早进入内存的页面。

        这种算法实现起来很简单，但是会出现Belady现象：即分配的内存块更多，然而缺页次数不减反增。

        算法性能差。

最近最久未使用置换算法（LRU）

        每次淘汰的页面是最近最久未使用的页面。

        虽然算法性能好，但是实现困难，开销大

时钟置换算法（CLOCK）

        简单的CLOCK算法实现方法：

        改进型的CLOCK算法

3.2.4页面分配策略、抖动、工作集

驻留集

指在请求分页存储管理中，给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集的大小一般小于进程的总大小 

驻留集有两种分配策略：

1. 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行过程中不再改变。即，驻留集大小不变
2. 可变分配：先为每个进程分配一定数量的物理块，在进程运行过程中，视情况增加或减少。即，驻留集大小可变

抖动（颠簸）现象

刚刚换出的页面马上又要换入内存，或者  刚刚换入的页面马上又要换出到外存，这种频繁的页面调度现象称为抖动、或颠簸。

产生这一现象的主要原因：分配给进程的物理块不够

工作集

驻留集的大小一般不能小于工作集的大小

3.2.5 内存映射文件

第四章

4.1.4文件的物理结构

文件的分配方式-----连续分配

在逻辑地址上连续的逻辑块，存放在物理地址上时，也应该保持原有顺序，连续存放

文件的分配方式-----链接分配

采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显示链接。

显示链接：：将用于链接文件各物理块的指针显示地存放在一张表中，即，文件分配表（FAT，File Allocation Table）。FAT是一个磁盘对应一张。

隐式链接：只支持顺序访问，不支持随机访问

文件的分配方式-----索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表是一个文件对应一张。

4.1.6   文件存储空间管理

                

        

成组链接法

4.1.8 文件共享

硬链接 和  软链接

硬链接：各个用户的目录项指向同一个索引结点

软链接：其实就是快捷方式，原理是重定向，当打开它的文件时，自动就跳到了另一个文件。

硬链接的优点：某用户想要删除文件时，知识删除该用户的目录项，且count - -，只有count==0时候，才能真正的删除文件数据和索引节点；一个硬链接占用的空间很小

缺点：只能对已经存在的文件进行创建

软链接的优点：可以对不存在的文件或目录进行创建。

缺点：如果指向的原文件被删除了，则相关的软链接称为死链接；占用空间比较大

             

4.1.9文件保护

口令保护

• 口令存放在FCB或者索引结点中
• 用户需要先输入口令，操作系统会将其 与FCB中存储的口令对比，如果正确，就允许该用户访问文件

优点：空间开销不大，验证口令所需时间也不大

缺点：正确的口令  存放在系统内部，不够安全

加密保护

优点：保密性强，不需要在系统中存储密码

缺点：加密/解密 需要耗费一定的时间

访问控制

在每个文件的FCB或者索引结点中增加一个访问控制表，该表中记录各个用户可以对该文件执行哪些操作

虚拟文件系统VFS

1. 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
2. VFC要求下层的文件系统必须实现某些规定的函数功能

第五章

5.1.3    I/O控制方式

程序直接控制方式

中断驱动方式

DMA控制器

通道控制方式

5.2.3 设备的分配和回收

静态分配和动态分配

静态分配：进程运行之前，为其分配所有需要的资源，运行结束后返还资源

动态分配：进程在运行过程中，动态申请设备资源

5.3.1 磁盘的结构

磁盘属于一种I/O设备

5.3.2磁盘调度算法

先来先服务算法（FCFS）

根据请求到达的顺序，磁头依次移动到相应的磁道

优点：公平；如果请求访问的磁道比较集中的话，算法性能还能过得去

缺点：如果请求访问的磁道很分散，那么性能太差，寻道时间太长

最短寻找时间优先（SSTF）

优先处理的请求  是与磁头靠得最近的那个磁道

优点：性能较好，平均寻道时间短

缺点：会产生‘饥饿’现象

扫描算法（SCAN）--电梯算法

        为了解决最短寻找时间优先算法中 ，产生的“饥饿”现象。

只有磁头移动到最内侧的磁道时，才可以往外移动；只有磁头移动到最外侧的磁道时，才可以往内移动

LOOK调度算法

        为了解决扫描算法中，磁头必须移动到最顶端的缺点

如果磁头移动方向上，已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫LOOK）

循环扫描算法（C-SCAN）

        为了解决SCAN算法对于各个位置磁道的响应频率不均。

只有磁头向某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动到起始段而不处理任何请求

C-LOOK算法

如果移动的方向上没有磁道访问请求了，就可以立即让磁头返回到最前面（这个时候的移动不处理任何磁道请求），并且磁头返回到有磁道访问请求的位置即可