北林操作系统2015级教材用书：《操作系统实用教程》第三版 任爱华，王雷
概念题：
实时操作系统：指操作系统能及时(或即时)响应外部事件的请求，和实施任务相结合能在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。
可分为实时处理系统和实时控制系统两类。
主要特点：专用性强，种类多，用途各异，人工干预少；基本特征是事件驱动设计。
分布式操作系统：通过通信网络将物理上分布的具有自治功能的计算机系统互连起来，实现信息交换和资源共享，协作完成任务。处理和控制的分散（相对于集中式系统）是其主要特点。
分布式系统是以计算机网络为基础的，它的基本特征是处理上的分布，即功能和任务的分布。
分布式操作系统的所有系统任务可在系统中任何处理机上运行，自动实现全系统范围内的任务分配并自动调度各处理机的工作负载。
分布式操作系统特点: 系统状态的不精确性；控制机构的复杂性；通信开销引起性能的下降；
嵌入式系统：用于控制、监视或者辅助操作机器和设备的装置。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成,软硬件可裁剪。
嵌入式操作系统：运行在嵌入式智能芯片环境中，对整个智能芯片以及它所操作、控制的各种部件装置等等资源进行统一协调、调度、指挥和控制的系统软件。
原语：由若干条机器指令构成的用于完成特定功能的一段程序。
进程：具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。进程的组成（程序+进程控制块+数据）
线程：是进程的一个实体，是CPU调度的基本单位。（不拥有系统资源，它与同属同一个进程的其他线程共享进程所拥有的全部资源。）
死锁：如果一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称这一组进程或系统此时发生了死锁。
资源：需要排他性使用的对象称为资源。分为可抢占式和不可抢占式。
虚拟存储：虚拟存储器的基本思想是把作业地址空间和实际主存的存储空间，视为两个不同的概念。一个计算机系统采用一定技术为程序员提供了一个足够大的地址空间，而完全不必考虑实际主存的大小。
内存交换：多个程序并发执行，将暂时不能执行的程序送到外存中，从而获得内存空间来装入新程序，或读入达就绪状态的进程。交换单位为整个进程的地址空间。
颠簸（抖动）在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。
文件：是指具有符号名的数据信息的集合。
目录：文件系统层次结构的一个非终结节点，一个目录通常包含有许多目录项，每个目录项可以是一个文件或目录（文件控制块或目录的有序集合）。
用户态和系统态：系统程序工作的状态称为管态或系统态；用户工作的状态称为算态或用户态。
系统调用：指系统为用户程序调用操作系统核心实现系统功能的过程。
逻辑地址、物理地址和地址映射：
1.逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。
2.物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。
3.地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。
内存紧缩(compaction)：将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。
临界区和临界资源:一次仅供一个进程使用的资源。在进程中涉及到临界资源的程序段叫临界区.
物理转储和逻辑转储
① 物理转储：从磁盘的第0块开始，将全部磁盘块按顺序输出到存储设备上，直到最后一块复制完毕。
② 逻辑转储：从一个或几个指定的目录开始，并递归的转储其自给定基准日期后，有所更改的全部文件和目录。
简答题：
1、程序、进程、线程的基本概念及区别
进程：具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。
线程：是进程的一个实体，是CPU调度的基本单位。（不拥有系统资源，它与同属同一个进程的其他线程共享进程所拥有的全部资源）
程序：程序是一组指令的有序集合。
进程与程序的区别：
1、进程-动态，程序-静态：作为程序的执行，进程通常不可在计算机之间迁移；作为有序代码集合，程序对应的文件是静态、和可复制的。
2、进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
3、进程能真实描述并发执行，程序不能：进程是独立调度并能和其他进程并行执行的单位。
4、进程可以创建其它进程，而程序不能；
5、进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。
6、进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
进程和线程的比较
1、 进程是资源分配的基本单位。线程与资源分配无关，它只属于某一个进程，并与进程内其他线程一起共享进程的资源。
2、进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间。
3、进程包含了PCB，用户地址空间和堆栈。线程只由相关的堆栈（用户栈和系统栈）、寄存器和线程控制表TCB组成。
4、进程切换时将涉及到有关资源指针的保存以及地址空间的变化等问题。线程切换时，由于同一进程
内的线程共享资源和地址空间，将不涉及上述内容的保存，故减少了操作系统的开销时间。
5、进程的调度与切换都是由操作系统内核完成，而线程则既可由操作系统内核完成，也可由用户程序进行。
2、进程的组成，基本状态，三状态模型，五状态模型
进程的组成【代码+PCB（进程控制块、进程状态信息）+数据】
代码—程序；资源句柄—分配的资源；寄存器—执行状态；堆栈—运行场景；数据—特定的数据集合
基本状态：就绪态、运行态、阻塞态
（运行、就绪和阻塞三状态模型就是对暂停状态的细化）
就绪态（Ready）：一个进程已经具备运行条件，当调度给其CPU时，立即可以运行；
运行态（Running）：执行状态：
阻塞态（Blocked）：指进程因等待某种事件的发生而暂时不能运行的状态。
其他状态：创建态、结束态
3、临界资源、临界区、临界区访问原则
临界资源:一次仅供一个进程使用的资源。
临界区:在进程中涉及到临界资源的程序段。
临界区的访问原则：
空闲让进：当无进程在临界区时，任何有权使用临界区的进程可进入
忙则等待：不允许两个以上的进程同时进入临界区
多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待
有限等待：任何进入临界区的要求应在有限的时间内得到满足
让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权.
4、四种数据传送控制方式的工作过程：
程序直接控制方式：
外围设备接收到CPU的start命令，开始准备接收或发送数据；
此过程中CPU始终等待设备，反复检测设备的状态；
设备标志位触发器置“done”时，CPU才执行下条指令开始数据传送；
中断方式：
外围设备接收到CPU的start命令，准备数据并将其置入缓冲寄存器；
此过程中CPU调度其他进程执行；
数据缓冲寄存区满后，设备控制器发中断请求，CPU进行中断处理；
DMA方式：
1、进程要求输入数据时CPU把准备存放输入数据的内存始址及要传输字节数分别送入DMA控制器中的内存地址寄存器和字节计数器；另外，将中断允许位和启动位置1，从而启动设备，开始数据输入。
2、当前进程进入阻塞状态， 调度程序调度其它进程执行。
3、输入设备不断地挪用CPU工作周期， 将数据从内部缓冲区源源不断地送入内存，直至所要求的字节数全部传送完毕。
4、DMA控制器在传输完成时发出中断信号， CPU接到中断信号，进行中断处理。
5、中断处理结束后， CPU返回被中断的进程或去运行重新被调度的进程。
通道控制方式
1、 CPU：执行用户程序，当遇到I/O请求时，可根据该请求生成通道程序放入内存，并将该通道程序的首地址放入CAW中；之后执行“启动I/O”指令，启动通道工作。
2、通道：接收到“启动I/O”指令后，从CAW中取出通道程序的首地址，并根据首地址取出第一条指令放入CCW中，同时向CPU发回答信号，使CPU可继续执行其他程序，而通道则开始执行通道程序，完成传输工作。
3、当通道传输完成最后一条指令时，向CPU发I/O中断，并且通道停止工作。CPU接收中断信号，从CSW中取得有关信息，决定下一步做什么。
5、页式、段式、段页式的工作原理及区别
页式管理的基本原理
把用户程序划分成大小相等的页，从0开始编制页号，页内地址是相对于0编址进程。虚拟地址为页号P与页内地址W组成。内存空间也按页的大小划分为大小相等的内存块，以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻，通过页表把作业的各个页面与页框对应起来。
段式管理的基本原理
按程序自身的逻辑关系划分为若干程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。虚拟地址为段号P与段内地址W组成。内存空间被动态的划分为若干个长度不相同的物理段，以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。
段页式管理的基本原理
按程序的逻辑关系划分为段，并有各自的段号s，对于段s中的程序或数据，则按照一定的大小将其划分为不同的页。虚拟地址由段号s，页号p，和页内地址w三个部分组成。将存储空间分成大小固定的页，一个段中的程序或数据在内存中可以分开存放与不相邻的页。
分页与分段的主要区别：
1、段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
2、页的大小固定不变，由系统决定。段的大小是不固定的，它由其完成的功能决定。
3、段式向用户提供的是二维地址空间，页式向用户提供的是一维地址空间，其页号和页内偏移是机器硬件的功能。
4、由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制。
段页式是存储：
每个程序建立一张段表，为每个段又必须建立一张页表；
由于在段页式管理中，页表不再是属于进程，而是属于某个段的，因此，段表中应有专项指出该段所对应页表的起始地址等信息。
6、P/V操作的基本概念及基本工作机制
P(S)：表示申请一个资源 ；
V(S)：表示释放一个资源；
P、V操作的基本概念：P、V操作均为原语操作，执行必须是连续的，在执行过程中不允许被中断。
P、V操作目的：避免在执行临界区操作时会有其它的进程也进入临界区，即实现并发进程间的互斥操作
****P操作：
（1）sem减1；
（2）若sem减1后仍大于等于0，则进程继续执行；
（3）若结果小于0，则该进程睡眠，进入等待队列。
****V操作：
（1）s值加1；
（2）若相加结果大于0，进程继续执行；
（3）否则，唤醒一个等待队列中的进程，然后本进程继续执行。
关于P、V操作：成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；
P、V原语不能次序错误、重复或遗漏。
当为互斥操作时，它们同处于同一进程
当为同步操作时，则不在同一进程中出现
如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前。而两个V操作无关紧要。
信号量的使用：
必须置一次且只能置一次初值；
初值不能为负数；
只能执行P、V操作
S>0表示有S个资源可用
S=0表示无资源可用
S<0则| S |表示S等待队列中的进程个数
(信号量sem：是一个整数，在sem大于等于零时，代表可供并发资源使用的
资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。sem代表
资源的实体。)
优点：简单且表达能力强，用P.V操作可解决任何同步互斥问题
缺点：不够安全；P.V操作使用不当会出现死锁；
遇到复杂同步互斥问题时实现复杂
看PV操作实例的代码！！
7、连续、随机、串联的文件保存方式
文件的保存方式：
连续文件（顺序结构）
文件的信息存放在若干连续的物理块中。
优点：简单；支持顺序存取和随机存取；顺序存取速度快；所需的磁盘寻道次数和寻道时间最少
缺点：文件不能动态增长；不利于文件插入和删除；外部碎片问题
串联文件（链接结构）
文件的信息存放在若干连续的物理块中，通过指针链接，前一个物理块指向下一个物理块。
优点： 提高空间利用率；有利于文件动态扩充；有利于文件插入和删除；不存在外部碎片问题
缺点：不适于随机存取；存取速度慢；更多的寻道次数和寻道时间；可靠性问题，如指针出错；链接指针占用一定的空间
随机文件（索引结构）
一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个索引表，并将这些块的块号存放在索引表中。
优点：
1.即能顺序存取，又能随机存取
2. 有利于文件动态扩充
3.有利于文件插入和删除
4. 不存在外部碎片问题
缺点：
1.较多的寻道次数和寻道时间；
2.索引表本身带来了系统开销；
8、操作系统的各项基本功能以及操作系统的发展阶段
操作系统的功能 :处理机管理、存储管理、设备管理、文件管理、用户接口。
功能一、处理机管理
进程控制：创建、撤销、改变进程的状态
进程调度：作业和进程的运行切换，以充分利用处理机资源和提高系统性能；
进程同步：协调并发进程之间的推进步骤，以协调资源共享；
进程通信：进程之间传送数据，以协调进程间的协作；
功能二、存储管理：
目标：提高利用率、方便用户使用、提供足够的存储空间、方便进程并发运行。
存储分配与存储无关性：地址重定位（地址映射）
存储保护：保证进程间互不干扰、相互保密；
存储扩充：提高主存利用率、扩大进程的主存空间；
功能三、设备管理：
目标：方便设备使用、提高CPU与I/O设备利用率；
设备无关性：提供统一的I/O设备接口；
设备分配与回收：在多用户间共享I/O设备资源。
虚拟设备：设备由多个进程共享，每个进程如同独占。
设备的传输控制：利用设备驱动程序完成对设备的操作。
功能四、文件管理：
目标：解决软件资源的存储、共享、保密和保护。
文件存储空间管理：解决如何存放信息，以提高空间利用率。
目录管理：解决信息检索问题，方便用户按名存取。
文件的读写管理和存取控制：解决信息安全问题。
软件管理：软件的版本、相互依赖关系、安装和拆除等。
功能五、用户接口：
目标：提供一个友好的用户访问操作系统的接口。
系统命令：供用户用于组织和控制自己的作业运行。
编程接口：供用户程序和系统程序调用操作系统功能。
图形接口：窗口、菜单和对话框
操作系统发展史：
（1）1946-50年代：无操作系统时代，工作环境 是电子管计算机
（2）50-60年代：单道批处理系统
（3）60年代中-70年代：多道批处理系统
（4）70年代中期至今：分时系统-个人计算机
9、文件系统的层次结构
10、安全设计原则
① 应该公开系统设计方案。
② 默认规则应该是不能访问。
③ 检查当前权限。
④ 给每个进程尽可能小的权限。
⑤ 保护机制应该简单。
⑥ 所选的安全方案应该是心理上可接受的。
⑦ 设计尽可能简单。
11、文件备份的考虑问题和因素
处理两个潜在问题：从意外的灾难中恢复，从愚蠢的操作中恢复。
考虑的因素：
备份整个文件系统还是仅一部分
增量转储结合周期性的全面的转储
备份前进行压缩操作
对当前活动的文件进行转储比较困难，即备份时发生增删修改等操作
要面临许多非技术问题，例如，人员的行为管理
12、多媒体进程调度(详见第八章)
① 调度同质进程：固定数目的电影，所有电影使用相同的帧率、视频分辨率、数据率以及其他参数。所有进程同等，轮换调度，加上定时机制老保证每个进程以恰当的帧率传输。
② 一般实时调度：实际中，电影数目，压缩后的帧大小分辨率等差异大。多个相互竞争的进程，其中若干进程或全部进程具有必须满足的最终时限的调度成为实时调度。特点：最终时限使得存在抢先的特性。有时并不一定存在可调度的方案。
③ 速率单调调度：静态的实时调度算法。满足条件：每个周期性进程必须在其周期内完成。没有进程依赖于任何其他进程。每一个进程再一次突发中需要相同的CPU时间量。任何非周期性进程都没有最终时限。进程抢先即刻发生而没有系统开销。
④ 最早最终时限优先调度：一种动态算法，不考虑周期性，不考虑每个CPU突发有相同的时间。只要一个进程需要CPU时间，它就宣布它的到来和最终时限。调度程序维护一个可运行进程的列表，该列表按照最终时限排序。edf算法运行列表中的第一个进程。新进程就绪，检查是否最终时限在当前运行进程结束之前，如果是，则新进程抢占CPU
13、死锁的产生原因和必备条件
原因：系统资源不足；进程推进顺序不合适；
必要条件 ：
- 互斥控制（资源独占）
- 非剥夺控制（不可剥夺）
- 请求和保持（部分分配，占有申请）
- 环路条件（循环等待）
14、多处理机系统的三种典型结构（详见第八章）
共享存储器的多处理机；主从多处理机；对称多处理机
15、逻辑地址、物理地址以及地址映射的基本过程
逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。
– 其首地址为0，其余指令中的地址都相对于首地址来编址。
– 不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。
地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。
– 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。
16、与实验有关的经典同步/互斥问题
同步：进程之间的一种通信方式，有时序上的制约关系，或者说是进程之间为了协同工作而存在的一种等待关系。
互斥：进程之间对临界资源的一种竞争关系，排他性地对资源的访问方式。
(生产者与消费者/ 读者与写者)
17、各种经典的调度算法
① FCFS先来先服务
② SJF短作业优先
③ HRF高响应比优先
④ HPF高优先级优先
⑤ 资源均衡型调度
18、中断执行的过程
19、系统调用与普通调用的区别：
相同点：
改变指令流程
重复执行和公用
改变指令流程后需要返回原处同
不同点：
系统调用是动态调用，而CALL调用方式是静态调用；
执行状态不同
内部实现过程不同
与进程调度的关系不同：
嵌套或递归调用
计算题
【例1】下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）
| 作业号 | 提交时间 | 运行时间 |
|---|---|---|
| 1 | 0.0 | 8.0 |
| 2 | 0.4 | 4.0 |
| 3 | 1.0 | 1.0 |
解：采用先来先服务调度策略，则调度次序为l、2、3。
| 作业号 | 提交时间 | 运行时间 | 开始时间 | 完成时间 | 周转时间 |
|---|---|---|---|---|---|
| 1 | 0.0 | 8.0 | 0.0 | 8.0 | 8.0 |
| 2 | 0.4 | 4.0 | 8.0 | 12.0 | 11.6 |
| 3 | 1.0 | 1.0 | 12.0 | 13.0 | 12.0 |
平均周转时间T＝（8＋11.6＋12）/3＝10.53
采用短作业优先调度策略，则调度次序为l、3、2。
| 作业号 | 提交时间 | 运行时间 | 开始时间 | 完成时间 | 周转时间 |
|---|---|---|---|---|---|
| 1 | 0.0 | 8.0 | 0.0 | 8.0 | 8.0 |
| 3 | 1.0 | 1.0 | 8.0 | 9.0 | 8.0 |
| 2 | 0.4 | 4.0 | 9.0 | 13.0 | 12.6 |
平均周转时间T＝（8＋8＋12.6）/3＝9.53
【例2】在一个单道的程序设计系统中，有3个作业J1、J2、J3，它们到达输入井的时间分别为8：50、9：00、9：30，它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在10：00按响应比高者优先算法对它们进行调度，请回答：
（1）作业被选中执行的次序是什么？ （2）作业被选中时的响应比分别是多少？
分析： 响应比＝作业周转时间/作业运行时间 ＝1＋作业等待时间/作业运行时间
系统在10：00，计算作业的响应比：
以J1为例，它的作业计算时间是1.5小时，即90分钟；J1从8：50到达输入井，在10：00时刻，J1的等待时间为70分钟，因此作业J1的响应比为：
1＋70分钟/90分钟=1.77
同理，J2：1＋60分钟/24分钟=3.5 J3：1＋30分钟/60分钟=1.5
因此按照响应比高者优先算法，优先调度J2。
在10：24，J2完成。这时计算J1、J3的响应比：
J1：1＋（70＋24）分钟/90分钟=2.04 J3：1＋（30＋24）分钟/60分钟=1.9
按照响应比高者优先算法，优先调度J1。
在11：54，J1完成，系统调度J3，J3的响应比为
1＋（30＋24＋90）分钟/60分钟=3.4
因此，作业被选中执行的次序是J2、J1、J3。
三个作业被选中时的响应比分别是：J1，2.04；J2，3.5；J3，3.4。
解：（1）作业被选中执行的次序是J2、J1、J3。
（2）三个作业被选中时的响应比分别是：J1，1.04；J2，2.5；J3，2.4。
【例3】设有进程A、B、C、D依次进入就绪队列（相隔一个时间单位），它们的优先级（优先数大的优先级较高）如下表所示：
| 进程 | CPU时间 | 优先数 |
|---|---|---|
| A | 20 | 3 |
| B | 15 | 1 |
| C | 8 | 4 |
| D | 10 | 3 |
求采用“先来先服务”、“静态优先数法”调度算法（注：优先数大的优先级高），选中进程的执行次序。
解：采用先来先服务调度算法，按照进程进入就绪队列的先后次序占有CPU，其执行次序是A-B-C-D。
采用静态优先数法，进程A最先就绪，在0时刻先占有CPU运行，随后1时刻进程B进入就绪队列，2时刻进程C进入就绪队列，3时刻进程D进入就绪队列。由于采用静态优先数法，不容许随时间的推移改变进程的优先级，所以当进程A运行结束时，系统的就绪队列中有B、C、D三个进程，而进程C优先级最高，于是选中C；这样分析下去，进程的执行次序是A-C-D-B。
【例4】在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096字节,现有一逻辑地址为2F6AH,且第0, 1, 2页依次存放在物理块5, 10 ,11中,问相应的物理地址为多少?
解:由题目所给给条件可知,本页式系统的逻辑地址结构为:
页号P,页内位移W
逻辑地址2F6AH的二进制表示如下:
| P | W |
|---|---|
| 0010 | 111101101010 |
由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中,用十六进制表示志号为B,所以物理地址为BF6AH.
【例5】（南开大学1994年试题）在采用页式存储管理的系统中，默作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映象表（即页表）如下：
| 页号 | 块号 |
|---|---|
| 0 | 2 |
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
试借助地址变换图（即要求画出地址变换图）求出有效逻辑地址4865所对应的物理地址。
解：在本题中，一页大小为2048字节，则逻辑得志4865的页号机页内位移:为：
页号： 4865/2048=2
页内位移 4865-2048x2=769
然后，通过页表查知物理块号为6，将物理块号与逻辑地址中的页内位移拼接，形成物理地址，即：6*2048+769=13057
【例6】考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问： （1）逻辑地址需要多少二进制位表示？ （2）物理地址需要多少二进制位表示？
分析 在分页存储管理中，逻辑地址结构如下图所示。
它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页内位移）d。页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳的页面数为220，即1MB个页面。页内地址位数确定了每页的大小，若页内地址为12位，则每页大小为212，即2KB。
同理，物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。
解 因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节， 1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。
（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。
（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。
【例7】若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。
| 页号 | 块号 |
|---|---|
| 0 | 2 |
| 1 | 3 |
| 2 | 1 |
| 3 | 6 |
分析 页式存储管理的地址结构是一维的，即逻辑地址（或物理地址）只用一个数值即可表示。若给定逻辑地址A，页面的大小为L，则页号p和页内地址d可按照下式求得： p=int [A/L] d=A mod L
其中，int是取整函数（取数值的整数部分），mod是取余函数（取数值的余数部分）。
物理地址的计算公式为：
物理地址＝块的大小（即页的大小L）x 块号f＋页内地址d
解: 本题中，为了描述方便，设页号为p，页内位移为d，则：
（1）对于逻辑地址1011，p＝int（1011/1024）＝0，d＝1011 mod 1024＝1011。查页表第0页在第2块，所以物理地址为1024*2＋1011＝3059。
（2）对于逻辑地址2148，p＝int（2148/1024）＝2，d＝2148 mod 1024＝100。查页表第2页在第1块，所以物理地址为1024＋100＝1124。
（3）对于逻辑地址4000，p＝int（4000/1024）＝3，d＝4000 mod 1024＝928。查页表第3页在第6块，所以物理地址为1024*6＋928＝7072。
（4）对于逻辑地址5012，p＝int（5012/1024）＝4，d＝5012 mod 1024＝916。因页号超过页表长度，该逻辑地址非法。
【例8】某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：
| 页号 | 物理块号 |
|---|---|
| 0 | 5 |
| 1 | 10 |
| 2 | 4 |
| 3 | 7 |
问：逻辑地址0A5C（H）所对应的物理地址是什么？
分析 页式存储管理的逻辑地址分为两部分：页号和页内地址。
由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。
逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。
解 逻辑地址0A5C（H）所对应的物理地址是125C（H）。
【例9】 设一计算机系统有输入机一台、打印机两台，现有二道程序同时投入运行，且程序 A 先开始运行，程序 B 后运行。程序 A 的运行轨迹为：计算 50ms，打印信息 100ms，再计 算 50ms ,打印信息 100ms ,结束。程序 B 运行的轨迹为：计算 50ms，输入数据 80ms，再 计算 100ms，结束。要求： (1) 用图画出这二道程序并发执行时的工作情况。 (2) 说明在二道程序运行时，CPU 有无空闲等待？若有，在哪段时间内等待？为什 么会空闲等待？ (3) 程序 A、B 运行时有无等待现象？在什么时候会发生等待现象？
【例10】 LRU 和 FIFO （看PPT吧。。）
页面置换算法
1.先进先出置换算法
2.最近最久未用置换算法(LRU)
3.近似的LRU算法（NRU算法）
在一个请求分页系统中,假如一个作业的页面走向为：1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。当分配给该作业的物理块数为4时,分别采用最佳置换算法、LRU和FIFO页面置换算法,计算访问过程中所发生的缺页次数和缺页率。
程序题
P/V 操作:
// 请复习生产者和消费者的实验 ！！！
procedure P(var s:samephore);
{
s.value=s.value-1;
if (s.value<0)
asleep(s.queue);
}
procedure V(var s:samephore);
{
s.value=s.value+1;
if (s.value<=0)
wakeup(s.queue);
}
/*
asleep(s.queue）：执行此操作的进程的PCB进入s.queue尾部，进程变成等待状态
wakeup(s.queue）：将s.queue头进程唤醒插入就绪队列
s.value初值为1时，可以用来实现进程的互斥。
*/
例题
设公共汽车上，司机和售票员的活动分别如下：
司机的活动：启动车辆：正常行车；到站停车。
售票员的活动：关车门；售票；开车门。
在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。
分析
答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。
应设置两个信号量：s1、s2；s1表示是否允许司机启动汽车(其初值为0)；s2表示是否允许售票员开门(其初值为0)。
用P、V原语描述如下：
var s1,s2：semaphore;
s1 = 0; s2 = 0;
cobegin
{
driver();
busman();
}
coend
driver ()
begin
while (1)
{
P(s1);
启动车辆;
正常行车;
到站停车;
V(s2);
}
end
busman()
begin
while (1)
{
关车门;
V(s1);
售票;
P(s2);
开车门;
上下乘客;
}
end
