甘肃省专升本计算机科学与技术专业习题19.docx
《甘肃省专升本计算机科学与技术专业习题19.docx》由会员分享，可在线阅读，更多相关《甘肃省专升本计算机科学与技术专业习题19.docx（37页珍藏版）》请在冰点文库上搜索。
甘肃省专升本计算机科学与技术专业习题19
甘肃省2013年专升本计算机科学与技术专业习题
我要升本网2013年第19期
目录
习题一1
习题二3
习题三7
习题四16
习题五23
习题六27
习题一
一．思考题
3.什么是操作系统？
计算机系统中配置操作系统的主要目标是什么？
答（p1）：
操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务，合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。
配置操作系统的主要目标可归结为：
（1）方便用户使用
（2）扩大机器功能（3）管理系统资源（4）提高系统效率（5）构筑开放环境。
5.操作系统要为用户提供哪些基本和共性的服务？
答（p25）：
操作系统提供给程序和用户的共性服务大致有：
（1）创建程序
（2）执行程序（3）数据I/O（4）信息存取（5）通信服务（6）错误检测和处理
9．试叙述系统调用的实现原理。
答（p28）系统调用的实现有以下几点：
⑴编写系统调用处理程序⑵设计一张系统调用入口地址表，每个入口地址都指向一个系统调用的处理程序，有的系统还包含系统调用自带参数的个数⑶陷入处理机制，需开辟现场保护，以保存发生系统调用时的处理器现场。
10.试叙述系统调用与过程调用的主要区别。
答（p29）⑴调用形式不同⑵被调用代码的位置不同⑶提供方式不同⑷调用的实现不同
二．应用题
2.一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，程序B后开始运行。
程序A的运行轨迹为：
计算50ms、打印100ms、再计算50ms、打印100ms，结束。
程序B的运行轨迹为：
计算50ms、输入80ms、再计算100ms，结束。
试说明
（1）两道程序运行时，CPU有无空闲等待？
若有，在哪段时间内等待？
为什么会等待？
（2）程序A、B有无等待CPU的情况？
若有，指出发生等待的时刻。
答：
画出两道程序并发执行图如下：
（1）两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间（见图中有色部分）。
（2）程序A无等待现象，但程序B有等待。
程序B有等待时间段为180ms至200ms间（见图中有色部分）。
学生补充：
程序B在0~50ms时也存在等待。
习题二
一．思考题
26.什么是进程？
计算机操作系统中为什么引入进程？
（教材113~教材114页）
进程的定义：
进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。
引入进程的原因：
一是刻画系统的动态性，发挥系统的并发性，提高资源利用率。
二是解决共享性，正确描述程序的执行状态。
28.进程最基本的状态有哪些？
哪些事件可能引起不同状态之间的转换？
进程最基本的状态有三种：
运行态：
进程占有处理器正在运行。
就绪态：
进程具备运行条件，等待系统分配处理器以便运行。
等待态：
又称为
态或睡眠态，指进程不具备运行条件，正在等待某个事件的完成。
进程状态转换的具体原因：
运行态等待态等待使用资源或某事件发生，如等待外设传输、等待人工干预。
等待态就绪态资源得到满足或某事件已经发生，如外设传输结束；人工干预完成。
运行态就绪态运行时间片到，或出现有更高优先权进程。
就绪态运行态CPU空闲时被调度选中一个就绪进程执行。
34.叙述组成进程的基本要素，并说明它的作用。
（教材120页）
每个进程有4个要素组成：
控制块、程序块、数据块和堆栈。
（1）进程控制块每一个进程都将捆绑一个进程控制块，用来存储进程的标志信息、现场信息和控制信息。
进程创建时建立进程控制块，进程撤销时回收进程控制块，它与进程一一对应。
（2）进程程序块即被执行的程序，规定了进程一次运行应完成的功能。
通常它是纯代码，作为一种系统资源可被多个进程共享。
（3）进程数据块即程序运行时加工处理对象，包括全局变量、局部变量和常量等的存放区以及开辟的工作区，常常为一个进程专用。
（4）系统/用户堆栈每一个进程都将捆绑一个系统/用户堆栈，用来存储进程的标志信息、现场信息和控制信息。
进程创建时建立进程控制块，进程撤销时回收进程控制块，它与进程一一对应。
38.什么是进程的上下文？
简述其主要内容。
（教材120页）
操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文（processcontext）。
它包括三个组成部分：
（1）用户级上下文（user-levelcontext）。
由用户进程的程序块、用户数据块（含共享数据块）和用户堆栈组成的进程地址空间。
（2）系统级上下文（system-levelcontext）。
包括进程控制块、内存管理信息、进程环境块，以及系统堆栈等组成的进程地址空间。
（3）寄存器上下文（registercontext）。
由程序状态字寄存器、各类控制寄存器、地址寄存器、通用寄存器、用户栈指针等组成。
52.试从调度、并发性、拥有资源和系统开销四个方面对传统进程和线程进行比较。
线程
进程
调度
是操作系统中的基本调度和分派单位，具有唯一的标识符和线程控制块。
进程具有独立的虚地址空间，以进程为单位进行任务调度，系统必须交换地址空间，切换时间长。
并发性
同一进程的多个线程可在一个/多个处理器上并发或并行地执行
许多多任务操作系统限制用户能拥有的最大进程数目，这对许多并发应用来说是不够的。
拥有
资源
同一进程的所有线程共享但不拥有进程的状态和资源，且驻留在进程的同一个主存地址空间中，可以访问相同的数据，通信和同步的实现十分方便。
是系统中资源分配和保护的基本单位，也是系统调度的独立单位。
每个进程都可以各自独立的速度在CPU上推进。
系统
开销
作为系统调度和分派的基本单位，会被频繁地调度和切换。
同一进程中的多线程共享同一地址空间，能使线程快速切换。
对多个进程的管理（创建、调度、终止等）系统开销大，如响应客户请求建立一个新的服务进程的服务器应用中，创建的开销比较显著。
58．什么是内核级线程、用户级线程和混合式线程？
对它们进行比较。
内核级线程线程管理的所有工作由操作系统内核来做。
优点：
（1）在多处理器上，内核能够同时调度同一进程中多个线程并行执行；
（2）若其中的一个线程被阻塞了，内核能调度同一进程的其它线程占有处理器并运行，也可以运行其它进程中的线程。
（3）由于内核线程仅有很小的数据结构和堆栈，KLT的切换比较快，内核自身也可以用多线程技术实现，从而，能提高系统的执行速度和效率。
缺点：
应用程序线程在用户态运行，而线程调度和管理在内核实现，在同一进程中，控制权从一个线程传送到另一个线程时需要用户态——内核态——用户态的模式切换，系统开销较大。
用户级线程线程管理的全部工作都由应用程序来做，在用户空间内实现，内核是不知道线程的存在的。
优点：
（1）线程切换不需要内核特权方式。
（2）按应用特定需要允许进程选择调度算法。
缺点：
（1）在传统的基于进程操作系统中，大多数系统调用将阻塞进程。
（2）在纯ULT中，多线程应用不能利用多重处理的优点。
二．应用题
11.有5个批处理作业A到E均已到达计算中心，其运行时间分别10、6、2、4和8分钟；各自的优先级分别被规定为3、5、2、1和4，这里5为最高级。
若不考虑系统切换开销，计算出平均作业周转时间。
（1）FCFS（按A、B、C、D、E）；
（2）优先级调度算法，（3）时间片轮转法（每个作业获得相同的2分钟长的时间片）。
（1）FCFS调度算法（调用次序：
A、B、C、D、E）
（2）优先级调度算法（调用次序：
B（5）、E（4）、A（3）、C
（2）、D
（1））
（3）时间片轮转法（调用次序：
按照2s的时间间隔循环）
按次序ABCDEABDEABEAEA轮转执行。
14.单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法性能较好？
请完成下表：
FIFO
HRRF
开始时只有作业1，作业1被选中，执行时间2小时。
作业1执行完毕后，作业2的时间响应比为1+（2-1:
50）/1=1.1667
作业3的时间响应比为1+（2-1:
35）/0:
25=1+0.416667故选3
然后选择作业2。
可见HRRF比FIFO要好。
本次的作业出现如下四个问题：
1）结果未能全部化为小数2）单位要统一
3）小数点四舍五入4）大多数同学没有能够画图说明
习题三
一．思考题
8.解释进程的竞争关系和协作关系。
（教材213页）
竞争关系：
系统中的多个进程之间彼此无关，它们并不知道其它进程的存在，并且也不接受其它进程执行的影响。
协作关系：
某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。
当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，知道其它合作进程发来协调信号或消息后方被唤醒并继续执行。
这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。
9．试说明进程的互斥和同步两个概念之间的异同。
进程的互斥是解决进程间竞争关系（间接制约关系）的手段。
进程互斥是指若干个进程要使用同一资源时，任何时刻最多允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。
进程的同步是解决进程间协作关系（直接制约关系）的手段。
进程同步指两个以上进程基于某个条件来协调它们的活动。
一个进程的执行依赖于另一个协作进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒。
10．什么是临界区和临界资源？
对临界区管理的基本原则是什么？
临界区——并发进程中与共享变量有关的程序段。
临界资源——共享变量代表的资源。
临界区管理的基本原则：
Ø
（1）一次至多一个进程能够在它的临界区内；
Ø
（2）不能让一个进程无限地留在它的临界区内；
Ø（3）不能强迫一个进程无限地等待进入它的临界区。
特别，进入临界区的任一进程不能妨碍正等待进入的其它进程的进展；
19．试比较管程与进程的不同点（教材237页）。
19.
（1）管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块；进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。
20.
（2）管程可以作为程序设计语言的一个成分，采用管程作为同步机制便于用高级语言来书写程序，也便于程序正确性验证。
有相对固定的代码编写模式；进程则可以采用中级语言（C语言）也可以采用高级语言实现，其代码编写模式相对自由。
21.（3）管程提供了一种互斥机制，进程可以互斥地调用这些过程；进程可以并发地执行，进程的并发性能改进资源利用率提高系统效率。
22.（4）管程把分散在各个进程中互斥地访问公共变量的那些临界区集中了起来，提供对他们的保护；进程既是系统中资源分配和保护的基本单位，也是系统调度的独立单位。
23.（5）管程是一段管理临界区资源的代码，而进程则有生命周期。
24．什么是管道？
如何通过管道机制实现进程间通信？
（教材254页）
管道（pipeline）是连接读写进程的一个特殊文件，允许进程按先进先出传送数据，也能使进程同步执行操作。
发送进程视管道文件为输出文件，以字符流形式把大量数据送入管道；接收进程将管道文件视为输入文件，从管道中接收数据，所以，也叫管道通信。
管道中的消息是无界的，它存于外存。
此外，还需要一定的机制协调读写进程。
25．什么是消息队列机制，叙述其工作原理。
消息队列本身是操作系统核心为通信双方进程建立的数据结构，两个用户进程间通过发送和接收系统调用来借助消息队列传递和交换消息，这样通信进程间不再需要共享变量。
如图3-11（教材263页）所示，进程间的通信通过消息队列进行。
消息队列可以是单消息队列，也可以是多消息队列（按消息类型）；既可以单向，也可以双向通信；既可以仅和两个进程有关，也可以被多个进程使用。
28．什么是死锁？
什么是饥饿？
试举日常生活中的例子说明之。
如果在一个进程集合中的每个进程都在等待只能由该集合中的其它一个进程才能引发的事件，则称一组进程或系统此时发生了死锁（教材268页）。
饥饿是指一个进程由于其它进程总是优先于它而被无限期拖延（教材214页）。
29．叙述产生死锁的必要条件。
（1）互斥条件（mutualexclusion）：
进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。
（2）占有和等待条件（mutualexclusion）：
进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已经被占用的资源时，它被置成等待状态，直到占用者释放资源。
（3）不剥夺条件（nopreemption）：
任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。
（4）循环等待条件（circularwait）：
存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。
二．应用题
2.设有n个进程共享一个互斥段，如果：
（1）每次只允许一个进程进入互斥段；
（2）每次最多允许m个进程（m≤n）同时进入互斥段。
试问：
所采用的信号量初值是否相同？
信号量值的变化范围如何？
所采用的互斥信号量初值不同。
1）互斥信号量初值为1，变化范围为[-n+1，1]。
当没有进程进入互斥段时，信号量值为1；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为0；当有1个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-1个进程等待进入互斥段，故此时信号量的值应为-（n-1）也就是-n+1。
2）互斥信号量初值为m，变化范围为[-n+m，m]。
当没有进程进入互斥段时，信号量值为m；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为m-1；当有m个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0；当有m个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-m个进程等待进入互斥段，故此时信号量的值应为-（n-m）也就是-n+m。
4.有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。
试用：
1）信号量和P、V操作；2）管程，来实现用户进程的同步算法。
1）使用信号量和P、V操作：
varA:
array[1..100]ofRec;
Rec=record
number:
integer;
name:
string;
end;
i:
integer;
fori:
=1to100do{A[i].number:
=i;A[i].name:
=null;}
mutex,seatcount:
semaphore;//semaphore中文含义：
信号量
mutex:
=1;seatcount:
=100;
cobegin
processreaderi（varreadername:
string）（i=1,2,…）{
P（seatcount）;
P（mutex）;
fori:
=1to100do{
i++;
ifA[i].name=nullthenA[i].name:
=readername;/*读者登记*/
}
//必须采用这种方式,因为该空位是随机产生的。
我们无法知道哪个
//读者何时离开。
V（mutex）
进入阅览室，座位号i，坐下读书;
P（mutex）;//读书完毕，需要退场
A[i]name:
=null;
V（mutex）;
V（seatcount）;
离开阅览室;
}
coend.
2）使用管程操作：
TYPEreadbook=monitor
VARR:
condition;
i,seatcount:
integer;
name:
array[1..100]ofstring;
DEFINEreadercome,readerleave;
USEcheck,wait,signal,release;
procedurereadercome（readername）
begin
check（IM）;
ifseatcount≥100wait（R,IM）
seatcount:
=seatcount+1;
fori=1to100doi++
ifname[i]==nullthenname[i]:
=readername;
gettheseatnumber=i;
release（IM）;
end
procedurereaderleave（readername）
begin
check（IM）;
seatcount--;
fori=1to100doi++
ifname[i]==readernamethenname[i]:
=null;
release（IM）;
end
begin
seatcount:
=100;name:
=null;
end
cobegin
processreaderi（i=1,2.…）
begin
readercome（readername）;
readthebook;
readerleave（readername）;
leavethereadroom;
end
coend.
如何做管程题目？
参考书上的例题程序一步步做下来即可。
21．系统有同类资源m个，被n个进程共享，问：
当m＞n和m≤n时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁?
当m≤n时，每个进程最多请求1个这类资源时，系统一定不会发生死锁。
当m>n时，如果m/n不整除，每个进程最多可以请求”商+1”个这类资源，否则为”商”个资源，使系统一定不会发生死锁。
28．把死锁检测算法用于下面的数据，并请问：
（1）此时系统此时处于安全状态吗？
（2）若第二个进程提出资源请求request2（0，0，1，0），系统能分配资源给它吗？
（3）若第五个进程提出资源请求request5（0，0，1，0），系统能分配资源给它吗？
答：
（1）此时可以找出进程安全序列：
P4，P1，P5，P2，P3。
故系统处于安全状态。
（2）可以分配，存在安全序列：
P4，P1，P5，P2，P3。
（3）不可分配，系统进入不安全状态。
习题四
一．思考题
3．什么是逻辑地址（空间）和物理地址（空间）（教材306~307页）？
用户目标程序使用的地址单元称为逻辑地址（相对地址），一个用户作业的目标程序的逻辑地址稽核称为该作业的逻辑地址空间。
主存中的实际存储单元称为物理地址（绝对地址），物理地址的总体相应构成了用户程序实际运行的物理地址空间。
4．何谓地址转换（重定位）？
有哪些方法可以实现地址转换（教材307页）？
为了保证程序的正确运行，必须把程序和数据的逻辑地址转换为物理地址，这一工作称为地址转换或重定位。
地址转换有两种方式，一种方式是在作业装入时由作业装入程序（装配程序）实现地址转换，称为静态重定位；这种方式要求目标程序使用相对地址，地址变换在作业执行前一次完成；
另一种方式是在程序执行过程中，CPU访问程序和数据之前实现地址转换，称为动态重定位。
5．分区存储管理中常用哪些分配策略？
比较它们的优缺点。
常用的分配策略有两种：
固定分区存储管理及可变分区存储管理。
固定分区存储管理
优点：
预先将主存分割成若干个连续区域，分割时各区在主存分配表中可按地址顺序排列。
其主存分配算法十分简单。
解决单道程序运行在并发环境下不能与CPU速度很好匹配的问题。
解决了单道程序运行主存空间利用率低的问题。
缺点：
预先规定了分区大小，使得大程序无法装入，用户不得不采用覆盖等技术补救，不但加重用户负担，而且极不方便。
主存空间的利用率不高，往往一个作业不可能恰好填满分区。
因为分区的数目是在系统初启时确定的，限制了多道运行的程序数。
可变分区存储管理
优点：
克服固定分区方式中的主存空间的浪费，进一步提高了主存资源利用率。
有利于多道程序设计。
实现了多个作业对主存的共享。
缺点：
回收算法复杂。
各种分配算法都有一定的缺陷，难以避免内存碎片的产生。
采用动态重定位装入作业，作业程序和数据的地址转换需要专门硬件寄存器的支持。
13．试比较分页式存储管理和分段式存储管理。
段式
页式
分段由用户设计划分，每段对应一个相应的的程序模块，有完整的逻辑意义
分页用户看不见，由操作系统为内存管理划分
段面是信息的逻辑单位
页面是信息的物理单位
便于段的共享，执行时按需动态链接装入。
页一般不能共享
段长不等，可动态增长，有利于新数据增长。
页面大小相同，位置不能动态增长。
二维地址空间：
段名、段中地址；段号、段内单元号
一维地址空间
管理形式上象页式，但概念不同
往往需要多次缺页中断才能把所需信息完整地调入内存
实现页（段）的共享是指某些作业的逻辑页号（段号）对应同一物理页号（内存中该段的起始地址）。
页（段）的保护往往需要对共享的页面（段）加上某种访问权限的限制，如不能修改等；或设置地址越界检查，对于页内地址（段内地址）大于页长（段长）的存取，产生保护中断。
二．问答题
3．一个页式存储管理系统使用FIFO、OPT和LRU页面替换算法，如果一个作业的页面走向为：
（1）2、3、2、1、5、2、4、5、3、2、5、2。
（2）4、3、2、1、4、3、5、4、3、2、1、5。
（3）1、2、3、4、1、2、5、1、2、3、4、5。
当分配给该作业的物理块数分别为3和4时，试计算访问过程中发生的缺页中断次数和缺页中断率。
（1）物理块数=3
FIFO
缺页中断次数为9次，缺页中断率为9/12=75.0%
OPT
缺页次数为6次，缺页中断率为6/12=50.0%
LRU
缺页次数为7次，缺页中断率为7/12=58.3%
物理块数=4
FIFO
缺页次数为6次，缺页中断率为6/12=50.0%
OPT
缺页次数为5次，缺页中断率为5/12=41.7%
LRU
缺页次数为6次，缺页中断率为6/12=50.0%
（2）物理块数=3
FIFO
缺页次数为9次，缺页中断率为9/12=75.0%
OPT
发生7次缺页中断，缺页中断率为7%12=58.3%
LRU
发生10次缺页中断，缺页中断率为10/12=83.3%
物理块数=4
FIFO
发生10次缺页中断，缺页中断率为10/12=83.3%
OPT
发生6次缺页中断，缺页中断率为6/12=50.0%
LRU
发生8次缺页中断，缺页中断率为8/12=66.7%
（3）物理块数=3
FIFO
发生9次缺页中断，缺页中断率为9/12=75.0%
OPT
发生7次缺页中
升级会员 