调度算法

（FCFS，短作业优先，时间片轮转，多级反馈队列）

原理+各自的优缺点+解决办法

FCFS(先来先服务)

从后备作业队列中选择最先进入该队列的一个或几个作业，将其调入内存，分配必要的资源，创建进程并放入就绪队列（非抢占式）

算法简单+效率低

优点：有利于长作业和CPU繁忙型作业
缺点：不利于短作业和I/O繁忙型作业
解决办法：结合其他调度策略中使用

短作业优先

从就绪队列中选择一个估计运行时间最短的作业，调入内存运行，将处理机分配给它，直到完成或者发生某事件而阻塞时，才释放。
优点：平均等待时间，平均周转时间最短
缺点：该算法对长作业不利，长作业可能长期不被调度，甚至“饿死”。未考虑作业的紧迫性，不能保证紧迫作业（进程）会被及时调度。

由于作业（进程）的长短只是根据用户所提供的估计时间而定的，致使该算法不一定能真正做到短作业优先调度。人机交互无法实现。

时间片轮转

系统把就绪队列中的所有进程，按先来先服务的原则，排成一个队列；每次调度时，把CPU分配给队首进程，并让它执行一个时间片；

每当执行的时间片用完，调度程序便停止该进程的执行，将其送入就绪队列尾部；然后进行下一次进程调度。
优点：适用于分时系统
缺点：时间片小，意味着会频繁切换执行进程调度和进程上下文，增加系统的开销；时间片选择太长，
会使每个进程都能在一个时间片内完成，退化为先进先出算法，无法满足短作业和交互式用户的需求。
解决办法：选择一个大小适当的时间片

多级反馈队列

动态调整进程优先级和时间片大小。在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。在优先级越高的队列中，其时间片就越小。不必事先知道各进程所需的执行时间，而且还可以满足各种类型进程的需要。
优点：终端型作业用户，短作业优先
短批处理作业用户，周转时间最短
长批处理作业用户，不会长期得不到处理

文件的常用操作（创建、删除、读、写、打开、关闭）

具体是什么，以及为何需要这些操作

创建文件

系统为新文件分配必要的外存空间；
在文件目录中为其建立目录项。目录项中应包含文件名及其在外存的地址等属性。

删除文件

找到要删除文件的目录项，使之成为空项；
回收文件所占的存储空间。

读文件

在相应的系统调用中给出文件名和应读入的内存目标地址。
为此，须先查找目录，找到指定的目录项，从中得到被读文件的外存地址和文件读指针

写文件

在相应的系统调用中给出文件名和该文件在内存的（源）地址。
查找目录，找到指定的目录项，再利用目录中的写指针进行写操作。

打开文件

是指系统将指明文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称索引号）返回给用户。
作用：当用户再要求对该文件进行相应操作时，便可利用该索引号向系统提出操作请求。系统可直接利
用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。节省了大量的检索时间，也显著提高了对文件的操作速度。

关闭文件

如果用户已不再需要对该文件操作时，可利用“关闭”(Close)系统调用来关闭此文件，OS将会从打开文件表中把该文件对应的表目删除。

利用PV操作解决生产者消费者问题（编程实现）

课后作业1

设有三组进程Pi、Qj、Rk，其中Pi、Qj构成一对生产者-消费者，共享一个由M1个缓冲区构成的循环缓冲buf1。Qj、Rk构成另一对生产者-消费者，共享一个由M2个缓冲区构成的循环缓冲buf2。如果Pi每次生产一个零件投入buf1，Qj每次从buf1中取两个零件组装成一个产品后投入buf2，Rk每次从buf2中取出三个产品包装出厂。试采用信号量和P、V操作编写他们同步工作的算法程序。

semaphore empty1,full1,mutex1,empty2,full2,mutex2
int in1,in2,out1,out2;
empty1=M1;empty2=M2;
mutex1=mutex2=1;
full1=full2=0;
in1=out1=in2=out2=0;
parbegin;
process Pi(i=1,2,3...){
   
	while(1){
   
		//生产一个产品x
		p(empty1);
		p(mutex1);
		buf1[in1]mod M1;
		v(mutex1);
		v(fuu1);
	}
}
process Qj(j=1,2,3...){
   
	while(1){
   
		for(m=0;m<2;m++){
   
			p(full1);
			p(mutex1);
			y[m]=buf1[out1];
			out1=[out1 + 1]mod M1;
			v(mutex1);
			v(empty1);
		}
		//把y0和y1组成一个产品
		p(empty2);
		p(mutex2);
		buf2[in2]=y;
		in2=(in2+1) mod M2;
		v(mutex2);
		v(full2);
	}
}
process Rk(k=1,2,3...){
   
	while(1){
   
		for(n=0;n<3;n++){
   
			p(full2);
			p(mutex2);
			z[n]=buf2[out2];
			out2=(out2+1) mod M2;
			v(mutex2);
			v(empty2);
		}
		//将z0,z1,z2打包成一个
	}
}
parend

课后作业2

有一个仓库存放两种零件A和B，最大库容量为可存放1000个零件A或B。有一车间不断地取A和B进行装配，每次各取一个。有两组供应商分别不断地供应A和B（每次一个）。为保证齐套和合理库存，当某种零件的数量比另一种数量超过100个时，暂停对数量大的零件的进货，集中补充数量少的零件。试用P、V操作正确地实现之。

semaphore mutex,empty,full1,full2,sa,sb
mutex.value = 1;empty.value = 1;fulla.value=fullb.value=0;
sa.value=100;sb.value=100;
cobegin
process p_a{
   
	while(true){
   
		p(empty);
		p(sa);
		p(mutex);
		store a;
		v(mutex);
		v(sb);
		v(fulla);
	}
}
process p_b{
   
	while(true){
   
		p(empty);
		p(sb);
		p(mutex);
		store b;
		v(mutex);
		v(sa);
		v(fullb);
	}
}

多道作业执行时的调度过程

计算各个作业进入主存时间，结束时间，周转时间以及平均周转时间
p54
周转时间=作业完成时间-作业提交时间
平均周转时间=各作业周转时间之和/作业数
带权周转时间=作业周转时间/作业实际运行的时间
平均带权周转时间=各作业带权周转时间之和

请求分页系统中页面存取的各种情况

计算在各种情况下内存的访问时间
p183
页面置换算法

文件的组织形式（连续、链接、索引）

p240
各种组织形式的结构，以及对应的FCB中应设置哪些描述字段
了解三种文件组织形式包括各自优缺点以及分别适用于哪些情况

连续分配方式

为每一个文件分配一组相邻的盘块。把逻辑文件中的记录顺序地存储到相邻的物理盘块中。顺序式文件结构，又称顺序文件
结构:第一块的磁盘地址+连续块的数量
优点:实现简单、存取速度快
缺点:文件长度不宜动态增加，可能会产生外部碎片
适用:长度固定的文件

链接分配方式

隐式链接分配

结构:每个文件对应一个磁盘块的链表，每个盘块都有指向下一个盘块的指针，目录包括文件第一块指针 和最后一块指针
优点:消除了外部碎片、提高了磁盘空间利用率，无需事先知道文件大小，且增、删、改方便
缺点:无法直接访问盘块，稳定性差（会导致文件数据丢失）

显式链接分配

结构:提取指针，显示放在内存的链接表中（FAT），每个表项存放下一个磁盘号，第一个盘块号记录在目录中，后续盘块通过查 FAT找到
优点:提升了检索速度、减少访问磁盘次数 ，支持直接访问
缺点:FAT需要占用较大的内存空间，不能支持高效的直接存取

索引分配方式

结构:每个文件都有索引块（磁盘块地址的数组），目录包括索引块的地址
优点:支持直接访问，且没有外部碎片
缺点:索引块的分配，增加了系统存储空间的开销
适用:需要较高检索速度的文件

I/O系统中各层软件（中断处理程序、设备

驱动程序、设备独立性软件）存在的目的
p273

中断处理程序

中断在操作系统中有着特殊重要的地位，它是多道程序得以实现的基础，没有中断，就不可能实现多道程序，因为进程之间的切换是通过中断来完成的。另一方面，中断也是设备管理的基础，为了提高处理机的利用率和实现CPU与I/O设备并行执行，也必需有中断的支持。中断处理程序是I/O系统中最低的一层，它是整个I/O系统的基础。

设备驱动程序

是I/O系统的高层与设备控制器之间的通信程序。接收上层软件发来的抽象I/O要求，如read或write命令，再把它转换为具体要求后，发送给设备控制器，启动设备去执行；它也将由设备控制器发来的信号传送给上层软件。

设备独立性软件

为了方便用户和提高OS的可适应性与可扩展性，在现代OS的I/O系统中，都无一例外地增加了与设备无关的I/O软件，以实现设备独立性，也称为设备无关性。应用程序中所用的设备，不局限于使用某个具体的物理设备。

OS中各个资源管理模块中那些设计理念能够体现虚拟性

时分复用技术：虚拟处理器、虚拟设备

虚拟存储器

多次性

虚拟内存技术

请求段页式存储管理
空分复用技术：虚拟磁盘、虚拟内存