东北大学秦皇岛分校_编译原理_操作系统_试卷.doc

《东北大学秦皇岛分校_编译原理_操作系统_试卷.doc》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校_编译原理_操作系统_试卷.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级东 北 大 学 秦 皇 岛 分 校课程名称： 操作系统 试卷： (A ) 考试形式： 闭卷 授课专业： 信息与计算科学 考试日期：2004年12月22日 试卷：共 3 页 题号一二三四五总分得分阅卷人一、 选择题：（每题1分，共10分）1、（B）的主要特点是提供即时响应和高可靠性。生产过程的控制、武器系统、航空订票系统、银行业务就是这样的系统。A.分时系统 B.实时系统 C.批处理系统 D.分布式系统2、下列进程状态的转换中，哪一个是不正确的(C)。 A.就绪一运行 B.运行一就绪 C.就绪一阻塞 D.阻塞一就绪3、利用信号量实现进程的

2、（B），应为临界区设置一个信号量mutex，其初值为1，表示该资源尚未使用，临界区应置于P（mutex）和V（mutex）原语之间。A.同步 B.互斥 C.竞争 D.合作4、作业调度的关键在于(B)。A.选择恰当的进程管理程序 B.选择恰当的作业调度算法C.用户作业准备充分 D.有一个较好的操作环境5、下列存储管理方案中，不采用动态重定位的是（C）。A.页式管理B.可变分区 C.固定分区D.段式管理6、关于虚拟存储器，以下说法正确的是（D）。A.可提高计算机运算速度的设备 B.容量扩大了的主存实际空间C.通过SPOOLING 技术实现的 D.可以容纳和超过主存容量的多个作业同时运行的一个地址空

3、间7、下面几个设备中，（C）是共享设备。A.打印机 B.磁盘 C.读卡机 D.扫描仪8、文件系统采用多级目录结构的目的,不包括是（B） A.缩短访问文件的寻找时间 B.节省存储空间 C.解决文件的命名冲突 D.易于实现文件共享9、磁盘驱动调度算法中（B）算法可能会随时改变移动臂的运动方向。 A.电梯调度 B.先来先服务 C.扫描 D.循环扫描10、正在运行的进程在信号量S上作P操作之后，当S0的时候，进程进入信号量的 （A）。 A.等待队列 B.提交队列 C.后备队列 D.就绪队列二、填空题：（每空1分，共15分）1、不论是分时系统、实时系统还是批处理系统都具有四个基本特征 并发 、 共享 、

4、 虚拟 、 异步 。2、特权指令只能在_系统 _态下执行，若在用户态下执行则被认为是非法指令。3、_PCB_是进程存在的唯一标志。4、设基址寄存器内容为1000，在采用动态重定位的系统中，当执行指令“LOAD A,2000”时，操作数的实际地址是_3000_。5、按照调度的层次我们把调度分为 高级 、 低级 、 中级 。6、根据文件的逻辑结构，文件可以分为 有结构文件 和_无结构文件_两类。7、目前常用的外存分配方法有：连续分配、_链接_分配、 索引 分配。三、名词解释（每题3分，共12分）1、操作系统：操作系统是一组控制和管理计算机硬件和软件资源（1分）、合理地对各类作业进行调度（1分）、以

5、及方便用户的程序的集合（1分）。2、临界区：每个进程中访问临界资源的（2分）那段代码（1分）称为临界区3、对换：所谓对换，是指把内存中暂不能运行的进程，或暂不用的程序和数据（1分），换出到外存上，以腾出足够的内存空间（1分），把已具备运行条件的进程，或进程所需的程序和数据，换入内存（1分）4、设备独立性：应用程序独立于具体的物理设备（3分）。四、简单题（每题6分，共24分）1、比较程序、进程的区别。 进程是动态的，程序是静态的，程序是有序代码的集合（1分）；进程是程序的执行（1分）；进程是暂时的，程序的永久的，进程是一个状态变化的过程，程序可长久保存（1分）；进程与程序的组成不同，进程的组成包

6、括程序、数据和进程控制块（即进程状态信息）（1分）；通过多次执行，一个程序可对应多个进程（1分）；通过调用关系，一个进程可包括多个程序（1分）。装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级2、什么是死锁？死锁预防的措施有哪些？所谓死琐，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进（3分）。死锁预防的措施有：（1）屏弃“请求和保持”条件，（2）屏弃“不剥夺”条件，（1分），（3） 摒弃“环路等待”条件（1分）。3、简述分页与分段的主要区别（1）页是信息的物理单位，已削减内存零头，提高内存利用率为目的，而不是用户的需求。（1分）段是信息的逻辑单

7、位，具有相对完整的意义，是为了满足用户的需求。（1分） （2）页的大小固定，由系统确定。（1分）段的大小不固定，决定于用户编写的程序。（1分） （3）分页的作业地址是一维的。（1分）分段的作业地址是二维的。（1分）4、什么是局部性原理？什么是抖动？你有什么办法减少系统的抖动现象？局部性原理是指在几乎所有程序的执行过程中，在一段时间内，CPU总是集中地访问程序中的某一个部分而不是对程序的所有部分具有平均的访问概率。（2分）抖动是指当给进程分配的内存小于所要求的工作区时，由于内存外存之间交换频繁，访问外存的时间和输入输出处理时间大大增加,反而造成CPU因等待数据而空转,使得整个系统性能大大下降。（

8、2分）在物理系统中，为了防止抖动的产生，在进行淘汰或置换时，一般总是把缺页进程锁住，不让其换出，从而防止抖动的产生。（1分）防止抖动产生的另一个办法是设置较大的内存工作区。（1分）五、应用与计算（共39分）1、现有一个具有n个缓冲区的缓冲池，Produce进程把它生产的消息放入一个缓冲区，Consumer进程可从一个缓冲区中取得一个消息消费。用信号量实现生产者和消费者之间的同步与互斥。请将下面的生产者和消费者算法补充完整。生产者和消费者对缓冲池互斥访问的信号量为SM，缓冲池的初值SB=n，缓冲池中消息个数初值为SP=0。（本题9分） 初值设置SM= 1 ；SB=n；sp=0P生产者： Whil

9、e(1) .Producer an item Wait( SB )Wait(SM) 缓冲操作Singal(SM Singal( SB )C消费者： While(1) .Wait(SB )Wait(SM 缓冲操作Singal(SM Singal(SB )Consume the item2、银行家算法中，若出现下述的资源分配情况： ProcessAllocationNeedAvailableP00 , 1 , 07 , 4 , 33 , 3 , 2P12 , 0 , 01 , 2 , 4P23 , 0 , 26 , 5 , 0P32 , 1 , 10 , 1 , 1P40 , 0 , 24 , 3

10、 , 1试问：（1）当前系统状态是否安全？如果安全写出安全序列。（7分） （2）若进程P1 提出请求 Request ( 1 , 0 , 2 ) 后，系统能否将资源分配给它？（3分） （1）存在如下进程序列，可使进程顺利执行完毕： 进程 可用资源数P3：执行完 5 ，4 ，3P4：执行完 5 ，4 ，5P1：执行完 7 ，4 ，5P0：执行完 7 ，5 ，5P2：执行完 10 ，5 ，7当前系统是安全的，安全序列是：P3 , P4 , P1 , P0 , P2 . （8分）(2) 如果将资源分配给进程P1 ,这时所有待执行的进程中就没有满足所需资源数=系统可提供资源数条件的，所以系统不可以将资

11、源分配P1（2分）3、假设一磁道有200个柱面，编号为0 199 ，在完成了磁道125处的请求后，当前正在磁道143处为一请求服务，若请求队列的先后顺序为86，147，91，177，94，150，102，175，130。试分别采用FCFS（先来先服务）、SSTF（最短寻道时间优先）算法完成上述请求，写出磁道移动的顺序，并计算磁头移动的总距离。装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级（本题8分）（1）采用FCFS算法调度，磁头移动顺序为：143-86-147-91-177-94-150-102-175-130磁头移动总量为：565（柱面）。（4分）（2）采用SSTF算法调度，磁

12、头移动顺序为：143-147-150-130-102-94-91-86-175-177磁头移动总量为：162（柱面）。（4分）4、我们打开计算机中的某个word文档，然后通过打印机打印文档中的内容，在这个过程中，操作系统为我们做了什么？试从操作系统功能的角度加以分析。（本题12分）进程管理：执行时完成调度（2分）存储管理：为调度的进程分配内存，以及从硬盘中读取文件。（2分）文件管理：所调度文件的查询与读取（2分）设备管理：打印机的驱动，以及打印工作的执行。（2分）用户接口：执行程序时的界面，以及程序进程本身所含的系统调度。（2分）整个过程是五个功能合作完成。（2分）装 订 线装 订 线 内 不

13、 要 答 题学 号姓 名班 级东 北 大 学 秦 皇 岛 分 校课程名称： 计算机操作系统 试卷： (A ) 考试形式： 闭卷 授课专业： 计算机 考试日期： 年 月 日 试卷：共 3 页 题号一二三四总分得分阅卷人一、 单项选择题：（每题2分，共30分）1、操作体统是对( C )进行管理的软件。 A. 软件 B. 硬件 C. 计算机资源 D. 应用程序2、操作系统的基本类型主要有( B ) A. 批处理系统、分时系统及多任务系统 B. 实时操作系统、分时操作系统及批处理操作系统 C. 单用户系统、多用户系统及批处理系统 D. 实时系统、分时系统和多用户系统3、在进程管理中，当( C)时，进程

14、从阻塞状态变为就绪状态。 A. 进程被进程调度程序选中 B. 等待某一事件 C. 等待的事件发生 D. 时间片用完4. 若P、V操作的信号量S初值为2，当前值为-1，则表示有( B )等待进程。 A. 0个 B. 1个 C. 2个 D. 3个5、操作系统通过( B )对进程进行管理。 A. JCB B. PCB C. DCT D. CHCT6、多道程序环境下，操作系统分配资源以(D )为基本单位。 A. 程序 B. 指令 C. 进程 D. 作业7、发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏( A )条件是不太实际的。 A. 互斥 B. 不可剥夺 C. 部分分配

15、D. 环路等待8、在分时操作体统中，进程调度经常采用( C)算法。 A. 先来现服务 B. 最高优先权 C. 事件片轮转 D. 随机9、系统“抖动”现象的发生是由( A )引起的。 A. 置换算法选择不当 B. 交换的信息量过大 C. 内存容量不足 D. 请求页式管理方案10、首次适应算法的空闲区是( A ) A. 按地址递增顺序连在一起 B. 始端指针表指向最大空闲区 C. 按大小递增顺序连在一起 D. 寻找从最大空间区开始11、CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用( ) A. 并行技术 B. 通道技术 C. 缓冲技术 D. 虚拟技术12、从用户的角度看，引

16、入文件系统的主要目的是( ) A. 实现虚拟存储 B. 保存系统文件 C. 保存用户和系统文档 D. 实现对文件的安名存取13、在下列文件的物理结构中，( )不利于文件长度增长。 A. 顺序结构 B. 连接结构 C. 索引结构 D. Hash结构14、磁盘上的文件以( )单位读写。 A. 块 B. 记录 C. 柱面 D. 磁道15、操作系统提供给程序员的接口是( ) A. 进程 B. 系统调用 C. 库函数 D. 系统调用和库函数二、 填空题：（每空1分，共15分）1、操作系统的基本功能包括 处理机管理、 存储器 管理、设备管理、文件 管理。除此之外还为用户使用操作系统提供了用户接口。2、临界

17、资源的概念是 ，而临界区是指 。3、作业调度又被称为 ，用于决定把外存上地哪些作业调入内存，并为它们创建 、分配必要的资源。4、在页式存储器管理中，逻辑地址由 和 两部分组成。5、根据文件的逻辑结构，文件可以分为_和_两类。6、目前常用的外存分配方法有：连续分配、_分配、_分配。7、一个进程只有在获得通道、 和所需设备三者之后，才具备进行I/O操作的物质条件。三、简答题（每题5分，共20分）1、程序和进程的主要区别是什么？装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级2、什么是虚拟存储器？虚拟存储器有哪些基本特征？3、段式存储器管理和页式存储器管理的区别是什么？4、二级目录和多级目

18、录的好处是什么？四、应用题（共35分）1、现有一个具有n个缓冲区的缓冲池，Produce进程把它生产的消息放入一个缓冲区，Consumer进程可从一个缓冲区中取得一个消息消费。用信号量实现生产者和消费者之间的同步与互斥。请将下面的生产者和消费者算法补充完整。生产者和消费者对缓冲池互斥访问的信号量为SM，缓冲池的初值SB=n，缓冲池中消息个数初值为SP=0。把下面的算法填写完整。（本题8分）初值设置SM= ；SB=n；sp=0P生产者： While(1) .Producer an item Wait( ) 缓冲操作 Singal( )C消费者： While(1) .Wait( ) 缓冲操作 Si

19、ngal( )Consume the item2、银行家算法中，若出现下述的资源分配情况： ProcessAllocationNeedAvailableP00 , 0 , 3, 20 , 0 , 1, 21 , 6 , 2, 2P11 , 0 , 0, 01 , 7 , 5, 0P21 , 3 , 5, 42 , 3 , 5, 6P30 , 3 , 3, 20 , 6 , 5, 2P40 , 0 , 1, 40 , 6 , 5, 6试问：（1）当前系统状态是否安全？如果安全写出安全序列。（5分） （2）若进程P1 提出请求 Request ( 1 , 2 , 2, 2 ) 后，系统能否将资源分

20、配给它？（2分） 装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级3、已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给作业分配2个物理块，采用FIFO页面淘汰法时缺页率为多少？要求写（画）出页面置换过程。（本题 5分）4、假设一磁道有200个柱面，编号为0 199 ，在完成了磁道125处的请求后，当前正在磁道143处为一请求服务，若请求队列的先后顺序为86，147，91，177，94，150，102，175，130。若采用SSTF（最短寻道时间优先）算法完成上述请求，写出磁道移动的顺序，并计算磁头移动的总距离。（本题5 分）5、我们打开计算

21、机中的某个word文档，然后通过打印机打印文档中的内容，在这个过程中，操作系统为我们做了什么？试从操作系统五大功能的角度加以分析。（本题 10分）装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级东 北 大 学 秦 皇 岛 分 校课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页 题号一二三四总分得分阅卷人一、 填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 表格管理 和出错

22、处理。2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。4、LR（0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。7、确定有穷自动机DFA是 NFA 的一个特例。8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。二、 选择题（每题2分，共20分）1、LR语法分析栈中存放的状态是识别 B 的DFA状态。A、前缀 B、可归前缀 C、项目 D、句柄2、 D 不可能是

23、目标代码。A、汇编指令代码 B、可重定位指令代码 C、绝对机器指令代码 D、中间代码3、一个控制流程图就是具有 C 的有向图A、唯一入口结点 B、唯一出口结点 C、唯一首结点 D、唯一尾结点4、设有文法GS：Sb|bBBbS，则该文法所描述的语言是 C 。A、L（G）=bi|i0 B、L（G）=b2i|i0 C、L（G）=b2i+1|i0 D、L（G）=b2i+1|i15、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。A、编译器 B、汇编器 C、解释器 D、预处理器6、在目标代码生成阶段，符号表用于 D 。A、目标代码生成 B、语义检查 C、语法检查 D、预处理器地址分配7、

24、规范归约是指 B 。A、最左推导的逆过程 B、最右推导的逆过程 C、规范推导 D、最左归约逆过程8、使用 A 可以定义一个程序的意义。A、语义规则 B、词法规则 C、语法规则 D、左结合规则9、经过编译所得到的目标程序是 D 。A、三元式序列 B、四元式序列 C、间接三元式 D、机器语言程序或汇编语言程序10、在一个基本块内进行的代码优化是 B 。A、全局优化 B、局部优化 C、循环优化 D、代码外提三、简答题（3小题，共30分）1、已知文法GS：SAc|aBAab Bbc证明该文法具有二义性（本题6分）证明：因为该文法的句型abc存在如下两棵语法树：所以，该文法具有二义性装 订 线装 订 线 内 不 要 答 题学 号姓 名班 级3、若有文法GS：SbAb A（B|a BAa）。构造该文法的简单优先关系矩阵。（10分）解：4、构造正规表达式（a|b）* b的DFA并化简。（14分）解：先构造其NFA如下：确定化为DFA： 将其最小化如下：四、综合题（20分）设有文法GS：SBAABS|dBaA|bS|c（1） 证明文法G是LL（1）文法。（2） 构造LL（1）分析表。（3） 写出句子adccd的分析过程。解：（1）可见，文法G是是LL（1）文法。（2）（3）