njuseos
TBD
存储管理
TBD
页式
逻辑地址：
| 页号 | 单元号 |
|---|
物理地址：
| 页框号 | 单元号 |
|---|
地址转换通过查页表完成。
页的共享
- 数据共享：不同进程可以使用不同页号共享数据页
- 程序共享：不同进程必须使用相同页号共享代码页
快表
快表表项：页号，页框号
联想存储器，按内容寻址，而不是按照地址访问。
多道程序环境下的进程表
进程表中登记了每个进程的页表。
| 用户作业名 | 页表地址 | 页表长度 |
|---|---|---|
局部性
页式虚拟存储管理
- CPU处理地址
- 若页驻留，则获得块号形成绝对地址
- 若页不在内存，则CPU发出缺页中断
- OS处理缺页中断
- 若有空闲页框，则根据辅存地址调入页，更新页表与快表等
- 若无空闲页框，则决定淘汰页，调出已修改页，调入页，更新页表与快表
页面调度
CLOCK
- 页面调入主存时，其引用标志位置 1
- 访问主存页面时，其引用标志位置 1
- 淘汰页面时，从指针当前指向的页面开始扫描循环队列
- 把所遇到的引用标志位是 1 的页面的引用标志位清 0，并跳过
- 把所遇到的引用标志位是 0 的页面淘汰，指针推进一步
Belady's Anomaly
FIFO时，增加页框数导致缺页增加的现象。
TBD
并发
并发程序设计的特性
- 并行性
- 共享性
- 交往性
无关与交往的并发进程
- 无关：一组并发进程分别在不同的变量集合上运行，一个进程的执行与其他并发进程的进展无关
- Bernstein条件：并发进程的无关性是进程的执行与时间无关的一个充分条件。
- 交往：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果
互斥与临界区
- 临界资源：互斥共享变量所代表的资源（一次只能被一个进程使用的资源）
- 临界区：并发进程种与互斥共享变量相关的程序段
临界区管理
软件
硬件
- 关中断
- 实现互斥的最简单
- 不建议用户程序
- 测试并建立指令
- 兑换指令
- TS和swap都是忙等待，效率低
- 可以在进入临界区时开关中断解决
PV操作
数据结构
设s为一个记录型数据结构，一个分量为整型量value，另一个为信号量队列queue，P和V操作原语定义：
P(s)：将信号量s减去1，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态
V(s)：将信号量s加1，若结果不大于0，则释放(唤醒)一个等待信号量s的进程，使其转换为就绪态
信号量只允许使用PV原语操作，不能直接读写。
P操作意味着请求一个资源（阻塞进程）。
V操作意味着释放一个资源（唤醒被阻塞进程）。
进程状态转换
就绪态 <==> 运行态 (CPU调度)
运行态 =P(s)=> 阻塞态
阻塞态 =V(s)=> 就绪态
信号量
- s为正值：实际可用的资源数
- s为负值：正在等待的进程个数
管程
定义
管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块。
属性
- 共享性
- 安全性
- 互斥性
条件变量
在管程内，只有在管程中才能被访问。对管程内所有过程都是全局的，只能通过两个原语控制。
wait()
阻塞调用进程并释放管程，直到另一个进程在该条件变量上执行signal()。
引起进程阻塞。
signal()
如果存在其它进程wait(), 则释放。若没有进程等待，不保存信号。
释放阻塞进程。
霍尔管程
使用P和V操作原语实现对管程种过程的互斥调用，及实现对共享资源互斥使用的管理。
不要求signal操作是过程的最后一步操作，wait和signal可中断。
数据结构
mutex
初值为1。
进程调用管程种的任何过程时，应执行P(mutex)，退出管程时，需要判断是否有next在等待。若有next_count > 0，则V(next)唤醒一个发出signal的进程，否则V(mutex)，让其它调用者进入。
next 和 next_count
next初值为0。
凡是发出signal操作的进程应该用P(next)阻塞自己，直到被释放或产生其它等待条件。
next_count初值为0。用来记录在next上等待的个数。
进程在退出管程的过程前，必须检查是否有别的进程在信号量next上等待。
x_sem 和 x_count
x_sem初值为0，申请资源得不到满足时，执行P(x_sem)阻塞。
使用x_count记录等待资源的进程数。
执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程（V(x_sem)）。