量子波动速度《现代操作系统》(上)

727 阅读8分钟

本文是《现代操作系统》一书的阅读笔记,主要记录俺觉得重要的知识。

第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节点组织文件,为了支持超大文件,还引入了一级、二级、三级间接块。