操作系统复习总结

自闭了、自闭了，好好做人好好复习

2020/3/25：16：57起步

3/25：20：48暂时休息，明天争取更新的差不多、另外发现C的还要补充一些新东西
3/26：更新的大题差不多了，会持续补充

3/27补充了一些新东西

1、操作系统的功能

  • 用户接口：命令接口、程序接口、图形接口

  • 处理机管理：进程控制、进程同步、进程通信、进程调度

  • 存储管理：内存分配、内存保护、地址映射、内存扩充

  • 设备管理：缓冲管理、设备分配、设备处理、虚拟设备管理

  • 文件管理：文件存储空间管理、目录管理、文件读写管理、文件保护、文件系统的安全性、文件接口

2、操作系统结构

内核（kernel）与外壳（shell）：
从整体上讲，操作系统一般可分为“内核”（kernel）和“外壳”（shell）两大部分。操作系统的内核是实现操作系统基本功能的程序模块的集合，在机器的系统态（核心态）下运行；操作系统的外壳，指的是运行在内核之上的、完成OS外层功能（如命令解释、机器诊断等）的程序，他们运行在机器的用户态下，是一种开放式结构，其功能可方便地修改或增删。

3、操作系统的特征

操作系统的基本特征：并发、虚拟、共享、不确定性

  • 并发：所谓并发是指在一段时间内有多道程序“在宏观上同时运行”，这样的系统叫并发系统。

  • 虚拟：操作系统中的虚拟概念，指的是操作系统使用某种技术，要么把物理上的一个变成逻辑上的多个，例如，把一台物理CPU变成多台逻辑上独立的CPU；要么把物理上的多个变成逻辑上的一个，例如，把物理上分开的主存和辅存变成逻辑上统一编址的编程空间，即虚拟内存。

  • 共享：多道必然带来共享，即多道程序、多个用户作业共享有限的计算机系统资源。计算机系统中的资源共享有两种类型：互斥共享和“同时”共享。

  • 不确定：操作系统的不确定，不是说操作系统本身的功能不确定，也不是说在操作系统控制下运行的用户程序的结果是不确定的，而是指在操作系统控制下的多个作业的执行顺序和每个作业的执行时间是不确定的。

现代操作系统新特征：微内核、多线程、多处理器、分布式操作系统、面向对象技术

操作系统分类：多批道处理系统、分时系统、实时系统、网络操作系统、分布式操作系统。

4、核心态和用户态

**用户态：**用户态具有较低特权的执行状态，在这种状态下，处理机只能执行规定的指令，访问指定的寄存器和存储区，用户程序通常只能在这一级别执行。

**核心态：**核心态是操作系统内核的运行状态，在这种状态下，处理机具有较高的特权，能执行一切指令，可以访问所有的寄存器和存储区。

在实际系统中，之所以要区分机器的两种运行状态，目的是给操作系统内核以某些特权，
为了安全性。在cpu的一些指令中，有的指令如果用错，将会导致整个系统崩溃。分了内核态和用户态后，当用户需要操作这些指令时候，内核为其提供了API，可以通过系统调用陷入内核，让内核去执行这些操作。

核心态和用户态的切换

用户态到核心态：

  1. 系统调用:

    这是用户进程主动要求切换到内核态的一种方式，用户进程通过系统调用申请操作系统提供的服务程序完成工作。系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现

  2. 异常：

    当CPU在执行运行在用户态的程序时，发现了某些事件不可知的异常，这是会触发由当前运行进程切换到处理此。异常的内核相关程序中，也就到了内核态，比如缺页异常。也是中断

  3. 外围设备中断：

    当外围设备完成用户请求的操作之后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条将要执行的指令，转而去执行中断信号的处理程序，如果先执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了有用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

用户态切换到内核态的步骤主要包括：

  1. 从当前进程的描述符中提取其内核栈的ss0及esp0信息。

  2. 使用ss0和esp0指向的内核栈将当前进程的cs,eip，eflags，ss,esp(各种地址指针)信息保存起来，这个过程也完成了由用户栈找到内核栈的切换过程，同时保存了被暂停执行的程序的下一条指令。

  3. 将先前由中断向量检索得到的中断处理程序的cs，eip信息装入相应的寄存器，开始执行中断处理程序，这时就转到了内核态的程序执行了。

5、中断技术、多通道技术

在现代计算机系统中，中断和通道技术是主机和外部设备并行工作的基础，是多道程序并发执行的推动力，也是整个操作系统的推动力——操作系统是由中断驱动的。

多通道存储器技术（英语：Multi-channel memory technology）是一种可以提升存储器数据发送性能的技术。它的主要原理，是在动态随机存储体和存储器控制器/芯片组之间，增加更多的并行通信通道，以增加数据发送的带宽。理论上每增加一条通道，数据发送性能相较于单通道而言会增加一倍。当前常见的多通道技术多为双通道的设置，理论上它们都拥有两倍于单通道的数据发送带宽。（from wiki）

**中断：**中断是指某个事件（电源掉电、加法溢出或外部设备传输结束等）发生时系统终止现行程序的运行，引出中断处理程序对该事件进行处理，完毕后返回断点继续运行，这个过程称为“中断”。

**中断的作用：**CPU与I/O设备并行工作、硬件故障处理、实现人机通信、实现多道程序的并发执行等。

**中断的类型：**硬件故障中断、程序性中断、外部中断、输入/输出设备中断、访管中断。

为什么说中断是多道程序并发执行的推动力呢？

在单CPU计算机系统中，要使多道程序得以并发执行，关键在于CPU能在这些程序间不断的切换，使得每道程序都有机会在CPU上运行。导致这种切换的动力是什么？主要是***时钟中断***。

6、进程和线程

  • 进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。
  • 线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

区别

  1. 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
  2. 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。
  3. 进程是资源分配的最小单位，线程是CPU调度的最小单位。
  4. 系统开销：在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。进程切换的开销也远大于线程切换的开销。
  5. 进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉

场景

  • 多进程间拥有各自独立的运行地址空间，进程间不会相互影响，程序可靠性强，但是进程创建、销毁和切换复杂，速度慢，占用内存多，进程间通信复杂，但是同步简单，适用于多核、多机分布。CPU密集型

  • 多线程之间共享同一个进程的地址空间，线程间通信简单，同步复杂，线程创建、销毁和切换简单，速度快，占用内存少，适用于多核分布式系统，但是线程间会相互影响，一个线程意外终止会导致同一个进程的其他线程也终止，程序可靠性弱。I/O密集型

7、进程/线程通讯

进程通讯

**答：**进程间通信主要包括无名管道、有名、消息队列、信号量、信号、共享内存等、以及套接字socket。

  • 管道是一种半双工的通信方式，数据只能单项流动，并且只能在具有亲缘关系的进程间流动，进程的亲缘关系通常是父子进程。
  • 命名管道也是半双工的通信方式，它允许无亲缘关系的进程间进行通信。
  • 信号量是一个计数器，用来控制多个进程对资源的访问，它通常作为一种锁机制。
  • 消息队列是消息的链表，存放在内核中并由消息队列标识符标识。
  • 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
  • 共享内存就是映射一段能被其它进程访问的内存，这段共享内存由一个进程创建，但是多个进程可以访问。
  • 套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

几种方式的比较
管道：速度慢，容量有限
消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题。
信号量：不能传递复杂消息，只能用来同步
共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了一块内存。

进程通讯 参考博客：https://blog.csdn.net/yufaw/article/details/7409596

线程同步(通讯是很简单的 毕竟共享)

**答：**临界区、事件、互斥量、信号量

  1. 临界区（CCriticalSection）

    当多个线程访问一个独占性共享资源时，可以使用临界区对象。通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问；

  2. 事件（CEvent）

    事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。方便的实现多线程优先级的比较操作

  3. 互斥量（CMutex）

    互斥对象和临界区对象非常相似，只是其允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，但是更节省资源，更有效率。

  4. 信号量（CSemphore）

    当需要一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。CSemaphore类对象保存了对当前访问某一个指定资源的线程的计数值，该计数值是当前还可以使用该资源的线程数目。

线程同步 参考博客 https://www.cnblogs.com/lebronjames/archive/2010/08/11/1797702.html

8、进程同步和互斥

互斥与同步
所谓互斥，指的是多个进程之间由于竞争临界资源而相互制约。

**什么是临界资源？**就是指一次仅允许一个进程使用的资源，即不能同时被共享的资源。

**进程的同步，**指多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。

进程同步的主要任务：是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

同步机制遵循的原则：
（1）空闲让进；
（2）忙则等待（保证对临界区的互斥访问）；
（3）有限等待（有限代表有限的时间，避免死等）；
（4）让权等待，（当进程不能进入自己的临界区时，应该释放处理机，以免陷入忙等状态）

9、用户级线程和内核线程

根据线程的控制方式不同，可将线程分为内核线程和用户级线程。

  • **内核级线程：**这类线程依赖于内核，又称为内核支持的线程或轻量级进程。无论是在用户程序中的线程还是系统进程中的线程，它们的创建、撤销和切换都由内核实现。为此，需要在内核中建立一个线程控制块，内核根据该控制块而感知该线程的存在并对线程进行控制。

  • **用户级线程：**它仅存在于用户级中，这种线程是不依赖于操作系统核心的。应用进程利用线程库来完成其创建、同步、调度和管理线程。因此用户线程间的切换不需要内核特权，不需要用户态/核心态切换，速度快，操作系统内核无法感知用户级线程的存在。

区别

  1. 内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。
  2. 用户级线程的创建、撤消和调度不需要OS内核的支持；而内核支持线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。
  3. 用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。
  4. 在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。
  5. 用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。

内核线程的优点：当有多个处理机时，一个进程的多个线程可以同时执行。

缺点：由内核进行调度，增加了内核负担。

用户线程的优点：

  1. 线程的调度不需要内核直接参与，控制简单。
  2. 可以在不支持线程的操作系统中实现。
  3. 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少得多。
  4. 允许每个进程定制自己的调度算法，线程管理比较灵活。这就是必须自己写管理程序，与内核线程的区别。
  5. 线程能够利用的表空间和堆栈空间比内核级线程多。
  6. 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起。另外，页面失效也会产生同样的问题。

缺点：资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用

10、处理机(CPU)调度机制

  • 先来先服务（FCFS，First-Come-First-Served）: 此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。

  • 短作业优先（SJF,Shortest Process Next）：这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。

  • 时间片轮转调度算法（RR，Round-Robin）：当某个进程执行的时间片用完时，调度程序便停止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。

  • 高响应比优先（HRRN，Highest Response Ratio Next）: 按照高响应比（（已等待时间＋要求运行时间）/ 要求运行时间）优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行。

  • 优先权(Priority)调度算法: 按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法。

  • 多级队列调度算法：多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。

  • 多级反馈队列调度算法
    这是当下公认的比较好的，使用最广泛的调度算法。其原理也不难。例如，某计算机采用多级反馈队列调度算法，设置了5个就绪队列。第一个就绪队列优先级最高，时间片为2ms。第二个就绪队列优先级第二，时间片为4ms，其余队列也一样，优先级依次递减，时间片依次增加。如果某个进程进入就绪队列，首先把它放在第一个就绪队列的末尾，轮到它执行就执行2ms，时间片结束，若该进程还没有执行完毕，就把该进程移入第二个就绪队列的末尾。只有当第一个队列的进程都执行完时间片，才会执行第二个队列。如此依次执行，若该进程服务时间很长，将被移到最后一个就绪队列。在最后一个就绪队列，进程将按照时间片轮转调度法执行。处理机执行过程中，只有当优先级高的队列中的线程都执行完毕，才会执行优先级低的队列。

11、死锁

死锁的概念：在两个或多个并发进程中，如果每个进程持有某种资源而又都等待别的进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗地讲，就是两个或多个进程被无限期地阻塞、相互等待的一种状态。

死锁产生的原因 主要是：1、 系统资源不足；2、进程推进顺序非法。

产生死锁的必要条件：

  • **互斥 **一个资源每次只能被一个进程使用；
  • 不可抢占 进程已获得的资源，在未使用完之前，不能强行剥夺；
  • **占有并等待 **一个进程因请求资源而阻塞时，对已获得的资源保持不放；
  • 环形等待 若干进程之间形成一种首尾相接的循环等待资源关系。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

解决死锁的基本方法主要有 预防死锁、避免死锁、检测死锁、解除死锁 、鸵鸟策略 等。

  • 采用某种策略来消除条件1-4中的一个条件的出现来**【防止死锁】**

  • 基于资源分配的当前状态做动态选择来避免死锁**【死锁避免】**

    死锁避免是属于事先预防策略，但并不会事先采取某种措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法限制条件比较弱，可以获得较好的系统性能。

    • 如果一个进程的请求会导致死锁，则不启动此进程。
    • 如果一个进程增加资源的请求会导致死锁，则不允许此分配。

    最著名的死锁避免算法银行家算法。

  • 试图去检测死锁的存在并试图从死锁中恢复出来**【死锁检测】**

    死锁预防和死锁避免嗾使以牺牲系统效率和浪费资源为代价的，这与操作系统的设计目标相违背。而死锁检测策略则完全相反，它不采取任何限制错误来保证系统不进入死锁状态，即允许死锁发生，但操作系统不断地监督进程的进程路径，判断死锁是否真的发生，一旦死锁发生，则采取专门的措施解除死锁，并以最小代价使得整个系统恢复正常。

    • 剥夺资源
    • 撤销进程

12、进程有哪几种状态？

  • 就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源；

  • 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数；

  • 阻塞状态： 进程等待某种条件，在条件满足之前无法执行；

  • 在引入的虚拟内存后 3、活动阻塞，静止阻塞，活动就绪，静止就绪

    1）活动阻塞：进程在内存，但是由于某种原因被阻塞了。

    2）静止阻塞：进程在外存，同时被某种原因阻塞了。

    3）活动就绪：进程在内存，处于就绪状态，只要给CPU和调度就可以直接运行。

    4）静止就绪：进程在外存，处于就绪状态，只要调度到内存，给CPU和调度就可以运行。

13、线程有哪几种状态？

**答：**创建(new)、就绪(runnable/start)、运行(running)、阻塞(blocked)、等待(waiting)、时间等待(time waiting) 和 消亡(dead/terminated)。在给定的时间点上，一个线程只能处于一种状态

14、内存管理

存储器管理的主要功能对存储空间进行分配和管理、存储器保护、地址转换、扩充主存容量(虚拟内存)。

存储器的地址转换：静态地址转换和动态地址转换（实现非连续存储，为虚拟存储器的实现打下了基础）。

存储器的分区存储管理：固定式分区存储管理（内部碎片）和动态分区存储管理（外部碎片）。

内存碎片分为：内部碎片和外部碎片

  • 内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；内部碎片是处于**（操作系统分配的用于装载某一进程的内存）区域内部或页面内部**的存储块。
  • 外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

分段式存储管理、分页式存储管理，两个的区别？

目的不同：

  • 分页是由于系统管理的需要而不是用户的需要，它是信息的物理单位；
  • 分段的目的是为了能更好地满足用户的需要，它是信息的逻辑单位，它含有一组其意义相对完整的信息；

大小不同：

  • 页的大小固定且由系统决定，而段的长度却不固定，由其所完成的功能决定；

  • 地址空间不同： 段向用户提供二维地址空间；页向用户提供的是一维地址空间；

信息共享：

  • 段是信息的逻辑单位，便于存储保护和信息的共享；

  • 页的保护和共享受到限制；

内存碎片：

  • 页式存储管理的优点是没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）；
  • 而段式管理的优点是没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）。

段页式内存管理的概念

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。

段页式管理就是将程序分为多个逻辑段，在每个段里面又进行分页，即将分段和分页组合起来使用。这样做的目的就是想同时获得分段和分页的好处，但又避免了单独分段或单独分页的缺陷。

如果我们将每个段看做一个单独的程序，则逻辑分段就相当于同时加载多个程序。

15、虚拟存储器

虚拟内存的好处：

  1. 扩大地址空间；

  2. 内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定的内存地址提供写保护，可以防止代码或数据被恶意篡改。

  3. 公平内存分配。采用了虚存之后，每个进程都相当于有同样大小的虚存空间。

  4. 当进程通信时，可采用虚存共享的方式实现。

  5. 当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存

  6. 虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把CPU交给另一个进程使用。在内存中可以保留多个进程，系统并发度提高

  7. 在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片

虚拟内存的代价：

  1. 虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存

  2. 虚拟地址到物理地址的转换，增加了指令的执行时间。

  3. 页面的换入换出需要磁盘I/O，这是很耗时的

  4. 如果一页中只有一部分数据，会浪费内存。

虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外在容量之后所决定，其运行速度接近于内存速度，每位的成本接近于外存。(目的)

虚拟存储器理论基础：时间局部性原理和空间局部性原理。

虚拟存储器的实现方法：其实现，都是建立在离散分配的存储管理方式的基础上。一般有分两种：请求分页系统、请求分段系统。

页面置换算法（策略/全局/局部置换）

  • 最佳置换算法（Optimal）：即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。（它是一种理想化的算法，性能最好，但在实际不能实现预知未来？）。
  • 先进先出置换算法（FIFO）：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
  • 最近最久未使用置换算法LRU（Least Recently Used）：该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。
  • Clock置换算法：也叫最近未用算法NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置“1”。在选择一页淘汰时，就检查其访问位，如果是“0”，就选择该页换出；若为“1”，则重新置为“0”，暂不换出该页，在循环队列中检查下一个页面，直到访问位为“0”的页面为止。由于该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，所以把该算法称为最近未用算法。
  • 最少使用置换算法LFU：该算法选择最近时期使用最少的页面作为淘汰页。

全局置换：

  • 工作集算法

    工作集替换算法是可实现的算法，只不过不是往前看，而是往后看。驻留集未规定用多少页框，而是动态增长的，当然在实际系统中肯定设置了上限，对于一个进程来说，不用考虑那么远，看当下如何替换即可。工作集窗口大小是一个时间概念，不是说动态集合分配的页框数。

    • 如果页面再时间间隔(t,t+τ)内(t,t+τ)内未被再次引用，那么就移出内存页面，否则该页被保留到进程的驻留集中，直到再次被引用。
    • 事先知道页面的引用串

  • 缺页率算法

    缺页率置换算法PFF,Page-Fault-Frequency,通过调整常驻集使得每个进程的缺页率保持在一个合理的范围：缺页率过高，则增加常驻集；缺页率过低，则减少常驻集。

理论：

  • 时间上的局部性：最近被访问的页在不久的将来还会被访问；

  • 空间上的局部性：内存中被访问的页周围的页也很可能被访问。

抖动

所谓抖动是指，在具有虚拟存储器的计算机系统中，由于频繁的页面置换活动，使得访问外存储器次数过多，从而引起的系统效率大大降低的一种现象。

解决策略包括：

  • 如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；
  • 如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；
  • 否则，还剩下两个办法：终止该进程或增加物理内存容量。

页面分配策略

分配策略：

  • 固定分区分配

    其基本思想是将内存划分成若干固定大小的分区，每个分区中最多只能装入一个作业。当作业申请内存时，系统按一定的算法为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，造成存储空间浪费。

  • 动态分区分配

    可变分区存储管理不是预先将内存划分分区，而是在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等。这种处理方式使内存分配有较大的灵活性，也提高了内存利用率。但是随着对内存不断地分配、释放操作会引起存储碎片的产生。

  • 伙伴系统

    伙伴系统从物理连续的大小固定的段上进行分配。从这个段上分配内存，采用 2 的幂分配器来满足请求分配单元的大小为 2 的幂（4KB、 8KB、16KB 等）。请求单元的大小如不适当，就圆整到下一个更大的 2 的幂。例如，如果请求大小为 11KB，则按 16KB 的段来请求。

可采取的实现方式： “固定分配，全局置换”说明置换的页(Page)来自于整个主存，不限于该进程本身。假设A进程置换掉了B进程的一页，此时B进程分配到的页数量就减少了1(被A进程使用了)。显然，不可能是“固定分配”。

1、固定分配局部置换
2、可变分配全局置换
3、可变分配局部置换

16、设备管理

磁盘存储器的管理

磁臂调度

  • 先来先服务算法
  • 最短查找时间优先算法 每次找最近的
  • Scan算法(电梯算法）来回扫描
  • C-Scan（Circular SCAN），扫描方向永远是一个方向。

磁盘高速缓存

利用内存中的存储空间来暂存从磁盘上读出的一系列盘块中的信息，这里的高速缓存是一组在逻辑上属于磁盘，物理上是驻留在内存中的盘块，高速缓存在内存中可以分成两种形式，第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受到应用程序的影响。第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时（作为磁盘高速缓存）共享。此时的高速缓存大小不再固定。

设备分配

在进行设备分配时所需要的数据结构有**设备控制表**、**控制器控制表**、**通道控制表**和**系统设备表**等。
**设备控制表（DCT）**，系统为每个设备都配置了一张设备控制表，用于记录本设备的情况。
**控制器控制表（COCT)**，系统为每个控制器都设置了一张用于记录本控制器情况的控制器控制表。
 **通道控制表（CHCT）**，每个通道都配有一张通道控制表。
**系统设备表（SDT）**，系统范围的数据结构，记录了系统中全部设备的情况，每个设备占用一个表目，其中包括有设备类型、设备标识符、设备控制表及设备驱动程序的入口等。

SPOOLing技术

  • 输入井和输出井，这是在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据，输出井是模拟脱机输出时的磁盘，用于暂存用户程序和输出数据。

  • 输入缓冲区和输出缓冲区，缓和CPU与磁盘之间速度不匹配，在内存中开辟的两个缓冲区，输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井，输出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备。

  • 输入进程SPi和输出进程SPo，利用两个进程来模拟脱机I/O时的外围控制机，其中，进程SPi模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当CPU需要输入数据时，直接从输入井读入内存；进程SPo模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。

作用 ：提高了I/O速度 、将独占设备改造为共享设备、 实现了虚拟设备功能

缓冲管理

在设备管理中，为了缓和CPU与I/O设备速度不匹配的矛盾，提高CPU与I/O设备的并行性，在I/O设备与处理机交换数据时都用到了缓冲区。

① 缓和CPU和I/O设备间速度不匹配的矛盾。

② 减少对CPU的中断频率，放宽对CPU中断响应时间的限制。

③ 提高CPU和I/O设备之间的并行性。

I/O 设备管理这里很杂 也很复杂 不再过多总结了

17、文件系统

物理结构

  • 连续分配—顺序文件

  • 链接分配 —链接文件

  • 索引分配 —索引文件

    索引文件是实现非连续存储的另一种方法，系统为加快记录的检索过程，为每个文件建立了一张索引表，每个逻辑块在索引表中占有一个表项，登记存放该逻辑块的盘块号。在FCB中放置了索引表指针，它指向索引表始址，索引表存放在盘块中。

  • UNIX/Linux直接间接混合寻址方式
    由于80％以上文件是小文件，为了解决能高速存取小文件和管理大文件的矛盾，UNIX将直接寻址、一级索引、二级索引和三级索引结合起来，形成了混合寻址方式。

文件别名（文件共享）

文件共享是指不同的用户使用不同的文件名来使用同一文件。在用一般共享目录结构时，一用户增加文件的内容，只改变自己的文件目录，其它用户不知改变。

文件的存取控制

存取控制表
存取控制矩阵由于太大而往往无法实现。一个改进的办法是按用户对文件的访问权力的差别对用户进行分类，由于某一文件往往只与少数几个用户有关，所以这种分类方法可使存取控制表大为简化。UNIX系统就是使用这种存取控制表方法。它把用户分成三类：文件主、同组用户和其它用户，每类用户的存取权限为可读、可写、可执行以及它们的组合。
用户权限表
改进存取控制矩阵的另一种方法是以用户或用户组为单位将用户可存取的文件各集中起来存入一表，这称为用户权限表，表中每个表目表示该用户对应文件的存取权限。

补充

CPU中的缓存和操作系统中的缓存分别是什么？

操作系统的缓存是指快表。在操作系统中，为提高系统的存取速度，在地址映射机制中增加一个小容量的联想寄存器，即快表，用来存放当前访问最频繁的少数活动页面的页号。当某用户需要存取数据时，根据数据所在的逻辑页号在快表中找到其对应的内存块号，再联系页内地址，形成物理地址。如果在快表中没有相应的逻辑页号，则地址映射仍可以通过内存中的页表进行，得到空闲块号后必须将该块号填入快表的空闲块中。如果快表中没有空闲块，则根据淘汰算法淘汰某一行，再填入新的页号和块号。快表查找内存块的物理地址消耗的时间大大降低了，使得系统效率得到了极大的提高。
CPU中的缓存是指高速缓存。CPU的执行速度越来越快，系统架构越来越先进，而主存的结构和存取速度改进则较慢，因此，高速缓存技术将越来越重要。 高速缓冲存储器是位于CPU和内存之间的临时存储器，它的容量比内存小但交换速度快。在高速缓冲存储器中的数据是内存中的一小部分，但这一小部分是短时间内CPU即将访问的。

操作系统中的程序的内存结构

可以看到一个可执行程序在存储（没有调入内存）时分为代码段、数据区和未初始化数据区三部分。

一个程序本质上都是由BSS段、data段、text段三个组成的：

  • BSS段（未初始化数据区）：通常用来存放程序中未初始化的全局变量和静态变量的一块内存区域。BSS段属于静态分配，程序结束后静态变量资源由系统自动释放。

  • 数据段：存放程序中已初始化的全局变量的一块内存区域。数据段也属于静态内存分配

  • 代码段：存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域属于只读。在代码段中，也有可能包含一些只读的常数变量。

text段和data段在编译时已经分配了空间，而BSS段并不占用可执行文件的大小，它是由链接器来获取内存的。

数据段包含经过初始化的全局变量以及它们的值。BSS段的大小从可执行文件中得到，然后链接器得到这个大小的内存块，紧跟在数据段的后面。当这个内存进入程序的地址空间后全部清零。包含数据段和BSS段的整个区段此时通常称为数据区。

堆区/栈区

可执行程序在运行时又多出两个区域：栈区和堆区。

  • 栈区：由编译器自动释放，存放函数的参数值、局部变量等。每当一个函数被调用时，该函数的返回类型和一些调用的信息被存放到栈中。然后这个被调用的函数再为他的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的，是一块连续的内存区域，最大容量是由系统预先定义好的，申请的栈空间超过这个界限时会提示溢出，用户能从栈中获取的空间较小。

  • 堆区：用于动态分配内存，位于BSS和栈中间的地址区域。由程序员申请分配和释放。堆是从低地址位向高地址位增长，采用链式存储结构。频繁的malloc/free造成内存空间的不连续，产生碎片。当申请堆空间时库函数是按照一定的算法搜索可用的足够大的空间。因此堆的效率比栈要低的多。

缺页中断和一般中断

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

  1. 保护CPU现场
  2. 分析中断原因
  3. 转入缺页中断处理程序进行处理
  4. 恢复CPU现场，继续执行

但是缺页中断是由于所要访问的页面不存在于内存时，由硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

  1. 在指令执行期间产生和处理缺页中断信号

  2. 一条指令在执行期间，可能产生多次缺页中断

  3. 缺页中断返回是，执行产生中断的一条指令，而一般的中断返回是，执行下一条指令。

写时复制

Linux采用了写时复制的方法，以减少fork时对父进程空间进程整体复制带来的开销。

写时复制是一种采取了惰性优化方法来避免复制时的系统开销。它的前提很简单：如果有多个进程要读取它们自己的那部门资源的副本，那么复制是不必要的。每个进程只要保存一个指向这个资源的指针就可以了。

主要好处在于：如果进程从来就不需要修改资源，则不需要进行复制。惰性算法的好处就在于它们尽量推迟代价高昂的操作，直到必要的时刻才会去执行。

fork和vfork的区别：

  1. fork( )的子进程拷贝父进程的数据段和代码段；vfork( )的子进程与父进程共享数据段

  2. fork( )的父子进程的执行次序不确定；vfork( )保证子进程先运行，在调用exec或exit之前与父进程数据是共享的，在它调用exec或exit之后父进程才可能被调度运行。

  3. vfork( )保证子进程先运行，在它调用exec或exit之后父进程才可能被调度运行。如果在调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁。

  4. fork()当需要改变共享数据段中变量的值，则拷贝父进程。

有了进程，为什么还要有线程？

线程产生的原因：
进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量；但是其具有一些缺点：进程在同一时间只能干一件事。

操作系统引入了比进程粒度更小的线程，作为并发执行的基本单位，从而减少程序在并发执行时所付出的时空开销，提高并发性。

Linux的4种锁机制：

  • 互斥锁：mutex，用于保证在任何时刻，都只能有一个线程访问该对象。当获取锁操作失败时，线程会进入睡眠，等待锁释放时被唤醒

  • 读写锁：rwlock，分为读锁和写锁。处于读操作时，可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它获取写锁失败的线程都会进入睡眠状态，直到写锁释放时被唤醒。 注意：写锁会阻塞其它读写锁。当有一个线程获得写锁在写时，读锁也不能被其它线程获取；写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）。适用于读取数据的频率远远大于写数据的频率的场合。

  • 自旋锁：spinlock，在任何时刻同样只能有一个线程访问对象。但是当获取锁操作失败时，不会进入睡眠，而是会在原地自旋，直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗，在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长，则会非常浪费CPU资源。

  • RCU：即read-copy-update，在修改数据时，首先需要读取数据，然后生成一个副本，对副本进行修改。修改完成后，再将老数据update成新的数据。使用RCU时，读者几乎不需要同步开销，既不需要获得锁，也不使用原子指令，不会导致锁竞争，因此就不用考虑死锁问题了。而对于写者的同步开销较大，它需要复制被修改的数据，还必须使用锁机制同步并行其它写者的修改操作。在有大量读操作，少量写操作的情况下效率非常高。

A* a = new A; a->val = 1;在内核中的内存分配上发生了什么？

  1. A *a：a是一个局部变量，类型为指针，故而操作系统在程序栈区开辟4/8字节的空间（0x000m），分配给指针a。
  2. new A：通过new动态的在堆区申请类A大小的空间（0x000n）。
  3. a = new A：将指针a的内存区域填入栈中类A申请到的地址的地址。即*（0x000m）=0x000n。
  4. a->val：先找到指针a的地址0x000m，通过a的值0x000n和i在类a中偏移offset，得到a->i的地址0x000n + offset，进行*(0x000n + offset) = 10的赋值操作，即内存0x000n + offset的值是10。

给你一个类，里面有static，virtual，之类的，来说一说这个类的内存分布?

virtual修饰符

如果一个类是局部变量则该类数据存储在栈区，如果一个类是通过new/malloc动态申请的，则该类数据存储在堆区。

如果该类是virutal继承而来的子类，则该类的虚函数表指针和该类其他成员一起存储。虚函数表指针指向只读数据段中的类虚函数表，虚函数表中存放着一个个函数指针，函数指针指向代码段中的具体函数。

如果类中成员是virtual属性，会隐藏父类对应的属性。

class B{
public:
    virtual void f(){
        cout << "BBB" << endl;
    };

};

class D:public B { // virtual 会出现 基类是虚拟的 不能指向
public:
    virtual void f(){
        cout << "DDD" << endl;
    };
};

int main() {
    D d;d.f();
    D *dd = (D*)new B;dd->f();
    return 0;
}
DDD/nBBB //virtual //只是修饰多态的一个声明 简单理解

虚函数

一个基类的指针或引用指向派生类的对象；

基类指针在调用成员函数(虚函数)时，就会去查找该对象的虚函数表。虚函数表的地址在每个对象的首地址。查找该虚函数表中该函数的指针进行调用。

每个对象中保存的只是一个虚函数表的指针，C++内部为每一个类维持一个虚函数表，该类的对象的都指向这同一个虚函数表。

虚函数表中为什么就能准确查找相应的函数指针呢？

因为在类设计的时候，虚函数表直接从基类也继承过来，如果覆盖了其中的某个虚函数，那么虚函数表的指针就会被替换，因此可以根据指针准确找到该调用哪个函数。

static修饰成员变量

对于非静态数据成员，每个类对象都有自己的拷贝。而静态数据成员被当做是类的成员，无论这个类被定义了多少个，静态数据成员都只有一份拷贝，为该类型的所有对象所共享(包括其派生类)。所以，静态数据成员的值对每个对象都是一样的，它的值可以更新。(必须全局更新)

static修饰成员函数

与普通的成员函数相比，静态成员函数由于不是与任何的对象相联系，因此它不具有this指针。从这个意义上来说，它无法访问属于类对象的非静态数据成员，也无法访问非静态成员函数，只能调用其他的静态成员函数。

Static修饰的成员函数，在代码区分配内存。

协程

协程，又称微线程，纤程，英文名Coroutine。协程看上去也是子程序，但执行过程中，在子程序内部可中断，然后转而执行别的子程序，在适当的时候再返回来接着执行。协程的特点在于是一个线程执行。

协程和线程区别

那和多线程比，协程最大的优势就是协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显。

第二大优势就是不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

··在协程上利用多核CPU呢——多进程+协程，既充分利用多核，又充分发挥协程的高效率，可获得极高的性能。··

源码到可执行文件的过程

  1. 预编译

    • 处理宏， 编译指令，删除注释，保留#pragma，添加行号和文件标识

  2. 编译

    • 词法分析，语法分析，语义分析，优化，目标代码生成，目标代码优化

  3. 汇编

    • 将汇编代码转变成机器可以执行的指令(机器码文件)

  4. 链接

    • 将不同的源文件产生的目标文件进行链接，从而形成一个可以执行的程序。链接分为静态链接和动态链接。

      • 函数和数据被编译进一个二进制文件。在使用静态库的情况下，在编译链接可执行文件时，链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。

        空间浪费：因为每个可执行程序中对所有需要的目标文件都要有一份副本，所以如果多个程序对同一个目标文件都有依赖，会出现同一个目标文件都在内存存在多个副本；

        更新困难：每当库函数的代码修改了，这个时候就需要重新进行编译链接形成可执行程序。

        运行速度快：但是静态链接的优点就是，在可执行程序中已经具备了所有执行程序所需要的任何东西，在执行的时候运行速度快。

      • 动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。

        共享库：就是即使需要每个程序都依赖同一个库，但是该库不会像静态链接那样在内存中存在多分，副本，而是这多个程序在执行时共享同一份副本；

        更新方便：更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍。当程序下一次运行时，新版本的目标文件会被自动加载到内存并且链接起来，程序就完成了升级的目标。

        性能损耗：因为把链接推迟到了程序运行时，所以每次执行程序都需要进行链接，所以性能会有一定损失。

5种IO模型

  1. 阻塞IO:调用者调用了某个函数，等待这个函数返回，期间什么也不做，不停的去检查这个函数有没有返回，必须等这个函数返回才能进行下一步动作
  2. 非阻塞IO:非阻塞等待，每隔一段时间就去检测IO事件是否就绪。没有就绪就可以做其他事。
  3. 信号驱动IO:信号驱动IO:linux用套接口进行信号驱动IO，安装一个信号处理函数，进程继续运行并不阻塞，当IO时间就绪，进程收到SIGIO信号。然后处理IO事件。
  4. IO复用/多路转接IO:linux用select/poll函数实现IO复用模型，这两个函数也会使进程阻塞，但是和阻塞IO所不同的是这两个函数可以同时阻塞多个IO操作。而且可以同时对多个读操作、写操作的IO函数进行检测。知道有数据可读或可写时，才真正调用IO操作函数
  5. 异步IO:linux中，可以调用aio_read函数告诉内核描述字缓冲区指针和缓冲区的大小、文件偏移及通知的方式，然后立即返回，当内核将数据拷贝到缓冲区后，再通知应用程序。

缓存 I/O

缓存 I/O 又被称作标准 I/O，大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中，操作系统会将 I/O 的数据缓存在文件系统的页缓存（ page cache ）中，也就是说，数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

缓存 I/O 的缺点：
数据在传输过程中需要在应用程序地址空间和内核进行多次数据拷贝操作，这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

文件描述符fd

文件描述符（File descriptor）是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。

文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于UNIX、Linux这样的操作系统。

I/O 多路复用/select、poll、epoll

  1. 进程最大连接数：select：单个进程所能打开的最大连接数由FD_SETSIZE限制，默认比较小。Poll：本质与select没有区别，但是它没有最大连接数的限制，原因是它基于链表存储。Epoll：没有fd数量限制。
  2. FD剧增后到来的I/O效率问题：select：每次调用会对连接进行线性遍历，所以随着FD的增加会导致遍历速度的线性下降的性能问题。Poll：同select。Epoll：由于epoll是根据每个fd上的callback函数来实现的，只有活跃的socket才会主动调用callback，所以在活跃socket较少的情况下，使用epoll不会有性能问题，但是当所有socket都很活跃的情况下，可能会有性能问题。
  3. 消息传递方式：select：内核需要将消息传递到用户空间，需要内核的拷贝动作。Poll：同select。Epoll：通过内核和用户空间共享一块内存来实现，性能较高。
  • epoll事先通过epoll_ctl()来注册一 个文件描述符，一旦基于某个文件描述符就绪时，内核会采用类似callback的回调机制，迅速激活这个文件描述符，当进程调用epoll_wait() 时便得到通知。
  • IO的效率不会随着监视fd的数量的增长而下降。epoll不同于select和poll轮询的方式，而是通过每个fd定义的回调函数来实现的。只有就绪的fd才会执行回调函数。