操作系统定义:OS是配置在计算机硬件上的第一层软件,是对硬件系统的首次扩充

单道批处理系统:保证作业批量连续进入内存,在同一时刻内存中只有一个作业(IO和Cpu串行):可以连续处理作业
多道批处理系统:作业在外存中排成一个后备队列,由作业调度算法从队列中选取若干个作业进内存(IO和Cpu并行):提高资源利用和系统吞吐
分式系统:作业直接进入内存,采用轮转运行方式(时间片),使用多路卡扫面各个终端收集指令:人机交互(多路,独立,及时,交互)
实时系统:相对于分时系统,系统可靠度要求更高:实时计算(不仅逻辑结果正确,还限制计算时间)


操作系统基本特征:
并发性:
并行:多个事件在同一刻发生
并发:多个事件在同一时段发生(串行)
共享性:进程时间(内存独享)和空间(占用内存)互斥共享;
虚拟性:资源利用率低于1/N
空分复用:利用存储器空闲空间分区域存放其他任务数据
时分复用:利用cpu空闲时间处理其他任务
异步性:多个程序并发执行;


进程的基本状态:
新建:为进程分配资源
就绪:进程进入就绪队列(内存):从新建转换,在运行时被抢占
执行:独占cpu
阻塞:请求IO:进入等待队列,IO完毕进入就绪状态
终止:退出内存 转换图:   新建 -> 就绪 -> 运行 -> 终止 |----<-----| -<--阻塞 <--             CPU三级调度:
高级调度(作业):外存->内存
中级调度:等待->就绪,内存->内存
低级调度(进程):内存->Cpu


计算公式:
作业响应时间 = 已经等待时间+要求服务时间;R = w+s --理论上
作业响应比H = 作业响应时间/要求服务时间  H = (w+s)/s


作业周转时间Ti = 作业执行时间+作业等待时间(从提交到完成的时间); --实际中
平均周转时间:sum(Ti)/n 衡量不同调度算法的性能


作业带权周转时间:Ti/Ts 反应作业长度:短作业大,长作业小
平均带权周转时间:sum(Ti/Ts)/n 反应同一调度算法对不同作业流的性能Ts:作业在Cpu运行时间 


cpu利用率 = cpu工作时间/(cpu工作时间+cpu空闲时间);


进程调度算法:
FCFS:按提交时间排序,调入一个作业一直到阻塞(添加到就绪队列尾部)或终止;
SJF :按作业要求服务时间Ts排序,从就绪队列调入一直到阻塞(先进等待再就绪)或终止; 可能会产生饥饿现象;
HRRN:每次调入前计算就绪队列中每个作业的响应比H,排降序调入;
RR:就绪队列中的每个作业执行一个时间片,执行完毕进入队尾;
抢占式调度:SJF+HRRN+RR


死锁:一组进程中的每个进程都在等待另一个进程释放资源
1.资源同步互斥;
2.进程已经保持占用一个资源,并提出新请求;
3.进程已持资源不可抢占;
4.循环等待链:p0->p1->...->pn->p0;




*银行家算法:避免系统死锁(Dijkstra) { struct: avab[m]:表示m类可利用的系统资源数目:随系统运行动态运行 maxn[n][m]:n个进程宣告不的各类资源最大数目 alloc[n][m]:n个进程当前占用的资源数 need[n][m] = max[n][m]-alloc[n][m] 每个进程尚需资源数 检查第i个进程安全: work[m]=avab[m]系统可提供给进程继续运行的资源数 finish[m]=系统是否还有资源提供给进程运行使其完成,初始为false 算法流程:当前执行第i个进程(共n个) if(request[j]<=need[i][j])继续;else exit(-1); if(request[j]<=avab[j])继续;else 进程i等待; 试探分配: { avab[j] = avab[j]-request[j]; alloc[i][j] = alloc[i][j]+request[j]; need[i][j] = need[i][j] - request[j]; } if(执行安全检查ok)完成本次分配; else 回复,avab[j],alloc[i][j],need[i][j]进程i等待; 安全检查: { for(i=0;i      
存储器的多层结构
cpu寄存器,{高速缓存,主存储器,磁盘缓存}(主存,主存储器+寄存器 = 可执行存储器),{固定硬盘,移动磁盘}(辅存)


1.连续分配存储
固定分配:等分区分配,不等分区分配(每次装入内存前,从小到大扫描未分配内存区:贪心算法)
动态分配:数据结构+分配算法+回收操作


按地址号只排一次序:
FF首次适应算法:分区形成一个链,从头开始找一个能装下的块,拆成两节点,一个已分配,一个未分配(顺序查找)
NF循环首适应:在FF基础上添加一个起始查找地址,避免低地址空间碎片太多;


每次都匹配前排序:
BF最佳适应:把地址链按空间大小排升序(贪心算法),微观最佳,易产生极小碎片
WF最坏适应:直接找链表头比较,宏观上碎片大,查找快;


2.分页存储管理
页面:进程的逻辑地址空间块
地址结构(二进制):0000,000000   :页号,位移  --  2^4-1页 , 2^6-1页内位移;
页表:(key=页号,val=物理块号)


计算方法:(页面大小==物理块大小size)
物理地址addr->逻辑地址(p,w):
p=floor(addr/size),w=p%size;
逻辑地址(p,w)->物理地址addr:
addr=p*size + w;


3.页面置换算法(驻留集:物理块数,命中<->缺页)
进程抖动:刚淘汰的页面又要调入访问;
Belady现象:分配的页面数(驻留集)增多但缺页率(=缺页次数/进程页面数)反而提高


FIFO:总是淘汰最早进入(就算再次命中也不更新时间)驻留集的页面,会出现Belady现象;
LRU:淘汰最近最久没使用的页面;
OPT:淘汰未来最长时间不使用(同时间的取页号小者)的页面;理论只可用来评测其他算法性能;




磁盘的组织格式(虚拟几何,实际是不同环带扇区数相同,而不是所有磁道同扇区数):
盘片:一个磁盘包括多个盘片;
盘面Surface:每个盘片可能有多个存储面;
磁道(柱面)Track:磁道从外到里编号从0到多;磁道之间有间隙Gap;每个磁道可存储同数量二进制位(内部密度大);
扇区Sectors:一个磁道划分多个扇区,扇区之间有Gap;扇区容量相同;


固定磁头磁盘:每个道上有一个读写头,可以并行读写;
移动磁头磁盘:一个面只有一个读写头,只能串行读写;访问时间 = 寻道+旋转选扇区+读写传输


磁盘调度算法(改变寻道时间):注意磁头运动方向是否可双向读写;
FCFS:根据进程访问磁道先后顺序读写数据;
SSTF:读写和当前磁头距离最近的磁道,容易出现饥饿现象;
SCAN:在SSTF基础上限制磁头移动方向(同一方向最短寻道);         CSCAN:在SCAN基础上规定一个读写方向,逆读写方向时不进行读写操作;     改天补上银行家算法的C++版;