操作系统(OperationSystem,OS)是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。
操作系统控制硬件的功能，都是通过一些小的函数集合体的形式来提供的。这些函数以及调用函数的行为称为系统调用，也就是通过应用进而调用操作系统的意思。ru在程序中用到了time()以及printf()函数，这些函数内部也封装了系统调用。
C语言等高级编程语言并不依存于特定的操作系统，这是因为人们希望不管是Windows操作系统还是Linux操作系统都能够使用相同的源代码。因此，高级编程语言的机制就是，使用独自的函数名，然后在编译的时候将其转换为系统调用的方式（也有可能是多个系统调用的组合）。也就是说，高级语言编写的应用在编译后，就转换成了利用系统调用的本地代码（操作系统的底层命令，如C语言），再通过操作系统的底层命令去操作底层硬件。
理解：我们常说的解释器和编译器其实就是横架在操作系统和软件之间的沟通桥梁，软件代码通过解释器和编译器翻译为操作系统可以理解的底层代码语言，再进行运行。所以我们的python解释器就需要下载不同的操作系统版本才能进行使用。并且正因为Python是开源的，所以很多操作系统都会自行去适配python解释器。
我们说OpenGL、DirectX、Vulkan是一种规范，意味着它们并没有提供真正的实现，真正功能的实现，则是在显卡厂商提供给你的驱动程序中。用程序员的话来比喻则是：OpenGL、DirectX、Vulkan相当于一个定义了一些接口，而显卡厂商提供驱动程序是对这些接口的实现，因此不同的显卡，才需要不同的驱动程序。
大多数计算机系统将CPU执行状态分为目态与管态。管态就是supervisor（管理者）mode翻译来的。那么目态呢，其实是object（目标）mode翻译来的。
其中，系统调用可以认为是用户进程主动发起的，异常和外部设备中断则是被动的。
我们电脑上跑着的应用程序，其实是需要经过操作系统，才能做一些特殊操作，如磁盘文件读写、内存的读写等等。因为这些都是比较危险的操作，不可以由应用程序乱来，只能交给底层操作系统来。
因此，操作系统为每个进程都分配了内存空间，一部分是用户空间，一部分是内核空间。内核空间是操作系统内核访问的区域，是受保护的内存空间，而用户空间是用户应用程序访问的内存区域。以32位操作系统为例，它会为每一个进程都分配了4G(2的32次方)的内存空间。
CPU的上下文执行状态：
思考：为什么需要内核态？用户需要从用户态经过内核态才能对系统进行操作，这本质上其实是一种操作系统的权限控制。内核态会对你当前用户的权限进行检验，对一些危险操作进行禁止。
什么是上下文？CPU寄存器，是CPU内置的容量小、但速度极快的内存。而程序计数器，则是用来存储CPU正在执行的指令位置、或者即将执行的下一条指令位置。它们都是CPU在运行任何任务前，必须的依赖环境，因此叫做CPU上下文。
什么是CPU上下文切换？它是指，先把前一个任务的CPU上下文（也就是CPU寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。
一般我们说的上下文切换，就是指内核（操作系统的核心）在CPU上对进程或者线程进行切换。进程从用户态到内核态的转变，需要通过系统调用来完成。系统调用的过程，会发生CPU上下文的切换。
CPU寄存器里原来用户态的指令位置，需要先保存起来。接着，为了执行内核态代码，CPU寄存器需要更新为内核态指令的新位置。最后才是跳转到内核态运行内核任务。
理解：其实就是程序员使用编程语言，编程语言（用户态）使用操作系统内核（内核态），操作系统内核来操作计算机底层硬件。
现代操作系统使用虚拟内存，即虚拟地址取代物理地址，使用虚拟内存可以有2个好处：
可以发现，DMA做的事情很清晰啦，它主要就是帮忙CPU转发一下IO请求，以及拷贝数据。为什么需要它的？
主要就是效率，它帮忙CPU做事情，这时候，CPU就可以闲下来去做别的事情，提高了CPU的利用效率。大白话解释就是，CPU老哥太忙太累啦，所以他找了个小弟（名叫DMA），替他完成一部分的拷贝工作，这样CPU老哥就能着手去做其他事情。
做服务端开发的小伙伴，文件下载功能应该实现过不少了吧。如果你实现的是一个web程序，前端请求过来，服务端的任务就是：将服务端主机磁盘中的文件从已连接的socket发出去。关键实现代码如下：
while((n=read(diskfd,buf,BUF_SIZE))>0)write(sockfd,buf,n);传统的IO流程，包括read和write的过程。
从流程图可以看出，传统IO的读写流程，包括了4次上下文切换（4次用户态和内核态的切换），4次数据拷贝（两次CPU拷贝以及两次的DMA拷贝）。
对于操作系统来说，一个任务就是一个进程（Process），比如打开一个浏览器就是启动一个浏览器进程，打开一个记事本就启动了一个记事本进程，打开两个记事本就启动了两个记事本进程，打开一个Word就启动了一个Word进程。有些进程还不止同时干一件事，比如Word，它可以同时进行打字、拼写检查、打印等事情。在一个进程内部，要同时干多件事，就需要同时运行多个“子任务”，我们把进程内的这些“子任务”称为线程（Thread）。
类比：进程=工厂线程=工厂里各个流水线
注意：一个进程可能对应多个端口号，一个端口对应一个进程。
进程可以认为是程序执行时的一个实例。进程是系统进行资源分配的独立实体，且每个进程拥有独立的地址空间。（即资源的分配和调度的一个独立单元）进程控制块(ProcessControlBlock,PCB)：保存运行期间进程的数据，PCB是进程存在的唯一标志。
注意：****后备队列在外存中，而就绪队列在内存中。
互斥与同步：
在操作系统中，信号量S是一整数。当S≥0时，S表示可供并发进程使用的资源实体数；当S<0时，S表示正在等待使用资源实体的进程数。建立一个信号量必须说明此信号量所代表的意义并且赋初值。除赋初值外，信号量仅能通过PV操作来访问。
注意：PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。
代码化如下：P操作：
P(S){ S--; if(S<0){ 保留调用进程CPU现场； 将该进程的PCB插入S的等待队列； 置该进程为“等待”状态； 转入进程调度； }}V操作：
V(S){ S++; if(S<=0){ 移出S等待队列首元素； 将该进程的PCB插入就绪队列； 置该进程为“就绪”状态； }}进程通信根据交换信息量的多少和效率的高低，进程通信分为如下低级通信和高级通信。
若通信进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的信息传递方法实现进程通信。
可分为直接和间接两种通信方式：
全双工
类比：进程=物品共享空间=钱用钱进行交换，而不用物物交换
半双工
为了协调双方的通信，管道机制必须提供互斥、同步和确定对方存在三方面的协调能力。
个人理解：一个共享的是内存，一个共享的是外存磁盘上的文件，这就是差别，共享内存会更快。
共享内存和消息队列，FIFO，管道传递消息的区别：
消息队列，FIFO，管道的消息传递方式一般为：
上述过程通常要经过4次拷贝，才能完成文件的传递。
共享内存只需要：
对线程最基本的理解就是“轻量级进程”，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。（即CPU调度的基本单元）线程控制块(ThreadControlBlock,TCB)：保存运行期间线程的数据，TCB是线程存在的唯一标志。
死锁是指多个进程因竞争临界资源而造成的一种僵局（互相等待），若无外力作用，这些进程都无法向前推进。
互斥：你有我没有，我有你没有
占有：这个资源我马上要用的，拿着等一会
不剥夺：你不能强行抢我的
环路：你不给我，我不给你
注意：这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立；反之，只要上述条件之一不满足，就不会发生死锁。
预防死锁：通过设置一些限制条件，破坏死锁的一些必要条件，让死锁无法发生。
下面我们来举个例子吧！大家都知道，在并发情况下对两个账户进行转账操作可能会产生死锁，可能出现死锁的原因是,并发情况下对两个账户的操作无法保证其执行顺序。
1.并发问题描述假如现在执行下面的操作：
线程一执行的是：【账户A】给【账户B】转账
线程二执行的是：【账户B】给【账户A】转账
如果两个转账动作同时执行,则会出现线程一会请求对【账户B】进行加锁,线程二会请求对【账户A】进行加锁
由于此时的【账户A】已由线程一进行锁定,【账户B】已由线程二进行锁定此时就会产生死锁问题。接下来分析一下产生死锁的原因，以及如何避免死锁。
2.如何避免死锁有个叫Coffman的牛人总结过一条经验，只有当以下四个条件同时发生，才会出现死锁，所以只要打破其中一个条件，就可以避免死锁：
互斥，共享资源X和Y只能被一个线程占用占有且等待，线程A获取到资源X，在等待资源Y的时候，不释放资源X不可抢占，其他线程不能强行抢占线程A占有的资源循环等待，线程A等待线程B占有的资源，线程B等待线程A的资源首先，互斥这个条件是没法破坏的，因为锁存在的目的就是互斥，对于剩下的三个条件都可破坏。
你想要画画，笔和纸不分批次给你，而是同时给你笔和纸。
对于不可抢占，可以获取了部分资源，再进一步获取其他资源时如果获取不到时，把已经获取的资源一起释放掉。破坏不可抢占条件，需要线程在获取不到锁的情况下主动释放它拥有的资源。当我们使用synchronized的时候，线程是没有办法主动释放它占有的资源的。因为，synchronized在申请不到资源时，会使线程直接进入阻塞状态，而线程进入了阻塞状态就不能主动释放占有的资源。java.util.concurrent中的Lock接口，提供了如下三种设计思想都可以解决死锁的不可抢占条件：
对应方法
//支持中断的APIvoidlockInterruptibly()throwsInterruptedException;//支持超时的APIbooleantryLock(longtime,TimeUnitunit)throwsInterruptedException;//支持非阻塞获取锁的APIbooleantryLock();使用非阻塞的获取锁实现：
packagecom.zhouj.endless.diy;/***@authorNemo*@date2020-02-1917:07*@description可抢占*/publicclassPreemptible{publicbooleantransferMoney(AccountfromAcct,AccounttoAcct){while(true){//使用tryLock()获取锁if(fromAcct.lock.tryLock()){try{//使用tryLock()获取锁if(toAcct.lock.tryLock()){returntrue;}}finally{//释放前面获取到的锁fromAcct.lock.unlock();}}}}}破坏循环等待条件按主键id进行排序，从小到大获取锁。
对于循环等待，可以将需要获取的锁资源排序，按照顺序获取，这样就不会多个线程交叉获取相同的资源导致死锁，而是在获取相同的资源时就等待，直到它释放。比如根据账号的主键id进行排序，从小到大的获取锁，这样就可以避免循环等待。
packagecom.zhouj.endless.diy;/***@authorNemo*@date2020-02-1916:31*@description账户排序*/publicclassAccount{privateIntegerid;privateintbalance;/***转账**@paramtarget目标*@paramamt金额*/voidtransfer(Accounttarget,intamt){Accountleft=this;Accountright=target;if(this.id>target.id){left=target;right=this;}//锁定序号小的账户synchronized(left){//锁定序号大的账户synchronized(right){if(this.balance>amt){this.balance-=amt;target.balance+=amt;}}}}}避免死锁避免死锁：在动态分配资源的过程中，用一些算法（如银行家算法）防止系统进入不安全状态，避免死锁的发生。
DijkstraEW于1968年提出银行家算法。之所以称为银行家算法，是因为该算法可用于银行系统。
新进程进入系统时，它必须说明各类资源类型的实例的最大需求量，这一数量不能超过系统各类资源的总数。当进程申请一组资源时，该算法需要检查申请者对各类资源的最大需求量：
死锁的检测及解除：在死锁发生前不做任何操作，只是检测当前是否发生死锁，若发生死锁，则采取一些措施（如资源剥夺法、撤销进程法、进程回退法）来解除死锁。
处理机调度
调度算法是根据系统的资源分配策略所规定的资源分配算法。有的调度算法适用于作业调度，有的适用于进程调度，有的两种都适用。
优先级调度：该算法每次从后备队列/就绪队列中选择优先级最高的一个作业/进程，将资源分配给它。
根据新的更高优先级进程能否抢占正在执行的进程，可将该调度分为：
从上面的例子看，在多级反馈队列中，后进的作业不一定慢完成。
主存和内存是主存储器的两种不同叫法，其实就是一个东西。计算机中，主存储器又称内存储器，其作用是存放指令和数据，并能由中央处理器（CPU）直接随机存取。
主存管理的功能：
地址映射：为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。
地址映射分类：地址映射也可以称为地址重定位或地址变换，可以分为以下三类：
实存管理：
页面可以不连续是其重要优点，不会产生外碎片，更有效地利用了内存，不过会产生一些内碎片，即分配给进程的最后一个页往往不能正好用完，不过在页面大小不是很大的时候可以接受。
施加保护是分段式的优点，但其仍是像分区式管理一样的连续分配。
注意：以上四种全是实存管理，即进程要么全部载入内存中，要么就不能载入。
虚存管理：
三种分配方式：固定分配局部置换、可变分配全局置换、可变分配局部置换。固定分配、全局置换不能组合。
计算机系统在处理应用程序时，只装入部分程序代码和数据就启动起运行，由操作系统和硬件相配合完成主存和辅存之间的信息的动态调幅，这样的计算机系统好像为用户提供可以一个其存储容量比实际主存大得多的存储器，这个存储器称为虚拟存储器。
现代操作系统为支持多用户、多任务的同时执行，需要大量的主存空间。特别是现在需要计算机解决的问题越来越多，越来越复杂，有些科学计算或需要大量数据数据处理的问题需要相当大的主存容量，使系统中主存容量先得更为紧张，因此系统提供虚拟存储器来方便用户的使用和有效地支持多用户对主存的共享。
将程序地址空间中的逻辑地址变成主存中的物理地址的过程。
地址映射也可以称为地址重定位或地址变换，可以分为以下三类：
主存管理存储器的策略只要有3种：
现代操作系统中存储器由多个程序共享。为了保证多个程序之间互不影响，必须由硬件（软件配合）保证每个程序只能在给定的存储区域内活动，即存储保护。
在分区存储管理中，程序的地址空间是一维线性的，因为是连续分配的，指令或操作数地址只要给出一个信息量即可决定。（连续分配）
分区式管理：最简单直观的方式，在内存中连续分配一个区，将整个进程放入这个区。（数组）
与固定分区的区别就是：动态的划分分区。克服固定分区管理的“内碎片”问题。
分区存储管理中常用的分配策略有：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法。
首次适应算法：按地址从小到大排序，分配第一个符合条件的分区，即第一个足够装入它的可利用的空闲区。
循环首次适应算法：在首次适应算法的基础上，从上次查找结束的位置开始查找，分配第一个足够装入它的可利用的空闲区。
最佳适应算法：是按空间从小到大排序，分配第一个符合条件的分区，即与它所需大小最接近的空闲区。
最坏适应算法：是按空间从大到小排序，分配第一个符合条件的分区，即最不适合它的空闲区，即最大的空闲区。
在页式存储管理中，程序的地址空间是一维线性的，因为指令或操作数地址只要给出一个信息量即可决定。（离散分配）
理解：页式存储管理只用给出一个逻辑地址就行，因为页的大小是固定的，不需要刻意划分，当然不是逻辑地址÷页的大小=页号...余偏移量，因为页式存储是离散分配的。根据下文的地址变换过程可知，我们只需要提供逻辑地址这一个地址，就可以找到这个页式存储物理地址，所以是地址空间一维的，只用一个逻辑地址。
页之间一页紧跟着一页，没有外碎片；但是页内有可能分配不满，有内碎片。
分页式管理：将内存分成固定大小的页，离散分配若干页将整个进程载入。于是一个连续的程序空间在主存中可能是不连续的。为了保证程序能正确地执行，必须在执行每条指令时将程序中的逻辑地址变换为实际的物理地址，即进行动态重定位。在页式系统中，实现这种地址变换的机构称为页面映射表，简称页表。
其实如何利用页表来进行地址变换，这与计算机所采用的地址结构有关，而地址结构又与选择的页面尺寸有关。
相对物理块来说，页是逻辑地址空间（虚拟内存空间）的划分，是逻辑地址空间顺序等分而成的一段逻辑空间，并依次连续编号。页的大小一般为512B~8KB。
例如：一个32位的操作系统，页的大小设为\(2^{12}=4KB\)，那么就有页号从0编到\(2^{20}\)的那么多页逻辑空间。
物理块则是相对于虚拟内存对物理内存按顺序等大小的划分。物理块的大小需要与页的大小一致。
例如：\(2^{31}=2GB\)的物理内存，按照4KB/页的大小划分，可以划分成物理块号从0到\(2^{19}\)的那么多块的物理内存空间。
一级页表的缺陷：由于页表必须连续存放，并且需要常驻物理内存，当逻辑地址空间很大时，导致页表占用内存空间很大。例如，地址长度32位，可以得到最大空间为4GB，页大小4KB，最多包含4G/4K=1M个页。若每个页表项占用4个字节，则页表最大长度为4MB，即要求内存划分出连续4MB的空间来装载页表；若地址程度为64位时，就需要恐怖的\(4\*2^{52}Byte\)空间来存储页表了。而且页表采用的是连续分配，不是分页分配。采用离散分配方式的管理页表，将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
现代的大多数计算机系统，都支持非常大的逻辑地址空间(\(2^{32}～2^{64}\))。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用四个字节，故每个进程仅仅其页表就要占用4MB的内存空间，而且还要求是连续的。显然这是不现实的，我们可以采用下述两个方法来解决这一问题：
页表，页表项，页面，页面大小，物理块这里是真的有点混乱的说法，在操作系统中，我们知道一级页表不会有这么多称呼，但是多级页表就有了。我们知道一级页表中，就只有页号和位移量了（也就是所说的物理块块号），这里不会出现页表项，但是二级页表乃至多级页表时就会出现页表项了，页表项我们知道是有一个“项”的字的尾缀，那么很明显，这里是类似于一个整体的意思，也就是二级页表中外层页表每一项表示第二层的一页，也就是页表项了，直截了当的说就是页表项就是一个二级页（次级页）。
通俗的说页表项就是页表中的每一项，外层页表每一项指向的是次级页表的表头地址（代指次级页表一张），次级页表依次这样，如果是二级的话，次级页表项指的就是（页号对应一个页面，一个页面对应一个物理块）物理块了。
对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表(OuterPageTable)，在每个页表项中记录了页表页面的物理块号。下面我们仍以前面的32位逻辑地址空间为例来说明。当页面大小为4KB时(12位)，若采用一级页表结构，应具有20位的页号，即页表项应有1兆个；在采用两级页表结构时，再对页表进行分页，使每页中包含\(2^{10}\)(即1024)个页表项，最多允许有\(2^{10}\)个页表分页；或者说，外层页表中的外层页内地址P2为10位，外层页号P1也为10位。此时的逻辑地址结构可描述如下：
1.某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为\(2^{10}B\)，页表项大小为2B，逻辑地址结构为：
逻辑地址空间大小为\(2^{16}\)页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）。A，64B，128C，256D，512
答案：
一级页表需要使用128个页表项来表达128个二级页表的页面，每个二级页表的页面保存着\(2^{9}\)个页表项
也就是说，我们最终需要求解的是一级页表（页目录）下，应该有多少个二级页表
答案二：逻辑地址=页目录号+页号+页内偏移量
对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，采用两级页表是否仍可适用的问题，须做以下简单分析。如果页面大小仍采用4KB，即\(2^{12}B\)，那么还剩下52位，假定仍按物理块的大小(\(2^{12}位\))来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。
对于64位的计算机，如果要求它能支持\(2^{64}B(=1844744TB)\)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。故在近两年推出的64位OS中，把可直接寻址的存储器空间减少为45位长度(即\(2^{45}\))左右，这样便可利用三级页表结构来实现分页存储管理。
多级页表和二级页表是为了节省物理内存空间。使得页表可以在内存中离散存储。（单级页表为了随机访问必须连续存储，如果虚拟内存空间很大，就需要很多页表项，就需要很大的连续内存空间，但是多级页表不需要。）
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
抖动（颠簸）：是指在页面置换过程中，刚刚调出的页面马上又要调入内存，刚刚调入的页面马上又要调出，发生频繁的页面调度行为。
先进先出置换算法(FirstInFirstOut,FIFO)：将最早进入内存的页面调出。
该算法会产生Belady异常，即发生缺页时，如果对一个进程未分配它所要求的全部页面，有时分配页数↑，缺页率反而↑的异常现象。（先进先出，结果进来了一个需要的页，也出去了一个需要的页）
LRU缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
当然只有这个限制是不够的，我们前面也说了，由于内存是非常金贵的，导致我们可以存储在缓存当中的数据是有限的。比如说我们固定只能存储1w条，当内存满了之后，缓存每插入一条新数据，都要抛弃一条最长没有使用的旧数据。这样我们就保证了缓存当中的数据的价值都比较高，并且内存不会超过限制。
我们把上面的内容整理一下，可以得到几点要求：
如果是在面试当中被问到想到这里的时候，可能很多人都已经束手无策了。但是先别着急，我们冷静下来想想会发现问题其实并没有那么模糊。
对于缓存来说其实只有两种功能，第一种功能就是查找，第二种是更新。
查找会分为两种情况，第一种是没查到，这种没什么好说的，直接返回空即可。如果能查到节点，在我们返回结果的同时，我们需要将查到的节点在链表当中移动位置。我们假设越靠近链表头部表示数据越旧，越靠近链表尾部数据越新，那么当我们查找结束之后，我们需要把节点移动到链表的尾部。
更新也同样分为两种情况，第一种情况就是更新的key已经在HashMap当中了，那么我们只需要更新它对应的Value，并且将它移动到链表尾部。对应的操作和上面的查找是一样的，只不过多了一个更新HashMap的步骤，这没什么好说的，大家应该都能想明白。
第二种情况就是要更新的值在链表当中不存在，这也会有两种情况，第一个情况是缓存当中的数量还没有达到限制，那么我们直接添加在链表结尾即可。第二种情况是链表现在已经满了，我们需要移除掉一个元素才可以放入新的数据。这个时候我们需要删除链表的第一个元素，不仅仅是链表当中删除就可以了，还需要在HashMap当中也删除对应的值，否则还是会占据一份内存。
最不经常使用置换算法(LeastFrequentlyUsedLFU)：将最近应用次数最少的页淘汰。
实现方法一般为双哈希表+双向链表。
\(freq\_table=<频率,双向链表>\)
\(key\_table=<键,链表指针（即内存地址）>\)
我们定义两个哈希表，
\(freq_table=<频率,双向链表>\)
\(key_table=<键,链表指针（即内存地址）>\)
时钟置换算法(CLOCK)：也称为最近未用算法(NotRecentlyUsed,NRU)，该算法是为每个页面设置一个使用位，需要替换页面时，循环检查各个页面，将使用位为1的页面重置为0（使用时再置为1），直到遇到第一个使用位为0的页面，将其调出。如果在每个页面再增加一个修改位，则得到改进型的CLOCK置换算法，类似的，需要替换页面时，将使用位和修改位都为0的页面调出。
段式存储管理的用户地址是二维的、按段划分的。（离散分配）
理解：段式存储管理必须给出（段号，偏移量），因为段的大小不固定，必须给出这个地址结构（逻辑地址)，由此找到段表中程序员设置的基址，由地址结构（逻辑地址）和基址这两个地址我们可以得到段式存储物理地址，所以是二维的，需要用到两个地址。
段内紧密连接为一个整体，没有内碎片；段之间不一定紧密连接，存在外碎片。
分段式管理：将程序分为若干个段，如数据段和代码段，加以不同的保护。
施加保护是分段式的优点，虽然不同段可以离散分配，但其段内仍是连续分配。
在这样的系统中作业的地址空间由若干逻辑分段组成，每个分段有自己的名字，对于一个分段而言，它是一个连续的地址区。
相同点：
不同点：
理解：分页存储管理里面的地址结构是：页号+位移量，这个地址结构就是一个地址；根据页号在页表项中找到对应页项，这个页项代表了一个块号，但是这个块号并不是一个地址，因为所有块是事先已经划分好且长度相等的，这些块是操作系统自己知道的，所以操作系统就可以仅根据地址结构直接访问，即分页存储管理的地址空间是一维的。分段存储管理里面的地址结构是：段号+段内地址（位移量），这个地址结构就是一个地址；根据段号在段表项中找到对应段项，这个段项和页项的组成成分不一样，其中还包含了一个基址，就是段在内存中的起始地址，这个地址不是操作系统划分，而是程序员事先设置的，操作系统并不知道，所以操作系统要访问内存就必须要结合地址结构和段表中的基址，所以分段的地址空间是二维的。
总结：分页是地址结构+块号，地址结构是地址，块号只是一个数字而已，所以是一维；（因为长度固定，所以只需要块号数字就行）分段是地址结构+基址，两者都是地址，所以是二维的。（因为长度不固定，所以需要基址才能找到）
段页式存储管理的用户地址也是二维的、按段划分的。只是在段中再划分成若干大小相等的页。
理解：段页式存储管理也必须给出（段号，偏移量），虽然段的大小不固定，但是段内页号和页内偏移可以根据偏移量算出来，所以还是二维的。
虚拟存储器：是指具有请求调入功能和置换功能，并能从逻辑上对内存容量加以扩充的一种存储器系统。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。
虚拟存储器基于局部性原理，在程序装入时，可以只将程序的一部分装入内存，就可以启动程序执行。在执行过程中，当所访问的信息不在内存中时，由操作系统将所需内容调入内存，使程序继续执行；
解释：****因为局部性原理，所以下一步需要访问的信息很有可能就在附近。
同时，操作系统将内存中暂时不用的内容调出到外存。
这样，系统就好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。
外存，指的是除了cpu缓存和内存以外的存储器，硬盘、光盘、U盘都可以被称为外存。所有的数据，也都存在这里面，故他的分配方式变得极其重要，这直接影响到了计算机的运行速度。
外存分配方式主要有这几种：连续分配，链式分配，索引分配。
文件分配对应于文件的物理结构，是指如何为文件分配磁盘块（外存）。
常用的磁盘空间分配方法有三种：
类比：像链表那样一个一个地顺序查找。-隐式链接分配：每个文件对应一个磁盘块的链表，磁盘块任意分布，除最后一个盘块外，每一个盘块都有指向下一个盘块的指针（类似于数据结构中的链表）。-显式链接分配：把用于链接文件各物理块的指针提取出来，显式地存放在内存里的一张链接表中，该表整个磁盘仅设置一张，由于分配给文件的所有盘块号都放在该表中，故称该表为文件分配表(FAT)。这本质上仍然是链接分配，即进程给出文件物理块起始地址等信息，然后根据内存FAT中地址的链接情况进行查找，得到所需物理块。在查找过程中仍然是一个一个地顺序查找。
索引分配与显式链接分配不同，索引分配是随机查找，不需要借助前一个物理块来找到后一个，直接就可以查找到，直达。
原理：创建文件时，分配一组连续的块；FAT（文档分配表）中每个文件只要一项，说明起始块和文件长度。对于顺序文件有利。
优点：
缺点：
原理：一个文件的信息存放在若干个不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。fat中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个物理块都可以加入到链中。
使用FAT文件分配表法，链接分配的变种，如MS-DOS和OS/2.
原理：每个文件在FAT中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在单独的一个块中，FAT中该文件的入口指向这一块。
先来先服务算法(FirstComeFirstService,FCFS)：根据进程请求访问磁盘的先后顺序进行调度。
该算法会产生“饥饿”现象。
扫描算法(SCAN)：也叫电梯算法，在磁头当前移动方向上选择与当前磁头所在距离最近的请求作为下一次服务的对象。
实际上是在SSTF算法的基础上规定了磁头运动的方向。
循环扫描算法(CyclicSCAN,C-SCAN)：在SCAN算法的基础上规定磁头单向移动来提供服务，到达磁盘端点返回时，直接快速返回起始端。
若磁头移动到最远端的请求后，即刻返回，而不是到达端点再返回，则将改进后的SCAN算法和C-SCAN算法称为LOOK算法和C-LOOK算法。