-
磁道请求
-
先来先服务(FCFS)：最简单。根据进程请求访问磁盘的先后次序进行调度。
优点：公平、简单。
-
每个进程的请求都依次得到处理，不会出现某一请求长期不满足。
-
等待时间越长，优先级越高
-
-
扫描算法(SCAN)：基于优先级的调度算法，可能导致优先级的进程发生“饥饿”现象。（电梯调度算法）
-
-
强占式优先级
- 只要系统中出现一个新的就绪进程，就进行优先权比较。若出现更高的优先权的进程，立即停止当前执行。并将处理机分配到新到优先权高的进程。
-
平均周转时间计算方法=周转总时间/作业个数
例：有五个批处理的作业（A，B，C，D，E）几乎同时到达一个计算中心，估计运行时间分别为2、4、6、8、10分钟，他们的优先级分别为1,2,3,4,5，对下面每种算法，求平均周转时间
最高级优先
E D C B A 结束 10 18 24 28 30
时间片轮转（时间片为2分钟）
A B C D E B C D E 0 2 4 6 8 10 12 14 16 结束 A B …… C D E D E E …… 18 20 22 24 26 28 30 …… C D E 时间片轮转算法主要把握好抢占，对于上述问题的解析：A使用第一个时间片两分钟后被B抢占，依次类推，一个循环之后，由于A已经进行完了，因此在E进行第一次使用完一个时间片之后会被B抢占，以此类推，只至所有的进程完成为止。
注意：若在时间片范围内未进行完则马上进行下一个进程，即若A运行时间为1分钟，则A在1分钟后结束，B从1分钟开始。即：
A B …… 0 1 3 结束 A
FCFS（先来先服务）
附加前提：作业到达顺序为CDBEA
C D B E A 结束 6 14 18 28 30
短作业优先
按时间,即ABCDE
-
死锁
-
死锁与安全状态的关系：死锁状态一定不是安全状态
（并非所有不安全状态都是死锁状态，当进入不安全状态，便可能死锁）
（只要处于安全状态，系统便可以避免死锁状态）
-
银行家算法
-
安全性算法判断：
图示
-
-
-
进程：
进程
需求资源数量（MAX）
已分配给该进程的资源A
还需要资源数量Need
Need=MAX-A
-
安全序列的判断：
Aollocation+Available满足谁
例：
Process Aollocation Need Available 0,0,3,2 0,0,1,2 1,6,2,2 1,0,0,0 1,7,5,0 1,3,5,4 2,3,5,6 0,3,3,2 0,6,5,2 0,0,1,4 0,6,5,6 -
该状态是否安全
-
若
提出Request(1,2,2,2)后，系统能否将资源给它？
-
安全序列（不要看作四位数）：
第一轮循环
-
-
->
-
->跳过
-
->跳过
-
->
-
->
第二轮循环 -
->
-
->
因此找到了一个安全序列{}，故系统是安全的。
-
-
①
②
③系统先假定可为P_2分配资源并修改Available，
和
向量；
而Available（0,4,0,0）满足不了任意一进程，因此进入不安全状态，即不能分配给
信号量机制（PV进程） -
-
实现同步|互斥
互斥：mutex=1∈（-1，0，1） /*当mutex=1时，两进程皆为进入需要互斥的临界区；mutex=0时，有一个进程进入临界区运行，另一个等待，挂入阻塞队列；mutex=-1时，有一个进程正在临界区进行，另一进程因等待而阻塞在信号队列中。*/ semaphore mutex=1: PA(){ while(1){ wait(mutex)//mutex=0进不了临界区 临界区； signal(mutex)//mutex多为1 剩余区； } } PB(){ while(1){ wait(mutex) 临界区; signal(mutex) 剩余区; } } /*访问临界资源一定要枷锁（mutex）*/ /*wait(mutex)和signal(mutex)必须成对出现。缺wait()系统会混乱，缺signal()临界资源不能释放*/ -
信号量
-
由一个整型（sem）变量和两个原子操作组成。
-
P（）：sem-1，若sem<0，进入等待，否则继续。P->Wait
-
V（）：sem+1，若sem
0，则唤醒另一个等待线程。V->Signal
semaphore::P(){ sem--; if(sem<0){ Add this thread to q; block(P); } } semphore::V(){ sem++; if(sem≤0){ Remove a thread t from q; wakeup(t); } } -
记录型信号量：（信号量是一个结构体而非普通变量）
Typedef struct{ int value; struct process-control-block *list; }semaphore wait(semaphore *s){//往停车场停车 s->value--;//来一辆车value-1 if(s->value<0)block(s->list); } signal(semaphore *s){ s->value++;//来一辆车value-1 if(s->value≤0)wakeup(s->list); }
-
-
管程：用于多线程互斥访问共享资源的程序结构
-
局部数据变量只能被管程过程访问，任何外部过程都不行。
一个进程通过调用管程的一个过程进入管程，
任何时候，只能有1个进程在管程中执行。
-
条件变量：
是管程内的等待机制
进入管理的线程因资源被占用而进入等待状态
每个条件变量表示一种等待原因，对应一个等待队列
P（Wait()）操作：
将自己阻塞在等待队列中
放弃对管程的互斥访问权限(同一时刻管程中能有1个进程访问)
V（Signal()）操作：
将等待队列中的一个线程唤醒（信号量机制中signal释放的一个信号量，如果信号量≤0则唤醒一个线程）
-
生产-消费者问题：（生产者->缓冲区->消费者）
（缓冲区满时，生产者等消费者；缓冲区空时，消费者等生产者）
生产者在生成数据后放入一个缓冲区里，消费者从缓冲区中读取数据，任何一个时刻只能有一个生产者或消费者可以访问缓冲区。
利用信号机制： -
int in=0,out=0;
item buffer[in];
semaphore mutex=1,empty=n,full=0;
void producer(){
do{
producer an item nextp;//生产一双鞋
...
Swait(empty,mutex);//记一个空位，empty-1
buffer[in]=nextp;//放进鞋
in=(in+1)%n;
Singal(mutex,full);//full 0->1;仓库有鞋了
}while(true)
}
void consumer(){
do{
Swait(full,mutex);//full=0时阻塞访问临界资源
nextc=buffer[out];
out=(out+1)%n;
Signal(mutex,empty);
consumer the item in nextc;
...
}while(true)
}
利用管程：（不加mutex管程就是为了解决互斥）
/*PC管程*/
Monitor producerconsumer{
item buffer[N];
int in,out;
condition notfull,notempty;
int count;
public:
void put(item x){
if(count≥N)
cwait(notfull);
buffer[in]=x;
in=(in+1)%N;
count++;//当count>N时，缓冲池满
csignal(notempty);
}
void get(item x){
if(count≥N)
cwait(notfull);
buffer[in]=x;
in=(in+1)%N;
count--;//当count<0时，缓冲池空，消费者应等待
csignal(notempty);
}
{in=0;out=0;count=0;}
}PC;
/*解决生产者-消费者问题*/
void producer(){
item x;
while(true){
...
produce an item in nextp;
pc.put(x);
}
}
void consumer(){
item x;
while(true){
pc.get(x);
consumer the item in nextc;
...
}
}
void main(){
cobegin
producer();
consunmer();
coend;
}
PS:使用记录型信号量时
void producer(){
do{
producer an...;
wait(empty)/wait(mutex);
//与用AND信号量不同的地方，consumer（）一样
}while(true)
}
-
哲学家进餐问题
用记录信号量解决时会产生死锁，解决方案：
至多允许四个拿左
仅左右筷子可用时拿筷子
奇数先拿右，偶数相反
用AND信号量
semaphore chopstrick[5]={1,1,1,1,1}; do{ ... //think; ... swait(chopstrick[(i+1)%5],chopstrick[i]); ... //eat ... signal(chopstrick[(i+1)%5],chopstrick[i]); }while(true); -
读者写者问题
reader+reader√
reader+writer×
writer+writer×
int RN; semaphore L=RN,mx=1; void Reader(){ do{ swait(L,1,1); swait(mx,1,0);//只要无write（）进入写 ... perform read operation; ... ssignal(L,1); }while(true); } void Writer(){ do{ swait(mx,1,1,L,RN,0); ... perform write operation; ... ssignal(mx,1); }while(true); } void main(){ cobegin Reader(); Writer(); coend }只要一旦有Writer进程进入写，其mx=0
swait(mx,1,1,L,RN,0)语句表示：
仅当既无Writer进程在写操作（mx=1），又无reader进程在该操作（L=RN）时，Writer才能进入临界区写操作。
-
前驱图与PV操作
前驱图
-
中间缓冲区：
缓冲区是计算机存储器中的一块存储空间，如我们编程时自己定义一块缓冲区一样。在速度之间有差异的地方都可以用缓冲区。
提高并行性，减少对CPU中断次数，放宽CPU对中断响应时间要求。
-
操作系统
-
批处理
单道批处理（CPU）
不交互，只提高CPU利用率
多道批处理（程序）
将一批作业提交给操作系统就不再干预
-
分时操作系统
联机多用户交互式操作系统（按时间片轮流把处理机分配给各联机作业）
多路、独立、及时、交互
-
实时操作系统
在指定时间内完成系统功能以及对外部或内部事件在同步或异步时间内做出响应的系统
对响应时间有严格要求
-
-
进程状态：组成（程序、数据、PCB（程序控制块））
-
执行态
正在执行
-
阻塞态
进程只在某些事情发生前不能执行，等待阻塞进程时间完成
引起原因：时间片切换、等待I/O、进程Sleep等、输入或输出事件发生
-
就绪态
进程已做好准备，只要有机会就会执行
-
-
原语
-
系统态下执行某些具有特定功能的程序段称为原语
-
分类
-
机器指令级
执行期间不允许中断（不可分割）
-
功能性
作为原语的程序段不允许并发执行
-
-
-
X信号量的物理意义：
当信号量大于0时表示资源的数目，当信号量小于0时表示等待资源的进程数
-
通信共享缓存区（了解）
共享缓存区为空时才可写入
-
联想寄存器（特点：绝对路径名）
联想存储器中每个存储单元都含有存储、比较、读写、控制等电路
-
存储器管理中的碎片是指
-
内部碎片
系统已经分配给用户使用，用户自己没有使用那部分的存储空间
-
外部碎片
系统无法分配出去供用户使用的那部分存储空间
-
-
虚拟存储器（基于层次）
-
一次性
作业内容必须全部装入内存后程序才可开始执行
-
驻留性
作业一旦进入内存，直到作业结束运行都不会调出，即使发生了IO阻塞
-
Belady现象
内存中的每个进程分配了3块进程执行时使用的页号为432143543215
-
该进程运行时共缺页9次
-
若每个进程存4块，产生10次缺页
解释：
页面淘汰算法产生异常现象，即当分配给进程的物理页面数增加时，缺页页数反而增加。
-
-
-
中断DMA方式
-
程序I/O
-
I/O通道
控制干预最少的是I/O通道
-
-
设备管理的方法：（什么程序完成的）
-
程序驻留在BIOS中 -
设备管理程序负责
-
对系统中的各种输入输出设备进行管理
-
处理用户和应用程序的输入输出请求
-
-
每个设备都有自己的驱动程序
-
-
假脱机操作（替代打印机）
借助磁盘存储实现的，实现的打印机的结构是：共享设备
-
字符设备、块设备的根本区别：
字符设备只能顺序读取，块设备可以随机读取。
-
解决文件重名：建立树形目录结构
-
计算机网络共享任一文件用到数据移动方式
-
文件逻辑结构分类
-
无结构的流式文件
-
有结构的记录式文件
索引顺序文件既适合于交互方式应用也适合批处理方式
-
-
文件关闭时干了什么：
系统将其主存中的文件控制块的内容复制到磁盘上的文件目录项中并释放文件的控制块
-
文件打开时干了什么：
把该文件的有关目录表复制到主存的约定目录建立文件控制块（建立用户和文件的联系）
目的：节省内存、减少访问时间、加快访问速度
-
操作系统的管理
作业管理、文件管理、存储管理、设备管理、进程管理
-
程序的组成：程序、数据、PCB
-
进程实现了同步、互斥相互等待（抢占非强占）
-
找地址（段表、段号）
-
例：某段表如下
段号 段首地址 段长度 1 320k 30k 2 760k 40k 3 570k 20k 4 450k 30k 则逻辑地址为（3,1024）的实际物理地址为：(571k)
-
-
碎片出现的位置
-
分页（对内存）—内部碎片
内存往往装不满
-
分段（换入换出）—外部碎片
eg:5k出4k入则有1k外部碎片
单道连续分配只有内部碎片，多道固定连续分配既有内部碎片，又有外部碎片
-
-
设备分配相关的数据结构
- 设备控制表、控制器控制表、系统设备表、通道控制表
-
文件存储空间（以块为单位）
-
顺序访问——链接分配
-
（小文件）直接访问——连续分配
-
大文件——索引分配
-
-
设备独立性：用户在编制程序时所使用的设备与实际使用的设备无关
-
最佳适应法中空闲块按块的大小从小到大排序
-
产生死锁的必要条件：
-
互斥条件：一个资源每次只能被一个进程使用
-
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源不救
-
不剥夺条件：进程已获得的资源，在未使用完之前，不能被强行剥夺
-
循环与等待条件：若干进程之间形成一种头尾相连的循环等待关系
-
-
程序顺序执行时的特征：顺序性、封闭性、可再现性
-
动态定位：程序运行过程中要访问数据时再进行逻辑地址与物理地址的交换
在逐条指令执行时完成地址映射
原作者：傅
电子版：小哲
未经许可禁止转载
网友评论