操作系统重点

第一章、操作系统概述

一、为什么要区分系统态和用户态？

防止操作系统和关键数据受到用户程序有意或无意的破坏，通常将处理机的执行状态分为系统态和用户态

用户态下操作受到限制不能执行特权指令，防止操作系统或其他程序收到破坏，用户态的程序通过系统调用

接受系统态下的运行的服务
用户态下的程序只能存取自己的指令和数据，不能存取其他程序和操作系统的指令和数据

但是系统态下的进程可以存取操作系统和用户进行的数据，可以执行一切指令

二、多道程序设计的意义？

提高系统资源利用率和吞吐率。当程序需要等待某种事情的发生时，操作系统不用空闲等待，可以执行其他程序、这样CPU和外设可以并行操作
客观世界本身就是一个多道，客观世界有些问题想要快速解决，需要多道系统的出现

三、客户机和服务器模型常用语网络和分布式系统，是否可用于单机系统？

客户机/服务器模型是通用模型，广义上讲，提供服务的叫服务器，请求服务的叫客户机，在客户机/服务器模型中的，文件服务，进程服务都是以服务器进程的形式运行与用户态，用户进程通过向服务器请求或得服务，所以客户机/服务器模型即可用于网络和分布式系统，也可用户单机系统

四、系统调用和一般的函数调用的区别？

系统调用执行的程序在操作系统中的系统态下执行，一般的函数调用由用户准备在用户态下执行

五、过程调用和系统调用的相同点是什么？它们与中断调用的差别是什么？

过程调用和系统调用的执行是完全同步的，在相同的数据集上重复执行，都需要保存现场信息转而执行其他的程序，执行后返回。
中断调用的执行是异步的，在相同的数据集上重复执行，中断的发生点可以是不同刘的。

六、一般计算机的启动过程？

由ROM程序对硬件进行检测
ROM中的启动程序将磁盘引导块读入内存
引导块将OS内核调入内存
执行OS内核程序进行初始化
加载外核处理程序，给出提示，等待用户操作

七、多道程序如何实现CPU计算和IO操作并行？

多道程序系统中CPU无需直接控制IO操作的完成，而是通过通道，DMA，和中断机构控制IO完成，CPU不是空闲等待IO操作的完成，而是转而执行其他应用程序

八、为什么相同的硬件条件下，一个应用程序可以在DOS和Windows下运行却不能在UNIX下运行？

虽然硬件是相同的，但是应用程序的运行需要OS的支持，Windows是兼容DOS的，所以在DOS下运行的应用程序也能在OS下面运行，但是DOS，Windows和UNIX在系统结构,用户接口,API等方面是不兼容的，比如应用用到了windows下的系统调用的API，但是UNIX下没有，程序就无法运行。

九、为什么中断机构对多道操作系统来说是比不可少的？

操作系统的进程切换很多时候都是通过中断来完成的，如时钟中断，特别是在分时系统中，系统调用通过软中断来实现，通道和外设的操作也需要向操作系统发送中断。

十、网络操作系统和分布式操作系统的区别？

1、网络操作系统用户使用自己的机器可以通过网络访问其他机器的资源，通过网络将很多的机器连接起来共享硬件资源，但整个系统对用户来说是分散的，不透明的

2、分布式OS也是通过网络将整个系统连接起来，但是整个系统对用户来说是透明的，用户使用分布式OS就像在使用自己的电脑

十一、将手工操作，单道批处理，多道批处理，多用户分时系统按照CPU利用率从小到大排序

手工<单道批处理系统<多用户分时系统<多道批处理系统

第二章、进程和线程的管理

一、举例说明多道程序系统时区封闭性和再现性

有两个循环程序，共享一个变量N，

Pa{
	repeat
		N:=N+1;
	until false
}

Pb{
	repeat
		print(N);
		N=0;
	until false
}

某时刻N的初值为n,可能出现以下三种情况

1、在在print(N)和N:=0之前，n的变化过程为：n+1,n+1,0

2、在print(N)和N:=0中间，n的变化过程是：n,n+1,0

3、在print(N)和N:=0之后，n的变化过程是：n,0,n+1

二、进程的挂起状态、阻塞状态、以及就绪状态的区别？

共同点是它们都没有占用CPU

不同点是挂起的进程处于禁止状态，在解除挂起之前不会参与对资源的竞争，也没有机会占用CPU

阻塞状态和就绪状态的进程都处于活动状态，都有活动处理机的机会，都可能有新的资源要求

三、、在多道程序系统中，当需要等待某种事情发生时，系统将处于何种状态？

这取决于进程程序的处理方式

1、调用阻塞原语，阻塞自己、让出CPU资源

2、进行忙等，不放弃CPU

当等待某种事件发生时，不一定要进入阻塞状态

四、用户线程和内核支持线程有何区别？

1、用户级线程是OS不可感知的，内核支持级线程是OS可感知的

2、用户级线程的创建、撤销和调度不需要OS内核支持，是在语言这一级处理的，而内核支持级线程的创建、撤销、调度都需要OS内核的支持，与进程的创建撤销和调度是大致相同的

3、用户级线程执行系统调用指令时会导致其所属进程被中断，内核支持线程执行系统调用指令时只会导致改线程被中断

4、在只有用户级线程的系统内，CPU调度是以进程为单位，一个进程所对应的多个线程由用户程序切换运行，而在内核支持系统，CPU的调度以线程为单位，通过OS的线程调度程序负责调度

5、用户级线程支持的程序实体是运行在用户态下面的程序，内核支持用户程序实体可以运行在任何状态下

第三章、进程的同步与通信

一、多个进程对信号量S进行了5次 P操作，2次V操作后，现在信号量的值是 -3，与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？

处于阻塞状态的进程有3个
初值为-3+5-2=0

二、设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开车门。试问：

(1) 在汽车不断地到站、停车、行驶过程中，司机和售票员的活动是同步关系还是互斥关系？

司机的活动：开车、停车

售票员的活动：关车门、售票、开车门

司机停车、售票员开门、乘客下车、售票员关门、司机开车、售票员售票

司机和售票员的活动是同步关系

(2) 用信号量和P、V操作实现他们间的协调操作。

<司机进程>{
    repeat
      车门是否关闭?没关则等待
      启动车辆
      正常行车
      到站停车
      设置车辆已停标志
    until false 
}
<售票员进程>{
    repeat
        关车门
        设置车门已关标志
        售票
        车辆是否到站？没到站则等待
        开车门
        乘客上下车
    until false
}

设置两个信号量

S1车门是否关闭 0

S2车辆是否停车 1

<司机进程>{
    repeat
        P(S1);
        车辆启动;
        正常行车;
        到站停车;
        V(S2);
     until false
}
<司机进程>{
    repeat
        V(S1);
        售票;
        P(S2);
        开车门;
        乘客上下车;
}

三、说明管程中条件变量的含义和作用？

管程中的条件变量是调用管程过程的进程用来执行Wait和Signal操作来挂起或解挂的变量

信号量与管程的条件变量的对比：

信号量要赋初值，而条件变量不用，它只是一个队首指针
在信号量执行P操作不一定会被阻塞，在条件变量上执行Wait()操作会被挂起
在信号量上执行S操作，信号量的值加1，若加1后的值仍小于0，则会唤醒等待的进程，但唤醒者自身不受影响

但是在条件变量上执行Signal()操作则有两种选择，1、P等待，Q离开或等待另一条件发生，2、Q等待，P离开或等待另一条件发生，P和Q是两个进程

四、如下图所示，有多个PUT操作同时向BUFF1放数据，有一个MOVE操作不断地将BUFF1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。BUFF1的容量为m，BUFF2的容量是n, PUT、 MOVE、 GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用Ｐ、Ｖ原语协调PUT、 MOVE的操作，并说明每个信号量的含义和初值。

多生产者消费者问题

buff1 m
buff2 n
put into buff1
move from buff1 to buff2
get from buff2、
多个PUT
<PUT>{
    repeat
        buff1是否有空间?没有则等待
        buff1是否可操作
        PUT
        设置buff1可操作标志
        设置buff1有数据标志
    until false
}
一个MOVE
<MOVE>{
    repeat
        buffer1是否有数据，没有则等待
        buff2是否有空间，没有则等待
        buff1是否可操作
        buff2是否可操作
        MOVE
        设置buff1可操作标志
        设置buff2可操作标志
        设置buff1有空间标志
        设置buff2有数据标志
    until false
}
多个GET
<GET>{
    repeat
        buff2是否有数据？没有则等待
        buff2是否可操作
        GET
        设置buff2可操作标志
        设置buff2有空间标志
    until false
}

五、某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定：

(1) 每两个学生组成一组，各占一台机器，协同完成上机实习；

(2) 只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房；

(3) 上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。

试用P、V操作模拟上机实习过程。

<门卫>{
    repeat
        学生1是否到达？没有则等待
        学生2是否到达？没有则等待
        是否有空闲计算机1？没有则等待
        是否有空闲计算机2？没有则等待
        分配计算机
        设置学生1可进入标志
        设置学生2可进入标志
    until false
}
<学生>{
	   设置有学生到达标志
       学生是否可进入？
       上机实习
       设置实习完成标志 
       老师是否可检查？不能则等待
       离开机房
}
<教师>{
     repeat
         是否有学生1完成实习？没有则等待
         是否有学生2完成实习？没有则等待
         检查实习
         设置学生1完成实习的标志
         设置学生2完成实习的标志
     until false
}
computer 2m	2m
student 2n	0  到达的学生	0
finish：是否有学生完成实习	0
enter：学生是否可以进入	 0
test：老师是否检查完一组学生 0
    
<门卫>{
    repeat
		P(student);
    	P(student);
    	P(computer);
    	P(computer);
    	V(enter);
    until false
}
<学生>{
    V(studnet);
    P(enter);
    上机
    V(finish)
    P(test(i))
    V(computer)
}
<教师>{
    repeat
        P(finish)/**是否有需要检查的学生，等待实习完成**/
        P(finish)/**是否有需要检查的学生，等待实习完成**/
        选出可检查的第i组学生
        检查第i组学生的实习成果
        V(test(i))
        V(test(i))
    until false
}

第四章、调度与死锁

一、有三个作业A（到达时间8:50，执行时间1.5小时）、B（到达时间9:00，执行时间0.4小时）、C（到达时间9:30，执行时间1小时）。当作业全部到达后，单道批处理系统按照响应比高者优先算法进行调度，则作业被选中的次序是？

响应比 = 1+(等待时间/执行长度)

作业全部到达后，操作系统才开始调度

进程	到达时间	开始时间	运行长度	结束时间
A	8:50	9:54	1.5	11:44
B	9:00	9:30	0.4	9:54
C	9:30	11:44	1	12:44

各个作业的等待时间为：开始调度的时间-到达的时间

A：0.67

B：0.5

C：0

各个进程的响应比为

响应比 = （等待时间+要求服务时间）/ 要求服务时间

当任务全部到达时，系统开始调度，此时A的等待时间

A：1+0.67/1.5 =1.44

B：1+0.5/0.4 = 2.25

C：1+0/1 = 1

选择B进行运行

当B完成后，时间为9:54,A的等待时间64min,C的等待时间为24m

A=1+64/90=1.71

C=1+24/60=1.4

选A运行，最后再运行C

二、有三个进程P1、P2和P3并发工作。进程P1需要资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3，回答：

（1）若对资源分配不加限制，会发生什么情况？为什么？

可能发生死锁，P1持有S1,P2持有S2，P3持有S3，的同时，再同时申请其他资源，会形成循环等待

（2）为保证进程正确地工作，应采用怎样的资源分配策略？为什么？

采用静态资源分配，在进程运行前分配给其所需的全部资源
资源按序分配，避免出现循环等待的现象
采用银行家算法再分配资源之前进行检测

三、有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。

(1) 先来先服务（按A，B，C，D，E）算法。

从提交到完成所用的时间

执行顺序	运行时间	优先级	等待时间	周转时间
A	10	3	0	10
B	6	5	10	16
C	2	2	16	18
D	4	1	18	22
E	8	4	22	30

平均周转时间(10+16+18+22+30)/5=19.2min

(2) 优先级调度算法。

执行顺序	运行时间	优先级	等待时间	周转时间
B	6	5	0	6
E	8	4	6	14
A	10	3	14	24
C	2	2	24	26
D	4	1	26	30

平均周转时间(6+14+24+26+30)/5=20

(3) 时间片轮转算法。如果系统采用时间片轮转（RR）算法，令时间片为2分钟，5个任务轮流执行的情况为：

第一轮：A B C D E

第二轮：A B D E

第三轮：A B E

第四轮：A E

第五轮：A

平均周转时间为（15+11+3+8+14）*2/5 = 20.4 min

四、考虑由n个进程共享的具有m个同类资源的系统，证明：如果对i=1，2，…，n进程，有Need>0而且所有最大需求量之和小于m+n,那么该系统是死锁无关的。

设每个进程的最大需求量为x，最差的情况下，每个进程占有（x-1）个资源，各自最多再申请一个资源就能完成运行，进而释放它们所占有的资源

此时系统剩余资源为 m-n(x-1),当m-n(x-1)>=1，即n*x<=(m+n-1),也就是当最大资源需求量之和小于(m+n)，那么该系统是死锁无关的

五、设系统中有三种类型的资源（A、B、C）和五个进程（P1、P2、P3、P4、P5），A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表1和表2所示。系统采用银行家算法实施死锁避免策略。

(1) T0时刻是否为安全状态？若是，请给出安全序列。

P1（3，4，7）

P2（1，3，4）

P3（0，0，6）

P4（2，2，1）

P5（1，1，0）

在T0时刻，存在一个安全序列（P4，P5，P3，P2，P1），所以系统是安全的

(2) 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？

不能实施分配，因为系统的可用资源不足，所以只能推迟分配

(3) 在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？

可以，此时系统仍能找到一个安全序列（P4，P1，P3，P5，P2）

(4) 在③的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？

可以实施资源分配

第五章、存储器管理

一、动态重定位的特点有哪些？

动态重定位的实现主要依靠硬件地址变换机构，并且存储管理的软件算法比较复杂
程序代码是按照原样装入内存，在重定位过程中不发生变化
相同的逻辑地址，每次执行都要重定位一次
改变基地址，很容易实现代码在内存中的移动
动态重定位可以将程序分配到不连续的存储区中
实现虚拟存储器需要动态重定位技术的支持

二、有一计算机系统，内存容量为512K，辅存容量为2G，逻辑地址形式如下，求其虚拟存储器的实际容量？**

虚拟内存的理论容量：2^10*2^20B=2^30B=1024M

最大段内地址：2^20B =1M，远大于内存容量

段长超过 512K的内存容量，所以，最大实际段长为512K

所以虚拟存储器的实际容量为：2^10*0.5M=0.5G，所以虚拟存储器的实际容量为0.5G

三、解释静态链接、装入时动态链接和执行时动态链接的不同？

1、静态链接本来是编译系统的工作，但是随着程序执行方式的改进，“程序链接”不再是编译系统的事情，它还需要

OS的支持

程序的静态链接，是指在程序装入内存之前，将已经编译好的多个模块链接成可执行程序，其特点为：1、链接好的可执行程序可反复执行 2、被链接好的模块不能再拆分，不便于修改3、不便于多个程序共享某些模块，需要使用同一模块的多个程序需要将该模块链入自己的程序空间

装入时动态链接，是指在程序加载进内存的时候，由OS将磁盘中的模块在内存中链接成一个可执行程序，特点是：

1、可执行程序只在内存中，每次执行需要重新链接

2、被链接的各个模块在磁盘上是独立存放的

3、多个程序共享某一模块时，只需要在内存中保留该模块的一个副本

执行时动态链接是把程序的链接推迟到程序执行时动态的根据需要进行链接，它除了有装入时动态链接的特点以外，还有一个显著的特点是，只会装入需要的模块，从而减少时空的开销，他增加了链接的复杂性，需要一定的硬件支持。

四、在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us，假设页表的查询与快表的查询同时进行。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。

(1) 求对某一数据进行一次次存取可能需要的时间？

对数据存取有3中情况：

数据在内存中，并且已经存放到块表：

此时用时：1us+8us=9us
数据在内存中，但是其页表项没有存储到快表

此时的用时为：8us查页表+8us存取内存数据
存取的数据不再内存，发生缺页中断

此时的用时为：查询页表+缺页中断+查询页表+存取内存

8us+20us+8us+8us=44us

(2) 现连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间?

第一次存取可能需要的时间为：

1us+8us=9us,8us+8us=16us，8us+20us+8us+8us=44us

第二次，第三次，第四次对应的页表项已经交换到了快表中，所用的存取时间都是一样的1us+8us=9us

五、为什么说分段系统相比于分页系统更容易实现信息的共享和保护？如何实现。

在分页或分段的存储管理中，多个进程并发运行共享同一内存块中的数据是可行的，为了实现共享，在共享者的段表或者页表中，必须有指向共享内存的表目

在分段系统中，被共享的程序或数据可以作为单独的一段，在物理上它是一段，在不同进程中，可以对应不同的逻辑段，相对来说，实现是比较容易的

在分页管理中，这要困难的多，首先必须保证被共享的程序或数据占有整数快，以便和非共享数据分开，其次对于共享数据的访问应该是有限制条件的

因此从共享和保护的实现来看，共享的程序或数据应该作为一个逻辑单位，在分段管理中也就是一段，实现共享和保护就方便的多

实现方式：分段系统中是通过两个或多个进程的段表中的表目指向相同的物理块，并设置共享计数来实现的。

每段设置访问方式，就能实现保护。

六、在虚拟页式的存储管理系统中，为什么要引入缺页中断？缺页中断的实现有那几部构成？各个部分是怎么实现的？

虚拟页式存储管理系统是在页式管理系统上实现的虚拟存储器，作业在执行时，并不是把所有的页都放在主存中的，当要访问的页面不存在时，需要系统通过缺页中段将所需页面由辅存装入主存

缺页中断由缺页处理和页淘汰完成的

缺页处理实现：
1. 中断触发
  
  查询页表时发现逻辑页不在内存中，将其修改位置为0，触发缺页中断
2. 页面调入
  
  OS查找对应页面的辅存地址，将页面调入内存，进行页面淘汰
3. 修改页表
  
  将页面的内存地址填入页表，并将状态位修改为1，缺页中断结束，恢复现场，重新执行指令
页淘汰的实现：
1. 如果内存有空闲页，直接调入外存的页面，修改页表
2. 如果内存已满，则根据页面置换算法，淘汰页面
3. 如果要淘汰的页面的修改位为0，则从外存调入页面覆盖并修改页表
4. 如果要淘汰的页面修改位为1，则申请一块交换空间，将原页面的内容复制到交换空间中，然后将辅存的页面调入其中，并修改页表

第六章、设备管理

一、IO软件一般分为四个层次，用户层，设备无关软件层，设备驱动程序，中断处理程序，请说明下面各项工作是在哪一层完成的？

设备驱动层：

1、将抽象的要求转化为具体的要求，编码转换

2、发送IO指令，控制设备启动

3、检查用户是否有权使用设备

软件层：

负责解释用户的请求，并将请求转化成具体的输入输出，但不检查权限

设备无关的软件层：将逻辑设备名转换为具体的物理设备，实现设备的分配与回收，以及缓冲区管理

向设备寄存器写命令

属于直接操作设备控制器的操作，属于设备驱动层
检查用户是否有权使用设备

设备驱动层
将二进制整数转换成ASCII码以便打印

这属于将抽象的要求转化为具体的要求

二、在缓冲池中有3个队列，分别为空白缓冲队列em，输入缓冲队列in，以及输出缓冲队列out。过程add_buf（type，numb）和take_buf（type，numb）分别用来把缓冲区numb插入type队列和从type队列中取出缓冲区numb。试描述进程从任一缓冲队列得到一个缓冲区的过程get_buf（type,numb）和将一个缓冲区numb放入缓冲队列的过程put_buf（type,numb）？

设置队列的互斥信号量为S，初值为1，设置资源数目信号量为RS，初值为n

Semaphore mutex=1;
Semaphore RS=n;
procedure  put_buf(type,numb)
begin
	P(S);
	add_buf(type,numb);
	V(mutex);
	V(RS);
end;

procedure get_buf(type,numb)
begin
    P(RS);
	P(mutex);
    buffer(numb)=get_buff(type,numb);
    V(mutex);
end;

三、描述操作系统使用公用缓冲池时，数据插入缓冲队列的输入过程？

缓冲池由多个缓冲区构成，每个缓冲区由缓冲池首部和缓冲体构成，系统通过操作缓冲池的首部实现对缓冲区的管理。

通常缓冲池有3个队列，em为空白缓冲区队列，in为装满输入数据的缓冲区队列，out为装满输出数据的缓冲区队列，

另参数type表示缓冲队列类型，参数number表示缓冲区号，缓冲池管理中负责数据输入过程可包括：

1、过程get_buff(type,numb)；以某种规则从type指定的缓冲区队列中摘取一个缓冲区

2、过程put_buff(type,numb)；将numb缓冲区放入相应的缓冲队列

使用上述操作：

输入过程可被描述如下：

1、进程调用get_buff(type,numb),从em队列中获取一个空白缓冲区，返回的编号为numb，获取的缓冲区命名为hin

2、将输入的数据装入到hin中，当hin中装满了数据之后，调用put_buff(in,hin)将该缓冲区插入到输入缓冲队列中

四、试给出两种IO调度算法，并说明为什么IO调度不能使用时间片轮转法？

1、FCFS 先来先服务算法。当多个进程对同一IO设备进行输入输出请求时，按照到达时间排成队列，将IO设备分配给队列的第一个进程

2、优先级高者优先算法。多个进程对同一IO设备进行输入输出请求时，按照进程的优先级排成队列，将IO设备分配给优先级最高的设备

IO设备因其固有属性，只能独占使用，当一个进程使用完的时候其他进程才能使用，在由通道控制的输入输出系统中，通道程序不能被时钟中断所打断，所以IO调度不能使用时间片轮转法。

五、某操作系统中采用单缓冲传送磁盘数据。设从磁盘将数据传送到缓冲区所用时间为T1，将缓冲区数据传送到用户区所用时间为T2，CPU处理数据所用时间为T3。问系统处理该数据所用总时间为多少？

第一个数据块从外存输入到缓冲区并将缓冲区的数据输入到用户区时，第二个数据块将数据输入缓冲区就能和