操作系统考研习题详细解析（1）

包含进程管理的PV操作--消产问题、读写问题；内存管理的计算题；文件管理的计算题。IO管理的计算题不准备更新，如有大佬路过or new idea 欢迎私聊或评论，让我们一起完善它！多图目录进程管理-PV操作有差值的容器叫号服务内存管理基本分页存储计算公式计算占字节、占页数等进制转化类型计算访存次数基本分段存储计算公式页面置换算法小题分页与分段之比较-摘自王道文件管理文件存储链式、连续、索引存储混合

AlexNett

33344人浏览 · 2020-10-19 15:48:53

AlexNett · 2020-10-19 15:48:53 发布

包含进程管理的PV五大操作；内存管理的计算题；文件管理的计算题。IO管理的计算题不准备更新，如有大佬路过or new idea🆘 欢迎私聊或评论，让我们一起完善它！📡 多图

另外感谢互联网上的大牛分享自己的知识！

分享一个博主：（5万字、97 张图总结操作系统核心知识点）5万字、97 张图总结操作系统核心知识点 - 程序员cxuan - 博客园

 操作系统考研习题详细解析（2）本文内容过多故分成两部分

另附各个章节的调度算法图解

本文预计7+20+18+8+8=60+道题（若想复习，可以借此分配时间）

因为后续调整过文章可能文章一些页内跳转会失败😵

计算占字节、占页数等

计算访存次数

进程管理

调度算法

链接：操作系统中常用的进程调度算法_GeorgiaStar的博客-CSDN博客_操作系统fifo进程调度算法、三分钟基础：有哪些经典的进程调度算法？ - 腾讯云开发者社区-腾讯云

题1：将一组进程分为4类，如下图所示。各类进程之间采用优先级调度算法，而各类进程的内部采用时间片轮转调度算法。请简述P1,P2, P3, P4, P5, P6, P7, P8进程的调度过程。

解1：这里只需知道优先级算法和时间片算法的内涵即可，另外注意此处不是多级反馈队列调度算法，所以先进行P1、P2、P3 并且内部采用时间片直到三个进程都运行完毕，进行到P4、P5，内部同前面的，P6、P7、P8也不用说了。贴上答案的详解：由题意可知，各类进程之间采用优先级调度算法，而同类进程内部采用时间片轮转调度算法。因此，系统首先对优先级为4的进程P1 P2 P3采用时间片轮转调度算法运行;当P1, P2, P3均运行结束或没有可运行的进程(即P1, P2,P3都处于等待态; 或其中部分进程已运行结束，其余进程处于等待态)时，对优先级为3的进程P4 P5采用时间片轮转调度算法运行。在此期间，若未结束的P1, P2, P3有一个转为就绪态，则当前时间片用完后又回到优先级4进行调度。类似地，当P1~P5均运行结束或没有可运行进程(即P1~P5都处于等待态;或其中部分进程已运行结束，其余进程处于等待态)时，对优先级为2的进程P6, P7, P8采用时间片轮转调度算法运行，一旦P1~P5中有一个转为就绪态,当前时间片用完后立即回到相应的优先级进行时间片轮转调度。

题2：设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运动轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图(可以用Cantt Chart)，并说明：

(1)开始运行后，CPU有无空闲等待？若有，在哪段时间内等待？计算CPU的利用率。

(2)进程A运行时有无等待现象？若有，在什么时候发生等待现象？

(3)进程B运行时有无等待现象？若有，在什么时候发生等待现象？

解2：甘特图有多种画法感觉，只要能表示出来他们的关系即可

题3：有一个CPU和两台外设D1、D2，且能够实现抢占式优先级调度算法的多道程序环境中，同时进入优先级由高到低的P1、P2、P3三个作业，每个作业的处理顺序和使用资源的时间如下：
P1：D2(30ms)，CPU(10ms)，D1(30ms)，CPU(10ms)
P2：D1(20ms)，CPU(20ms)，D2(40ms)
P3：CPU(30ms)，D1(20ms)
假设对于其他辅助操作时间忽略不计，每个作业的周转时间T1、T2、T3分别为多少CPU和D1的利用率各是多少

解3：进程调度算法毕竟是第二章，相对来说比较简单，只要慢慢算，知道怎么算就可以了，比如周转时间什么的。

各种时间计算

仅贴链接：完成时间，周转时间，平均周转时间以及带权周转时间和平均带权周转时间_Tseward的博客-CSDN博客_平均等待时间和平均周转时间

这两个是链接里没有的

4) 等待时间。是指进程处于等处理机状态时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常只需简单地考察等待时间。

5) 响应时间。是指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般釆用响应时间作为衡量调度算法的重要准则之一。从用户角度看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。

五大经典PV

1.生产者--消费者

详细博文：生产者消费者问题（PV操作）_csjinzhao的博客-CSDN博客_生产者消费者pv（用empty和full来来实现同步）

//以下5个PV问题中的中文是基本操作，也可以写成英文
//1.原CPP代码样式不见了 找不到黑底的代码样式，如有知道的评论或私聊，
//1.已解决 原来是主题的缘故，下面的代码段里就不一一改了
//喜欢这种样式的 那我也就不改了

semaphore empty = n;   //初始容器大小 用于判断能否装入 不要因为英文是"空"的意思而赋值0
semaphore full = 0;    //初始装入数量  用于判断能否取出
semaphore mutex = 1;  //不管是否需要互斥都要加上
producers(){
    while(1){
        P(empry);    //查看是否容器满了
        P(mutex);    //互斥装入

        生产;

        V(mutex);    
        V(full);    //生产出一个产品  可消费量+1
    }
}

customers(){        //与生产者相反即可
    while(1){
        P(full);    //查看容器内的产品
        P(mutex);   //互斥取出

        消费;

        V(mutex);    
        V(empry);    //消费一个产品 容器可装入量+1
    }
}

2.读者--写者

详细解释（包含读优先、写优先、读写优先）：PV经典问题之读写者问题_进阶媛小吴的博客-CSDN博客_读写者问题代码（用count来计算某物数量用if-else实现读写互斥）

//如果该种样式不习惯的话 我换成C++样式
semaphore rmutex = 1;    //读写互斥
int count = 0;   //记录读者数量  用于判断是否释放互斥
semaphore mutex = 1;    //用于互斥访问count

readers(){
    while(1){
        P(mutex);    //互斥count 防止count值变化
        ++count;   //读者数量+1
        if (count == 1) P(rmutex);   //第一个读者给写者加锁
        V(mutex);    
        
        读;
        
        P(mutex);    //一般出现 变量 就要加互斥
        --count;    
        if (count==0) V(rmutex);    //最后一个离开的读者解锁
        V(mutex);
    }
}

writers(){
    while(1){
        P(rmutex);
        写;
        V(rmutex);
    }
}

3.哲学家进餐

详细解释（三种方法）：【操作系统】“哲学家进餐”问题_diligentyang的博客-CSDN博客_哲学家进餐(用左右互斥操作来实现进餐)

//如果该种样式不习惯的话 我换成C++样式
//此种方法我个人觉得最容易记的，其他方法看上面的博文

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;    //互斥拿起筷子
philosophers() { 
	while (1) {
        P(mutex);
		P(chopstick[i]);     //拿左边筷⼦
		P(chopstick[(i + 1) % 5]);     //拿右边筷⼦
        V(mutex);

		吃;

		V(chopstick[i]);     //放左边筷⼦
		V(chopstick[(i + 1) % 5]);     //放右边筷⼦
		想;
	}
}

4.理发师

问题：理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。（用判断语句if-else来实现等待、离开过程，区分读写问题）

详细博文（可运行源码+套娃博文+排队理发）：linux下C语言实现睡眠理法师问题_WorldWelcome的博客-CSDN博客_linux 睡眠的理发师问题代码

//如果该种样式不习惯的话 我换成C++样式
semaphore customres = 0;
semaphore barber= 0;    //初始💇‍♂️睡觉
semaphore mutex = 1;
int chairs = n;    //初始容器（椅子）大小
int waiting = 0;    //初始可装入量（顾客量）

customers(){
    while(1){
        P(mutex);
        if (waiting < chairs){    //判断是否离开，若椅子满了转入else
            ++waiting;
            V(customers);   //“妈妈桑” 来客人了🤣唤醒理发师
            V(mutex);    //先解锁 以让顾客进来，
                        //来加大并发数。
            P(baber);    //请求理发
            等待理发;
        }else
            V(mutex);    //人满离开
    }
}

baber(){      //💈
    while(1){
        P(customers);    //无人堵塞 睡觉，有人进行理发
        P(mutex);    //互斥变量
        --waiting;    //椅子释放
        V(baber);    //必须在互斥里，否则可能waiting一直减， 
                    //导致baber只理发了一些人。
        V(mutex);
        理发;
    }
}

5.吸烟者

三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西:烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地)在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。（有点类似生消问题只不过有了制约关系电影院问题可用此方法）
详细博文（图+解析）：操作系统——吸烟者问题 - 王陸 - 博客园（此外原博主可能会加锁文章，我博客里复制了该文章，若原文失效可以看看）

//如果该种样式不习惯的话 我换成C++样式

semaphore offer1 = 0;     //提供📃/🌿
semaphore offer2 = 0;     //提供🌿/💣
semaphore offer3 = 0;     //提供📃/💣
semaphore finish = 0;
int random;
providers(){    //供应者
    while(1){
        random = 生成一个随机数;    //如果实现轮流 <(￣ c￣)y▂ξ 的话
                                   //int i = 0;    
        random = random % 3;       //random = (++i)%3;
        if (random == 0){
            V(offer1);        //提供📃/🌿
        if (random == 1){
            V(offer2);        //提供🌿/💣
        if (random == 2){
            V(offer3);        //提供📃/💣

        放两种材料（📃/🌿/💣）;
        P(finish);            //材料准备好，可以🚬
    }
}

have💣(){             //三个抽烟者进程 类似 代码
    while(1){
        P(offer1);    //缺什么申请什么
        卷烟并抽烟;
        V(finish);    //抽烟完成，解锁供应者
    }
}
have📃(){
    while(1){
        P(offer2);
        卷烟并抽烟;
        V(finish);    //抽烟完成，解锁供应者
    }
}
have🌿(){
    while(1){
        P(offer3);
        卷烟并抽烟;
        V(finish);    //抽烟完成，解锁供应者
    }
}

生产者-消费者问题

环形缓冲区

1.有M个生产者P1，P2, ... ,PM和K个消费者C1, C2, ... ,CK,一个大小为n的环形缓冲区，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语实现生产者和消费者的同步操作。

Semaphore empty = n; //剩余空间
Semaphore full  = 0; //已占空间
Semaphore mutex = 1;
int in=0, out=0;
P (){
    while(1){
        P (empty):
        P (mutex);
        放入缓冲区buffer[in];
        in = (in+1) mod n;    //❗
        V (mutex);
        V (full);
    }
}
C (){
    while(1)
        P (fulI);
        P (mutex) ;
        在buffer[out]中取出产品:
        out = (out+1) mod n;    //❗
        V (mutex);
        V (empty);
    }
}

有差值的容器

题目：在一个仓库中可以存放A和B两种产品，要求:

1.每次只能存入一种产品。

2.A产品数量-B产品数量<M。

3.B产品数量-A产品数量<N。

其中，M,N是正整数，试用Р操作、V操作描述产品A与产品B的入库过程。

解：这种我一开始看到有点懵 A-B<M 又B-A<N 这是什么东东感觉关系有点难找后来突然灵光一现。

如图，我们可以把A看成生产者和消费者，B也看成两种身份。加就是生产的过程，减就是消费的过程，那仓库就可以分成两块，一部分是M容量，一部分是N容量。同时因为M仓库最多能容纳A有M-1个（∵A<M）同理N容纳B有N-1个。图中A到B的箭头指的是生产。M到B指的是消费。

代码就不过多赘述了，知道这种关系就很好理解了。ps 基本操作如入库需要加互斥，就算题目不需要加你加了也没什么影响万一要加呢。此外Sa就可以看成生产者消费者里的empty Sb就是full。（做题先画图，可以更好理解）

叫号服务--理发+生消

题目1：面包师有很多面包，由n名销售人员推销。每名顾客进店后取一个号，并且等待叫号，当一名销售人员空闲时，就叫下一个号。试设计—个使销售人员和顾客同步的算法。

解1：(这道题没什么好说的根据答案也能看的懂就是一看就会一做就废（有思路的欢迎评论）纯粹为了与下一题比较。注意这里是叫下一个号有次序关系)

题目2：【2011统考真题】某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。[当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下:

cobegin
{
    process 顾客i
    {
        从取号机获取一个号码；
        等待叫号；
        获取服务；
    }

    process 营业员
    {
        while(TRUE)
        {   
            叫号；
            为客户服务；
        }
    }
}coend

请添加必要的信号量和P,V[或 wait(), signal()]操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

解2：这里是选取一位顾客可以不用次序一开始我就直接套上面需要次序的代码了😓。

典型的生产者和消费者（还是有点不熟练，看到答案才发现原来是生产者和消费者，生产者和消费者这类问题的特征就是有一个容器能容纳多少东西，并且有进程可以往容器里增加或者取出）

（为了排版，图片点击可以放大）

//当有两个服务窗口时
semaphore seats = 10;    //可容纳顾客数
semaphore requests = 2, service = 0;    //请求服务的相关信号量
semaphore mutex = 1;    //互斥取号
Customers (){
    while (1){
        P (seats);    //请求座位
        P (mutex);
        取 号;
        V (mutex);
        
        P (request);    //请求服务
        请求服务;
        V (service);    //通知营业员
    }
}

Employees (){
    while (1){
        P (service);    //初始为空，0则休息
        服 务
        V（seats)//释放座位
        服务完毕;
        V (request)//释放营业员，起身去接受服务
    }
}
//这空格对的就很灵性😋
//自己写的 不确定对不对

银行家算法

题：某系统有R1, R2和R3,共三种资源，在T0时刻P1，P2，P3和P4这四个进程对资源的占用和需求情况见下表，此时系统的可用资源向量为(2,1,2)试问
1）用向量或矩阵表示系统中各种资源的总数和此刻各进程对各资源的需求数目。
2）若此时进程P1和进程P2均发出资源请求向量Request(1,0,1)，为了保证系统的安全性，应如何分配资源给这两个进程?说明所采用策略的原因。

3）若2）中两个请求立即得到满足后，系统此刻是否处于死锁状态?

解：(银行家算法也没啥好解释，注意可用资源（available）矩阵和需求（need）矩阵即可。每次就是可用与需求比较，满足就可以分配，并且下次的可用资源加上分配的那个进程的已分配资源即可.)

1）系统中资源总量为某时刻系统中可用资源量与各进程已分配资源量之和，即(2,1,2)+(1,0,0)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6）各进程对资源的需求量为各进程对资源的最大需求量与进程已分配资源量之差即

2）若此时P1发出资源请求Request 1(1,0,1)，则按银行家算法进行检查:

Request1(1,0,1)<=Need1(2,2,2)
Request1(1,0,1)<=Available(2,1,2)
试分配并修改相应数据结构，由此形成的进程P1请求资源后的资源分配情况见下表。~~(干我还特地调了方框颜色，居然没显示出来😭)~~

	Allocation			Need			Available
P1	2	0	1	1	2	1	1	1	1
P2	4	1	1	2	0	2
P3	2	1	1	1	0	3
P4	0	0	2	4	2	0

再利用安全性算法检查系统是否安全，可用资源Available(1, 1,1)已不能满足任何进程,系统进入不安全状态，此时系统不能将资源分配给进程P1。
若此时进程P2发出资源请求Request2(1,0,1)，则按银行家算法进行检查:

Request2(1,0,1)<=Need2(2,0,2)
Request2(1,0,1)<=Available(2,1,2)
试分配并修改相应数据结构，由此形成的进程P2请求资源后的资源分配情况下表:

	Allocation			Need			Available
P1	1	0	0	2	2	2	1	1	1
P2	5	1	2	1	0	1
P3	2	1	1	1	0	3
P4	0	0	2	4	2	0

再利用安全性算法检查系统是否安全，可得到如下表中所示的安全性检测情况。注意表中各个进程对应的Work+Allocation向量表示在该进程释放资源之后更新的Work向量。（Available是work执行后系统所剩资源，~~银行家其实算简单的计算题了，后面的内存、文件真的烦💰~~）

	Allocation			Need			Work			Available
P2	5	1	2	1	0	1	1	1	1	6	2	3
P3	2	1	1	1	0	3	6	2	3	8	3	4
P4	0	0	2	4	2	0	8	3	4	8	3	6
P1	1	0	0	2	2	2	8	3	6	9	3	6

从上表中可以看出，此时存在一个安全序列{P2, P3, P4, P1}，因此该状态是安全的，可以立即将进程P2所申请的资源分配给它。
3）若2）中的两个请求立即得到满足,则此刻系统并未立即进入死锁状态，因为这时所有的进程未提出新的资源申请，全部进程均未因资源请求没有得到满足而进入阻塞态。只有当进程提出资源申请且全部进程都进入阻塞态时，系统才处于死锁状态。

内存管理

补充一下页目录号的概念（一个页目录号对应一个页表，一个页号对应一个物理块。反正就是指向页表的叫页目录号，指向数据块的叫页号）

逻辑地址和物理地址

别跟页表的位数搞混了（~~本人在此~~）

1.一个采用请求式页面存储的系统，其物理内存为512M字节，虚拟地址空间大小为4G字节，页面大小为4K字节，试问:
(1)物理地址应设为多少位?
(2)主存中有多少物理页?
(3)虚拟地址应该设多少位?
(4)虚拟地址空间最多可以有多少页?
(5)页内最大和最小偏移量是多少?

解：

1.物理地址就是算物理内存的次数即可512MB=2^29B 即29位。2. 2^29 / 2^12 = 2^17页。3. 4G=2^32B 即32位。4. 2^32 / 2^12 = 2^30. 5.最大偏移量指的是大小不是位数，所以是4095和0 下标从0开始

基本分页存储 计算公式

其中L-页面大小 A-逻辑地址 E-物理地址 P-页号 b-物理块号 W-页内偏移量

无意中看到一篇讲的挺不错的博文，mark：分页存储管理方式附网易校招笔试题_南宫小仙僧的博客-CSDN博客

可能对理解分页有帮助用书来形容：某计算机采用二级页表的分页存储管理方式，按字节编址，页面大小__牛客网、（单开）关于页目录项_AlexNett的博客-CSDN博客_页目录项是什么

题目1：【2013统考真题】某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4B。请回答下列问题:

1）若使用一级页表的分页存储管理方式，逻辑地址结构为

则页的大小是多少字节?页表最大占用多少字节?
3）采用1）中的分页存储管理方式，一个代码段的起始逻辑地址为0000 8000H，其长度为8KB,被装载到从物理地址0090 0000H开始的连续主存空间中。页表从主存0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增)。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号，以及代码页面2的起始物理地址。（~~还是有一定的难度的二刷还没做成来😥~~）

字节：B、位：b

解1：（1）根据页内偏移量页的大小为2^12B；页表最大占用2^32 / 2^12*4B=2^22B。（页内偏移量=页的大小，有多少页面就有多少页表项乘上页表项大小即页表大小）（地址空间有2^32B大，一页占2^12B，所以除一下就是页数，即一共有2^20页）（又迷糊了一下对于位变成2^12后就变成字节了，附链阶）

（3）根据上面的分页公式可得页号Ｐ＝页表始址Ｆ＋页号Ｐ×页表项长度＝0020 0000H + 8*4B(转换成十六机制即0020H)=0020 0020H （其中8根据代码段逻辑地址以及逻辑地址结构，后12位为偏移量即000H为偏移量 前20位为页号即0000 8为页号（注意十六进制一个0代表二进制4个0，8H: 0100））所以物理地址1为0020 0020H，

因为一个页表项占4B所以物理地址2 = 0020 0020H + 4B = 0020 0024H

物理地址3 = 0090 0000H + 4KB(2^12转换成十六进制1000H) = 0090 1000H （代码段长8KB 一页4KB所以代码页1的地址+4KB即可。此外主存空间都是大小相等且固定的块）

页框号1和2即块号即 00900H和00901H （块号和页号一一对应所以块号也是20位，根据块号+偏移量就是物理地址0090 0000H，页号是隐含所以不放在页表里，此外页表项就是页表内的一项数据）

题目2：

解2：答案已经很清晰了就是注意一下编程空间为32个页面即2^5个需要五位，主存为16KB/1KB=16个页面2^4个。

题目3：在一个分页存储管理系统中，地址空间分页（每页 1KB），物理空间分块，设主存总容量是256KB，描述主存分配情况的位示图如下图所示（0表示未分配,1表示已分配），此时作业调度程序选中一个长为5.2KB的作业投入内存。
1）为该作业分配内存后（分配内存时，首先分配低地址的内存空间)，填写该作业的页
表内容。
2）页式存储管理有无零头存在？若有，会存在什么零头？为该作业分配内存后，会产
生零头吗?若产生，大小为多少？（提示:这里的零头是指一页中未被使用的部分。）

3）假设一个64MB内存容量的计算机，其操作系统采用页式存储管理（页面大小为4KB），内存分配采用位示图方式管理，请问位示图将占用多大的内存？

解3：这里第一题只需要算出该作业需要6>5.2即6页，同时位示图一位(b)表示一个物理块，所以从左到右，从上到下，找那些位置是0（未分配）即可。每行有16个。注意页表号和物理块下标是0开始。第二题只要是分配固定空间的就有内部碎片。可变长的就是外部碎片，如分段。常见的内部碎片：分页式、段页式、固定分区分配。外部碎片：分段式、多道可变连续分配。第三题很常规，算出几个物理盘块就有几页与之对应，即2^14页。1B=8b 1KB=2^10B 转化一下就是2KB了。2^6MB=2^16KB / 2^2 = 2^14页

计算占字节、占页数等

题目4：【2015统考真题】某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示:
10位 10位 12位
页目录号页表索引页内偏移量
请回答下列问题:
1）页和页框的大小各为多少字节?进程的虚拟地址空间大小为多少页?
2）若页目录项和页表项均占4B，则进程的页目录和页表共占多少页?写出计算过程。
3）若某指令周期内访问的虚拟地址为0100 0000H和0111 2048H，则进行地址转换时共访问多少个二级页表?说明理由。

解4：页是虚拟页=页框是真正放在物理块里的页。 页目录项映射页表页表项映射物理地址页、页表、页框关系

1）页和页框大小均为4KB。进程的虚拟地址空间大小为2^32 / 2^12=2^20页。（页目录号对应一个含2^10的页表，2^10个页目录号有2^20页）
2）(2^10x4)/2^12(页目录所占页数）＋ (2^20×4)/2^12(页表所占页数)=1025页。(侧边表现了顶级（目录）表只能放一页里)
3）需要访问一个二级页表。因为虚拟地址01000000H和 0111 2048H 的最高10位的值都是
4，访问的是同一个二级页表。010=0000 0001 0000、011=0000 0001 0001

进制转化类型

记录一下10->16进制

260/16=16---4 120/16=7---8

16/16=1---0 7/16=0-----7 78H

1/16=0----1 104H

重点是算出页号位数和页内偏移量位数。这里推荐一个B站视频：22_C编程预备计算机专业知识_什么叫进制【重点】 =_哔哩哔哩_bilibili 郝斌老师讲的：什么叫进制

题目1：

（二刷在第二小问有点懵逼，实际上转化成16进制即可。难道默认地址都是用16进制表示吗）

解1：其中72的十进制转化如图。进制转化：计算机基础进制转换（二进制、八进制、十进制、十六进制）_daixiangcn的博客-CSDN博客_十进制转八进制这类题目与下面的题目要注意的就是算出页号位数和页内偏移量位数 根据转化后的二进制来判断哪些属于页号如下图后1001位块号转化为十六进制为9 0000 0000 0000 为页内偏移量所以000 合起来就是9000H，页内偏移量=页面大小（也可以2^6+3^3=72 来确定地址即1后6个0+1后3个0=1001000）

题目2：

解2：八进制转化 注意页大小为64B 所以页内偏移量为64B =2^6B 占6位.（二刷体悟：八进制用111-000表示，一共3位；又页内偏移量用6位表示，因此不需要管后两个数字。我还以为702B是干什么的，原来判断越界的）

计算访存次数

题目1：某一页式系统，其页表存放在主存中:
1）若对主存的一次存取需1.5us，问实现一次页面访问时存取时间是多少?
2）若系统有快表且其平均命中率为85%，而页表项在快表中的查找时间可忽略不计，试问此时的存取时间为多少?

解1：注意快表是在高速缓存中，所以不需要访问内存即快表只需要一次访存就可以实现存取数据。在有快表的分页存储系统中，计算有效存取时间时，需注意访问快表与访问内存的时间关系。通常的系统中，先访问快表，未命中时再访问内存;在有些系统中，快表与内存的访问同时进行，当快表命中时就停止对内存的访问。这里题中未具体指明，我们按照前者进行计算。但若题中有具体的说明，计算时就应注意区别。

题2：在一个磁盘高速缓存系统中，高速缓存的平均访问时间为100μs，磁盘平均访问时间10ms，问高缓访问命中率为多少时，平均访问时间达到1ms？

解2：本题会错意了，我还以为是平常的访问还要访问磁盘，因为题目给的是平均访问时间不是存取时间，所以只需设命中率为k即 0.1k+(1-k)(0.1+10) = 1 -> k=0.91

题目2：某分页式虚拟存储系统，用于页面交换的磁盘的平均访问及传输时间是20ms。页表保存在主存中，访问时间为1μs，即每引用一次指令或数据，需要访问内存两次。为改善性能，可以增设一个关联寄存器，若页表项在关联寄存器中，则只需访问一次内存。假设80%的访问的页表项在关联寄存器中，剩下的20%中，10%的访问（即总数的2%)会产生缺页。请计算有效访问时间.

解2：80%*(1μs) + 20%*10%*(1μs+1μs+1μs+20ms) + 20%*90%(1μs+1μs) = 401.22μs。（二刷体会，一刷缺页中断拎不清，实际访问快表失败（不耗时间），再访问页表，缺页中断20并把页号放在页表中，访问页表，再访存）

解释一下1+20+1+1这怎么来的，1是访问内存中的页表失败，然后缺页中断处理20，然后根据将页面调入快表中（不需要访存），1是缺页后访问内存中的页表，然后直接根据拼接好的物理地址访问，用时1

看不懂的那个是1us

题目3：

解3：1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即2^12，得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号Р如下（十六进制的一位数字转换成二进制的4位数字，因此十六进制的低三位正好为页内位移，最高位为页号，建议先写出二进制和十进制的对应关系，1111：8421)
2362H:P=2，访问快表10ns，因初始为空，访问页表100ns,得到页框号，合成物理地址后访问主存100ns，共计10ns + 100ns + 100ns = 210ns。
1565H:P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理10^8ns，访问快表10ns，合成物理地址后访问主存100ns，共计10ns+100ns + 10^8ns + 10ns + 100ns =100000220ns。（与上面的第二题冲突 以真题为准这个是直接访问快表拼接物理地址上面的是根据页表拼接）
25A5H:P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns + 100ns=110ns。
2)当访问虚地址1565H时，产生缺页中断，合法驻留集为2（不考虑页号1的原因是驻留集为2，而且题目页框号都直接划去了也没地方算），必须从页表中淘汰一个页面，
根据题目的置换算法（最近最久未使用），应淘汰0号页面，因此1565H 的对应页框号为101H。由此可得1565H 的物理地址为101565H。

~~心酸写的那么仔细，没人看。😭~~

题目4：现有一请求页式系统，页表保存在寄存器中。若有一个可用的空页或被置换的页未被修改，则它处理一个缺页中断需要8ms;若被置换的页已被修改，则处理一缺页中断因增加写回外存时间而需要20ms，内存的存取时间为1us。假定70%被置换的页被修改过，为保证有效存取时间不超过2us，可接受的最大缺页中断率是多少?

解4：在缺页中断处理完成，调入请求页面后，还需1us的存取访问，即
1）当未缺页时，直接访问内存，用时1us。
2）当缺页时，若未修改，则用时8ms + 1us。（题目指出页表在寄存器中即高缓中，没有指明查快表时间，所以只记录存取时间1（别忘了还要存））
3）当缺页时，而且修改了，则用时20ms + 1us。

因此,设最大缺页中断率为p,有(1-p)×1us+(1-70%)p×(1us + 8ms)+ 70%×p×(1us+20ms)=2us,即1us+ (1-70%)×px8ms + 70%×p×20ms = 2us，解得p =0.00006。

（这里总结一下，如果有快表或者页表在寄存器中，则只需访存一次实现读写；如果无快表或者快表访问失败，则只需两次访存实现读写；如果缺页中断，根据题目的意思来，一般是各查快、页表一次，然后再处理缺页一次，最后访问快表一次加上访存一次，实现读写。）

各个存储管理的访存次数

基本分段存储 计算公式

几级页表

(虚地址位数 - 页内偏移量位数) / 页内索引项位数（更确切的说就是虚地址是页表的页号有几位）

如虚地址48，页内偏移量12，一页存放2^9个则36 / 9 = 4级页表

题目1：已知系统为32位实地址，采用48位虚拟地址，页面大小为4KB，页表项大小为8B，每段最大为4GB。
5）若系统采用段页式存储，则每用户最多可以有多少个段?段内采用几级页表?
题目有点不完整，去这里

解1：系统采用48位虚拟地址，每段最大为4GB，因此段内地址为32位，段号为48-32=16位。(段号是看有多少个物理块非大小)每个用户最多可以有2^16段。段内采用页式地址，与1）中计算同理，(32-12)/9，取上整为3，因此段内应采用3级页表。页式地址使用实地址32位，减去12位页内偏移量即20位装页号一页只能装9位的页表项即[20/9]需要三级页表。总之先算页号占多少位，然后除以一页的页表项个数的次数（2^9取9次）

页面置换算法

最佳置换算法。OPT（OPTimal）
先进先出置换算法。FIFO（First In First Out）
最近最久未使用算法。LRU（Least Recently Used）
最近未使用算法即CLOCK算法。NRU（Not Recently Used）
简单CLOCK和改进性CLOCK算法。

以上名词解释

附：我的页面置换算法的画法。

如下，将先进来的放到最后，再根据调度算法，将替换页放到最上面，其实相当于队列，先进先出。当然，如果不适合你，就不要强求了，有自己的画法也可，最重要把题目做出来。

题目1：在一个请求分页存储管理系统中，一个作业的页面走向为4,3,2,1,4,3,5,4,3,2,1,5，当分配给作业的物理块数分别为3和4时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面)，并比较结果。
1.LRU算法 2.FIFO算法

解1：仅记录先进先出其他的都比较简单。先进先出的先进的页面不会因为再次访问到而改变自己在链表中的位置，所以先出。最近最久未使用可以像这样子套娃来判断出去哪页，这里就不告诉访问顺序自己摸索一下加深印象。

题目2.1（存疑）：一进程已分配到4个页帧，见下表（编号为十进制,从0开始)。当进程访问第4页时，产生缺页中断，请分别用FIFO(先进先出)、 LRU(最近最少使用)、NRU(最近不用)算法，决定缺页中断服务程序选择换出的页面。

虚拟页号	页帧	装入时间	最近访问时间	访问位	修改位
2	0	60	161	0	1
1	1	130	160	0	0
0	2	26	162	1	0
3	3	20	163	1	1

解2.1：FIFO看装入时间 替换页帧3 LRU看最近访问时间 替换页帧1 NRU（存疑）看循环列表指针指向位置，因为页帧1最先访问，页帧0第二访问，访问位在第一次循环时已经在0上了所以访问位置为0，但下一页2还是访问位是1，所以替换页帧0.这里加个改进型CLOCK算法：会替换页帧1（第三张图是改进型置换过程）.

表格来源（博主解释也挺不错的）：【考研复习】操作系统NRU置换算法小题_近战法师王德福的博客-CSDN博客_nru算法例题（该博主的理解是访问一轮之后找访问位为0，答案的意思是在当下时刻看到页帧为0，不轮一轮直接替换）

题目2.2：【2010统考真题】设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page）数据存储空间，页的大小为 1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框( Page Frame)，见下表。在装入时刻260前，该进程的访问情况也见下表（访问位即使用位)。

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。回答下列问题:
1）该逻辑地址对应的页号是多少?
2）若采用先进先出（FIFO）置换算法，则该逻辑地址对应的物理地址是多少﹖要求给出计算过程。若采用时钟( Clock)置换算法，则该逻辑地址对应的物理地址是多少?要求给出计算过程。设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如下图所示。

解2.2：本题比较简单，除了答题规范。仅于上面的CLOCK算法做对比，真题都会给图片的。

1）由于该计算机的逻辑地址空间和物理地址空间均为64KB = 2^16B，按字节编址，且页的大
小为1K=2^10，因此逻辑地址和物理地址的地址格式均为

页号/页框号（6位)

页内偏移量（10位)

17CAH= 0001 0111 1100 1010B，可知该逻辑地址的页号为000101= 5。

2）采用FIFO置换算法，与最早调入的页面即0号页面置换，其所在的页框号为7，于是对
应的物理地址为0001 1111 1100 1010B = 1FCAH。
3）采用 CLOCK 置换算法，首先从当前位置（2号页框）开始顺时针寻找访问位为0的页面，当指针指向的页面的访问位为1时，就把该访问位清“0”，指针遍历一周后，回到2号页框，此时2号页框的访问位为0，置换该页框的页面，于是对应的物理地址为0000 1011 1100 1010B = 0BCAH。

题目3：【2012统考真题】某请求分页系统的页面置换策略如下:从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计)且本轮未被访问过的页框将被系统回收,并放入空闲页框链尾，其中内容在下一次分配之前不清空。当发生缺页时，若该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中;否则，从空闲页框链表头部取出一个页框。忽略其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页的页框号依次为32,15,21,41。进程Р依次访问的<虚拟页号,访问时刻>为<1, 1>，<3,2>，<0,4>,<0,6>,<1,11>,<0,13>,<2,14>。请回答下列问题:
1）当虚拟页为<0,4>时，对应的页框号是什么?
2）当虚拟页为<1,11>时，对应的页框号是什么?说明理由。
3）当虚拟页为<2,14>时，对应的页框号是什么?说明理由。
4）这种方法是否适合于时间局部性好的程序?说明理由。

解3：空闲链表：32->15->21->41

物理页号（0-4时刻）	虚拟页号	访问时刻	物理页号（5-9时刻）	虚拟页号	访问时刻	物理页号（10-14时刻）	虚拟页号	访问时刻
32	1	1	21	0	6	32	1	11
15	3	2				21	0	13
21	0	4				41	2	14
该轮未被访问过	无		该轮未被访问过（数据还在）	1->32	3->15

1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框(21)，其对应的页框号为21。
2）页框号为32。理由:因11>10，因此发生第三轮扫描，页号为1的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。
3）页框号为41。理由:因为第41页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
4)合适。理由:程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
这里有个疑惑当虚拟页号映射到同一个物理地址的时候会发生什么事？是原先的内容会覆盖掉或者在该页继续往下写或访问，无关题目。

题目4：有一个矩阵int A[100,100]以行优先方式进行存储。计算机采用虚拟存储系统，物理内存共有三页，其中一页用来存放程序，其余两页用于存放数据。假设程序已在内存中占一页，其余两页空闲。若每页可存放200个整数，程序1、程序2执行的过程中各会发生多少次缺页﹖每页只能存放100个整数时，会发生多少次缺页?以上结果说明了什么问题?

解4：存数据按行优先存，因为程序1按行优先进行循环所以10000/200=50次而程序2按列优先进行循环，10000/2=5000次。当存放100个整数时，同理。

程序1的第一页(行，列)	0,0	...	...	0,99
	1,0	...	...	1,99
从行开始装数据所以每200个数据缺页

程序2的第一页(行，列)	0,0
	1，0
从列开始装数据所以每2个数据缺页

小题

解1：首先根据页大小和页表项大小得出有一页可以存放2的9次个页表项个数，然后逻辑地址空间有2的16次页数，需要2的16次/2的9次=2的7次张页面数存储所以顶级页表（对应于页目录表）要存储2的7次即128个页表项来映射到这128页。

他人回答：逻辑地址空间的大小注意是2^16页，而页的大小是2^10,所以逻辑地址空间是2^26,所以表中三项一共26位，而页内偏移位占10位，要让页目录号最少，就要让页号最多，而页号最多只能占据一页的容量，也就是2^10/2=2^9，也就是9位，最后26-10-9=7,2^7=128则表示整个逻辑地址空间的页目录表中包含表项的个数至少__牛客网

页目录和页表和页的关系：【OS学习笔记】三十一保护模式九：页目录、页表和页三者的关系详解_杨柳_的博客-CSDN博客_页目录号和页号的区别

解2：

（二刷思路，根据10GB和4KB可得 $10\times 2^{18}$ 个簇，占 $10\times 2^{5}K$ ，又算位图占多少簇，即 $320K / 4KB = 80$ ）

题3：已知系统为32位实地址，采用48位虚拟地址，页面大小为4KB，页表项大小为8B。假设系统使用纯页式存储，则要采用( )级页表，页内偏移( )位。

A.3，12 B. 3，14 C.4，12 D. 4，14

解3：一页2^12B 一个页表项8B 则一页有2^9B个页表项 2^48/2^12 有2^36页需要2^9 * 2^9 * 2^9 * 2^9来装满2^36页所以36/9需要4级页表。注意采用多级页表时，最高级页表项不能超过一页大小。等同于此处

题4：在页式虚存管理系统中，假定驻留集为m个页帧(初始所有页帧均为空)，在长为p的引用串中具有n个不同页号(n>m)，对于FIFO、LRU两种页面置换算法，试给出页故障数的上限和下限,说明理由并举例说明。

解4：发生页故障的原因是，当前访问的页不在主存，需要将该页调入主存。此时不管主存中是否已满（已满则先调出一页)都要发生一次页故障，即无论怎样安排，n个不同的页号在首次进入主存时必须要发生一次页故障，总共发生n次，这是页故障数的下限。虽然不同的页号数为n小于等于总长度p(访问串可能会有一些页重复出现)，但驻留集m<n，所以可能会有某些页进入主存后又被调出主存，当再次访问时又发生一次页故障的现象，即有些页可能会出现多次页故障。最差的情况是每访问一个页号时，该页都不在主存中，这样共发生p次故障。（驻留集：分配的物理页框的集合，工作集：某段时间间隔内，进程要访问的页面集合，工作集窗口：比工作集大且会有重复的页面号）
因此，对于FIFO、LRU置换算法，页故障数的上限均为p，下限均为n。例如，当m=3,p=12,n=4时，有访问串111223334444，则页故障数为4，这是下限n的情况。又如，有访问串123412341234，则页故障数为12，这是上限p 的情况。