操作系统

　　1、操作系统概述

　　操作系统的概念、演变历程、特性、分类、运行环境、功能。

　　2、进程

　　进程、进程描述及进程状态转换。

　　3、线程、对称多处理SMP和微内核

　　(1)线程的概念，定义线程的必要性和可能性;

　　(2)线程的功能特性与实现方式;

　　(3)对称多处理SMP体系结构;

　　(4)操作系统的体系结构(微内核与巨内核)及其性能分析。

　　4、并发性

　　(1)并发性问题及相关概念，如临界区、互斥、信号量和管程等;

　　(2)进程互斥、同步和通信的各种算法;

　　(3)死锁的概念、死锁的原因和条件;

　　(4)死锁的预防、避免和检测算法。

　　5、存储器管理

　　(1)分区存储管理、覆盖与交换;

　　(2)页式管理及段式管理;

　　(3)段、页式存储管理方法及实现技术;

　　(4)虚存的原理及相关的各种算法和数据结构。

　　6、处理器调度

　　(1)处理器调度的类型;

　　(2)进程调度的各种算法及其特点;

　　(3)实时进程的特点;

　　(4)限期调度和速率单调调度方法。

　　7、设备管理和磁盘调度

　　(1)操作系统中输入/输出功能的组织;

　　(2)中断处理;

　　(3)设备驱动程序、设备无关的软件接口和spooling技术;

　　(4)缓冲策略;

　　(5)磁盘调度算法;

　　(6)磁盘阵列。

　　8、文件系统

　　(1)文件系统特点与文件组织方式;

　　(2)文件系统的数据结构;

　　(3)目录的基本性质及其实现方法;

　　(4)磁盘空间的管理。

　　二、考试要求

　　数据结构

　　1、 掌握有关数据结构的基本概念，包括数据的逻辑结构、存储结构。

　　2、 掌握算法的基本概念以及算法分析的基本方法。

　　3、 掌握线性表的基本概念， 在两种存储结构下的构造原理及相应的操作;

　　4、 掌握堆栈和队列的基本概念与特征以及在两种存储结构下如何对堆栈和队列进行插入和删除等操作，具备使用堆栈与队列解决实际问题的能力。

　　5、 掌握串的基本概念以及串的存储结构和相关的算法。

　　6、 掌握数组、广义表和稀疏矩阵的基本概念以及基本操作。

　　7、 掌握树型结构的逻辑特征以及各种存储结构的构造原理，能够熟练使用基于树的三种遍历方法。

　　8、 掌握二叉排序树的逻辑特征、建立过程， 具备使用其解决实际问题的能力。

　　9、 了解图的逻辑结构的特点以及常用的两种存储方法，了解最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的具体求解过程。

　　10、 掌握各种顺序文件的结构与相应的查找方法以及各种查找算法之间时空效率的差异;了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及基于散列的查找。

　　11、 掌握各种排序方法的排序特点和排序过程，并且能够对每一种排序方法排在时间、空间、排序的稳定性等性能进行简单分析。

　　操作系统

　　1、 掌握操作系统的基本概念，以及操作系统的特性与功能。

　　2、 掌握进程的本质特征、进程与程序之间的差别、进程的各种状态以及各种状态之间的转换。了解线程的基本概念以及引入线程作为运行实体的必要性;

　　3、 掌握如何利用信号量、管程等技术解决互斥和同步问题;了解死锁的概念和产生死锁的充分必要条件;了解死锁的预防、避免和检测算法;

　　4、 掌握存储管理的功能及存储管理对多道程序设计的支持;掌握段、页式存储管理方法及实现技术; 重点掌握虚拟内存的基本原理及页替换的各种算法;了解抖动现象的产生原因及相应的解决方法;

　　5、 掌握单处理器进程调度的各种算法及其适用环境;

　　6、 掌握输入输出设备及操作系统中输入/输出功能的组织、中断处理、设备驱动程序、设备无关的软件接口和spooling等技术，了解各种用于提高性能的缓冲策略和磁盘调度算法;

　　7、 掌握文件系统特点与文件组织形式、文件系统实现时的基本数据结构、文件目录以及文件的安全性保护。

　　三、主要参考书目

　　1、数据结构(C语言版). 严蔚敏，吴伟民 编著，北京：清华大学出版社，2007年

　　2、计算机操作系统(第三版). 汤小丹等编著，西安电子科技大学出版社，2007年

　　3、William Stallings. Operating Systems: Internals and Design Principles. Fifth Edition, Prentice Hall, 2004;英文影印版：操作系统——精髓与设计原理(第5版)，电子工业出版社，2006

　　编制单位：中国科学院研究生院