四川大学2011年攻读博士学位研究生入学考试试题
（操作系统3130）
一、简述（50分，每小题5分） 1、死锁预防
死锁预防是计算机操作系统，在设计时确定资源分配算法，为保证不发生死锁，而破坏产生死锁的必要条件的行为过程
死锁产生条件：
1、互斥条件 每一资源或者被分配给一个进程，或者空闲。 2、占有并请求条件 已分配到了一些资源的进程可以申请新的资源
3、不可剥夺条件 已分配给某些进程的资源不可被剥夺，只能有占有它的进程使用完后主动释放
4、循环等待条件 系统必然存在一条有两个或两个以上的进程组成的循环，联众的每一个进程都在等待相邻进程所占用的资源
2、页面抖动
抖动(Thrashing)就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调出一页程序或数据送磁盘的对换区中，如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访问，因而又需将它调入，如此频繁更换页面，以致花费大量的时间，我们称这种现象为\"抖动\";
产生抖动的原因是由于CPU的利用率和多道程序度的对立统一矛盾关系引起的，为了提高CPU利用率，可提高多道程序度，但单纯提高多道程序度又会造成缺页率的急剧上升，导致CPU的利用率下降，而系统的调度程序又会为了提高CPU利用率而继续提高多道程序度，形成恶性循环，我们称这时的进程是处于\"抖动\"状态. 3、快表
在操作系统中引入快表是为了加快地址映射速度。
在虚拟页式存储管理中设置了快表，用于保存正在运行进程页表的子集，通常快表存放在（高速缓冲存储器Cache）中。
快表和页表的区别与区别
页表指出逻辑地址中的页号与所占主存块号的对应关系。
作用：页式存储管理在用动态重定位方式装入作业时，要利用页表做地址转换工作。 快表就是存放在高速缓冲存储器的部分页表。它起页表相同的作用。由于采用页表做地址转换，读写内存数据时CPU要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。
4、最短进程优先调度
最短作业优先调度算法SPF，是指对短进程优先调度的算法。短进程优先调度算法从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而阻塞放弃处理机时再重新调度。
5、实时操作系统
实时操作系统（RTOS）是指当外界事件或数据产生时，能够接受并以足够快的速度予以处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统做出快速响应，调度一切可利用的资源完成实时任务，并控制所有实时任务协调一致运行的操作系统。提供及时响应和高可靠性是其主要特点。
6、磁盘冗余阵列RAID
磁盘冗余阵列（RAID，redundant array of independent disks，redundant array of inexpensive disks）是把相同的数据存储在多个硬盘的不同的地方的方法。
基本思想就是把多个相对便宜的小磁盘组合起来，成为一个磁盘组， 使性能达到甚至超过一个价格昂贵、容量巨大的磁盘。根据选择的版本不同，RAID比单盘有以下一个或多个方面的益处：增强数据整合度，增强容错功能，增加吞吐量或容量。另外，磁盘组对于计算机来说， 看起来就像一个单独的磁盘或逻辑存储单元。分为RAID-1，RAID-10，RAID-3，RAID-30，RAID-5，RAID-50。
围绕RAID的基本想法就是把多个便宜的小磁盘组合到一起，成为一个磁盘组式的逻辑硬盘，因此，操作系统仅把它们看作一个单一的逻辑存储单元或磁盘。通过这种手段使逻辑硬盘的性能达到或超过一个容量巨大、价格昂贵的磁盘。RAID常被用在服务器计算机上，并且常使用完全相同的硬盘作为组合。由于硬盘价格的不断下降与和RAID功能更加有效地与主板整合，它也成为了高级最终用户的一个选择，特别是需要大量存储的工作，如：视频与音频制作。
7、索引顺序文件
在文件中随机存取记录，需要知道记录的地址。例如，一个客户想要查询银行账户，客户和出纳员都不知道客户记录的地址，客户只能给出纳员自己的帐号（键）。这里，索引文件可以把帐号和记录地址关联起来。
索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段；顺序文件的键和在磁盘上相应记录的地址。存取文件中的记录需按以下步骤：
（1）整个索引文件都载入到内存中（文件很小，只占用很小的内存空间）。 （2）搜索项目，用高效的算法（如折半查询法）查找目标键。 （3）检索记录的地址。
（4）按照地址，检索数据记录并返回给用户。 由索引表和主文件两部分构成。
索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的每项称作索引项。索引项是按键（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。
索引顺序文件 (Indexed Sequential File)
主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。
索引非序文件(Indexed NonSequentail File)
主文件按主关键字无序的文件称索引非顺序文件。在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。
索引文件的好处之一就是可以有多个索引，每个索引有不同的键。例如，职员的文件可以按社会保险号或姓名来检索。这种索引文件被称为倒排文件。
8、强制访问控制
通过无法回避的访问来阻止直接或间接地非法入侵。
自主访问控制又称自主存取控制(DAC :Discretionary Access Control )：
同一用户对于不同的数据对象有不同的存取权限，不同的用户对同一对象也有不同的权限，用户还可将其拥有的存取权限转授给其他用户。
强制访问控制又称强制存取控制(MAC : Mandatory Access Control )：
每一个数据对象被标以一定的密级，每一个用户也被授予某一个级别的许可证，对于任意一个对象，只有具有合法许可证的用户才可以存取。
两者区别：DAC的数据存取权限由用户控制，系统无法控制；MAC安全等级由系统控制，不是用户能直接感知或进行控制的。
9、缓冲区溢出攻击
缓冲区溢出攻击是利用缓冲区溢出漏洞所进行的攻击行动。缓冲区溢出是一种非常普遍、非常危险的漏洞，在各种操作系统、应用软件中广泛存在。利用缓冲区溢出攻击，可以导致程序运行失败、系统关机、重新启动等后果。
缓冲区溢出是指当计算机向缓冲区内填充数据位数时超过了缓冲区本身的容量，溢出的数据覆盖在合法数据上。理想的情况是：程序会检查数据长度，而且并不允许输入超过缓冲区长度的字符。但是绝大多数程序都会假设数据长度总是与所分配的储存空间相匹配，这就为缓冲区溢出埋下隐患。操作系统所使用的缓冲区，又被称为“堆栈”，在各个操作进程之间，指令会被临时储存在“堆栈”当中，“堆栈”也会出现缓冲区溢出。
10、非对称加密
对称加密算法在加密和解密时使用的是同一个秘钥；而非对称加密算法需要两个密钥来进行加密和解密，这两个秘钥是公开密钥（public key，简称公钥）和私有密钥（private key，简称私钥）。
与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。
二、设计题（30分）
在设计异地磁盘镜像系统时，我们经常遇到的问题是：生产服务器的数据带宽（例如，生产服务器的磁盘带宽）要比备份网络的带宽高，这在基于Internet的备份网络时尤其突出。因此，我们需要解决生产服务器数据带宽与备份网络带宽的匹配问题。设本地生产服务器的磁盘写驱动为P，需要写入的数据为Data。一般地，同步镜像系统的工作原理是：P将Data同时写到本地数据磁盘以及远程镜像磁盘。显然，在Internet环境下，生产服务器的效率要大打折扣。因此，一种可行的办法是采取异步的方法：即，P将Data同时写到本地数据磁盘以及本地的一个缓冲区B就可以了；而程序Q只要发现B中有数据则立刻将其取出（按先进先出原则）并发送到远程备份服务器，然后再由远程备份服务器将其写入镜像磁盘。
现在请你设计上述异步镜像系统的工作过程，要求给出系统的工作原理、框图、伪代码、主要的数据结构等，假设系统运行前本地磁盘与远程镜像磁盘的格式、大小以及内容等完全一样。
三、论述题（20分）
1、什么是用户级线程和内核级线程？它们有什么区别？（10分）
在多线程操作系统中，各个系统的实现方式并不相同。在有的系统中实现了用户级线程，有的系统中实现了内核级线程
1.内核级线程：
（1）线程的创建、撤销和切换等，都需要内核直接实现，即内核了解每一个作为可调度实体的线程。
（2）这些线程可以在全系统内进行资源的竞争。
（3）内核空间内为每一个内核支持线程设置了一个线程控制块（TCB），内核根据该控制块，感知线程的存在，并进行控制。
在一定程度上类似于进程，只是创建、调度的开销要比进程小。有的统计是1：10 2.用户级线程：
（1）用户级线程仅存在于用户空间。——>对比内核(3) （2）内核并不能看到用户线程。——>重要的区别
（3）内核资源的分配仍然是按照进程进行分配的；各个用户线程只能在进程内进行资源竞争。
1 .内核级线程:切换由内核控制，当线程进行切换的时候，由用户态转化为内核态。切换完毕要从内核态返回用户态；可以很好的利用smp，即利用多核cpu。windows线程就是这样的。
2. 用户级线程内核的切换由用户态程序自己控制内核切换,不需要内核干涉，少了进出内核态的消耗，但不能很好的利用多核Cpu,目前Linux pthread大体是这么做的。
线程的实现可以分为两类：用户级线程(User-Level Thread)和内核线线程(Kernel-Level Thread)，后者又称为内核支持的线程或轻量级进程。在多线程操作系统中，各个系统的实现方式并不相同，在有的系统中实现了用户级线程，有的系统中实现了内核级线程。
以下是用户级线程和内核级线程的区别：
（1）内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。 （2）用户级线程的创建、撤消和调度不需要OS内核的支持，是在语言（如Java）这一级处理的；而内核支持线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。
（3）用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。
（4）在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。
（5）用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。
内核线程的优点：
（1）当有多个处理机时，一个进程的多个线程可以同时执行。 缺点：
（1）由内核进行调度。 用户进程的优点：
（1） 线程的调度不需要内核直接参与，控制简单。 （2） 可以在不支持线程的操作系统中实现。
（3） 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少得多。 （4） 允许每个进程定制自己的调度算法，线程管理比较灵活。这就是必须自己写管理程序，与内核线程的区别
（5） 线程能够利用的表空间和堆栈空间比内核级线程多。
（6） 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起。另外，页面失效也会产生同样的问题。
缺点：
（1）资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用
2、谈谈云存储的前景，安全隐患及其对策。（10分）
云存储是在云计算(cloud computing)概念上延伸和发展出来的一个新的概念，是一种新兴的网络存储技术，[1] 是指通过集群应用、网络技术或分布式文件系统等功能，将网络中大量各种不同类型的存储设备通过应用软件集合起来协同工作，共同对外提供数据存储和业务访问功能的一个系统。当云计算系统运算和处理的核心是大量数据的存储和管理时，云计算系统中就需要配置大量的存储设备，那么云计算系统就转变成为一个云存储系统，所以云存储是一个以数据存储和管理为核心的云计算系统。简单来说，云存储就是将储存资源放到云上供人存取的一种新兴方案。使用者可以在任何时间、任何地方，透过任何可连网的装置连接到云上方便地存取数据。
