2024年2月26日发(作者：)
填 空
绪论：批处理系统、分时系统、实时系统的概念与特点，原语与原子操作。
1.批处理操作
（1）单道批处理系统概念
单道批处理系统是指系统通过作业控制语言将作业组织成批，使其能自动连续运行，但是，在内存中任何时候只有一道作业的系统。
单道批处理系统特征
顺序性 单道性 自动性
（2）多道批处理系统概念
系统对作业的处理是成批进行的，并且在主存中能同时保留多道作业的系统。多道批处理系统的主要目标是提高系统吞吐率和各种资源的利用率。
多道批处理系统特征
无序性 多道性 调度性
2.分时系统
（1）概念
分时操作系统是指在一台主机上连接了多个联机终端，并允许多个用户通过终端以交互的方式使用主计算机，共享主机资源的系统。
（2）分时系统的主要目标是实现人与系统的交互性。分时系统设计的目标是保证用户响应时间的及时性。
（3）分时系统的特征
多路性 独立性 及时性：满足用户对响应时间的要求 交互性
3.实时操作系统
（1）概念
实时操作系统是指系统能够及时响应外部（随机）事件的请求，并能在规定的时间内完成对该事件的处理，控制系统中所有的实时任务协调一致地工作。
（2）实时操作系统的特征
多路性 独立性 及时性：满足实时任务截止时间的要求 交互性 可靠性
4.原语：操作系统内核或微核提供核外调用的过程或函数称为原语，是由若干条指令构成，用于完成特定功能的一段程序。原语在执行过程不允许被中断。
5.原子操作：执行中不能被其它进程（线程）打断的操作就叫原子操作。当该次操作不能完成的时候，必须回到操作之前的状态，原子操作不可拆分。
进程管理：什么是进程？进程与程序的区别与联系？进程的特征有哪些？进程之间的关系有哪些？什么是信号量？信号量的物理含义？
1.进程定义
可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的基本单位。
2.进程特征
（1）动态性 （2）并发性 （3）独立性 （4）异步性 （5）结构特征：
3.进程与程序的关系
（1）程序是一组指令的集合，是静态的概念；进程是程序的执行，是动态的概念。(本质区别)
（2）进程有生命周期，它的存在是暂时的；程序的存在是永久的。
（3）进程包括程序代码、数据和“进程控制块”三部分。
（4）进程是一个独立的运行单位，是系统进行资源分配和调度的独立单位。
（5）一个程序在执行中可对应多个进程，一个进程也可能包含多个程序段。
4，进程的基本状态
（1）运行状态（Running):已得到CPU，正在执行的状态。
（2）就绪状态（Ready)：得到了除CPU以外的所有资源，正在等待CPU的状态。
（3）等待状态（Blocked，也称阻塞状态）：进程等待某一事件的发生而暂时停止运行的状态。
5. 进程之间的关系有哪些
同步 互斥
6.什么是信号量？
信号量是实现进程同步的一种变量。是一种有效的进程同步工具，可分为：整型信号量 、结构型信号量 、信号量集等。
7.信号量的物理含义
S>0表示有S个资源可用
S=0表示无资源可用
S<0则| S |表示S等待队列中的进程个数
P(S):表示申请一个资源
V(S)表示释放一个资源。信号量的初值应该大于等于0
设备管理：设备的分类
按数据传输单位，设备可分成：
字符设备（输入输出设备）：字符设备中存储和传送的是不定长的数据，是以字符为单位发送或和接收一个字符流，传输速度低、不可寻址(源地址或目标地址)。如打印机、键盘、网卡和显示器等。
块设备（存储设备）：块设备中存储是定长的、且可随机访问的数据块，每个块都有自己的地址，信息处理的基本单位是数据块，传输速度高、可寻址。如磁盘，CD-ROM。
按传输速率，设备可分成：
低速——键盘、鼠标器、语音的输入和输出设备
中速——行式打印机、激光打印机
高速——磁带机、磁盘器、光盘机
按共享属性，设备可分成：
独占设备：一次只允许一个进程访问的设备。
共享设备：一段间内允许多个进程同时访问的设备。
虚拟设备： 虚拟技术将一台独占设备转换为若干台逻辑设备，共多个进程同时使用。
按使用属性，设备可分成：
存储设备：相同中存储信息的主要设备，外存及后备存储器。
人机交互设备（输入/输出设备）：输入、输出和集成输入和输出的设备。
文件管理：什么是文件的逻辑结构和文件的物理结构？文件的逻辑结构有哪些？文件的物理结构有哪些？
1.文件的逻辑结构
（1）概念
是指用户可以直接处理的文件组织形式，也称文件组织。文件逻辑结构选取的主要考虑因素：存取速度、维护方便和可靠性等。
（2）分类
从逻辑结构上，文件分为：有结构文件（记录式文件）和无结构文件（字符流文件，是一种顺序文件。）
有结构文件（记录式文件）
①根据文件中记录特性分：定长记录文件 变长记录文件
②文件的组织方式（逻辑结构）：顺序文件 索引文件 索引顺序文件
2.文件物理结构
（1）概念
是指文件在外存上的存储结构，也称文件存储结构。文件的物理结构决定了文件信息在存储设备上的存放位置。
（2）物理结构的类型
连续文件 串联文件（链接文件） 索引文件 hash文件
简 答
1.进程的概念与特点、进程的同步与互斥。
进程概念
关于进程的定义有多种，其中最具代表性的定义有以下几个：
（1）进程是程序的一次执行
（2）进程是可以与别的计算并发执行的计算
（3）进程是一数据结构及能在其上进行操作的一个程序
（4）进程是一个程序及其数据在处理机上顺序执行时所发生的活动
（5）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位
进程特征
（1）动态性：动态性是进程的基本特性。进程具有生命周期，它由创建而产生，经调度而执行，由撤消而消亡。
（2）并发性：在内存中的多个进程实体能在一段时间内同时运行。
（3）独立性：进程是系统进行资源分配和调度的一个基本单位，是一个能够进行独立运行的基本单位。
（4）异步性：每个进程在运行时都在以不可预知的速度向前推进。
（5）结构特征：进程实体实际上是由三部分所组成：程序段、数据段和进程控制块PCB。在UNIX系统中，也把这三部分称为“进程映像”。
进程同步与互基本概念
（1）并发进程之间的协作控制通常称为进程同步。——直接制约关系（协作）
（2）并发进程之间的竞争控制通常称为进程互斥。——间接制约关系（竞争）
进程同步与互斥的主要任务就是保证多个并发进程能有效地合作并共享系统资源，使并发进程的执行结果具有可再现性。
2.死锁的概念、死锁产生的原因、死锁的预防和避免方法、资源分配图的简化、死锁定理。
（1）死琐概念
死锁是指多个并发执行的进程因资源争夺而出现的一种彼此都不能继续向前推进的僵持局面。
（2）产生死琐的原因
①竞争资源——竞争非剥夺性资源（如，打印机）和竞争临时资源（如，某进程生产的数据、消息）
②进程推进的顺序非法
（3）死琐的预防
①避开“ 请求和保持”条件：一次性请求，一次性分配。在进程运行期间不再提出资源请求。这种方法也称“预先静态分配法”。
②避开 “不剥夺”条件：进程逐个提出资源请求，当前请求不能满足时，必须释放它所拥有的全部资源。
③避开“环路等待”条件：将所有资源按类型进行线性排队，并赋予不同序号，要求进程申请资源时按序号递增的次序提出。这种方法也称“有序资源分配法”。
（4）死锁的避免——银行家算法，死锁的预防——资源有序分配法。
（5）资源分配图的简化
从图找一个进程结点pi，若它对资源Rj（1≤j≤m）的请求满足（既非阻塞也非孤立）：
abs(Pi,Rj) +
其中：Wj表示j类资源的总数，（Pi,Rj）表示进程Pi申请j类资源的数量，（ Rj, pk）表示分配给进程Pk的j类资源数。
简化操作：
①释放pi所占有的资源，即去掉它所有的请求边和分配边使其成为一个孤立结点。
②重复执行前两步，直到找不到满足条件的进程结点为止。
（6）死锁定理
系统状态S为死锁状态的充分条件，当且仅当S状态的系统资源分配图是不可完全简化的。（至少有一个进程结点不能简化为孤立结点。）该充分条件被称为死锁定理。
3.文件的多级目录结构（文件的物理结构、文件控制块、索引节点等）
文件物理结构
（1）概念
是指文件在外存上的存储结构，也称文件存储结构。文件的物理结构决定了文件信息在存储设备上的存放位置。
（2）物理结构的类型
连续文件 串联文件（链接文件） 索引文件 hash文件
文件控制块
（1）概念
是文件存在的标志，为提高查找速度，通常把FCB集中起来组织成文件目录(目录文件)。目录项分两种：子目录和文件的FCB。一个文件由FCB和文件体（文件内容）两部分组成。
FCB是操文件系统为每个文件建立的唯一管理数据结构，FCB主要包括下列信息：
文件标识符和控制信息：文件名、用户名、存取权限、文件类型和文件口令等
逻辑结构信息：记录类型、记录个数和记录长度等
物理结构信息：设备号、文件物理结构类型、文件索引位置等
使用信息：共享进程数、文件最大长度、当前大小和修改情况等
管理信息：文件的建立日期、访问日期和保留期限等
（2）文件目录
一个文件系统中所有FCB的有序集合称为文件目录。一个FCB就是一个文件目录项。一个文件目录也被看作是一个文件，称为目录文件。
（3）索引结点（i结点）
是由除文件名外的其他文件描述信息所构成的一种数据结构。
为什么要引入索引结点？
①文件目录占用大量的盘块，检索时间长
②在检索目录文件过程中只用到文件名
种类
①磁盘索引结点
存放在外存上的索引结点。基本信息包括：文件主标识符、文件类型、文件存取权限、文件物理地址（磁盘上的地址）、文件长度、和文件存取时间等信息。
②内存索引结点
存放在内存上的索引结点。内存索引结点包含磁盘索引接点的全部信息，并增加内存索引结点编号、状态、
访问计数、文件所属的逻辑设备号和链接指针等信息。
（4）文件的目录结构
①单级目录结构
整个文件系统只建立一张目录表，每个文件在目录表中占有一目录项。
缺点：
查找速度慢
不允许重名
不方便实现文件共享
②两级目录结构
在系统中建立一个主文件目录MFD，同时还为每个用户建立一用户文件目录UFD。
优点：
解决了文件的重名问题和文件共享问题----用户名|文件名
提高了目录检索的速度，降低查找时间
缺点：增加了系统开销
③树型目录结构（多级）
在两极目录的基础上，允许用户创建自己的子目录，子目录创建自己的子目录，依次类推。
优点：层次结构清晰，便于管理和保护；有利于文件分类；解决了文件的重名问题；提高了文件的检索速度；能进行存取权限的控制
缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响存取速度。
4.磁盘调度（磁盘调度方法：FCFS、SSTF，SCAN）
（1）先来先服务FCFS
根据进程请求访问磁盘的先后次序进行调度。
缺点：平均寻道时间长
（2）最短寻道时间优先SSTF
选择与当前磁头所在的磁道距离最近的磁盘访问请求服务。
缺点：出现“饥饿”现象。
（3）扫描（SCAN）算法（电梯调度算法）
首先考虑磁盘请求的磁头移动方向，在方向一致的情况下选择与当前磁头最近的磁盘请求服务。若同方向没有请求，磁头转向反方向移动。
寻道时间Ts（启动磁臂时间s+磁头移动时间） Ts=m×n+s (移动n条磁道)
旋转延迟时间 Tr=12r 传输时间Tt =bRn
其中，b为传输的字节数，N为一条磁道上的字节数，r为磁盘每秒的转数。
5.虚拟设备、缓冲技术、SPOOLING系统
虚拟设备
操作系统使用共享设备来模拟独占设备的操作，经过操作系统虚拟技术处理后的设备称为虚拟设备。
在虚拟设备环境中，一个独占设备可以允许两个或两个以上的进程并行使用，并且每个进程都感觉在独占使用该设备。
缓冲技术
（1）为什么要引入缓冲技术
缓和CPU和I/O设备之间速度不匹配的矛盾
减少对CPU的中断次数。
提高CPU和I/O设备之间的并行性
（2）缓冲的种类
单缓冲 双缓冲 循环缓冲 缓冲池
SPOOLing系统
SPOOLing技术是实现虚拟设备以提高独占设备利用率的技术 ，也是一种以空间换时间的技术。
SPOOLing 技术是在批处理操作系统时代引入的，即假脱机输入输出技术。把这种技术实质就是对输入／输出数据成批处理。
（1）概念
SPOOLing 技术是指在联机情况实现的同时外围操作，也称假脱机操作。它通过共享设备来模拟独占设备的动作，使独占设备成为共享设备，也称为虚拟设备技术。
（2）SPOOLing 技术实现原理
SPOOLing输入————作业预输入（输入机输入井）
SPOOLing输出————作业缓输出（输出井输出机）
由SPOOLing程序控制通道完成
（3） SPOOLing 系统的组成
①输入井和输出井（外存：暂存I/O设备传送的数据）
②输入缓冲区和输出缓冲区（内存：匹配CPU与磁盘之间速度不匹配的矛盾）
③输入进程和输出进程（假脱机进程）
（4） SPOOLing 系统的优点与缺点
优点：
①提高了I/O速度。用户程序对慢速独占设备的独占时间大大缩短了，提高了慢速独占设备的利用率；
②用户程序本身的执行时间大大缩短了,提高了系统吞吐量和资源的利用率。
③使独占设备成为共享设备，实现了虚拟设备的功能。
缺点：必须有高速、大容量和可随机存取的外存的支持。
综合应用题
1. 多道系统、作业调度、进程调度、抢占式调度、非抢占式调度、周转时间、带权周转时间
（1）概念
作业调度：是指按一定的作业调度算法，从外存的后备作业队列中选择若干个作业调入主存的过程。
进程调度：按一定的进程调度算法，从已在内存的进程中选择一个进程并把CPU分配给它的过程。
作业周转时间：从作业提交进入系统到结束退出系统所经历的一段时间。
平均周转时间：多道作业周转时间的平均值。
系统吞吐量(吞吐率)：单位时间系统所完成的总工作量（一般用作业数表示）。
（2）调度可分为三个层次：
作业调度：也称高级调度或长期调度，决定每次接收多少个作业和接纳哪些作业的问题。
交换调度：主要负责内外存上的进程交换。一般通过“挂起”和“解挂”的方法来实现，也称“中期调度”。
进程/线程调度：将处理器分配给一个或多个进程/线程的调度方法，也称“低级调度”和“短期调度”和“处理器调度”。
带权周转时间=周转时间/运行时间
例1：先来先服务调度（非抢占）
在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示，请计算其平均周转时间T和平均带权周转时间W。
执行提交时运行时等待时开始时完成时周转时带权周转作业 提交时刻 运行时间
次序 刻 间 间 刻 刻 间 时间
1 8.0 1.0
1 8.0 1.0 0
2 8.5 0.5
2 8.5 0.5 0.5
3 9.0 0.2 0.5
3
4
9.0
9.1
0.2
0.1
例2：若采用抢占的 高优先级调度算法，进程的调度次序是什么？（假定优先数越小的作业，优先权越高。）
作业 提交时刻 运行时间 优先数
1
2
3
4
8.0
8.5
9.0
9.1
1.0
0.5
0.2
0.1
3
1
2
1
时间：8.0 8.5 9.0 9.1 9.2 9.3 9.8
作业： 1 2 3(2) 4 3(4) 1(3)(1)
例3：短作业优先调度（短作业优先调度算法产生的平均周转时间短，系统吞吐量大。非抢占）
作业 提交时刻 运行时间
1
2
3
4
8.0
8.5
9.0
9.1
1.0
0.5
0.2
0.1
执行提交
次序 时刻
1
3
4
8.0
9.0
9.1
运行
时间
1.0
0.2
0.1
开始
时刻
完成时周转时带权周转时刻 间 间
2 8.5 0.5
作业平均周转时间
作业平均带权周转时间
例4：最短剩余时间优先调度（最短作业优先调度算法产生的平均周转时间最短，系统吞吐量最大。抢占式）
作业 提交时刻 运行时间
1
2
3
4
8.0
8.5
9.0
9.1
1.0
0.3
0.2
0.1
执行提交
次序 时刻
1
3
8.0
9.0
运行
时间
1.0
0.2
开始
时刻
完成时周转时带权周转时刻 间 间
4 9.1 0.1
2 8.5 0.3
作业平均周转时间
作业平均带权周转时间
例5：时间片轮转调度算法（是一种基于时间片的抢占式调度算法。）
假定系统规定的时间片大小为0.3，不考虑切换开销。作业提交情况如下表所示：
作业 提交时刻 运行时间
1
2
8.0
8.1
1.0
0.5
执行次 序
1
2
提交时 运行时间 运行及 周转 带权周刻
完成时刻
时间 转时间
8.0
8.0
1.0
0.5
3
4
8.2
8.3
0.2
0.1
例6：高响应比调度（非抢占）
响应比Rp= 等待时间+要求服务时间 = 响应时间
要求服务时间 要求服务时间
作业 提交时刻 运行时间
1
2
3
4
8.0
8.5
9.0
9.1
1.0
0.5
0.2
0.1
执行提交时刻 运行时 等待时 开始时 完成时 周转时 带权周转
次序 间 间 刻 刻 间 时间
1
2
8.0
8.5
1.0
0.5
3 9.0 0.2
4 9.1 0.1
作业平均周转时间
作业平均带权周转时间
eg1：在一个具有两道作业的批处理系统中，作业调度采用短作业优先的调度算法，进程调度采用优先数为基础的抢占式调度算法（作业优先数即为进程优先数，优先数越小优先权越高），忽略进程切换和调度开销。问题：根据下表求它们的平均周转时间。
作业名 到达时间 运行时间 优先数
执行提交 运行 优先数 运行及 周转 带权周转A 10：00 40分钟 5
次序 时刻 时间 完成时刻 时间 时间
B 10：20 30分钟 3
A 10:00 40分5
C 10：30 50分钟 4
钟
D 10：50 20分钟 6
B 10:20 30分3
钟
C 10:30 50分4
钟
D 10:50 20分6
钟
作业平均周转时间
作业平均带权周转时间
eg2:在某多道程序系统中，用户当前可使用的系统资源：内存空间100K，磁带机2台，打印机1台。系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入输出操作的时间忽略不计。假设作业调度采用先来先服务算法，内存分配采用首次适应算法且不准移动已在内存中的作业，进程调度采用短作业优先的调度算法。作业序列情况如下表。
作业号 提交时间 运行时间 内存需求 申请磁带机 打印机
1
2
3
4
5
8：00
8：20
8：20
8：30
8：35
30分钟
10分钟
20分钟
20分钟
15分钟
15K
30K
60K
20K
10K
1
0
1
1
1
1
1
0
0
1
问题：
（1）求作业调度的次序，并给出每道作业进驻内存的时刻（5分）。
（2）计算每道作业的周转时间（5分）。
解：（1）（5分）
作业调度的顺序：1→3→4→2→5
进驻内存的时刻分别为：8：00，8：20，8：30，
8：50，9：00 „„(5分)
（2）（5分）
作业的周转时间=作业的完成时间 - 作业到达系统的时间。
每道作业的周转时间如下：1号作业：30（分钟） 2号作业：40（分钟） 3号作业：30（分钟） 4号作业：65（分钟） 5号作业：40（分钟）
2. 虚拟页式存储器管理系统（页表、快表、虚地址、物理地址、快表命中、页表命中、页面淘汰算法（LRU、CLOCK），驻留集、置换策略、抖动、缺页中断）
（1）页表：放在系统空间的页表区，存储逻辑页与物理页帧之间的对应关系。每个进程的PCB表中有一个指向页表的指针，即每一进程拥有一张页表。
有效地址结构：
逻辑地址 = p(页号)*页面大小+d(页内位移) 物理地址 = f(页帧号) )*页面大小+d(同上)
p = 线性逻辑地址 / 页面大小； d = 线性逻辑地址 - p*页面大小。
例如：页面的大小为1KB，求逻辑地址4101的页号和页内位移。
15 14 13 12 11 10 9 6 5 3 1
8 6 4 2 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1
得到页号p=4，页内位移d=5
进程被调度占用CPU时，进程页表始址被装入页表地址寄存器。
例如：有一个32位的分页存储器管理系统，页面的大小规定为1KB，每个页表项占4个字节，求页表所占的最大内存空间？
32位计算机系统的逻辑地址空间应是232，页表长度（页表项的个数）为：
232/ 210=222
页表所占的内存空间：222×22=224个字节，即16MB。
（2）快表：由一组高速缓冲寄存器组成，用来存放当前访问过的页表项，以减少地址转换过程中的时间花费。
快表的表目结构：
页号 物理块号 进程号 访问权限
（3）命中率：选用8-12项组成的联想存储器，并采用适当的替换策略，在联想存储器中匹配成功的可能性可达80-90%。
（4）等效访问时间：设访问主存时间为750ns，搜索联想存储器的时间为50ns，若联想存储器的命中率为80%，则一次访问主存的平均时间为（假设先查联想存储器再查页表）：
80% *（750+50）+ 20% *（750+50+750）= 950ns
（5）虚拟地址：在虚存管理系统中，通常把运行进程访问的指令和数据的逻辑地址（目标程序中的相对地址）称为虚拟地址。虚拟地址的集合称为虚拟地址空间或逻辑空间。
（6）实地址：主存储器单元的实际地址。主存也称为实地址空间或物理空间。
（7）最近最久未使用（LRU）算法
原理
根据页面在内存中的使用情况，选择最近最久未使用的页面予以淘汰。即以“最近的过去”预测“最近的将来”，即淘汰上次使用距当前最远的页。
栈实现的LRU法——存放当前使用的各页面的页号。
实现原理：当进程访问某页时，就将该页的页号从栈底移出压入栈顶，或将新访问的页号压入栈顶。处于栈底的就是最近最久未使用的页面号。
（7）时钟（Clock）页面置换算法
将二次机会置换算法中的FIFO链组织成一个环状队列，设一指针指向当前最老的页面。当产生缺页中断时，如果指针所指向的页面的访问位为“0”，则淘汰，将新调入的页面插入到指针指向的位置，指针前移；如果访问位为“1”，则将其清“0”，指针前移，直到找到一个访问位为“0”的页面。
（8）页面分配的有关策略
①最小物理块数的确定
最小物理块数是指能保证进程正常运行所需要的最少物理块数。
相关因素：机器指令的格式、功能 和寻址方式。
②页面分配和置换策略
固定分配局部置换
可变分配全局置换：系统维护一个空闲物理块队列
可变分配局部置换：根据缺页率来动态增加或减少分配给每个进程的物理块数。
页面置换算法实现目标：不发生抖动现象，缺页率正常。
（9）驻留集：进程的合法页集合。
（10）抖动：如果分配给进程的存储块数量小于进程所需要的最小值，进程的运行将很频繁地产生缺页中断，这种频率非常高的页面置换现象称为抖动。
（11）缺页中断——当前访问的页面不再主存时产生缺页中断。
缺页中断与一般中断的区别：
①在指令执行期间产生和处理中断信号
②一条指令执行期间可能产生多次缺页中断
编 程
信号量P、V操作的编程 生产者——消费者问题 读—写问题
步骤：（1）抽象为几类进程 （2）分析进程之间的直接和间接制约关系
（3）设置信号量及其初值 (4）为各类进程编写代码
补 充
1.为什么引入进程？进程控制块。
（1）为使程序能并发执行，且为了对并发执行的程序加以描述和控制，人们引入了进程的概念。
（2）进程控制块PCB
是进程实体的一部分，是操作系统中作重要的记录型数据结构。PCB中记录了操作系统所需的。用于描述进程的当前情况以及控制进程运行的全部信息。进程控制块的作用是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程发生并发执行的进程。PCB是进程存在的唯一标识。
2.特权指令和非特权指令
特权指令：只能由操作系统使用的指令。特权指令的执行一般会引起处理器的状态切换。
处理器的状态:根据运行程序对资源和机器指令的使用权限将处理器设置为不同状态：
多数系统将处理器工作状态划分为管态和目态：
管态：操作系统管理程序运行的状态，又称为特权态、系统态、管理态或核心态
目态：用户程序运行时的状态，又称为普通态或、用户态
有些系统将处理器状态划分核心状态，管理状态和用户程序状态（目标状态）三种
管态和目态的比较:
处理器处于管态时
可以执行全部指令（包括特权指令）
可使用所有资源
具有改变处理器状态的能力
处理器处于目态时：只能执行非特权指令
特权级别不同，可运行指令集合也不同
特权级别越高，可以运行指令集合越大
高特权级别对应的可运行指令集合包含低特权级的
3.进程的阻塞与唤醒，进程的挂起与激活
（1）引起进程阻塞与唤醒的事件
进程请求系统为之服务
启动某种操作
需要的数据不能及时到达
本进程无工作可做（如发送进程）
（2）进程的阻塞过程
进程的阻塞通过阻塞原语来实现，阻塞是进程的一种主动行为，过程：
将进程状态由运行变为阻塞
将阻塞进程插入对应的阻塞队列
设调度标志为“真” ，进程调度程序调度新的就绪进程运行。
（3）进程的唤醒过程
进程的唤醒通过唤醒原语实现，唤醒是一种被动行为，过程：
将要唤醒的进程从阻塞队列中移出
将该进程的状态由阻塞变为就绪
将该进程插入就绪队列等待CPU调度
（4）进程的挂起（一个进程只能解挂自己的子孙进程，而不能解挂其他族系的进程。）
进程的挂起通过挂起原语来实现，主要过程：检查将要被挂起的进程的状态
若状态为：执行 停止，设置CPU调度标志为“真”
活动就绪 静止就绪
活动阻塞 静止阻塞
（5）进程的激活
进程的激活过程通过激活原语实现，过程：
检查将要被挂起的进程的状态：静止就绪 活动就绪
静止阻塞 活动阻塞
检查是否要进行重新调度
例如：请判断下列说法哪些的正确的？
答案：（2）、（3）
（1）进程可以由自己创建 （2）进程可以由自己阻塞 （3）进程可以由自己挂起
（4）进程可以由自己激活 （5）进程可以由自己唤醒 （6）进程可以由自己撤消
4.进程通信
进程通信通过发送原语和接受原语方式。
5.线程——什么是内核级线程？什么是用户级线程？
（1）级线程ULT：由用户应用程序建立的线程。并且由用户程序负责对他们的调度和管理工作。
（2）内核级线程KLT：这类进程依赖OS内核，所有线程的创建、调度和管理全部由操作系统内核负责。即所有线程的创建、切换和撤消等操作都需要进行系统调用，由OS内核来实现。
用户线程：运行在用户地址空间的线程。 内核线程：运行在内核空间的线程。
所有的用户级线程都是用户线程，内核级线程可以是用户线程，也可以是内核线程。
6.什么是环境调用单位是进程？什么是环境调用单位是线程？
（1）仅设置用户级线程的系统是以进程作为调度的基本单位。
（2）设置内核级线程的系统以线程作为调度的基本单位。
7.产生死琐的必要条件
（1）互斥条件：在一段时间内某资源只允许一进程使用。
（2）请求和保持条件：既占有又同时请求资源。
（3）不剥夺条件：资源在使用完前不能被抢夺。
（4）环路条件：发生死锁时必然存在一个进程-资源的环形链。
7.死琐的解除方法
剥夺资源 撤销进程
8.什么是静态重定位？
静态重定位：在装入一个作业时，由链接程序在程序执行前进行的重定位，即把作业中的指令地址和数据地址全部转换成绝对地址。静态重定位是由重定位装配程序完成，不支持程序浮动。
9.什么是主存的连续分配？
动态分区分配。根据进程实际需要，动态的分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三个问题。
10.可重定位分区
通过移动的方法，把主存中分散的各个小的存储分区拼凑成大存储区的过程，这种方法叫做紧凑。
动态重定位的特点：
动态重定位由硬件机构完成，硬件机构包括重定位寄存器和加法器。
在程序执行的过程中进行逻辑地址到物理地址的转换。
目标程序可以在内存中移动且可以不连续。
11.分页与分段的比较
(1)页是信息的物理单位；而段是信息的逻辑单位。
(2)页的大小固定；而段的大小是由它逻辑信息的长度的决定，不同段的长度通常不同。
(3)分页管理的地址空间是一维的，而分段管理的地址空间是二维的
(4)段式存储管理能够实现基于完整功能逻辑段的信息共享，便于实现动态链接。
12.信息共享
段的共享：对于那些被多个程序共享的段，在内存中只保留一个副本。副本采用可重入代码。
13.虚拟存储器的实现方法
（1）请求分页的存储器管理系统
（2）请求分段的存储器管理系统
（3）段页式虚存管理系统
14.请求分页存储器管理方式可能遇到哪些问题？
（1）最小物理块数的确定 （2）物理块的分配策略 （3）物理块的分配算法
15.分段保护
越界检查：每个进程只能运行在自己的地址空间。
存取控制检查：只读、只执行、读/写
环保护机构：不同的环具有不同的访问权限。原则是：
一个程序可以访问驻留在相同环或较低环中的数据
一个程序可以调用驻留在相同环或较高环中的服务
16.分页保护
越界保护：设置页表长度寄存器，查页表前，先检查页号是否越界。
操作访问保护：在每个页表项中增设一存储保护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报错。
17.设备管理的任务和功能
设备管理的主要任务是完成用户提出的I/O请求，为用户分配I/O设备，以提高CPU和I/O设备的利用率和系统的吞吐量。主要包括：
缓冲管理： 管理好各种类型的缓冲区。
设备分配： 根据用户的请求，分配相应的设备。
设备处理： 通过设备处理程序（设备驱动程序）来实现CPU和设备控制器之间的通信。
设备独立性和虚拟设备： 通过设备独立性程序可使应用程序独立于具体的物理设备；通过虚拟技术，可把一次只允许一个进程访问的物理设备改造成可同时供多个进程共享的设备。
18.设备分配的分配顺序
分配设备————分配控制器————分配通道
19.I/O系统的层次
两层: 设备相关层(驱动层) 设备无关层(独立层)
四层：用户进程——进行I/O调用；格式化I/O；spooling
设备无关I/O软件（设备独立性软件）——设备命名；保护；阻塞；缓冲；分配与释放
设备驱动程序——设置设备寄存器；检查状态
中断处理程序——当I/O结束时唤醒驱动
（硬件——执行I/O操作）
中断层具体功能
中断层是I/O子系统的最低层。主要工作是执行与中断有关的操作，并在 I/O结束时唤醒驱动程序。
驱动层的具体工作：
(1) 确定是否向设备发命令
(2) 确定向设备发什么命令
(3)向设备发命令（设置寄存器）
(4) 监督设备命令的正确执行和等待物理操作的完成
(5) 执行后处理：中断时被调用的驱动层物理操作的后续处理
独立层(逻辑I/O层)功能
（1）向用户层软件提供一个统一的接口
（2）设备命名
（3）设备保护：防止无权存取设备的用户存取设备。
（4）缓冲管理
（5）提供与设备无关的块尺寸：向更高一层隐藏不同设备的物理块大小的差别。
（6）块设备的存储分配
（7）分配和释放独占设备
（8）错误报告（与设备无关的错误报告）
用户空间层I/O软件——运行于用户空间的I/O软件
（1）与用户程序连接在一起的库过程。(输入输出的格式是由库过程完成的)
（2）在核心外运行的I/O程序。（如假脱机进程）
例如：请说明下列的各个工作是在设备管理的哪个层次完成的？
1.向设备寄存器写命令。 2.检查用户是否有权使用设备。
3.将二进制整数转换成ASCII码打印。 4.为一个读操作计算磁道和扇区。
解：1.驱动层； 2.设备无关I/O软件层； 3.用户空间层I/O软件; 4.驱动层.
20.I/O软件
设总体设计目标：是高效率和通用性。前者要确保I/O设备与CPU的并发性，以提高资源利用率；后者则是指尽可能地提供简单抽象、清晰而统一的接口。
重要原则：设法消除或屏蔽设备硬件内部的地基处理过程，为用户提供一个简便、易用、抽象的逻辑设备接口，保证用户安全、方便的实用各类设备。
21.文件属性结构
文件属性主要有：文件类型、文件长度、文件的物理位置、文件的建立时间等。
22.文件的打开和关闭是干什么的？
所谓“打开”（open），是指系统将指名文件的属性（FCB——包括该文件在外存上的物理位置）从外存拷贝到内存打开文件表的一个表目中，并将该文件返回给用户。
所谓“关闭”（close），系统调用来关闭系文件，OS将会把该文件从打开文件表中的表目上删除掉。
打开文件——任何一个文件使用前都要先打开，即把文件的FCB送到内存。
关闭文件：把文件在主存中的FCB写入磁盘，并修改系统打开文件表和用户打开文件表。
23.文件的读、写、删除是干什么的？
读文件：在读一个文件时，须在相应系统调用中给出文件名和应读入的内存目标地址。此时，系统同样要查找目录，找到指定的目录项，从中得到被读文件在外存中的位置。在目录项中，还有一个指针用于对文件的读、写。
写文件：在写一个文件时，须在相应系统调用中给出该文件名及该文件在内存中的地址。为此，也同样须查找目录，找到指定文件的目录项，再利用目录中的写指针进行写操作。
删除文件：当已不再需要某文件时，可将它从文件系统中删除。在删除时，系统应先从目录中找到要删除的文件找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
24.文件逻辑结构的类型和特点
（1）有结构文件
顺序文件：其中记录通常是定长记录，因而能用较快的速度查找文件中的记录。（顺序文件的优点适合顺序存取，批量存取的效率高。顺序文件的缺点变长记录文件随机直接存取效率低。）
索引文件：记录为可变长度时，为每个文件建立一张主索引表，每个逻辑记录在索引表中建立一个表项，以加快对记录的检索速度，每一个表项设一指针指向对应的逻辑记录。（索引文件很容易实现对逻辑文件的随机访问。）
顺序索引文件：将顺序文件的所有记录分成若干个组，并为顺序文件建立一张索引表，索引表的表项为每组第一个记录的键值和指向该记录的指针。（索引顺序文件一般按关键字顺序组织文件。）
（2）无结构文件
25.目录查询技术
当用户要访问一个已存在文件时，系统首先要利用用户提供的文件名对目录进行查询，找出该文件的文件控制块对应索引结点；然后，根据FCB或索引结点中所记录的文件物理地址，换算出文件在磁盘上的物理位置；最后，再通过磁盘驱动程序，将所需文件读入内存。目前对目录进行查询的方式有两种：线性检索法和Hash方法。
26.文件的共享
（1）基于索引结点的共享方式（硬链接）
（2）基于符号链的文件共享（软链接）
考研题
进程的描述与控制
D 单处理机系统中，可并行的是（）
I 进程与进程 II 处理机与设备 III 处理机与通道 IV 设备与设备
A．I、II 和 III B. I、II 和 IV C. I、III 和 IV D. II、III 和 IV
A 下列选项中，操作系统提供的给应用程序的接口是（ ）
A：系统调用 B：中断 C：库函数 D：原语
C 下列选项中，导致创进新进程的操作是（ ）
I用户成功登陆 II设备分配 III启动程序执行
A：仅I和II B：仅II和III C：仅I和III D：I，II，III
A 下列选项中，降低进程优先权级的合理时机是（ ）
A：进程的时间片用完 B：进程刚完成I/O，进入就绪队列
C：进程长期处于就绪队列中 D：就绪从就绪状态转为运行态
A 下列选项中，在用户态执行的是（ ）
A．命令解释程序 B．缺页处理程序 C．进程调度程序 D．时钟中断处理程序
D 在支持多线程的系统中，进程P创建的若干个线程不能共享的是（ ）
A．进程P的代码段 B．进程P中打开的文件 C．进程P的全局变量 D．进程P中某线程的栈指针
互斥与同步
三个进程p1,p2,p3互斥使用一个包含N（N>0）个单元的缓冲区，p1每次用produce()生成一个正整数并用put()送入缓冲区一个空单元中；p2每次用getodd从缓冲区中取一个奇数，并用countodd （）统计奇数个数； p3每次用geteven从缓冲区中取一个偶数，并用counteven （）统计偶数个数；请用信号量机制实现这三个进程之间的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。
设四个信号量: semaphore odd=0, even=0; empty=N; mutex=1；
Parbegin
P2: P3:
P1:
{ {
{X=prodeuce();
P(odd); P(even);
P(empty);
P(mutex); P(mutex);
P(mutex);
geteven(); geteven();
put();
countodd=countodd+1 counteven=counteven+V(mutex);
V(mutex); 1
if(X%2==0)V(even);
V(empty); V(mutex);
else V(odd);
} V(empty);
}
Parend }
调度与死锁
D 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）：
A.时间片轮转调度算法 B.短进程优先调度算法 C.先来先服务调度算法 D.高响应比优先调度算法
C 某计算机系统有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能发生死锁的K的最小值是( )：
A. 2 B.3 C.4 D.5
B 设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待资源的进程数，则M,N分别是（ ）
A. 0，1 B. 1，0 C. 1，2 D. 2，0
A 下列选项中，降低进程优先权级的合理时机是（ ）
A：进程的时间片用完 B：进程刚完成I/O，进入就绪队列
C：进程长期处于就绪队列中 D：进程从就绪状态转为运行态
B 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是
A．先来先服务 B．高响应比优先 C．时间片轮转 D．非抢占式短任务优先
A 下列选项中，在用户态执行的是
A．命令解释程序 B．缺页处理程序 C．进程调度程序 D．时钟中断处理程序
C 有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1 操作的指令序列分别如下所示。
//加1操作 // 减1操作
load R1，x load R2，x
// 取x到寄存器R1中
inc R1 dec R2
store x，R1 store x，R2
// 将R1的内容存入x
两个操作完成后，x的值
A．可能为-1或3 B．只能为1 C．可能为0、1或2 D．可能为-1、0、1或2
某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业 员空闲时，通过叫号选取一位顾客，并为其服务。
顾客和营业员的活动过程描述如下：
cobegin
{
process 顾客i
{从取号机获取一个号码；等待叫号；获取服务；
}
}coend
请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
semaphore seets = 10； // 有10个坐位的资源信号量
mutex = 1；// 取号机互斥信号量
haveCustom = 0; // 顾客与营业员同步，无顾客时营业员休息
process 顾客{
process 营业员
P(seets); // 等空位
{
P(mutex); // 申请使用取号机
while(True) {
从取号机上取号;
V(mutex); // 取号完毕
P(haveCustom);
V(haveCustom);
// 没有顾客则休息
// 通知营业员有新顾客到来
叫号;
等待营业员叫号;
为顾客服务;
V(seets); // 离开坐位
}
接受服务；
}
}
主存管理
A 分区分配内存管理方式的主要保护措施是：
A：界限地址保护 B：程序代码保护 C：数据保护 D：栈保护
C 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大的段长是：
A：28字节 B：216字节 C：224字节 D：232字节
D 某基于动态分区存储管理的计算机，其主存容量为55mb（初始空间），采用最佳适配（Best fit）算法，分配和释放的顺序为：分配15mb，分配30mb，释放15mb，分配8mb，此时主存中最大空闲分区的大小是
A：7mb B：9mb C：10mb D：15mb
虚拟存储器
A 29．当系统发生抖动（thrashing）时，可用采取的有效措施是
Ⅰ. 撤销部分进程 Ⅱ．增加磁盘交换区的容量 Ⅲ．提高用户进程的优先级
A．仅Ⅰ B．仅Ⅱ C．仅Ⅲ D．仅Ⅰ、Ⅱ
B 30．在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是
A．编辑 B．编译 C．链接 D．装载
设备管理
B 某文件占 10 个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100us，将缓冲区的数据传送到用户区的时间是50us，CPU对一块数据进行分析的时间为50us。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是
A．1500us、1000us B．1550us、1100us C．1550us、1550us D．2000us、2000us
A 假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有一 个磁道访问请求序列为 35，45，12，68，110，180，170，195，采用 SCAN调度算法得到的磁道访问序列是（）
A．110，170，180，195，68，45，35，12 B.110，68，45，35，12，170，180，195
C.110，170，180，195，12，35，45，68 D.12，35，45，68，110，170，180，195
A 程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是（）
A．逻辑设备名 B.物理设备名 C.主设备号 D.从设备号
文件管理
B 下列文件物理结构中，适合随机访问且易于文件扩展的是（）
A .连续结构 B.索引结构 C.链式结构且磁盘块定长 D.链式结构且磁盘块变长
C 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件的最大长度是（ ）
A：33kb B：519kb C：1057kb D：16513kb
C 设置当前工作目录的主要目的是（ ）
A：节省外存空间 B：节省内容空间 C：加快文件的检索速度 D：加快文件的读写速度
B 本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是（ ）
A：命令解释程序 B：中断处理程序 C：系统调用程序 D：用户登录程序
B 下列文件物理结构中既适合随机访问，又易于文件扩展的是 （ ）
A.连续文件 B. 索引文件 C.链式结构且磁盘块定长 D.链式结构且磁盘块变长
A 文件系统中，文件访问控制信息存储的合理位置是（ ）
A.文件控制块 B. 文件分配表 C.用户口令表 D. 系统注册表
B 设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，然后再建立F1的硬链接文件F3 ，然后删除F1，此时F2和F3的引用计数值分别是（ ）
A.0，1 B. 1，1 C.1，2 D.2，1
A 程序员通过系统调用打开I/O设备时，通常使用的设备标识符是（ ）
A.逻辑设备名 B. 物理设备名 C.主设备号 D. 从设备号
选择题例题
在批处理系统中，用户作业由 （ ）组成。
A. 程序 B. 程序+数据 C. 程序+作业说明书 D. 程序+数据+作业说明书
下列选择中，（ ） 不是操作系统关心的主要问题。
A.管理计算机裸机 B.提供用户与计算机硬件系统的接口
C.管理计算机系统资源 D.高级程序设计语言的编译器
（ ） 不是设计实时操作系统主要追求的目标。
A.安全可靠 B.资源利用率 C.及时响应 D.快速处理
在虚拟页式存储管理中，下列说明哪个是正确的（ ）
A. 页面长度固定，并且是软件的设计特性 B. 页面长度固定，并且是硬件的设计特性
C. 页面长度可变，并且是硬件的设计特性 D. 页面长度可变，并且是软件的设计特性
若系统中有同类资源10个，被3个进程所共享，每个进程最多可申请（ ）个该类资源时，系统不会发生死锁。
A.2 B.3 C.4 D.5
文件系统中，设立打开文件（open）系统功能调用的基本操作是（ ）。
A.把文件信息从辅存读入主存 B.把文件的FCB从辅存读入主存
C.把文件的FAT表信息从辅存读入主存 D.把磁盘的超级块从辅存读入主存
工作集是进程运行时被频繁访问的页面集合。进程在运行时，如果它的工作集页面都在（ ）就能够使该进程有效地运行，否则系统就可能会发生抖动现象。
A.外部存储器 B. 虚拟存储器 C.辅助存储器 D. 主存储器
已知某段式虚拟存储器管理系统中，段的逻辑地址结构为：段号为5位，段内地址为13位。主存容量为5K，辅存容量为200K，那么该虚拟存储器系统的实际容量为 。
A.160K B.200K C.205K D.256K
例 题
进程同步1：设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开门。
给出在汽车不断地到站、停车、行驶过程中，司机和售票员的活动的同步关系。
用信号量和wait, signal操作实现他们间的协调操作。
答：根据一般的常识，有
售票员应满足的同步关系为：当司机停车后，才将车门打开让顾客上下车。
司机的同步关系为：当售票员关门后，才能开车.
设互斥信号量 binary_semaphore bus_closed,bus_stopped; 初始值为bus_=0; bus_=0;
//表达初始情况第一次用到信号量时情形为车门没有关，车是开着的
进程为:
driver { busserver {
do { do {
wait(bus_closed); closing the door;
bus starting up； signal(bus_closed);
bus is driving； ticket selling;
bus is parking； wait(bus_stopped);
signal(bus_stopped); opening the door;
}while(1) getting onoff the bus;
} }while(1)
}
进程同步2：某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
(2)根据所定义的信号量，把应执行的P、V操作填入下面横线上，以保证进程能够正确地并发执行。
(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。
答：(1)定义一信号量S，初始值为20，其意义如下：
S>0 S的值表示可继续进入售票厅的人数
S=0 表示售票厅中已有20名顾客(购票者)
S<0 |S|的值为等待进入售票厅的人数
(2)根据所定义的信号量，把应执行的P、V操作填入下面横线上，以保证进程能够正确地并发执行。
COBEGIN PROCESS Pi(i=1，2，„„)
begin；
P(S)
进入售票厅；
购票；
退出；
V(S)
end；
COEND
(3) S的最大值为20；S的最小值为20－n
进程同步3：理发店里有一位理发师,一把理发椅和N把供等候理发的顾客坐的椅子.如果没有顾客,则理发师便在理发椅上睡觉.当一个顾客到来时,他必须先唤醒理发师.如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。
答：定义信号量如下：
Var Sn: semaphore; {位子数目，初值为n}
S: semaphore; {理发师睡觉，初值为1}
mutex: semaphore; {初值为1}
用P、V操作实现如下：
顾客进程 i:
P(Sn);{门外观望}
P(mutex);
进门；
V(mutex);
V(S); {if(sn==n-1) v(s); }
理发师进程 ：
Repeat
P(S);
P(mutex);
叫人理发；
V(mutex);
理发；
Until false;
等候；
理发；
V(Sn)
P(mutex);
出门；
V(mutex);
进程同步4： 桌子上有一只盘子，每次只能放入一只水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个儿子专等吃盘中的桔子，一个女儿专等吃盘中的苹果。请利用P、V操作实现他们之间的同步。
答：在本题中，应设置三个信号量s、so、sa，信号量s表示盘子是否为空，其初值为1；信号量so表示盘中是否有桔子，其初值为0；信号量sa表示盘中是否有苹果，其初值为0。同步描述如下：
int s=1;
int sa=0;
int so=0;
main ( )
{
cobegin
father ( );
son ( );
daughter ( );
coend
}
son ( )
{
p(so);
从盘中取出桔子；
v(s);
吃桔子；
}
father ( )
{
p(s);
将水果放入盘中；
if(放入的是桔子) v(so);
else v(sa);
}
daughter ( )
{
p(sa);
从盘中取出苹果；
v(s);
吃苹果；
}
进程同步5：桌子上有一只盘子，最多可容纳两个水果，每次只能放人或取出一个水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用Pv操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
答：盘子为互斥资源，因可以放两个水果，empty初值为2；再设信号量mutex初值为1，控制对盘子的互斥访问；apple表示盘中苹果个数，表示盘中桔子个数，初值均为0。
parbegin
Father: begin
L1: p(empty);
P(mutex);
放苹果；
V(mutex);
V(apple);
Mother: begin
L2: P(empty);
P(mutex);
放桔子；
V(mutex);
V(orange);
Goto L2;
End;
Goto L1;
End;
Daughter: begin
L3: p(apple);
P(mutex);
取苹果；
V(mutex);
V(empty);
Goto L3;
End;
Son: begin
L4: P(orange);
P(mutex);
取桔子；
V(mutex);
V(empty);
Goto L4;
End;
Parend
进程同步6： 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）
（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）
（2）当图书馆中没有座位时，后到的读者不等待，立即回家。
解(2)
解（1 )
设整型变量 COUNT=100;
设信号量：S=100; MUTEX=1
信号量：MUTEX=1;
P(S)
P(MUTEX);
P(MUTEX)
IF (COUNT==0)
登记
{ V(MUTEX);
V(MUTEX)
RETURN;
阅读
}
P(MUTEX)
COUNT=COUNT-1;
注销
登记
V(MUTEX)
V(MUTEX);
V(S)
阅读
P(MUTEX);
COUNT=COUNT+1;
V(MUTEX);
RETURN;
进程同步7： 有一座东西方向的独木桥；用P,V操作实现：
（1） 每次只允许一个人过桥；
（2） 当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。
（3） 当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。
(2)解
（1）解
设信号量： MUTEX=1 (东西方互斥)
设信号量 MUTEX=1
MD=1 (东向西使用计数变量互斥)
P (MUTEX)
MX=1 (西向东使用计数变量互斥)
过桥
设整型变量： CD=0 (东向西的已上桥人数)
V (MUTEX)
CX=0 (西向东的已上桥人数)
从西向东：
P (MX)
从东向西：
P (MD)
IF (CD=0)
{P (MUTEX) }
CD=CD+1
V (MD)
过桥
P (MD)
CD=CD-1
IF (CD=0)
{V (MUTEX) }
V (MD)
(3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。
进程同步8：有一个俱乐部，有甲乙两个服务员，当顾客有请求时，甲负责送烟，乙负责送火，无顾客请求时，服务员睡眠。顾客自己不能带烟和火，当顾客要抽烟时，可请求服务员送烟和火，烟和火还未送到时，顾客必须等待。
设信号量：SY, SH,CY,CH:初值都为0
甲服务员
乙服务员 顾客
REPEAT
REPEAT
V(SY) /*（请求送烟）*/
P(SY)
P(SH)
V(SH) /*（请求送火）*/
送烟
送火 P(CY) /* (等烟) */
V(CY)
V(CH)
P(CH) /* (等火) */
UNTIL FALSE
UNTIL FALSE
抽烟
进程同步9：有一个超市，最多可容纳N个人进入购物，当N个顾客满员时，后到的顾客在超市外等待；超市中只有一个收银员。可以把顾客和收银员看作两类进程，两类进程间存在同步关系。写出用P;V操作实现的两类进程的算法（2003年系统设计员考试的题目）
解：设信号量：S=0，C=0 (顾客与收银员的同步信号量)，M=N
顾客
收银员
P(M)
P(S)
进入店内购物
收银
V(S)
V(C)
P(C)
V(M)
进程同步10：一个盒子，内有黑白两种棋子（数量相等），甲每次从盒子中取出一颗黑子，乙每次从盒子中取出一颗白子，一人取了棋子后，必须等另一方取过棋子方可再取，（可假设甲先取）。
解： 设信号量：SJ=1,SY=0
乙
甲
REPEAT
REPEAT
P(SY)
P(SJ)
取一颗白子
取一颗黑子
V(SJ)
V(SY)
UNTIL 盒子中无白子
UNTIL 盒子中无黑子
内存管理1：在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时
间是20us，假设页表的查询与快表的查询同时进行 。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。
(1) 求对某一数据进行一次次存取可能需要的时间？
(2) 现连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间?
答：
(1) 当系统对数据进行存取时，有3种可能性。
① 所存取的数据的页面在内存，其页表项已经存储到快表，此时存取数据的时间是：
查询快表的时间+存取内存数据的时间=1us+8us= 9us
② 所存取的数据的页面在内存，但是其页表项没有存储到快表，没有命中快表，此时存取数据的时是：
查询页表的时间+存取内存数据的时间=8us+8us= 16us
③ 所存取的数据的页面不在内存，发生缺页中断，此时存取数据的时间是：
查询页表的时间+缺页中断的时间+查询页表的时间+
存取内存数据的时间=8us+20us+8us+8us = 44us
(2) 当对某一数据进行4次连续读取时：
① 第1次可能的时间为：
1us+8us= 9us；8us+8us= 16us；8us+20us+8us+8us。
② 第2次时，对应页面的页表项已经交换到快表中。因为存取是连续的，不存在页面被淘汰的可能性，所以第2次、第3次、第4次的存取时间是一样的，消耗的时间为1us+8us= 9us。
内存管理2：若在一分页存储管理系统中，某作业的页表如下所示。已知页帧大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址（注：此处块号即为页帧号）。
页号
0
1
2
3
块号
2
3
1
6
答： 本题中，为了描述方便，设页号为P，页内位移为W，逻辑地址为A，内存地址为M，页帧大小为L，则
P=int(A/L) W=A mod L 对于逻辑地址1011
P=int(1011/1024)=0 W=1011 mod 1024=1011 A=1101=(0,1101)
查页表第0页在第2块，所以物理地址为M=1024*2+1101= 3059。
对于逻辑地址为2148
P=2148/1024=2 W=2148 mod 1024=100 A=2148=(2,100)
查页表第2页在第1块，所以物理地址为M=1024*1+100=1124。
对于逻辑地址为3000
P=3000/1024=2 W=3000 mod 1024=952 A=3000=(2,952)
查页表第2页在第1块，所以物理地址为M=1024*1+952=1976
对于逻辑地址5012
P=5012/1024=4 W=5012 mod 1024=916 因页号超过页表长度，该逻辑地址非法。
内存管理5：有一计算机系统，内存容量为512K，辅存容量为2G，逻辑地址形式如下：
段号 段内地址
29 20 19 0
求其虚拟存储器的实际容量？
答：虚拟内存的实际大小由系统的逻辑地址结构、主存辅存容量共同决定。虚拟内存容量的理论值是210
*220=1G；
最大段内地址为220=1M，远大于内存容量，其段长超过512K的内存容量，故最大实际段长为512k而不是1M。
所以可计算虚拟存储容量为210
*512K =210
*0.5M=0.5G。 0.5G<2G，因此虚拟存储器的实际容量是0.5G。
概念复习：
1. 当时引入多道程序的目的在于（ C ）。
A.有利于代码共享，减少主、辅存信息交换量 B．充分利用存储器
C.充分利用CPU，减少CPU等待时间 D．提高实时响应速度
2. 在单处理机计算机系统中，（ B ）是并行操作的。
A.程序与程序 B.处理机的操作与通道的操作
C.主程序与子程序 D.用户程序与操作系统程序
3. 当线程处于阻塞状态时，线程( B )。
A. 正在占用处理机 B.没有占用处理机 C. 将进入执行状态 D.将进入结束状态
4. 当多道程序系统中发生死锁时，（ C ）。
A.计算机系统不能处理任何事情
B.某个进程不能够执行
C.一组进程相互等待，并进入阻塞状态
D.不能进行输入和输出
5. 下面哪一个不是程序在并发系统内执行的特点（ B ）。
A.产生死锁的必然性 B.资源分配的动态性 C.程序执行的间断性 D.相互通信的可能性
6. 进程和程序的一个本质区别是( D )。
A. 进程分时使用CPU，程序独占CPU B．进程存储在内存，程序存储在外存
C. 进程在一个文件中，程序在多个文件中 D．进程为动态的，程序为静态的
进程是操作系统发展以后引进的一个称谓。本质上他是运行起来的程序在从系统里面申的资源的管理代表。
发布评论