操作系统

ccb2021-08-152023-10-06

操作系统

进程管理

进程

进程是资源分配的基本单位（比如内存、打开的文件等），同一程序可产生多个进程（一对多关系），以允许同时有多位用户运行同一程序，却不会相互冲突。进程需要一些资源才能完成工作，如CPU使用时间、存储器、文件以及IO设备，且为依序逐一进行，也就是任何时间内仅能运行一项进程。

通常进程有如下5种状态，其中前3种是进程的基本状态。

运行状态(执行窗台)：进程正在处理器上运行。在单处理器环境下，每一时刻最多只有一个进程处于运行状态。
就绪状态：进程已处于准备运行的状态，即进程获得了除处理器之外的一切所需资源，一旦得到处理器即可运行。
阻塞状态：又称为等待状态，进程正在等待某一事件而暂停运行，如等待某资源为可用(不包括处理器)或等待输入输出完成。即使处理器空闲，该进程也不能运行。
创建状态：进程正在被创建，尚未转到就绪状态。
结束状态：进程正从系统中消失。可能是进程正常结束或其他原因中断退出运行。

进程的三个基本状态之间是可以相互转换的，如图1-1所示。

具体地说，当一个就绪进程获得处理机时，其状态由就绪变为执行；

当一个运行进程被剥夺处理机时，比如用完系统分给它的时间片、出现更高优先级别的其他进程，其状态由运行变为就绪；

当一个运行进程因某事件受阻时，如所申请资源被占用、启动IO传输未完成，其状态由执行变为阻塞；

当所等待事件发生时，如得到申请资源、IO传输完成，其状态由阻塞变为就绪。

==进程与程序的区别：==

进程是动态的概念，而程序是静态的概念

进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序、离开程序的进程没有存在的意义。从静态角度看，**进程是由程序、数据和进程控制块(PCB) 三部分组成的。而程序是一组有序的指令集合，是一种静态的概念**。
生存周期不同

进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命期，是暂时存在的；而程序则是一组代码的集合，它是永久存在的，可长期保存。
一个进程可以执行一个或几个程序，一个程序也可以构成多个进程。进程可创建进程，而程序不可能形成新的程序。
进程与程序的组成不同。

进程的组成包括程序、数据和进程控制块。

创建新进程时会创建新的地址空间：子进程是父进程的复制品，在fork 之后子进程获得父进程的数据空间、堆和栈的复制品，而线程使用当前的地址空间。

线程

或者叫做轻量级进程（Lightweight Process, LWP）, 是程序执行流的最小单元。

一个标准的线程由线程ID，当前指令指针(PC)，寄存器集合和堆栈(stack) 组成。另外，线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自已不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的资源（共享进程的内存地址空间），但拥有属于自己的栈空间以及独立的执行顺序。

一、线程共享的进程环境包括：

进程代码段、进程的公有数据（如全局变量，利用这些共享的数据，线程很容易的实现相互之间的通信）、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

二、线程自己的个性：

拥有这许多共性的同时，还拥有自己的个性。有了这些个性，线程才能实现并发性。这些个性包括:

线程ID

每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标识线程。
寄存器组的值

由于线程间是并发运行的，每个线程有自已不同的运行线索，当从一个线程切换到另一个线程上时，必须将原有线程的寄存器集合的状态进行保存，以便将来该线程在被重新切换时能得以恢复。
线程的堆栈(stack)

堆栈是保证线程独立运行所必须的。线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程必须拥有自己的函数堆栈，使得函数调用可以正常执行，不受其他线程的影响。在一个进程的线程共享堆区(heap)。
错误返回码
线程的信号屏蔽码
线程的优先级

一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。

由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。每一个程序都至少有一个线程，若程序只有一个线程，那就是程序本身。线程是程序中一个单一的顺序控制流程。在单个程序中同时运行多个线程完成不同的工作，称为
多线程。

引入线程后，进程的内涵发生了改变，进程只作为除CPU以外系统资源的分配单元，线程则作为处理器的分配单元。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。

==线程与进程的区别?==

调度：

引入线程后，线程是独立调度的基本单位，进程是资源分配的基本单位。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行的线程切换，则会引起进程切换。

拥有资源：

进程是拥有资源的基本单位，线程不拥有资源(也有一点必不可少的资源)，但线程可以共享其隶属进程的系统资源。

并发性：进程可以并发，同一进程内的多个线程也可以并发

在引入线程的操作系统中，不仅进程可以并发执行，而且同一进程内的多个线程也可以并发执行，从而使操作系统具有更好的并发性，大大提高了系统吞吐量。

系统开销：线程切换以及同步、通信的系统开销比进程小

创建和撤销进程时，系统都要为之分配或回收资源，如内存空间、IO设备等，因此操作系统所付出的开销远大于创建或撤销线程的开销。类似地，在进程切换时，涉及当前执行进程CPU环境的保存以及新调度的进程CPU环境的设置；而线程切换时只需保存和设置少量寄存器内容，因此开销很小。

另外，由于同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信比较容易实现，甚至无须操作系统的干预。

地址空间和其他资源（如打开的文件）：

进程的地址空间之间互相独立，同一进程的各线程间共享进程的资源，某进程内的线程对于其他进程不可见。

通信方面：

进程间通信需要借助操作系统，而线程间可以直接读/写进程数据段(如全局变量)来进行通信。

进程通信与进程同步

多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。

对临界资源的访问，必须互斥的进行，**在每个进程中，访问临界资源的那段代码称为临界区(Critical Section)**。

进程通信与同步有如下一些目的：

1)数据传输：一个进程需要将它的数据发送给另一个进程;

2)共享数据：多个进程想要操作共享数据，一个进程对共享数据的修改，别的进程应该立刻看到；

3)通知事件：一个进程需要向另一个或一组进程发送消息，通知它(它们)发生了某种事件(如进程终止时要通知父进程);

4)资源共享：多个进程之间共享同样的资源。为了做到这一点，需要内核提供锁和同步机制；

5)进程控制：有些进程希望完全控制另一个进程的执行(如Debug进程)，此时控制进程希望能够拦截另一个进程的所有陷入和异常，并能够及时知道它的状态改变。

==Linux下进程间通信的几种主要手段简介：==

管道(Pipe) 及有名管道(named pipe)

管道可用于具有亲缘关系进程间的通信，有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，有名管道还允许无亲缘关系进程间的通信;

信号(Signal)

信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；Linux 除了支持UNIX早期信号语义函数sigal外，还支持语义符合Posix.1标准的信号函数sigaction；

Message (消息队列)

消息队列是消息的链表，包括Posix消息队列System V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

共享内存

使得多个进程可以访问同一块内存空间，是最快的可用IPC（进程间通信）形式。是针对其他通信机制运行效率较低而设计的。往往与其他通信机制，如信号量结合使用，来达到进程间的同步及互斥。

信号量(semaphore)

主要作为进程间以及同一进程不同线程之间的同步手段。

套接口(Socket)

更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由UNIX系统的BSD分支开发出来的，但现在一般可以移植到其他类UNIX系统上：Linux 和System V的变种都支持套接字。

**Linux线程间通信**：互斥体(互斥量)，信号量，条件变量。.

**Windows进程间通信**：管道、共享内存、消息队列、信号量、socket。

**Windows线程间通信**：临界区(Critical Section)、互斥量(Mutex)、信号量(信号灯) (Semaphore)、事件(Event)。

**==临界区(Critical section)与互斥体(Mutex) 的区别==**：

临界区只能用来同步本进程内的线程，而不可用来同步多个进程中的线程；互斥量(Mutex)，信号量(Semaphore)，事件(Event) 都可以被跨越进程使用来进行同步数据操作；
临界区是非内核对象，只在用户态进行锁操作，速度快；互斥体是内核对象，在核心态进行锁操作，速度慢。
临界区和互斥体在Windows平台都下可用，Linux下只有互斥体可用。

调度算法

调度的基本准则包括CPU利用率、系统吞吐量、周转时间、等待时间、响应时间等。

系统吞吐量表示单位时间内CPU完成作业的数量。

==周转时间 = 作业完成时刻 - 作业到达时刻==

==带权周转时间 = 周转时间 / 所需服务时间==

等待时间是指进程处于等处理器状态的时间之和，等待时间越长，用户满意度越低。

响应时间是指从用户提交请求到系统首次产生响应所用的时间。

典型调度算法包括：先来先服务算法(FCFS)、短作业优先算法(SJF)、优先级调度算法、高响应比优先调度算法、时间片轮转算法、多级反馈队列调度算法。其中SJF的平均等待时间、平均周转时间最少；最高响应比优先算法能兼顾短作业和长作业。

先来先服务算法（FCFS）

按照作业到达系统的时间依次分配服务。
短作业优先算法（SJF）

已到达的作业中优先服务所需时间短的作业。

下列作业中，J1最先到达，服务完毕后，J2、J3、J4均已到达；然后从中挑选出所需服务时间最短的J3先执行，然后是J4、J2。
高响应比优先调度算法（HRRN）

==响应比 = （上一个作业的完成时间 - 本作业的到达时间 + 本作业的所需服务时间）/ 本作业的所需服务时间==

其中，上一个作业的完成时间 - 本作业的到达时间，就是本作业的等待时间。

J1最先到达，先服务J1。之后再计算已到达的J2、J3、J4的响应比，从中选出响应比最高的J3先服务；J3服务完之后，再次计算J2、J4的响应比，从中选出响应比最高的J2先服务；最后服务J4。
优先级调度算法

优先级的数值越大，优先级越高

执行顺序：P2、P3、P4、P1
时间片轮转算法（RR）

用于分时系统中的进程调度。按照时间片执行，总是选择就绪队列的队首进程，让其在CPU上运行一个系统预先设置好的时间片，不考虑优先级。一个时间片内没有完成运行的进程，返回到绪队列末尾重新排队，等待下一次调度。

由于题例中各进程同时到达，则初始就绪队列为P1、P2、P3、P4，每个进程依次执行，每次仅执行一个时间片（题例中q=1ms），执行完毕后来到队尾。执行完4个时间片后，P1又来到队首，再次依次执行。8个时间片后，P4执行满2个时间片，结束。

死锁

多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

死锁产生的原因

系统资源的竞争、进程推进顺序非法
死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。
- 互斥条件
  
  进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
- 不剥夺条件
  
  进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
- 部分分配条件（请求和保持条件）
  
  进程每次申请它所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。
- 循环等待条件
  
  存在一种进程资源的循环等待链，链中每个进程己获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{${P_1, P_2, P_3, ……, P_n}$} ,其中$P_i$等待的资源被$P_{i+1}$(i=0,1, … n-1)占有，$P_n$等待资源被$P_0$占有。
死锁的处理策略
1. 预防死锁：设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个。
2. 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态。银行家算法是著名的死锁避免算法。
3. 死锁的检测及解除：无须采取任何限制性措施，允许进程在运行过程中发生死锁，通过系统的检测机制及时地检测出死锁的发生，然后采取某种措施解除死锁。
死锁的检测可利用资源分配图来描述。死锁的解除主要方法如下:

(1) 资源剥夺法。

(2) 撤销进程法。

(3) 进程回退法。

==银行家算法==

在进程提出资源申请时，先预判此分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

解答：

（1）系统拥有A、B、C、D类资源各3、14、12、12个。对于这4类资源，已被五个进程占有的资源量分别为A类2个、B类9个、C类10个、D类12个。因此这4类资源分别还剩A类1个、B类5个、C类2个、D类0个。

（2）首先列出各个进程的已分配allocated、尚需need，以及剩余可用资源available。然后开始寻找可行的安全序列（不唯一）。

比如，最开始的available为1 5 2 0，可满足P1、P4的need，任选其一，选择P1。P1被满足后再释放已分配的资源allocated，使得available变为1 5 3 2，这时的available可满足P3、P4的need，继续选择即可。按照这个方法可以得到一条可行的安全序列P1、P4、P2、P3、P5。

（3）先判断所提需求的0 4 2 0是否小于等于P2的need（在其需求范围内），以及同时小于等于Allocated（在可提供资源范围内）。当同时满足这两个条件时，可以更新P2的need和Allocated，即P2的need减少0 4 2 0，P2的Allocated增加0 4 2 0，以及剩余可用资源available减少0 4 2 0。接着，再按照第2问的做法，寻找可行的安全序列。若能找到安全序列，则代表系统能满足P2的请求。

内存管理

操作系统对内存的划分和动态分配，就是内存管理的概念。

内存管理的功能有:

内存空间的分配与回收，包括内存的管理和共享。
地址转换，把逻辑地址转换成相应的物理地址。
内存空间的扩充，利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
存储保护，保证各道作业在各自的存储空间内运行，互不干扰。

逻辑地址空间与物理地址空间

逻辑地址：

编译后，每个目标模块都是从0号单元开始编址，称为该目标模块的相对地址(或逻辑地址)。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。

物理地址：

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址来存取主存。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。

内存分配管理方式

内存分配管理方式包括连续分配管理方式与非连续分配管理方式。

连续分配管理方式，是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。

非连续分配管理方式允许一个程序分散地装入到不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

固定分区：

将主内存分为固定大小的分区, 这些大小可以相等或不相等。每当我们必须分配进程内存时, 就会找到一个足够大的空闲分区来容纳该进程。然后将内存分配给进程。如果没有可用空间, 则进程在队列中等待分配内存。会产生内部碎片（处于已分配区域内部或页面内部的存储块，占有这些区域或页面的进程并不使用这个存储块。直到进程释放它，或进程结束时，系统才有可能利用这个存储块）。

动态分区

主内存不划分为多个分区, 并且为进程分配了一块足够大的可用内存。剩余的空间被视为可以由其他进程进一步使用的自由空间。会产生外部碎片（还没有被分配出去，不属于任何进程，但由于太小了无法分配给申请内存空间的新进程的内存空闲区域），外部碎片是处于任何已分配区域或页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

基本分页存储管理方式

基本分页存储管理方式中，分区（块）的大小是固定的；运行作业时要把作业的所有页面都装入内存才能运行；

概念

由于固定分区和动态分区都会产生内存的碎片，为了提高内存利用率，引入分页的思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。
特点：仅产生很小的页内碎片

分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。但它又有本质的不同点：

块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但是这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片(也称页内碎片)。
分页存储的几个基本概念

① 页面和页面大小

进程中的块称为页(Page)（逻辑上），内存中的块称为页框(Page Frame,或页帧)。外存也以同样的单位进行划分，称为块(Block)（物理上）。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。

为方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，如果页面太小，会使进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入换出的效率；页面过大又会使页面内碎片增大，降低内存的利用率。

②地址结构

分页存储管理的逻辑地址结构如下图所示：

地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量M。地址长度为32位，其中0~~11位为页内地址，即每页大小为$2^{12}$B，即4KB; 12~~31 位为页号，地址空间最多允许有$2^{20}$页。

③页表

为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般存放在内存中。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。

==注意==：页号是系统自动生成的，本身地址是线性连续的，当要访问特定地址时，只需要提供地址即可。系统会自动将地址划分为页号和页内位移，而页号对于程序员来说是没有实际意义的，因此分页地址空间是一维的。

基本分段存储管理方式

基本分段存储管理方式中，段的大小是不固定的；运行作业时要把作业的所有页面都装入内存才能运行；

段式管理方式按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序、两个子程序、栈和一段数据组成，于是可以把这个用户进程划分为5个段，每段从0开始编址，并分配一段连续的地址空间（段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的，段名+段内地址)。

其逻辑地址由段号s与段内偏移量W两部分组成。在下图中，段号为16位，段内偏移量为16位，则一个作业最多可有2^16= 65536个段，最大段长为64KB。

在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在段式系统中，段号和段内偏移量必须由用户显示提供，在高级程序设计语言中，这个工作由编译程序完成。

==分页和分段存储管理方式的区别：==

分页存储管理中块是信息的物理单位，能够提高内存利用率；而分段存储管理中段是逻辑单位，分段是为了反映程序的逻辑结构，方便满足用户程序模块化的需要；
页的大小是固定的，由系统决定；而段的大小不固定，取决于用户编写的程序；
分页的地址空间是一维的，因为页是连续的；分段的地址空间是二维的，需要段名+段内地址。

段页式管理方式

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

在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后再将每一段分成若干大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。（逻辑上分段，物理上分页）

在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量。为了实现地址变换，系统为每个进程建立一张段表，而每个分段有一张页表。段表表项中至少包括段号、页表长度和页表起始地址，页表表项中至少包括页号和块号。此外，系统中还应有一个段表寄存器，指出作业的段表起始地址和段表长度。在进行地址变换时，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。

虚拟内存管理

针对的问题

前面的分页、分段、段页式存储管理都具有以下两个共同特征（缺点）：运行作业时要把作业的所有页面都装入内存才能运行；驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。

由以上分析可知，许多在程序运行中不用或暂时不用的程序(数据)占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。
依据的原理

==局部性原理==是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

时间局部性：在一个具有良好的时间局部性的程序中，被访问过一次的存储器位置很可能在不远的将来会被再次访问。

空间局部性：在一个具有良好空间局部性的程序中，如果一个存储器位置被访问了一次，那么程序很可能在不远的将来访问附近的一个存储器位置。

虚拟存储器的定义和特征

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（对用户完全透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。

虚拟内存的实现有以下三种方式:

1)请求分页存储管理

2)请求分段存储管理

请求段页式存储管理

不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面: .

一定容量的内存和外存。
页表机制(或段表机制)，作为主要的数据结构。
中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
地址变换机构，逻辑地址到物理地址的变换。

段页式虚拟存储器

基本思想是对用户原来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的物理空间采用分页的方法管理。
段页式虚拟存储器一方面具有段式虚拟存储器的主要优点。例如，用户程序可以模块化编写，程序段的共享和信息的保护都比较方便，程序可以在执行时再动态链接等。另一方面也具有页式虚拟存储器的主要优点。例如：主存储器的利用率比较高，对辅助存储器的管理比较容易等。

请求分页管理方式

运行作业时不需要把作业的所有页面都装入内存才能运行，需要哪一页就请求哪一页。

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。

为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。

常见的置换算法有以下三种：最佳置换算法、先进先出(FIFO)页面置换算法、最近最久未使用(LRU)置换算法。

最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。最佳置换算法可以用来评价其他算法。
先进先出（FIFO）页面置换算法

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由Belady于1969年发现，故称为Belady异常，如图2-3所示。FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

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

选择最近最长时间未访问过的页面予以淘汰，它认为过去一-段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO 算法基于队列实现，不是堆栈类算法。

==手写LRU==

C++实现：https://blog.csdn.net/Appleeatingboy/article/details/118306037

/*使用双向链表 + 哈希表 实现*/
class LRUCache {
public:
    class Node{
        public:
            int key;
            int val;
            Node* pre;
            Node* next;
            Node(){}
            Node(int mkey, int mvalue):key(mkey),val(mvalue),pre(NULL),next(NULL){ }
    };
    //构造函数
    LRUCache(int capacity) {
        this->size = capacity;
        //头尾保护节点
        head = new Node();
        tail = new Node();
        //初始化双链表关系
        head->next = tail;
        tail->pre = head;
    }
 
    Node* delete_currentnode(Node* current){
        current->pre->next = current->next;
        current->next->pre = current->pre;
        return current;
    }
    
    //移动到最前面
    //相当于在链表中一个insert操作，在head 和 head的next之间插入一个节点
    void move_to_head(Node* current){
        Node* next = head->next;
        head->next = current;
        current->pre = head;
        next->pre = current;
        current->next = next;
    }
 
    void make_recently(Node* current){
        Node* temp = delete_currentnode(current);
        move_to_head(temp);
    }
    
    int get(int key) {
        int ret = -1;
        //get 到key的value,要进行将key的对值从存储结构中删除，然后重新排列前后的数据
        if(map.find(key)!= map.end()){
            Node* temp = map[key];
            make_recently(temp);
            ret = temp->val;
        }
        return ret;
    }
    
    void put(int key, int value) {
        if(map.find(key) != map.end()){
            //关键字存在，修改key,对应的值
            Node* temp = map[key];
            temp->val= value;
            //将key变为最近使用
            make_recently(temp);
        }
        else{
            //关键字不存在，插入,(key,value)
            Node* cur = new Node(key,value);
            if( map.size()==size ){
                //链表尾部就是最久未使用的key
                Node* temp = delete_currentnode(tail->pre);
                map.erase(temp->key);
            }
            move_to_head(cur);
            map[key] = cur;
        }
    }
 
public:
    //类内共享容量值
    int size;
    unordered_map<int, Node*> map;
    Node* head;
    Node* tail;

用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法：https://blog.csdn.net/lwb102063/article/details/114085191

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }
 
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
 
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
 
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
 
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

LFU（Least Frequently Used）算法

根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。

抖动

内存抖动：非常频繁的换页活动；

系统中的“颠簸”是由缺页率高引起的，与内存容量、交换信息量无直接关系。

在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种**频繁的页面调度行为称为抖动，或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸**。频繁的发生缺页中断，其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提高系统效率。但系统必须很“聪明”地管理页面分配方案。在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。但如果管理不当，处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，这就会大大降低系统效率。

工作集

工作集(或驻留集)是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。

工作集模型的原理是：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

正确选择:工作集的大小，对存储器的利用率和系统吞吐量的提高，都将产生重要影响。

Linux常用命令

目录和文件的相关操作

cd /home      # 变换工作目录
cd .          # 代表当前目录
cd ..         # 代表上一层目录
cd ~          # 代表前一个工作目录

1	pwd # 输出当前工作目录

1 2	mkdir /test # 新建单层目录 mkdir -p /test/testing # 新建多层目录

1
2
3

rmdir         # 只能用来删除空目录
rm -r test    # 删除目录时需要使用"-r"选项，删除非空目录
rm aaa        # 默认仅删除文件

ls

1 2	cp ./aaa /tmp/bbb # 将当前目录下的aaa文件复制到tmp下并更名为bbb cp -r /etc /tmp # 复制目录时需要使用"-r"选项，如复制/etc/目录下的所有内容到/tmp下

1	mv /home/test /home/test2 # 移动或更名现有的文件或目录

文本文件内容查看

cat：由第一行开始查看文件。cat 是Concatenate (连续)的简写，主要的功能是将-一个文件的内容连续输出在屏幕上。

cat ./aaa

tac：从最后一行开始显示，可以看出cat与tac是倒置的。cat 是由第一行到最后一行连续显示在屏幕上，而tac则是由最后一行到第一行反向在屏幕上显示出来。

tac ./aaa

nl：显示文件内容的时候，一起显示文件行号。

nl ./aaa

more、less：一页一页显示文件内容。前面提到的nl、cat、 tac等，都是一次性将数据显示到屏幕上面，若是文件行数很多，前面的内容就会看不到，这时就需要使用more与less来一页一页查看文件内容。命令如下:

1 2	more ./aaa # 向后翻页 less ./aaa # 向前翻页

head：head命令查看文本文件时，只显示头几行。用法如下：

1	head -n number 文件名 # 只显示文件的前number行

-n选项后面的参数number如果是负数，代表列出前面的所有行数，但不包括后面number行。如/etc/man.config 共有141行，则head -n -100 /etc/man. config就会列出前面41行，后面100行不会打印出来了。

tail：tail命令查看文本文件时，只显示尾几行。用法如下：

1	tail -n number 文件名

当number前面有“+”号时，与head -n -xx有异曲同工之妙。如tail -n +100 /etc/man.config代表该文件从100行以后都会被列出来，同样，在man.config共有141行，因此第100~141行就会被列出来，前面的99行都不会被显示出来。

touch：建立一个空文件。

touch aaa

grep：分析一行信息，若当中有需要的信息，就将该行显示出来。常用在管道中。例如将文件aaa中包含”root”的行的内容显示出来的命令为cat aaa | grep "root"或者grep "root" aaa。当使用grep -E表示后面跟着的是延申型正则表达式，等价于”egrep”。比如找到文件try_ grep含有以a字母为行开头的内容，可以使用grep -E ^a try_grep。^M表示以M开头的行，M$表示以M结尾的行。

1
2
3

cat aaa | grep "root"  # 文件aaa中包含"root"的行的内容
grep "root" aaa        # 与上一行作用相同
grep -E ^a try_grep    #

查看系统信息

df：列出文件系统的整体磁盘使用量。

ps：将某个时间点的程序运行情况显示出来。

top：动态观察程序变化，持续侦测程序运行状态。