本文是《现代操作系统》一书的阅读笔记,主要记录俺觉得重要的知识。
第2章:进程与线程
进程
进程会处于三种状态之一:
- 运行:正在使用CPU;
- 阻塞:直到特定外部事件发生后才运行;
- 就绪:让位CPU给其他进程,等待调度运行。
线程
线程和进程的区别可以从包含的内容不同看出:
每个进程中的内容 | 每个线程中的内容 |
---|---|
地址空间 | 程序计数器 |
全局变量 | 寄存器 |
打开文件 | 栈 |
子进程 | |
即将发生的警报 | |
信号与信号处理程序 | |
账户信息 |
进程间通信
竞争条件:两个或多个进程读写某些共享数据,而最后的结果取决干进程运行的精确时序。
互斥:当一个进程在使用一个共享变址或文件时,其他进程不能做同样的操作。
临界区域:对共享内存进行访问的程序片段。
互斥的实现可以有以下几个思路:
- 屏蔽中断:进人临界区后立即屏蔽所有 中断,并在就要离开之前再打开中断。(存在问题:用户权限、多核芯片)
- 锁变量:使用一个共字(锁)变最。(存在问题:变量本身竞争)
- 严格轮换法:(存在问题:浪费CPU、被临界区之外的进程阻塞)
- Peterson解法:在严格轮换法基础上增加了检查进入临界区意愿的环节。
- TSL指令
TSL RX, LOCK
:将一个内存字lock读到寄存器RX中,然后在该内存地址上存一 个非零值。XCHG RX. LOCK
:原子性地交换了两个位置的内容。
- 睡眠与唤醒: 当条件不满足时睡眠,当条件满足后唤醒。(存在问题:唤醒未即将睡眠的线程,可以设置标志位避免入睡)
- 信号量:用一个整型变鱼来累计唤醒次数,一个信号盖的取值可以为0 (表示没有保存下来的唤醒操作)或者为正值(表示有一个或多个唤醒操作)。
- 互斥量:互斥量是没有计数能力的信号量,可以处于两态:解锁和加锁。
- 管程:一个管程是一个由过程、变量及数据结构等组成的一个集合,它们组成一个特殊的摸块或软件包。进程可在任何摇要的时候调用管程中的过程,但它们不能在管程之外声明的过程中直接访问管程内的数据结构,任一时刻管程中只能有一 个活跃进程,
常见的进程同步方式还有:
- 消息传递:使用send和receive在进程之间传递消息。
- 屏障:除非所有的进程都就绪准备符手下一个阶段,否则任何进程都不能进入下一个阶段。当一个进程到达屏陓时.它就被屏陓阻拦,直到所有进程都到达该屏伴为止。
调度
按照是否能够抢占,调度算法可以分为:
- 非抢占式调度算法挑选一个进程,然后让该进程运行直至被阻塞(阻塞在 I/O上或等待另一个进程),或者直到该进程自动释放CPU。
- 抢占调度算法挑选一个进程,并且让该进程运行某个固定时段的最大值。
不同类型的操作系统有不同的调度目标和算法,对于所有的系统,调度算法应该做到公平、策略强割执行和平衡。
- 批处理系统:吞吐呈、周转时间、CPU利用率
- 先来先服务:进程按照它们悄求CPU的顺序使用CPU。
- 最短作业优先
- 最短剩余时间优先:调度程序总是选择剩余运行时间最短的那个进程运行。如果新的进程比当前运行进程蒂要更少的时间,当前进程就被挂起,而运行新的进程。
- 交互式系统:响应时间、均衡性
- 轮转调度: 每个进程袚分配一个时间段。
- 优先级调度:每个进程被予一个优先级,允许优先级最高的可运行进程先运行。
- 最短进程优先:首先运行最短的作业来使响应时间最短。
- 保证调度:向用户作出明确的性能保证,然后去实现它。例如:若用户工作时有n个用户登录,则用户将获得CPU处理能力的1/n。
- 彩票调度:向进程提供各种系统资源(如CPU时间)的彩哀.一旦要做出一项调度决策时,就随机抽出 一张彩哀,拥有该彩票的进程获得该资探。
- 公平分享调度:无论一个用户有多少进程存在,每个用户都会得到应有的CPU份额。
第3章:存储管理
地址空间
- 空闲内存管理主要有以下两种:
- 使用位图的存储管理:使用位图方法时,内存可能被划分成小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位,0表示空闲,1表示占用。
- 使用链表的存储管理:维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程,或者是两个进程间的一个空的空闲区。寻找一个空闲区域的策略有以下几种:
- 首次适配:存储管理器沿着段链表进行搜索,直到找到一个足够大的空闲区;
- 下次适配:每次找到合适的空闲区时都记录当时的位置。以便在下次寻找空闲区时从上次结束的地方开始搜索;
- 最佳适配:找出能够容纳进程的最小的空闲区;
- 最差适配:总是分配最大的可用空闲区;
- 快速适配:为那些常用大小的空闲区维护单独的链表。
虚拟内存
虚拟地址到物理地址的映射通过页表来实现。
虚拟地址被分成虚拟页号(高位部分)和偏移量(低位部分)两部分。虚拟页号可用做贞表的索引 ,以找到该虚拟页面对应的页表项.由页表项可以找到页框号(如果有的话)。然后把页框号拼接到偏移量的高位端,以替换掉虚拟页号,形成送往内存的物理地址。
一个典型的页表项包含:高速缓存禁止位、访问位、修改位、保护位、“在/不在”位和页框号。
为了加速页表访问,转换检剥缓冲区(TLB)被用来缓存页面项。
处理大页表有两种思路:
- 多级页面,其中页面目录包含了指向页表节点的指针。
- 倒排页表:内存中每一个页框有一个表项,而不是每一个虚拟页面有一个表项。
页替换算法
- 最优页面置换算法(无法实现):把因需要调人这个被替换页面而发生的缺页中断推迟到将来,越久越好。
- 最近未使用页面置换算法:将页面分为四类:第0类(没有被访间,没有被修改)、第1类(没有袚访问,已被修改)、第2类(已被访问,没有披修改)、第3类(已被访问,已被修改),算法随机地从类编号最小的非空类中挑选一个页面淘汰之。
- 先进先出页面置换算法:当发生缺页中断时,淘汰表头的页面井把新调人 的页面加到表尾。
- 第二次机会页面置换算法:先进先出会淘汰有用的旧页面,可以稍作修改。如果R位是0, 那么可以立刻置换。如果是1,就将R位消0,井把该页面放到链表的尾端。
- 时钟页面置换算法:和第二次机会页面置换算法相同,知识将链表用类似时钟的结构替代。
- 最近最少使用页面置换算法:置换未使用时间最长的页面。
- 工作集页面置换算法:跟踪进程的工作集,以确保任让进程运行以前,它的工作集就已在内存中。
- 工作集时钟页面置换算法:时钟页面置换算法的升级版,需要在选择替换的时候考虑页面是否存在于工作集中。
第4章:文件系统
文件系统实现
文件的组织方式主要有以下几种
- 连续分配:把每个文件作为一连串连续数据块存储在磁盘上。(然而可能找不到合适的连续空间);
- 链表分配: 为每个文件构造磁盘块链表(然而随机读取会很慢);
- 在内存中采用表的链表分配:取出每个磁盘块的指针字,把它放在内存的一个表中以加快访问。
- i节点:数据结构列出了文件属性和文件块的磁盘地址。
UNIX系统就是采用i节点组织文件,为了支持超大文件,还引入了一级、二级、三级间接块。