- 第五章 进程调度
- 第十二章 磁盘调度
- 第七章 死锁检测、死锁避免(银行家)
- 银行家算法
- 死锁检测
- 第十一章 文件系统
- 第八、九章 段/页式+虚存
- 第六章 同步,信号量
依据顾恺之吃甘蔗的理论,我们从易到难,越吃越有味。
第五章 进程调度
缩写:FCFS、SJF、SRTF(看到这个就不得不说SSTF是什么)、RR、priority、多级队列、多级队列带反馈。抢占or非抢占。
比如出一道题,给了到达时间、CPU brust、优先级。让用抢占式SJF调度算法,那么要知道,这就是考SRTF,不要看见抢占就想到优先级。此题给的优先级在混淆视听——此为“考概念是否理解”。
甘特图的画法。第二问来个等待时间和周转时间。
先算周转,就是进程完成时间-到达时间
等待时间=周转时间-brust时间
普通考题大致面貌如下:
(2021期中)
此外,也有可能不给具体的调度算法,让你自己设计调度算法。那就要根据给的进程的brust time情况枚举法找出最优的。试数法。
(2017期中)
如果跟第六章同步来结合,就会有点难度。但是原话是“不考太难”,故下题仅为参考。
(2021期中13-14,17-18班)
第十二章 磁盘调度
又是题目明确且缩写云集的一章内容。FCFS、SSTF最短寻道时间优先(SRTF是谁?)、SCAN、C-SCAN、LOOK、C-LOOK
最后四个的记法:
SCAN代表扫描,从头到尾,从尾到头……。
LOOK是不到头尾,只到最远请求就回头。就是要边走边看的嘛。
不带C的,两个方向都能扫。
带C的,C是循环的意思。一个方向扫,扫完猛甩头。
题目都长这样,四位以内加减法问题,没见过变样:
第七章 死锁检测、死锁避免(银行家)
上来给个表格。要么考检测要么考避免。
二者不同点:
检测 | 避免(银行家算法) |
---|---|
没有安全序列的概念,出现该字眼则扣分 | 有安全序列、安全状态的概念 |
没有max、need矩阵,只有allocation、request矩阵 | 没有request矩阵,有max、need矩阵 |
初始化,如果allocation=0,那么finish=true,即该进程不占有资源,必不参与死锁 | 初始化,finfish均为false |
work跟request比 | work跟need比 |
相同点:
相同点 |
---|
初始化 work=available |
更新work,work+=allocation[i] |
银行家算法
方法论:
例题:
死锁检测
方法论:
例题:
(2020模拟)
第十一章 文件系统
三种磁盘分配方式:连续分配、链式分配、索引分配。
考法:
- index(索引分配)组织方式下的文件上限大小
- 逻辑块到物理块的映射
- 磁盘IO次数
- 要看清什么东西已经在main memory中了。有的题是FCB,有的是……总之就是磁盘IO次数多1少1的问题。也有可能题意不清,这在练习题中非常常见
(yw原话:根据答案猜出题人的想法啦)
- 要看清什么东西已经在main memory中了。有的题是FCB,有的是……总之就是磁盘IO次数多1少1的问题。也有可能题意不清,这在练习题中非常常见
下面两道题描述得还算清楚,没什么争议:
(2022A)
逻辑块号:600
在二级索引中。
文件索引不在memory,所以依次读入inode、一级索引、二级索引、数据块。共四次。
(2020模拟)
逻辑块号:20
目标数据块在一级索引中。
root在memory中,依次读入C的inode、B的inode、M的inode、一级索引、数据块。共五次。
第八、九章 段/页式+虚存
考法:
- 逻辑地址转物理地址
- 给你逻辑地址,你能劈出页号和页内偏移。会根据页号查页表,得到页框号。再把页框号跟页内偏移合一起,即物理地址。
- 注意缺页的情况,页表中有一列i/v
- 且有个limit reg界限寄存器,不要忽略。很有可能你这个逻辑地址是非法的。
- 算EAT(有效访问时间)
(yw原话:根据答案猜出题人的想法啦)×2- 考试时如果没有明说页表和快表是同时访问还是依次访问,那么可以随便写一种,并且前面写上“假设xxxxx”
- 页置换算法(LRU,FIFO,OPT,clock/二次机会)
- 千万要注意!frame初始是空的还是提前装好了一波
- 2022A
- 2022B
- 小知识点(9.6节):抖动(/颠簸,thrashing)。定义:一个进程的调页时间多于执行时间。处理方法:工作集策略、缺页错误频率策略。
最后来看一道综合了“页置换算法、地址转换、求EAT”的英文阅读题:
思路:
第二问注意标黄的那几个单词,意思是进行“取这条指令以及取指令中的操作数地址”所产生的reference string是包含在题里的string中的。(我一开始理解为追加,以为要考最先换出哪个逻辑页)
第三问求EAT,如果缺页了,就是“访存时间+处理时间+访存时间”,如果命中,就是“访存时间+访存时间”(在没有快表的情况下)。那么在本题中是两个缺页,并且一个是页调入(耗时200),另一个是页置换(耗时300),所以一共耗时540.
第六章 同步,信号量
在互斥中,学习了三个经典模型,看见什么新情景就往这仨身上套。它们分别是:
生产者消费者问题(有界缓冲区问题)
-
它的特点是对称
一个进程:申请A……释放B
-
另一个
申请B……释放A
读写者问题
-
普通版:只要读者鱼贯而入的来,写者必进不去。
-
升级版1:允许最多M个读者同时读。方法:增加信号量empty。
-
升级版2:读写者公平竞争。方法:增加排队信号量queue
-
升级版3:写者优先。方法:增加信号量queue,变量write_cnt及其保护信号量。
哲学家就餐问题
- 重点是模板。
由以上三个经典模型,衍生出一系列周边,它们分别是:
橘子苹果问题
-
有界缓冲区+读写者
-
题目:一个盘子,能盛1个苹果或3个橘子,不能混放。father每次放入一个苹果,son每次拿走一个苹果。mother每次放入一个橘子,daughter每次拿走一个橘子。
盘子容量=1的东西对应的代码很简单很对称(father-son)// fatherwait(mutex_plate);放入苹果signal(apple);// sonwait(apple);拿走苹果signal(mutex_plate);// motherwait(orange_empty);wait(mutex_orange_count);orange_count++;if (orange_count == 1) wait(mutex_plate);signal(mutex_orange_count);放入橘子signal(orange);// daughterwait(orange);拿走橘子wait(mutex_orange_count);orange_count--;if (orange_count == 0) signal(mutex_plate);signal(mutex_orange_count);signal(orange_empty);
-
换汤不换药的猪虎饲养员问题:
-
问题2:一个盘子,能盛2个苹果或3个橘子,不能混放。father每次放入2个苹果,son每次拿走一个苹果。mother每次放入一个橘子,daughter每次拿走一个橘子。
盘子:能放m个苹果或者n个橘子father:每次放m个苹果mother:每次放1个橘子son:每次取一个苹果daughter:每次取一个橘子信号量:mutxe_plate = 1, apple_full = 0, orange_full = 0, orange_empty = n变量:int apple_cnt = 0, orange_cnt = 0保护信号量:mutex_apple_cnt = 1, mutex_orange_cnt = 1father:wait(mutex_plate);wait(mutex_apple_cnt);apple_cnt = m;signal(mutex_apple_cnt);放m个苹果for (int i=0; i<m; i++) signal(apple_full);son:wait(apple_full)取1个苹果wait(mutex_apple_cnt);apple_cnt--if (apple_cnt == 0) signal(mutex_plate);signal(mutex_apple_cnt);
士兵过桥问题
- 读写者问题,两边都是读者。2024期中。
睡眠理发师问题
- 需要注意是没有资源时顾客会离开而非等待。所以需要判断信号量的具体值是多少。用
普通变量+二元信号量保护
来平替信号量。 - 卖手机问题(2020模拟):一个售货员,卖100个手机,大厅里20个座。顾客来了后排队,一个一个买,每人买一个。如果每座了or手机卖没了,顾客离开。
和尚打水问题
- 某寺庙,小、老和尚若干
水缸,由小和尚提水入缸(向缸中倒水),老和尚从缸中提水饮用,水缸可容10 桶水
水取自同一井中,水井径窄,每次只能容1个桶取水
水桶总数为3个。每次向缸中倒水、或从缸中取水仅为1 桶,且不可同时进行
进程分配资源问题
- 有6个并发进程P1, P2, P3, P4, P5, P6,每个进程执行时需要同时使用1 page 内存资源和1个I/O设备
内存资源总量为3 pages,I/O设备总量为3
【附】小题复习
快问快答:
操作系统是什么驱动的?中断
中断向量中存放了什么?中断处理程序首地址
三种中断分别是?硬中断、syscall、trap/异常
双模操作是什么?用户模式、内核模式
API和syscall的区别?API封装了,不依赖具体操作系统
向操作系统传递参数的3种常用方法?各自优点?
系统调用分为哪6类?
文件属性包括?文件名、文件类型、保护码、记账信息
微内核的三个优点?便于扩展、安全、可靠
进程包括什么?代码、数据、堆、寄存器
PCB包括什么?(7个)进程状态、PC、通用寄存器、IO状态信息、内存管理信息、CPU调度信息、记账信息
PCB不包括什么?用户数据。
上下文包括什么?用户级上下文:指令,数据,共享内存、用户栈;寄存器上下文:程序计数器,通用寄存器,控制寄存器,状态字寄存器,栈指针(用来指向用户栈或者内存栈);系统级上下文:pcb,主存管理信息(页表&段表)、核心栈
切换上下文是什么意思?保存当前进程状态,恢复另一个进程状态。
目的?切换CPU到另一个进程。
僵尸进程、孤儿进程分别是什么,怎么处理它们?僵尸进程是已经已经结束但父进程没有回收它的资源。孤儿进程是父进程结束但子进程没结束。
微内核架构的代表?Mach 鸿蒙
booting的过程?bios-引导盘-内核-系统程序-应用程序
进程通信方式?共享内存 消息传递
临界区问题的解决方案要满足什么特点?互斥、进展、有限等待
死锁的必要条件?互斥、持有且等待、非抢占、循环等待
谁首次提出死锁概念、银行家算法?dijkstra
资源分配图怎么画?等待图?画图法使用的前提?资源为方,进程为圆。适用于每种资源只有一个实例
银行家算法是死锁什么算法?避免
死锁预防主要通过破坏哪必要条件?hold and wait 和circular wait(第二个和第四个,第四个最常用)。第一个完全没用,第三个适用于抢占能保存上下文的东西,如寄存器或cpu
死锁检测和死锁避免的区别?检测:无人申请,定时检测,按需回滚避免:有人申请,判断是否批准
三个binding的时机?哪个物理地址等于逻辑地址?什么是逻辑地址?编译时绑定,加载时绑定,执行时绑定。只有编译时绑定,PA才等于LA。前两个是静态链编,执行时绑定是动态链编。CPU产生的地址是逻辑地址。
内部碎片是什么?外部碎片是什么?
不同的内存分配方法导致内部碎片还是外部碎片?分段:仅外部分页:仅内部固定大小分区(多道程度固定):内外都有可变分区(3种fit):仅外部
为什么使用多级页表?它对于提高页表访问速度有帮助吗?有两种情况:一是页表太大无法连续存储,所以引出多级页表。二是如果进程的逻辑地址仅仅用了很小的几段,那么中间没用的没必要放到内存中。对提高访问速度没有帮助。
全局页置换和局部页置换分别是什么意思?
两级文件打开表分别是什么,存放什么内容?系统打开文件表、进程文件打开表。系统:磁盘位置、打开计数器进程:权限、读写指针
文件系统构成?逻辑文件系统(元数据、权限)、文件组织模块(映射)、基础文件系统(发命令)。后两个称为物理文件系统。IO子系统的功能?scheduling, buffering, caching, I/O protection, error handling调度,缓冲,缓存,保护,错误处理
IO系统构成?设备、设备控制器、IO子系统(包括内核IO子系统+驱动)
- 计算磁盘访问时间=寻道时间(给)+旋转时间(计算转半圈的时间)+延迟(给)+传输时间(用磁盘传输速率与块大小计算)
- 注意速率的单位是10的多少次方,不是2的多少次方(那是数据量)