定义

周转时间=等待时间+处理时间

响应时间=周转时间/处理时间=1+等待时间/处理时间

进程调度

批处理系统

先来先服务

最短作业优先

最短剩余时间优先

最高响应比优先

交互式系统

轮转调度

最高优先级调度

多级反馈队列调度

最短进程优先

保证调度

彩票调度

公平分享调度

进程互斥

软件实现

屏蔽中断

锁变量

严格轮换(单标志法)

由于需要严格轮换，所以无法满足当临界区空闲且有进程想进入时，能够及时进入临界区。

Peterson算法

interested[2]、turn

Dekker算法

硬件实现

中断屏蔽(开关中断指令)

TSL指令(TestAndSetLock指令)

把内存地址中的信息拷贝到寄存器中，并在地址中存储一个非零的值，指令结束之前，该内存地址不允许被访问

XCHG指令

交换寄存器和内存地址中的值，指令结束之前，该内存地址不允许被访问

LDREX、STREX指令

信号量

信号量只能初始化、P操作、V操作，使用原语操作，不可中断。

P、V操作

P操作：占用资源

V操作：释放资源

信号量机制实现进程互斥

信号量机制实现进程同步

使得两个进程能够按照一定的顺序执行

信号量机制实现前驱关系

进程同步的扩展

生成者-消费者问题

！！！！！实现互斥的P操作一定要在实现同步的P操作之后！！！！！

多生产者-多消费者问题

！！！！！如果缓冲区大于1，必须设置一个互斥信号量mutex来保证互斥访问缓冲区！！！！！

吸烟者问题

读者-写者问题

哲学家进餐问题

信号量vs管程

死锁

产生条件：互斥使用、 占有且等待、不可抢占、循环等待

发生死锁，一定有循环等待；但有循环等待，不一定发生死锁

死锁建模

二元组G=(V,E)

处理死锁的策略

忽略

假装不存在死锁

预防死锁

破坏产生死锁的四个条件

破坏互斥使用：把独占资源变为共享资源，SPOOLing技术。但很多情况下，并不能这样。不实用。

破坏不可抢占：当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源。不实用。

破坏占有且等待：采用静态分配方法，一次性申请全部需要的资源。不实用。

破坏循环等待：采用顺序资源分配法，给资源编号，每次申请只能申请更大的资源。不实用。

避免死锁

银行家算法寻找一条资源分配顺序的路线

E表示全部资源量，P表示已分配资源量，A表示剩余资源量

检测与恢复

**一、**死锁检测 可利用死锁模型检测、或矩阵检测 很想避免死锁中的银行家算法

**二、**解除死锁 资源剥夺法、撤销进程法、进程回退法（进程优先级、已执行时间、剩余时间、已使用资源量、交互式or批处理式）

内存管理

无存储抽象

①程序中的地址就是真实的内存地址。

②切换程序(进程)的时候整个程序(进程)在内存—硬盘之间切换。

③一段时间内内存中只有一个程序。

④保护机制：把内存划分为若干区域，每个区域设置访问权限，进程拥有自己的访问权限，只能访问权限相对应的内存。

地址空间

进程看到的是虚拟的地址，进程的地址空间相互独立且足够大，不是最终的物理地址，需要经过一个虚拟地址到物理地址的转换。

动态重定位

基址寄存器和界限寄存器

缺点：访问内存都需要进行加法和比较运算；内存空间可能是瓶颈。

交换技术

空闲内存管理(连续)

固定分区分配

优点：最简单的存储分配

缺点：利用率低，会产生内碎片

动态分配—位图

动态分配—链表

首次适配、下次适配、最佳适配、最差适配、快速适配

伙伴系统

slab机制

虚拟内存(非连续)

覆盖

缺点：程序员必须自行分割程序：费时且容易出错

分页式存储管理

基本概念

页表

页表位于内存中

硬件支持—MMU

加速分页过程TLB

多级页表

倒排页表

页面置换算法

最佳算法、先进先出、第二次机会、时钟算法、最近未使用、最近最少使用、最不经常使用、老化算法、工作集、工作集时钟

时钟算法

改进型时钟算法

最近最少使用(LRU)

最不常用算法与老化算法

工作集算法

工作集时钟页面置换算法

分段存储管理方式

段表

分页、分段对比

段页式管理方式

分页、分段的优缺点

基本思路

段表、页表

文件管理

文件有哪些属性？

文件名、标识符、类型、位置、大小、创建时间、上次修改时间、所有者、保护信息(权限)

文件结构

文件存放

顺序文件

顺序文件的缺点是增加或删除一个记录比较困难

索引文件

索引顺序文件

多级索引顺序文件

文件目录

单级目录结构

两级目录结构

层次目录结构

无环图目录结构

索引结点

文件的物理结构

连续分配

优点：读写速度最快

缺点：不灵活，利用率低

链接分配

隐式链接

显式链接

文件分配表FAT

索引分配与i结点

文件存储空间管理—空闲块管理

空闲表法

空闲链表法

位示图法

文件基本操作

创建文件

删除文件

打开文件

关闭文件

读文件

写文件

文件共享

系统中只有**“一份”**文件数据，某个用户修改了文件数据，其他用户也可以看到文件的变化，注意与复制的区分

基于索引结点的共享方式(硬链接)

基于符号链的共享方式(软连接) 快捷方式

对比

硬链接无需额外的开销，只需要在i结点中添加计数器，计数有多少个链接，而符号链接即软链接需要额外的开销来存储共享文件的路径名。

软链接只要简单地提供一个机器的网络地址以及文件在该机器上的驻留的路径，就可以链接全球任何地方的机器上的文件，而硬链接不能这样。

文件保护

口令保护

加密保护

例如异或加密等，系统中保存的是解密后的密文

优点：保密性强，不需要在系统中存储“密码”

缺点：加密/解密需要花费一定时间

访问控制

磁盘调度算法

一次磁盘读/写操作的时间：寻道时间、延迟时间(转动时间)、传输时间

先来先服务

根据进程请求访问磁盘的先后顺序进行调度

最短寻道时间优先

扫描算法/电梯算法

LOOK调度算法

循环扫描算法

C-LOOK调度算法

I/O管理

I/O控制器

I/O控制方式

程序直接控制

读操作(数据流向)：IO–>CPU–>内存

写操作(数据流向)：内存–>CPU–>IO

优点：实现简单

缺点：只能串行工作，CPU长期处于“忙等”状态

中断驱动方式

优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。

缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗比较多的CPU时间。

DMA方式(直接存储器存取)

CPU干预的频率进一步降低

通道控制方式

层次结构

设备独立性软件：①向上层提供统一的调用接口；②设备的保护；③差错处理；④设备的分配与回收；

​ ⑤数据缓冲区管理；⑥建立逻辑到物理的设备名的映射关系；

中断处理程序：

核心子系统

假脱机技术SPOOLing

设备的分配和回收

设备的固有属性：独占设备、共享设备、虚拟设备

安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才唤醒进程 缺点：只能串行工作

不安全分配方式：与安全分配方式相反 缺点：可能发生死锁

静态分配

进程运行前为其分配全部所需资源，运行结束后归还资源

动态分配

进行运行过程中动态申请设备资源

设备分配表DCT

控制器控制表COCT

总结

以上是生活随笔为你收集整理的[现代操作系统] 考前突击的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。