国外服务器购买推荐_网站源码官网_个人怎么在百度上打广告_百度官方下载

依据顾恺之吃甘蔗的理论，我们从易到难，越吃越有味。

第五章 进程调度

缩写：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原话：根据答案猜出题人的想法啦）

下面两道题描述得还算清楚，没什么争议：

（2022A）

逻辑块号：600
在二级索引中。
文件索引不在memory，所以依次读入inode、一级索引、二级索引、数据块。共四次。

（2020模拟）

逻辑块号：20
目标数据块在一级索引中。
root在memory中，依次读入C的inode、B的inode、M的inode、一级索引、数据块。共五次。

第八、九章 段/页式+虚存

考法：

1. 逻辑地址转物理地址
   • 给你逻辑地址，你能劈出页号和页内偏移。会根据页号查页表，得到页框号。再把页框号跟页内偏移合一起，即物理地址。
   • 注意缺页的情况，页表中有一列i/v
   • 且有个limit reg界限寄存器，不要忽略。很有可能你这个逻辑地址是非法的。
2. 算EAT（有效访问时间）
   • （yw原话：根据答案猜出题人的想法啦）×2
   • 考试时如果没有明说页表和快表是同时访问还是依次访问，那么可以随便写一种，并且前面写上“假设xxxxx”
3. 页置换算法（LRU，FIFO，OPT，clock/二次机会）
   • 千万要注意！frame初始是空的还是提前装好了一波
   • 2022A
   • 2022B
     
4. 小知识点（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子系统+驱动）

1. 计算磁盘访问时间=寻道时间（给）+旋转时间（计算转半圈的时间）+延迟（给）+传输时间（用磁盘传输速率与块大小计算）
2. 注意速率的单位是10的多少次方，不是2的多少次方（那是数据量）