“操作系统”复习提纲2010-6-261.什么是操作系统？如何理解它的“机器扩展（extended machine）”和“资源管理(resource management)”两个基本能力？答：操作系统是计算机系统中的一个系统软件，是一些程序模块的集合1、它们能以尽量有效、合理的方式组织和管理计算机的软硬件资源2、合理的组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能3、使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效地运行作为扩展机器的操作系统，为程序员隐藏硬件的实际细节，并提供一个可以读写的、简洁的命名文件视图的程序。
它还隐藏了大量与中断、定时器、存储管理以及其他与底层特征有关的令人烦恼的细节。
作为资源管理者的操作系统，主要任务是记录使用资源的情况、对资源的请求进行授权、计算使用费用，并且为不同的程序和用户协调互相冲突的资源请求。
在时间和空间上实现共享资源的复用。
2.中断发生时，操作系统底层的运行框架（Skeleton）？答：1）硬件压入堆栈技术器等2）硬件从中断向量装入新的程序计数器3）汇编语言过程保存寄存器值4）汇编语言过程设置新的堆栈5）C中断服务例程运行（典型的读和缓冲输入）6）调度程序决定下一个将运行的进程7）C过程返回至汇编代码8）汇编语言过程开始运行新的当前进程。
3.什么是进程和线程，区别是什么？答：线程是在进程内用于调度和占有处理机的基本单位，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。
进程是程序的一次动态执行过程，它也是系统资源分配的基本单位，它能和其他进程并发执行。
线程与进程的主要区别：进程是资源管理的基本单位，线程只是处理机调度的基本单位。
进程进行处理机切换和调度时间较长，而线程进行处理机切换和调度时间较短，不发生资源的变化。
线程和进程一样，都有自己的状态，也有相应的同步机制，不过由于线程没有单独的数据和程序空间，因此线程没有挂起状态。
进程的调度、同步机制大多数由操作系统内核完成，而线程的控制既可以由操作系统内核进行，也可以由用户控制进行。
4.针对如下的多线程Web Server代码，图式说明进程和线程的结构关系。
5.两种主要的线程实现技术比较：1）在用户空间；2）在内核中。
解：在用户空间：（1）由应用程序完成所有线程的管理（2）核心不知道线程的存在，当线程调用系统调用时，整个进程阻塞（3）线程切换不需要核心态特权（4）调度是针对应用的，是特定的（5）核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上在内核中：（1）所有线程管理由核心完成（2）没有线程库，但对核心线程工具提供API（3）核心维护进程和线程的上下文（4）线程之间的切换需要核心支持（5）以线程为基础进行调度（6）阻塞是在线程一级完成（7）对多处理器，核心可以同时调度同一进程的多个线程（8）在同一进程内的线程切换调用内核，导致速度下降6.概念理解：竞争条件（Race conditions）、互斥（Mutual exclusion）、临界区（critical regions）答：1）竞争条件（Race conditions）：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件2）互斥（Mutual exclusion）：以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。
3）临界区（critical regions）：对共享内存进行访问的程序片段7.基于信号量（semaphore）的生产者-消费者问题解决算法。
解：#define N 100 /*缓冲区中的槽数*/Typedef int semaphore; /*信号量是一种特殊的整型数据*/Semaphore mutex = 1; /*控制对临界区的访问*/Semaphore empty = N; /*计数缓冲区的空槽数*/Semaphore full = 0; /*计数缓冲区的满槽数*/V oid producer(void){Int item;While(true){ /*true是常量1*/Item = produce_item(); /*产生放在缓冲区的数据*/Down(&empty); /*将空槽数目减1*/Down(&mutex); /*进入临界区*/Insert_item(item); /*将新的数据项放到缓冲区中*/Up(mutex); /*离开临界区*/Up(&full); /*将满槽的数目加1*/}V oid consumer(void){Int item;While(ture){Down(&full)Down(&mutex);Item = remove_item();Up(&mutex);Up(&empty);Consume_item(item);}}8.基于线程、互斥锁（mutex）和条件变量（condition variables）的生产者-消费者问题解决算法。
9.基于管程（Monitor）的生产者-消费者问题解决算法。
解：monitor ProducerConsumercondition full,empty;integer count;Procedure insert(item:integer)BeginIf count = N then wait(full);Insert_item(item);Count :=count +1;If count =1 then signal(empty);EndFunction remove:integer;BeginIf count = 0 then wait(empty);Remove = remove_item;Count :=count+1;If count = N-1 then signal(full);EndCount :=0;End monitor;Procedure producerBeginWhile ture doBeginItem = produce_item;producerConsumer.insert(item);endendprocedure consumerbeginwhile true dobeginitem= producerConsumer.remove;consume_item(item)endend;10.基于消息传递的生产者-消费者问题解决算法。
#define N 100V oid producer(void){Int item;Message m;While(TURE){Item = produce_item();Receive(consumer,&m);Build_message(&m,item);Send(consumer,&m);}}V oid consumer(void){Int item,I;Message m;For(i=0;i<N;i++)Send(producer,&m)While(true){Receive(producer,&m);Item = extract_item(&m);Send(producer,&m);Consume_item(item);}}11.五个批处理作业A到E几乎同时到达计算中心，其预计运行时间分别为10, 6,2, 4和8分钟。
他们的优先级为3, 5, 2, 1和4, 其中5是最高优先级。
针对以下调度算法，请计算平均周转时间。
（进程切换开销忽略不计）a)Round robin.(轮转调度)在头10分钟里，每个作业获得1/5的cpu时间，在第10分钟时C结束，在接下来的8分钟里每个作业获得1/4的cpu时间，然后D完成，以此类推，因此，5个作业完成的时间分别为10,18,24,28,30分钟平均周转时间(10+18+24+28+30)/5=22分钟b)Priority scheduling（优先级调度）执行顺序是BEACD,各周转时间为6,14,24,26,30分钟平均周转时间：（6+14+24+26+30）/ 5 =20分钟c)First-come, first-served (run in order 10, 6, 2, 4, 8)（先来先服务）A的周转时间是10分钟，B是16分钟，C是18分钟，D是22分钟，E是30分钟。
平均周转时间：（10+16+18+22+30）/5=19.2分d)Shortest job first（最短作业优先）顺序是CDBEA，周转时间分别为2,6,12,20,30分钟平均周转时间：（2+6+12+20+30）/5=14分钟对于(a), 假设系统支持多道程序，每个作业获得等额CPU。
对于(b)到(d)，假设每次只运行一个作业，并绑定CPU，直到完成。
12.哲学家就餐问题解决算法。
#define N 5#define LEFT (i+N-1)%N#define RIGHT (i+1)%N#define THINKING 0#define HUNGRY 1#define EA TING 2typedef int semaphore;int state[N];semaphore mutex = 1;semaphore s[N];void philosopher(int i){while(true){think();take_forks(i);eat();put_forks(i);}}void take_forks(int i){down(&mutex)state[i]=HUNGRY;test(i);up(&mutex);down(&s[i]);}void put_forks(i){down(&mutex);state[i]=THINKING;test(LEFT);test(RIGHT);up(&mutex);}void test(i){if(state[i]=HUNGRY && state[LEFT]=EATING && state[RIGHT]=EATING){ state[i] = ETING;up(&s[i]);}13.reader-writer问题解决算法。
typedef int semaphore;semaphore mutex = 1;semaphore db = 1;int rc=0;void reader(void){while(TRUE){down(&mutex);rc =rc + 1;if(rc == 1)down(&db)up(&mutex);read_data_base();down(&mutex);rc = rc - 1;if(rc = 0)up(&db);up(&mutex);use_data_base();}}void writer(void){while(TRUE){think_up_data();down(&db);write_data_base();up(&db);}}14.基本内存分配算法：First fit/Next fit/ Best fit/ Worst fit15.假设虚拟页面的访问次序由一个较长的固定页面访问次序加一个随机页访问请求构成。