进程控制与同步通信
进程状态转换的典型事件
就绪 to 运行：CPU调度
运行 to 就绪：该进程时间片用完了
堵塞 to 就绪：I/O完成
运行 to 堵塞：等待I/O
信号量机制
1. 整型信号量
wait(s):
while s>=0;
s:=s-1;
signal(s):
s:=s+1;
2. 记录型信号量
3. AND型信号量集 多个锁
信号量解决并发问题
详细解释推荐The Little Book of Semaphores
或者中文翻译版（感谢翻译
1. 生产者-消费者问题
生产者：
P(empty);
P(mutex);
put();
V(mutex);
V(full);
消费者：
P(full);
P(mutex);
get();
V(mutex);
V(empty);
注意mutex的位置。
2. 读者-写者问题
问题分析：可以同时读，不可以同时写，也不可以一个读一个写，所以需要区分wmutex和rmutex。写者很简单，只有我一个人能写，所以加一组信号量即可；读者麻烦一点，想象一个读读读写读读读读写读的序列（实际程序中也是读比较多），我们要保证每一段连续的读可以同时进行，于是让第一个进来的读操作举旗（semaphore）：不要有写进来；让最后一个进来的读操作把旗子放下来：好了可以写了。
读者：
P(rmutex);
if readercount == 0 then P(wmutex);
readercount = readercount +1;
V(rmutex);
Perform read operation;
P(rmutex);
readercount = readercount -1;
if readercount == 0 then V(wmutex);
V(rmutex);
写者：
P(wmutex);
Perform write operation;
V(wmutex);
这个方案可能会把写者饿死，于是书上写用信号量集解决的方案，即规定一次能进入的数量。虽然这个方案没查到（
3. 哲学家进餐问题
问题：五个哲学家围成一圈，每两位哲学家之间有一把叉子。哲学家的生命中只有两件事，思考和吃饭。他们思考完，就要进餐，但只有当他们同时拿到左右两把叉子才会吃饭。吃完饭，放下叉子，继续思考。
解决方案：让四个人先拿左手边的叉子，一个人先拿右手边的叉子。
处理器调度与死锁处理
处理器调度和死锁有个啥的关系哦
进程调度算法
1. 轮转调度算法
2. 优先级调度算法
3. 多级反馈队列调度算法
死锁满足条件
互斥、请求和保持、不可抢占、循环等待
银行家算法
遍历所有线程所需剩余资源，如果现有资源大于其需求，则将资源分配给它，回收这个线程申请的所有资源，直到所有线程都被满足，其被满足的顺序形成一条安全序列。如果不存在这样一条安全序列，就不给这个请求分配资源。
内存管理
我们调度一个任务来执行，就要给它分配内存。先介绍几种连续分配内存的弱智算法。
内存分配算法
1. 首次适应算法 找到第一个能装下的块
2. 循环首次适应方法 从上次找到的分区开始找，找到第一个能装下的块
3. 最佳适应算法 满足要求最小的块
4. 最坏适应算法 满足要求最大的块（产生碎片小）
5. 快速适应算法 把空间按常用大小分好，每次找一块能装下它的
6. 伙伴系统 把空间分割成若干个2的幂次大小，假设要分配的大小为a，那么找到2i<a<2i+1，在i+1里找；如果没找到，就找2i+2，然后劈成两个2i+1，其中一块来放目标。
但是呢这些算法或多或少会产生碎片，于是引入离散分配内存的方式，也就是分页。
分页相关计算
页表：把内存分为离散的块，新建一个映射，也就是页表，来找这些块。
页表项：组成页表的单条数据。
二级页表：建完页表发现这玩意也挺占地的，内存没有那么多连续空间放它。于是把页表也拆成离散的，用哪页把哪页调入内存。再建立一个映射来找页表，也就是二级页表。
例：32位处理器，二级页表，一个页表项4B，一页大小8KB，求外层页表编号。
解：一页大小8KB，占13位地址；8KB/4B=211个页表项，需要11位；32-13-11=8，就剩8位来给外层页表编号了。
若采用多级页表机制，则各级页表的大小不能超过一个页面。
页面置换算法
1. 先进先出 出于礼貌介绍一下，现在可以叉出去了。
最好的页面置换算法是淘汰在最远的未来将使用的页面，但我们不能预测未来，于是根据时间局部性，将过去投射到未来，有了LRU算法。
2. LRU 把最近没使用的页面淘汰掉
但是LRU实现起来太费硬件了，很贵，需要再一步近似的算法。
3. 最少使用 给每个页面一个寄存器，每使用一次，最高位置1，最后淘汰寄存器值最小的页面。这是理想情况。实际访问速度太快，只能隔一段时间记录一次，起不到什么效果，而且移位寄存器也不便宜。
4. 简单Clock置换算法 顾名思义，整一个时钟一样的圆环。圆环被分为很多格，每格代表一个页面，每次被使用，就记录一个1。想象有一根指针始终指着十二点方向，圆环以圆心为轴匀速转动，每隔一段时间指向一个格子。如果被指到的格子值为1，则置零；如果为零，将该页淘汰。
显然这个算法会经常把页面踢出去，于是我们考虑另一个问题：要是每次能先把没有修改的页面踢出去就好了，这样写回可以少花点时间。
5. 改进Clock置换算法 添加一个修改位，1表示修改过，0表示每修改过。考虑让时间之轮（雾）转动。先扫描一圈，看看有没有既没访问过，又没修改过的理想替换页，如果有，踢出去（第一轮查找过程中不要把访问位置零）；如果没有，只能进行第二轮查找，找没有访问过，但是修改过的页面了，并且一边找一边把修改位置零。
文件管理及文件系统
文件的打开与关闭
每次访问文件，系统都要检索目录。为了避免这一行为反复发生，将文件属性拷贝到内存，并分配一个索引号。每次访问文件，就能根据索引直接找到文件了。这一过程叫做打开。与之对应，关闭就是把这个索引从表中删除。
文件平均查找次数
顺序文件：(N+1)/2
一级索引顺序文件：sqrt(N)+1
外存分配方式
1. 连续分配 如题
2. 隐式链接分配 文件被分成一块一块，文件目录给出起始和末尾，中间像链表一样一个接一个，指向下一个文件的指针存在磁盘上。可见这种方式只能顺序访问文件内容，并且一环断了，后面的就都访问不到了。
3. 显式链接分配 和上面差不多，就是将每块文件的块号写在一张FAT表里。
4. 索引分配 将需要的盘块号写在一个盘块里，这个盘块叫索引盘块，文件目录放这一块就好了。
5. 多级索引 盘块太多啦，一个索引盘块放不下。把它拆成树形结构吧。
然后给新来的文件分配空间。听起来有些许耳熟，但这次是分配外存，不像内存寸土寸金。而且不能将已有内容踢出去。
文件存储空间管理
1. 空闲表法 如题，属于连续分配方式。记录一张空闲盘块表，写从哪块开始，有多少块空闲的连续盘块。然后试图往里塞，又是首次适应啥啥啥的方法，反正效果都差不多。回收的时候和前后空闲区域连接一下就行。
2. 空闲链表法 这次分配的不连续了。把所有可用盘块拉成一条链，挨个分配，直到分配完。回收的时候再把链条挂回来。坏处是可能会把空间切得稀碎。
3. 位视图法 用一个二维数组记录磁盘盘块使用情况（听起来就占地），用的时候置1，回收置0.盘块b和第i行第j列换算公式：
b=n(i-1)+j
i=(b-1)/n+1
j=(b-1)%n+1
(i, j从1开始)
4. 成组链接法 比较复杂，直接看ppt了
注意最后一组栈底填0.
文件分配表空间开销计算
文件共享方式
索引结点、符号链
设备管理(含磁盘设备管理) 及系统调用接口和操作系统引论
I/O控制方式
程序I/O控制方式 简单的忙-等待方式
中断驱动I/O控制方式 中断机制的引入
直接内存存取型I/O控制方式 DMA控制器、数据传输单位扩大
通道型I/O控制方式
磁盘访问时间
寻道时间Ts=移动时间(通常是0.几) * n(移动道数) + 磁臂启动时间(约2ms)
设转速为r，
旋转延迟时间Tr=1/2*r
数据传输时间Tt=bytes/(r*bytesPerTrack)
访问时间为以上三者之和。
缓存
单缓冲平均耗时：
max(C, T)+M
双缓冲平均耗时：
max(M+C, T)
假脱机技术(SPOOLing)
SPOOLing 系统实现设备管理的虚拟技术，即：将独占设备改造为共享设备。它由专门负责 I/O 的常驻内存 进程以及输入、输出井组成。
移动头磁盘调度算法
小学算术，但考试爱考。
1. 先来先服务（FCFS） 如题
2. 最短寻道时间优先（SSTF） 假设当前磁盘头为止为x，选择离x最近的文件去访问。可类比耗时最短进程先执行，听上去有点问题的样子。
3. 扫描算法/SCAN/电梯调度算法 每次访问与当前移动方向一致的最近文件，如果没有了，转向。
听上去不错，但如果磁盘头前脚走，一个请求后脚来，它就只能等磁盘头再回来了，不好。
4. 循环扫描算法（CSCAN） 循环是指把磁道里外两头看作是连起来，即，走到最外圈，马上回到最里圈从里向外扫描，而非由外向里。
标签：文件,操作系统,存档,分配,算法,页表,习题,盘块,页面 From： https://www.cnblogs.com/capterlliar/p/17127675.html