操作系统学习笔记

DEAD

大佬博客

1 2

祖传计算题

四个必考计算题:银行家 进程调度 电梯算法 页表
(似乎前三个大题都是送分的)
计算题据说每年都一样,只是换换数据.

银行家算法

need矩阵:实际上就是进程右边再开一行,标注还需要多少资源,资源用元组()括号包住.

检查当前进程中是否存在资源足够能够完全供给的进程,如果有就供满然后把资源全抽出来,否则报告进程是不安全的.

  1. 判断当前进程是否安全,如安全给出安全序列,否则报告是不安全的.

方法:列表.(work=available是可用资源,need是还需要的资源,allocation是已分配的资源)

进程 work need allocation work+allocation finish
P1 1 2 3 4 5 6 7 8 9 10 11 12 √
  1. 假如进程Px请求一个request(xxx),能不能进行?为什么?

request的含义是,当前进程需要的资源总和都不变,只是这个进程想提前拿到一部分资源,所以要检查(1.req<=avail不能不够,2.req<=need不能多拿)然后变成一个新的进程,再跑一遍银行家看能不能找到.

  1. 银行家算法因为提前计算资源分配情况,如果不够就不会分配,所以不会进入死锁状态,只会进入不安全状态,也就是所有进程会进入阻塞状态.

页表

虚拟地址=逻辑地址.

一级页表

记录xx进程去内存哪个位置了(进程和内存按照相同大小分块)逻辑地址

页号 偏移量
有多少个页表项 块大小(如4KB对应2^12B所以偏移量填12)

二级页表

二级页表有多少个?
对应的一级页表占用的存储空间/一个二级页表的空间.

段表

分成多少段,每段怎么怎么着,造成什么中断?

越界中断(数组在段中越界了)
缺段中断(这个段就不在主存中)

页面置换算法

三种:最佳置换算法(OPT):淘汰后续用不使用/最长时间内不再被访问的(也就是向后看淘汰最后一个出现的页面,例如内存123访问4,4后续还要访问123,此时3是最后出现的会被挤掉)
先进先出页面置换算法(FIFO):挤掉最早进入内存的页面(看连续块的长度挤掉最长的)
最近最久未使用闲置算法(LRU):向前看淘汰最后一个出现的页面

考点:缺页次数(内存中没有该页需调入内存),也就是内存更改次数
页面置换次数(缺页但内存满了需要页面调换)
缺页率=缺页数/总进程数
命中率=1-缺页率

多级索引

记得先算一个数据块能放多少个索引地址.

直接索引:地址就是数据.
一级索引:地址指向一个数据块,数据块里面的内容全是地址,这么多地址指向数据.
二级索引:地址指向一个数据块,数据块里面全是一级索引…
三级索引:…

周期性实时任务 Grantt图 处理机调度

单道:所有设备都紧着当前进程供给(也就是说程序A即使正在用CPU,程序B也不能用IO设备)
多道:设备是分开供给的(程序A正在使用CPU的时候其他程序不可以用CPU但是可以用IO设备)

Grantt图:直接画就行,自己看,虚线表示正在等待占用.

1
2
3
4
5
6
7
程序
 |CPU
A|---------
 |设备甲    CPU
B|----     ---
 +------------>t
     5   10

最早截止期优先算法

实时调度算法

先来先服务(FCFS)

短作业优先(SJF)
非抢占:动态取当前最小进程一口气执行完.
抢占:基于最短执行时间:假设D执行5s,E在第3s插入,因为D是5小于E,所以这个时候D会让位给E,E完了再D.
基于最短剩余时间:还是上述条件,此时因为D还剩2s是小于E的3s的,所以D会被执行完,然后才轮到E.

优先权调度算法:直接按照给定的顺序模拟即可,优先级数字越大越优先.

动态优先权算法:优先权=1+等待时间/需要时间
每轮算一下,取最大的进程执行到底,然后再算,再取…

周转时间=完成时间-到达时间
带权周转时间=周转时间/服务时间

PV大题

信号量大题.一定要写清注释!

同步:等待
互斥:独立使用某种资源
分析是否需要while(1)
定义信号量 semaphore ,同步的信号量初始是0,互斥的信号量初始是1.

死锁:将同步P放在互斥P前面

1
2
3
4
5
6
7
semaphore aa;

A(){
    xxx
    P(B);//等待B
    V(B);//取消等待
}

例如有ABCDE五类操作,C要在AB后执行,E要在CD后执行,尝试写代码.

分析关系得到AB运行完要解除C的等待(V(C)),CD运行完要解除E的等待,而且B在运行前要检查AB的等待(P(A),P(B)),然后剩下的都无所谓了,注意检查死锁

磁盘调度算法

非常蠢的四种方法.
平均查找长度=(sum差的绝对值)/多少个请求

  1. 先来先服务(FCFS)
  2. 最短寻找时间算法(SSTF)(贪心的每次找最近的)
  3. 电梯算法(C-SCAN扫描算法)(先 人为规定 向上走,然后再向下,沿路接受访问)
  4. 循环扫描算法(SCAN,一直上升,到需求的顶了之后突然变成0,然后再接低层的)

页式虚拟存储

在一个采用页式虚拟存储管理的系统中,有一用户进程,它依次要访问的逻辑地址序列是:

1
2
3
4
07FEh 093Ah 0F42h
1357h 045ch 0BC0h
15AFh 05D2h 0A4Bh 
OCDEh 11F2h 16ABh

现分配给该进程的主存空间共4K字节,每页的大小为1K字节.
(1)按FIFO调度算法将产生缺页中断次数,淘汰的页号,缺页中断率.
(2)按LRU调度算法将产生缺页中断次数,淘汰的页号,缺页中断率.

原始内存是很大的,所以对页大小直接除,在这个题也就是说,这个16位有10位是原始数据,剩下的高6位会被分页,所以对每个数据取高位6作为页面编号,得到一个数字串,对其跑算法即可.

对一个分页逻辑转内存地址

E是实际地址
b是内存块号
l是一页大小
w是页内偏移(hex%l)
页号=(hex/l)

ADD

Fragmentation(碎⽚化)：指内存或磁盘中，因空间分配与回收⽽产⽣了许多不连续的⼩空间，这些空间太⼩⽽⽆法被有效
利⽤，造成了浪费。

RAID：独⽴磁盘冗余阵列 (Redundant Array of Independent Disks) 。它是⼀种将多个物理硬盘组合成⼀个逻辑单元的技
术，⽬的在于提升存储性能、数据冗余或两者兼备。

first fit(⾸次适应算法)：⼀种内存分配算法。当进程请求内存时，系统从头开始查找，并将进程放⼊第⼀个找到的、⼤⼩
⾜够的空闲内存块中。

地址映射：指将程序使⽤的逻辑地址（或虚拟地址）转换为内存条上的物理地址的过程。这个转换是实现虚拟内存和内
存保护的基础。（也就是重定位）

PCB (进程控制块)：它是操作系统⽤于描述和管理⼀个进程的核⼼数据结构，记录了进程ID、状态、资源占⽤情况等全部
信息，相当于进程的“⾝份证”。