《操作系统复习2016》由会员分享，可在线阅读，更多相关《操作系统复习2016（68页珍藏版）》请在金锄头文库上搜索。
1、操作系统原理复习,南京工业大学信息学院计算机系,注意要点,考核形式 试卷，闭卷考试，120分钟 可以带计算器，但不得使用手机中的计算器功能 试卷占总评成绩的80% 考察范围 第一章第九章 部分章节除外,2018/9/5,操作系统复习,2,题型分布,单选题15题，共30分 填空题10题，共10分 综合应用题6题，共60分,2018/9/5,操作系统复习,3,主要知识点,第一章 操作系统的目标 操作系统的作用 三种经典的操作系统类型 分时系统的特征 实时系统的特征 操作系统的基本特征 用户接口的种类,2018/9/5,操作系统复习,4,主要知识点,第二章 顺序执行程序的主要特征 并发执行程序的主要
2、特征 进程的特征 进程的各个状态，及各状态之间的转换条件 导致进程创建、终止、阻塞的条件 同步机制的4条设计原则 进程同步：只需要掌握用信号量解决P-C问题 进程通信的方法,2018/9/5,操作系统复习,5,主要知识点,第三章 处理机的调度层次 调度算法：FIFO，SJF，高相应比优先，时间片轮转 产生死锁的4个必要条件 银行家算法 资源分配图的简化,2018/9/5,操作系统复习,6,主要知识点,第四章 动态分区分配中分配和回收内存的方法 动态分区分配算法：FF，NF，BF，WF 逻辑地址到物理地址的转换及访问时间的计算 多级页表 段页式存储管理的地址转换 （虚地址到实地址的转换）,201
3、8/9/5,操作系统复习,7,主要知识点,第五章 虚拟存储器的特征 页面置换算法及缺页率的计算 最佳， FIFO， LRU， 时钟置换 抖动的概念,2018/9/5,操作系统复习,8,主要知识点,第六章 I/O系统的基本功能 I/O系统的层次结构 I/O设备的类型 设备控制器的基本功能 单缓冲和双缓冲传输时间的计算 磁盘访问时间的计算 磁盘调度算法：FCFS，SSTF，SCAN，CSCAN,2018/9/5,操作系统复习,9,主要知识点,第七章 文件的组织分类及其特征 目录管理的要求 目录结构的组织形式 目录检索的方法 文件共享的方法 （文件）,2018/9/5,操作系统复习,10,主要知识点
4、,第八章 连续组织方式的优缺点 隐式连接、显示链接组织方式的优缺点 索引组织方式的优缺点 混合索引文件最大容量的计算方法 位示图法存储空间管理（位图计算）,2018/9/5,操作系统复习,11,主要知识点,第九章 用户接口的类型 主要联机命令 Shell命令语言的主要简单命令 系统调用的实现方法,2018/9/5,操作系统复习,12,1. 假设有一磁盘含有64000块，块号记为164000，现用2000个32位(Bit)的字作该盘的位示图，试问第59999块对应于位示图中第几字的第几位(字、位均从0开始)；而第1599字的第17位对应于磁盘的第几块? 解：由块号b，求字号i和位号j的公式为：
5、i=(b-1) div 32 (div表示整数除法，32是字长) j=(b-1) mod 32 (mod表示整数相除取余数) (59999-1) div 32=1874 (59999-1) mod 32=30 故59999块对应于位示图中第1874字的第30位。 由位示图的字号i和位号j，求对应的磁盘块号b的公式为： b=i32+j+1=159932+17+1=51186 即第1599字的第17位对应于磁盘的第51186块。,2018/9/5,操作系统复习,13,2. 页式存储管理中，主存空间按页分配，可用一张“位示图”构成主存分配表。假设主存容量为2M字节，页面长度为512字节，若用字长为3
6、2位的字作主存分配的“位示图”需要多少个字？如页号从1开始，字号和字内位号（从高位到低位）均从1开始，试问：第2999页对应于何字何位；99字19位又对应于第几页？ 解：(1) 内存总块数=2MB/512B=4096 位示图需要字数=4096/32=128 (2) 字号=(2999-1)/32+1=94 位号=(2999-1)%32+1=23 即第2999内存页对应于位示图中94字的23位。 (3) 99*（32-1）+19=3088 即位示图99字19位对应于内存的3088页,2018/9/5,操作系统复习,14,2018/9/5,操作系统复习,15,3某多道程序设计系统供用户使用的主存为1
7、00KB，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业的I/O时间。现有如下作业序列：,作业调度采用FCFS策略，优先分配主存低地址区域且不准移动已在主存中的作业，进程调度采用时间片轮转算法(即在主存中的作业均分CPU时间)。现求：,2018/9/5,操作系统复习,16,(1) 作业被调度的先后次序； (2) 全部作业运行结束的时间； (3) 作业的平均周转时间； (4) 最大作业周转时间。,作业达到及结束顺序分析： 8:00 J1到达，分配它所需资源(15KB内存、 1台磁带机、1台打印机后，调入内存运行。余内存85KB、磁带机1台。 8:20 J2到
8、达，因无打印机，不调入。同时J3到达，分配它内存60KB，磁带机1台，调入内存，与J1均分CPU时间运行。余内存25KB、磁带机和打印机都已分完(余0台)。 8:30 J1结束，释放内存15KB、磁带机1台、打印机1台。虽有打印机但内存不够，J2仍不能调入；J4到达，因低端内存15KB不够，分配高端内存20KB和磁带机1台，调入内存与J3一起运行。剩下内存空闲块是15KB、5KB，打印机1台 8:35 J5到达，因无磁带机，不能调入。,2018/9/5,操作系统复习,17,9:00 J3结束。释放资源后，系统有内存75KB，5KB、打印机和磁带机个1台。J2调入，内存余45KB，5KB、磁带机
9、剩1台、打印机0台。J5仍不能进入(无打印机)。将J2、J4运行。J4还需运行5分钟。 9:10 J4结束，释放资源后，内存空余70KB、磁带机空2台、打印机0台。J5仍不能进入。J2单独运行(还需5分钟)。 9:15 J2结束，释放资源后，内存有100KB、磁带机有2台、打印机有1台。J5调入运行。 9:30 J5结束。,解：(1) 作业被调度的先后次序为J1, J3, J4, J2, J5 (2) 全部作业运行结束的时间为9:30 (3) 作业的平均周转时间为(30+55+40+40+55)5=44 (分钟) (4) 最大作业周转时间为55分钟。,2018/9/5,操作系统复习,18,CP
10、U,磁带1,磁带2,打印机,8:00,8:20,J1,J1,J1,J1, J3,J3,8:30,J1,J1,J1结束,J4,J3,J2,J3到 J2不入 J3进入,J3, J4,8:35,J3, J4,J5到达J5不入,9:00,J4,J3,J3结束,9:10,J4结束,内存余,85K,25K,15, 5,15, 5,J2, J4,45, 5,J4,J2,9:15,J2,J2,70K,J2结束,9:30,90K,J5,J5,J5,J5结束,J1到达 J1进入,J4到达 J2不入 J4进入,J2进入,J5仍不能进入,J5进入,以下是画图分析法：,2018/9/5,操作系统复习,19,4多道批处理
11、系统中配有一个处理器和2台外设(D1和D2)，用户存储空间为100MB。已知系统采用可抢占式的高优先数调度算法和不允许移动的可变分区分配策略，设备分配按照动态分配原则。今有4个作业同时提交给系统，如下表所示。,作业运行时间和I/O时间按下述顺序进行： A. CPU (1分钟)，D1(2分钟)，D2(2分钟) B. CPU (3分钟)，D1(1分钟) C. CPU (2分钟)，D1(3分钟)，CPU(2分钟) D. CPU (4分钟)，D1(2分钟) 忽略其他辅助操作，求4个作业的平均周转时间是多少分钟。,11分钟,分析见后页,2018/9/5,操作系统复习,20,CPU,D1,D2,时间,A的
12、周转时间为12分钟 B的周转时间为13分钟 C的周转时间为7分钟 D的周转时间为12分钟 所以平均周转时间为(12+13+7+12)/4=11(分钟),5. 有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高： (1) 列出所有作业进入内存时间及结束时间。 (2) 计算平均周转时间。,2018/9/5,操作系统复习,21,分析： 10：10 J1到达，进入系统，运行10分钟 10：20 J2到达，进入系统，因优先级高于J1抢夺C
13、PU开始运行 10：30 J3到达后备队列，因为系统已经载入2个作业，无法进入系统 10：50 J2运行结束退出，J4到达，根据短作业优先，调入J4，由于 J1 的优先级高于J4，J1开始运行 11：00 J1运行结束退出，J3进入系统，由于J3优先级较高，开始运行 11：25 J3运行结束退出，J4开始运行 11：45 J4运行结束,2018/9/5,操作系统复习,22,答：（1）各个作业进入主存时间、结束时间和周转时间如下表所示： （2）平均周转时间：（50+30+55+55）/4=47.5（min）,2018/9/5,操作系统复习,23,6有一个多道程序设计系统，采用不可移动的可变分区方
14、式管理主存空间，设主存空间为100K，采用最先适应分配算法分配主存，作业调度采用响应比高者优先算法，进程调度采用时间片轮转算法（即内存中的作业均分CPU时间），今有如下作业序列： 假定所有作业都是计算型作业且忽略系统调度时间。回答下列问题： (1)列表说明各个作业被装入主存的时间、完成时间和周转时间； (2)写出各作业被调入主存的顺序； (3)计算5个作业的平均周转时间。,2018/9/5,操作系统复习,24,答：（1）各个作业被装入主存的时间、完成时间和周转时间如下表所示： （2）作业被调入主存的顺序为J1，J2，J5，J3，J4。 （3）平均周转时间=（65+60+85+95+55）/5=
15、72（分钟）。,2018/9/5,操作系统复习,25,26,信号量机制解决进程同步问题的一般方法：,为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)； 同步双方任一进程在进入临界区之前，应先对自己的信号量执行wait()操作，以测试是否有自己可用的资源。若有资源可用，则进入临界区，否则阻塞； 同步双方任一进程离开临界区后，应对合作方 (对方)的信号量执行signal()操作，以通知(若对方处于阻塞状态，则唤醒它)对方已有资源可用(对方已可进入临界区)。,27,用信号量机制解决P-C问题的基本方法：,为生产者设置1个私有信号量empty，其初值为1
16、，表示有1个空缓冲区；为消费者设置1个私有信号量full，其初值为0，表示开始时没有满缓冲区；（信号量初值由物理意义确定） 生产者将产品存入缓冲区之前，应先测试缓冲区是否空：执行wait(empty)操作；离开临界区(存入产品)后，应通知(可能会唤醒)消费者：执行signal(full)操作； 消费者从缓冲区取产品之前，应先测试缓冲区是否满：执行wait(full)操作；离开临界区(取走产品)后，应通知(可能会唤醒)生产者：执行signal(empty)操作,2018/9/5,操作系统复习,28,7. 进程P1使用缓冲区buffer向进程P2，P3，P4发送消息，要求每当P1向buffer中发消息时，只有当P2，P3，P4进程都读取这条消息后才可向buffer中发送新的消息。利用P、V原语描述如下图所示进程的动作序列。,2018/9/5,操作系统复习,29,设P1、P2、P3、P4的资源信号量分别为S1、S2、S3、S4 semaphore S1,S2,S3,S4; S1.value=3;S2.vale=S3.vale=S4.value=0; parbegin process P1 while (condition) P1生成一个消息； P（S1）；P（S1）；P（S1）； P1将消息存入缓冲区buffer； V（S2）；V（S3）；V（S4）； ,
