《现代操作系统》17年第四版 阅读笔记

Tags:

系统调用

fork

创建一个原有进程的精确副本。

被复制的东西:

  • 所有的文件描述符
  • 所有的寄存器

没被复制的东西:

  • 程序正文

在fork后,原有的进程和其副本(父与子)就分开了。

返回值,用来在进程里区分谁是父谁是子:

  • 在子进程中该值为0
  • 在父进程中等于子进程的PID

shell为例:

while(true) {
    type_prompt();
    read_command(cmd, params);
    if(fork()!=0) {
        // 父
        waitpid(-1, &status, 0);
    } else {
        // 子
        execve(command, params, 0);
    }
}

waitpid

参数:

  • 子进程PID,填-1就是任意一个子进程PID
  • status(statloc)子进程的返回状态码
  • 一般为0

exec

使得整个核心映像(core image)被一个文件所替代。

参数:将要执行的文件名、一个指向变量数组的指针、一个指向环境数组的指针(通常为0)

例子:

cp file1 file2

execve(cp, [file1, file2], 0)

main(argc, argv, envp)

argc为3,argv[0]为cp,argv[1]为file1,argv[2]为file2;没有envp。

exit(status)

status是用户指定的,status其实就是waitpid的staloc,子进程设定的status最终可以告诉父进程。

link

在unix中,每个文件都有唯一的编号(i-node)。

每个目录有一个i-node到文件名的表。

link时,是在指向目录里面创建一个新条目,i-node为原文件的i-node,文件名都link参数里指定的文件名。

目录和i-node是双向指向的,i-node也存有一个表,记录了指向该i-node的目录项。

进程和线程

进程模型

CPU利用率

  • t1, 一个进程等待I/O操作的时间
  • t, 一个进程停留在内存中时间
  • p, 一个进程等待I/O操作的时间与其停留在内存中时间的比。
  • n为同时存在的进程数量

利用率 = \( 1 - p^{n}\)

这是简单模型,只适用于进程之间互相独立。例如对于单CPU,即使进程就绪,但已有一个进程正在被CPU处理,那么还是会等待。

用户空间线程

优缺点:

内核空间线程

调度程序激活机制 和 上行调用(upcall)

IPC:信号量

  • 创建信号量:sem_t *sem_open(const char *name, int oflag, 权限, 初始值)。返回值:返回一个信号量对象,若失败,则返回SEM_FAILED,并设置errno。man page
  • P(down)操作,即int sem_wait(sem_t *sem),检查信号量的值是不是大于0,若大于0,则减1并返回;若等于0,则进程睡眠,sem_wait阻塞不返回;非阻塞版本是sem_trywait,用返回值EAGAIN代替阻塞;限时的down操作是sem_timedwait,使得阻塞不是永久的。返回值:0代表成功,-1代表失败,并设置errno。
  • V(up)操作,即int sem_post(sem_t *sem),对信号量加1,若是从0变1,那么那些阻塞在这个信号量的进程或线程会被唤醒。返回值同P。V操作是怎么都不会阻塞的。
  • 本进程关闭信号量:int sem_close(sem_t *sem)。没什么特别的。
  • 真·销毁信号量:sem_unlink,前提是open了信号量的进程已经调用了close或者已经结束了进程(调用了exit或者main函数返回),如果还没close就调用,那么没效果。

github代码实例,双信号量实现父进程和子进程的同步。

信号量2个能力:

  • 实现互斥量
  • 实现计数

IPC:futex 快速用户空间互斥

  • linux特有
  • 实现了基本的锁(很像互斥锁),但避免了陷入内核
  • 内核服务:提供一个等待队列,它允许多个进程在一个锁上等待。把进程放到等待队列代价很大(系统调用)。
  • 避免锁争用:没有争用时,futex完全在用户空间工作;加锁时,如果锁没有被锁,那么直接加锁成功,不需要陷入内核;如果已经被锁了,执行系统调用把线程放到等待队列(不自旋)。

IPC:管程 montior

原因:为了更易于编写正确的程序。

  • 管程是编程语言的组成部分,能不能用管程得看是什么语言,例如java
  • 任一时刻管程中只能有一个活跃进程
  • 进程可在任何需要的时候调用管程中的过程(procdeure)
  • 进入管程是的互斥由编译器负责,出错的可能性要小得多
  • 写管程的人无需关心编译器是如何实现互斥的,只需知道将所有临界区转换成管程即可

IPC:消息传递

其实就是用socket来实现IPC。

IPC:屏障 barrier

概念上像是gpu渲染一帧,n个gpu核都在计算它负责的像素点,有的快有的慢,但必须全部核的任务都处理完毕,才能进入下一个阶段。

IPC:无锁化,RCU(读取-复制-更新)

调度

何时进行调度

  1. 创建一个新进程后,需要决定是运行父进程还是运行子进程。可以任意决定。
  2. 一个进程退出时必须做出调度决策。必须从就绪进程集合选择另外某个进程。
  3. 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞是,必须选择其他进程运行。阻塞原因会成为选择的因素,然而调度程序并不拥有做出这种相关考虑的必要信息
  4. 在一个I/O中断发生时,必须做出调度决策。可能等待I/O的进程变成就绪了,有三种可能,让新就绪进程运行;继续当前进程的运行;让别的进程运行。

根据如何处理时钟中断,可以把调度算法分2类:

  • 非抢占式:进程自己释放CPU时/阻塞时,才会切换到别的进程。即时钟中断不会进行调度。
  • 抢占式:让进程运行某个固定时段的最大值,然后挂起它,调度别的进程继续运行。前提是有时钟,不然就得用非抢占式的调度算法。

根据环境选择算法:

  • 批处理。适合用非抢占式调度。一个进程需要运行长时间。也就减少了进程切换,优化了性能。
  • 交互式。适合抢占式。
  • 服务器。适合抢占式。
  • 实时系统。一般是非抢占式。

调度算法目标

适用所有环境的目标:

  • 公平
  • 策略强制执行。即调度进程有一些优先级策略
  • 平衡。保证系统的所有部分都忙碌

批处理系统的测量指标:

  • 吞吐量:每小时完成的作业数量
  • 周转时间:一个作业从提交到完成的统计平均时间

能够使吞吐量最大化的调度算法不一定就有最小的周转时间。例如,系统优先处理大量小作业导致长作业无法被处理,这样有做大的吞吐量但平均周转时间无限长。

交互式系统:

  • 最小响应时间。能够让所有的交互式请求首先运行的则是好服务。
  • 均衡性。满足用户的期望(这个概念比较模糊)

交互式系统的调度

轮转调度(round robin)

  • 每个进程被分配一个时间片(quantum)。注意,进程可在时间片花完前提前结束运行,例如阻塞了。
  • 时间片过小,容易发生抢占,过多的切换进程,降低CPU效率;
  • 时间片太长,则引起对短的交互请求的响应时间变长。
  • 一般为20~50ms

优先级调度

每个进程加一个优先级属性,优先级大的先执行完,再执行次优先的。

问题:只按优先级来执行进程的话,低优先级进程可能永远都不会被执行。

解决方法:

  • 被执行的进程的优先级每个时钟滴答减1,直到低于次优先级进程时切换。
  • 最大时间片法,用完时间片就轮到次优先的进程

优先级的赋予:

  • 静态:人工分配,例如商业计算中心,高优先级的任务价格高
  • 动态:根据 1/f公式分配优先级。例如在50ms的时间片中只使用2ms就挂起的进程,优先级为1/(2/50) = 25。

变种:按优先级分类,然后用轮转调度,高优先级的进程组里的进程集合轮转调度,优先执行,都执行完时切换到次优先级组。

多级队列

基于上面的优先级分类,设计了多级队列调度。

原理是:属于最高优先级类的进程运行一个时间片,属于次高优先级类的进程运行2个时间片,再次一级运行4个时间片;当进程用完分配的时间片后,它被移送到下一类。

例子:假设一个进程要完成计算任务总共需要100个时间片。一开始被分配1个时间片,然后就被换出,下次到它时获得2个时间片,又被换出。总共经历了1、2、4、8、16、32、64个优先级类。在64优先级类的第37个时间片就完成了工作。总共用了7次进程上下文切换。要比轮转算法轮转100次要高效。

最短进程优先

最短路程含义是进入运行到挂起的时间间隔最短,这种进程优先处理,对实时系统挺友好。例如交互式进程,每条用户命令相当于一次短作业。

但如何知道这个作业将执行多久呢?方法是用过去的数据来做预测,\( T = aT_{0} + (1 - a)T_{1} \)。

保证调度

也是绝对公平的调度。有两种情况:

  • 多用户同时登录工作。每个用户可获得CPU的1/n的处理能力。
  • n个进程在运行的单用户系统。每个进程获得CPU的1/n的处理能力。不过这种情况需要记录每个进程从创建以来已累积获得的CPU时间。因为没有时间片的概念,所以进程实际获得的运行时间和理应获得的时间可能会不一致,此时可以算一个比值(优先级),使得较亏的进程可以先运行。

彩票调度

即给每个进程发一些彩票。调度时,随机抽一张彩票,哪个进程持有这张彩票就被执行。

可以给某个进程赋予比别人多的彩票数量,来提高优先级(中奖几率)。

公平分享调度

这个是对于多用户环境而言的。每个用户的所有进程占x%的时间。有点像上面的保证调度。

调度策略参数化

例如一个数据库父进程下面有多个子进程,父进程才知道怎么调度子进程才是最优。那么就可以设计一种参数化调度机制,让父进程向内核设置参数,如子进程优先级,更好地做调度。

线程调度

要分用户级线程和内核级线程两种情况。

经典IPC问题

页面置换算法

最优页面置换算法

基于2点:

  • 当缺页中断(page fault)发生时,有些页面在内存中,其中有一个页面(包含紧接着的下一条指令的那个页面)将很快被访问,其他页面则可能要10、100、1000条指令后才会访问,这个指令数就是标记
  • 最优页面置换,就是置换掉标记最大的页面

然而无法实现,因为操作系统无法知道各个页面下一次将在什么时候被访问。

不过可以作为性能对比工具,例如弄个仿真程序,先跟踪一遍所有页面的访问情况,然后第二次运行则可以用第一次的数据来跑出最优页面置换算法。之后再用其他算法也跑一下,从而做对比。不过此方案问题在于是针对某个特定程序而言的。

最近未使用页面置换算法(NRU,not recently used)

首先每个页面设置2个状态位:

  • R位,被访问时设置
  • W位,被写入时设置

算法:

当启动一个进程时,它的所有页面的两个位都由操作系统设置成0,R位被定期地清零(比如每次时钟中断时)以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时,操作系统检查所有的页面并根据它们当前的R位和M位的值,把它们分为4类:

  1. 没有被访问,没有被修改
  2. 没有被访问,被修改
  3. 被访问,没有被修改
  4. 被访问,被修改

本算法随机地从类编号最小的非空类中挑选一个页面淘汰。

先进先出置换算法 FIFO

页面按照访问时间顺序组成链表,每次发生缺页中断时直接从表头的页面干掉,并把新页面放到表尾。

问题在于常用页面也可能会被淘汰,

第二次机会页面置换算法

这个是 FIFO的改进:要淘汰时,检查最老页面的R位,如果是0,那么可以置换掉;如果是1,那么就是最近访问过的,把R位设0,并移动到链表末端。

如果所有页面都被访问过了,那么退化为普通的FIFO。

时钟页面置换算法

上面的算法的问题在于要经常在链表移动页面。改进方法:改成环形链表,一个指针指向最老的页面。

当发生缺页中断时:

  • 检查指针指向的页面,若R位为0,则淘汰该页面,把新页面放入这个位置,指针移动到下一个位置;
  • 若R为1,则清除R位,指针还是++,重复这个过程直到找到一个R为0的页面。

最近最少使用算法(LRU)

在缺页中断发生时,置换未使用时间最长的页面。

假设还是用链表,要达到LRU,需要每次访问内存都更新链表:在链表中找到这个页面,删除它,然后把它移动到表头。

不用链表,有别的方案:

每个页表存一个属性:指令计数器,每条指令执行完后加1;当发生缺页中断时,检查所有页表项的计数器值,找到值最小的页面,就是最近最少使用的页面了。这是基于硬件的方案。

软件实现的LRU

NFU(Not Frequently Used,最不常用)算法:

内存里做一个表,把每个页面和一个软件计数器相关联,初值为0,每次时钟中断时,操作系统扫描内存中所有的页面,把每个页面的R位的值加到计数器上,这个计数器大体跟踪了各个页面被访问的频繁程度。发生缺页中断时,淘汰计数器值最小的页面。

改进的NFU——Aging老化算法:

因为NFU对旧状态记忆得太深,不能应对快速变化的程序状态,有可能根据计数器淘汰了最经常访问的页面。可以修改一下:

  • 在R位被加进计数器前,计数器右移一位(除2);
  • 将R位加到计数器最左端的位而不是最右端的位;

发生缺页中断还是淘汰计数器值最小的页面。老化算法的问题在于计数器只有有限位,限制了它对过往状态的记忆能力。

基本工作集页面置换算法

  • 工作集:一个进程当前正在使用的页面的集合称为它的工作集。
  • 颠簸:如果内存太小不足以容纳整个工作集,那么每执行几条指令就会发生一次缺页中断
  • 预先调页:在进程运行前预先装入其工作集页面

工作集的严格定义:在任一时刻t,都存在一个集合,它包含所有最近k次内存访问所访问过的页面,称为w(k,t)

w是k的单调非递减函数,且会收敛到一个稳定的范围。预先调页原理就是基于以下推测:程序上次结束时w有一个稳定范围,可预先装下这个范围的工作集。

实现条件:操作系统必须跟踪哪些页面在工作集中。

基于工作集的页面置换算法:当发生缺页中断时,淘汰一个不在工作集的页面。精确地统计工作集,就是确定一个k值。

问题:工作集的计算不容易。2种方案:

  • 按使用频率计。成本比较高。k还是按次数的k。
  • 按执行时间计。k变成秒数r,工作集变成在过去的r秒实际运行时间(使用了CPU的时间)中进程所访问页面的集合。

缺页中断时,需要扫描整个页表,找出适合的页面来淘汰。

工作集时钟页面置换算法

上面的算法问题在于需要扫描整个页表来淘汰页面。

改进(类似前面的时钟页面置换算法):

建立一个以页框为元素的循环表。每次缺页中断时,首先检查指针指向的页面,如果R为1,则把R改为0,并把指针++,重复这个逻辑;R为0时,如果指针当前页面的生存时间大于r,并且页面是干净的(M=0),它就不在工作集中且磁盘上有一个有效的副本,置换替换掉此页框即可,如果M为1,为了避免写磁盘操作引起进程切换,指针继续++,检查下一个页。

总结

最好的算法是:

  • 老化算法(LRU)
  • 工作集时钟算法

分页系统的设计问题

进程之间的内存竞争

考虑多个进程的页面置换算法称为全局算法,反之就是局部算法。

全局算法一般是基于PFF,page fault frequency,缺页中断率,它指出了何时增加或减少分配给一个进程的页面,但却完全没有说明在发生缺页中断时应该替换掉哪一个页面。仅控制分配集的大小。

PFF的测量:PFFF = (当前1秒的PFF + 旧PFF)/ 2

负载控制

问题:即使是使用最优页面置换算法,也可能会发生颠簸,如内存不足的时候。

解决方案:将一部分进程交换到磁盘,释放他们所占有的所有页面。

页面大小

有公式可以算页面大小,对于平均进程大小为1MB,每个页表项为8B的系统,最优页面是4KB。一般范围是到64KB。

分离指令空间和数据空间

地址空间太小时,拆成2个空间就会改善情况。不过现在64位系统的地址空间很大,拆2个空间是因为别的原因了。

共享页面&共享库&内存映射文件

原因:避免在内存中有一个页面的两个副本。

策略:共享I空间。

还有问题:释放页面要考虑有没别的进程在使用这个页面。所以共享页面要有特殊的数据结构来记录。

其他问题:fork调用,理应拷贝数据段,但就会产生大量副本。解决方法是写时复制COW。

共享库就是DLL了,不过有个问题是地址。共享库要用相对地址,办法是编译时设置参数。

内存映射文件,应该就是共享内存了。

清除策略

弄个分页守护进程(paging daemon),定时被唤醒检查内存、看是不是要置换掉页面,如果已修改,那么要写硬盘,如果未修改且硬盘有副本,则直接清除。

有关实现

缺页中断处理流程

  1. 硬件陷入内核,在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
  2. 启动一个汇编代码例程保存通用寄存器和其他易失的信息,以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
  3. 当操作系统发现一个缺页中断时,尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息,如果没有的话,操作系统必须检索程序计数器,取出这条指令,用软件分析这条指令,看看它在缺页中断时正在做什么。
  4. 一旦知道了发生缺页中断的虚拟地址,操作系统检査这个地址是否有效,并检査存取与保护是否一致。如果不一致,向进程发出一个信号或杀掉该进程(segment fault!)。如果地址有效且没有保护错误发生,系统则检査是否有空闲页框。如果没有空闲页框,执行页面置换算法寻找一个页面来淘汰。
  5. 如果选择的页框“脏”了,安排该页写回磁盘,并发生一次上下文切换,挂起产生缺页中断的进程,让其他进程运行直至磁盘传输结束。无论如何,该页框被标记为忙,以免因为其他原因而被其他进程占用
  6. —旦页框“干净”后(无论是立刻还是在写回磁盘后),操作系统査找所需页面在磁盘上的地址,通过磁盘播作将其装入,该页面正在被装入时,产生缺页中断的进程仍然被挂起,并且如果有其他可运行的用户进程,则选择另一个用户进程运行„
  7. 磁盘中断发生时,表明该页已经被装人,页表已经更新并可以反映它的位置,页框也被标记为正常状态。
  8. 恢复发生缺页中断指令以前的状态,程序计数器重新指向这条指令。
  9. 调度引发缺页中断的进程,操作系统返回调用它的汇编语言例程。
  10. 该例程恢复寄存器和其他状态信息,返回到用户空间继续执行,就好像缺页中断没有发生过一样。

指令备份

即怎么记忆发生中断的指令位置,以及怎么恢复。方法是在执行一条指令前用一个寄存器备份这条指令。

锁页面

例如缺页中断时把别的进程的缓冲区的页面置换掉了,别的进程如果用DMA传输数据中,就会覆盖掉了刚被装入的页面,全乱了。解决方法是对页面加锁。

后备存储

即置换页面,把页面放到硬盘哪里的问题。

方法:设立一个交换分区,专门来做这个事情。具体而言要3个区:正文、堆栈、数据。

分段

现在x86-64都去掉分段机制了,目测没有学习的必要。

文件系统

  • 主引导记录:磁盘的0号扇区(Master Bot Record, MBR),用来引导计算机
  • 分区表:在MBR的末尾,给出了每个分区的起始和结束地址
  • 活动分区:分区表的某一个分区被定为活动分区

启动流程:

  1. 计算机被引导
  2. BIOS读入并执行MBR
  3. MBR确定活动分区
  4. MBR读入活动分区的第一个块(引导块)
  5. 引导块中的程序将装在该分区中的操作系统

Note:为统一起见,每个分区都从一个引导块开始,即使它不含有一个可启动的操作系统

文件的实现

  • 连续分配。读取速度快,但容易产生碎片。存储时就需要知道文件大小。
  • 链表分配。随机读取速度慢。指针占用一些字节,导致一些效率问题。
  • 文件分配表FAT。在内存中弄一张表,用来获取磁盘块链表信息,从而避免了在磁盘块头存节点信息。随机读取速度变快。问题是如果块大小才1KB,但是磁盘空间1T,内存分配表就需要10亿个项,假设每项3个字节,就需要3GB内存。
  • i节点。是对FAT的改进,把链表信息存到磁盘上形成一个i节点文件,打开某个文件时把i节点文件信息载入到内存。i节点的唯一问题是定长大小的话,怎么动态扩容。

目录的实现

目录系统主要功能:把文件名映射成定位文件数据所需的信息

  • 目录:一堆目录项,kv对
  • 目录项:k是文件名,v可以随意,一般是i节点号

问题:文件名不定长。定长的话容易浪费空间。

解决方案:

  1. 让目录项大小不一致。问题一是如果移走一个文件会导致出现大小不定的空隙,二是目录项可能会跨页面,在读取文件名时可能会发生缺页中断。
  2. 目录项大小一致,但把文件名移出目录项,放到目录最后的堆里。但就要对堆进行管理。

共享文件

  • 硬链接:创建直接与目标文件关联的i节点。删除文件操作会变得复杂。
  • 符号链接:创建一个符号文件(类型link),文件中只包含所链接的文件的路径。删除文件没什么大问题。额外开销时是要通过路径找到目标文件的i节点,以及符号文件本身还是要有一个i节点和一个磁盘块放路径,毕竟还是个文件。

文件系统

mmap

https://blog.csdn.net/hj605635529/article/details/73163513

https://blog.csdn.net/luckywang1103/article/details/50619251

(未经授权禁止转载)
Written on July 10, 2018

博主将十分感谢对本文章的任意金额的打赏^_^