操作系统导论 订阅
《操作系统导论》是2019年8月人民邮电出版社出版的图书,作者是[美]雷姆兹·H·阿帕希杜塞尔、[美]安德莉亚·C·阿帕希杜塞尔。 展开全文
《操作系统导论》是2019年8月人民邮电出版社出版的图书,作者是[美]雷姆兹·H·阿帕希杜塞尔、[美]安德莉亚·C·阿帕希杜塞尔。
信息
页    数
482页
作    者
[美]雷姆兹·H·阿帕希杜塞尔、[美]安德莉亚·C·阿帕希杜塞尔
定    价
99元
装    帧
平装
书    名
操作系统导论
出版时间
2019年8月
开    本
16开
出版社
人民邮电出版社
ISBN
9787115508232
操作系统导论内容简介
这是一本关于现代操作系统的书。全书围绕虚拟化、并发和持久性这3个主要概念展开,介绍了所有现代系统的主要组件(包括调度、虚拟内存管理、磁盘和I/O子系统、文件系统 )。本书共50章,分为3个部分,分别讲述虚拟化、并发和持久性的相关内容。本书大部分章节均先提出特定的问题,然后通过书中介绍的技术、算法和思想来解决这些问题。笔者以对话形式引入所介绍的主题概念,行文诙谐幽默却又鞭辟入里,力求帮助读者理解操作系统中虚拟化、并发和持久性的原理。本书内容全面,并给出了真实可运行的代码(而非伪代码),还提供了相应的练习,适合高等院校相关专业教师教学和高校学生自学。 [1] 
收起全文
精华内容
下载资源
问答
  • 操作系统导论
    2021-11-26 08:28:31

    第八章 多级反馈队列

    多级反馈队列(MLFQ)

    • 规则一:如果A的优先级>B的优先级,运行A(不运行B)。

    • 规则二:如果A的优先级=B的优先级轮转运行A和B。

    • 规则三:工作进入系统时,放在最高优先级(最上层队列)

    • 规则四:一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次CPU),就降低其优先级(移入低一级队列)。

    • 规则五:经过一段时间S,就将系统中所有工作重新加入最高优先级队列。

    更多相关内容
  • 操作系统导论课后作业代码
  • 50823操作系统导论.rar

    2020-11-19 18:43:37
    老师那里要过来的,操作系统导论ppt,方便期末考试复习,以及平时读书的时候翻阅,还有一些老外整理的笔记。
  • 操作系统导论》英文版,PDF格式,带书中的源代码 出版时间:2019年6月1日 雷姆兹·H.阿帕希杜塞尔(,Remzi,H.,Arpaci-Dusseau),[美] 安德莉亚·C.阿帕希杜塞尔(Andrea ... 著)
  • 操作系统导论.zip

    2020-09-04 00:47:01
    操作系统的基本概念,何一个计算机系统都是由两部分组成:计算机硬件和计算机软件。计算机硬件通常是由中央处理机(运算器和控制器)、存储器、输入设备和输出设备等部件组成。 计算机软件包括系统软件和应用软件。...
  • 这是一本关于现代操作系统的书。全书围绕虚拟化、并发和持久性这3个主要概念展开,介绍了所有现代系统的主要组件(包括调度、虚拟内存管理、磁盘和I/O子系统、文件系统 )。
  • 仓库非标准答案,只是作者在阅读操作系统导论时的解答,以及对部分README的翻译 本人翻译水平有限,见谅。欢迎指出错误 部分章节课后习题的英文翻译书上是没有的,但在原版上存在: 英文原版: : 书籍翻译: : ...
  • 操作系统导论(Operating Systems: Three Easy Pieces)中文版(部分),可以先简单了解下本书,读完一定让你决定买本书好好看!
  • Operating Systems - Three Easy Pieces. v1.0 操作系统导论英文版 这是一本开源书籍:http://pages.cs.wisc.edu/~remzi/OSTEP/#book-chapters 这里是pdf合集
  • UNIT1操作系统导论讲义课程.
  • 书评《操作系统导论》 OSTEP Operating Systems: Three Easy Pieces 在操作系统的书籍中,最出名的应该就是《操作系统设计与实现》和他的修订版《现代操作系统》了。作者作为MINIX操作系统的创始人,连Linux都是...

    书评《操作系统导论》 OSTEP  Operating Systems: Three Easy Pieces

     

    在操作系统的书籍中,最出名的应该就是《操作系统设计与实现》和他的修订版《现代操作系统》了。作者作为MINIX操作系统的创始人,连Linux都是收到它的启发而开发的。但是两年前,我读这本《现代操作系统》的时候,却发现读不下去。

    原因在于书中出现的概念太多,讲的又太含糊(翻译的不好),以至于我读过之后只有一个模糊的印象,无法在脑子里把知识串联起来。后来在网上看了一些书评才发现,看操作系统这本书,是需要学习很多前置课程的。

     

    看操作系统一般需要的前置课程如下:

    C语言,Linux/Unix,汇编语言,计算机组成原理(学组原还要会数字电路)等等。

    当时汇编我一点都不懂,Linux/Unix也不会(只会用GUI肯定不算),组成原理也只是了解一点。这时候看操作系统,肯定是一头雾水。于是当时我只是草草读了一遍《现代操作系统》,便放弃了。

     

    两年后,对于上面的前置课程,我也仅仅是多学了Linux。不是我懒,而是我的工作内容和这些底层的汇编,组成原理没啥关系(我现在做Web前端呀)。这时候,我再想读一本介绍操作系统原理有关的书籍,应该选哪本?

    我对市面上流行的操作系统书籍做了调查之后,最后选了这本:《操作系统导论》。这本书应该是最适合基础差的同学的操作系统书籍了。

    读这本书所需要的前置课程:C语言,Linux/Unix,少量计算机组成原理知识。

    这几个条件,我刚好符合。于是我就选了这本书。当然,如果你会的知识更多,比如汇编语言也会,那么读这本书肯定更轻松。但是——如果你会这么多,我就推荐你读更经典,难度也更高的操作系统书籍了。

     

    这本书的不仅对阅读容易,对新人友好,还有更大的特色就是——习题非常棒!

    像其它大部分操作系统书籍,一般都没有习题或者不重视习题。而这本书习题占据了很重要的部分。习题不仅有C语言编程,还有模拟作业。这个模拟作业对于理解操作系统概念非常棒。以往都是干巴巴的看书,书中的概念只是有个印象,你不知道这个概念这个算法实际在系统中运行是什么样子,有什么效果。但是有了这个模拟作业,你可以自己设定参数,设定任务,观察系统的反应。虽然仅仅是个模拟,但是也起到了实践的效果,比单纯看书好多了。

    书的最后部分也提供了一些系统项目和xv6项目,如果想要对操作系统加深了解,可以试着做一下。大部分项目看起来是有点复杂的。

     

    这本书的讲述相对比较“幽默”,还有困在书中的教授和学生作为旁白。对于知识屏蔽做的比其他操作系统书籍要好,不一下子给读者大批的概念让读者无所适从,也不会假设读者具有一切基础知识。

    但是相对的,这本书讲的内容太少。虽然是一本接近于500页的书籍,但相比于其它操作系统书籍,能了解到的知识少了一些。这也是由于这本书更基础导致的。

    另外,这本书的英文版是开源的,作者提供了PDF可以免费下载。附带还有作业程序。与英文开源版本相比,中文版在第二第三部分少了很多很多作业题目。

     

    展开全文
  • 前言 我看的是这本,豆瓣9.4,很经典的教材书,在文章末尾我附上了网盘链接 这篇博客算是一个完整的... 也就是说,操作系统将物理(physical)资源(如处理器、内存或磁盘)转换为更通用、更强大且更易于使用的虚拟形式。

    前言

    我看的是这本,豆瓣9.4,很经典的教材书,在文章末尾我附上了网盘链接
    这篇博客算是一个完整的读书笔记,我大概读了20天看完的,电子版做笔记很方便,推荐一波,很多课上没有讲到的知识在这本书里都详细阐释了

    全书的思维导图
    在这里插入图片描述

    操作系统介绍

    一个正在运行的程序会做:取址执行。从内存中获取指令,对其解码,执行。

    操作系统主要利用一种通用的技术,我们称之为虚拟化(virtualization)。 也就是说,操作系统将物理(physical)资源(如处理器、内存或磁盘)转换为更通用、更强大且更易于使用的虚拟形式。

    操作系统取得CPU,内存和磁盘等物理资源,并对它们进行虚拟化;处理与并发相关的麻烦事;持久化地存储文件,使文件长期安全。

    虚拟化

    4.抽象 进程

    进程可以被简单地视为正在运行的程序。

    进程的创建首先将代码和静态数据加载到内存中,创建和初始化栈,执行I/O设置相关的其他工作,操作系统就为程序的执行搭建好了舞台,最后需要启动程序。

    一般来说进程可以在三个状态:运行,就绪,阻塞。

    存储关于进程的信息的个体结构称为进程控制块(Process Control Block,PCB),这是谈论包含每个进程信息的 C 结构的一种方式。

    5.插叙:进程API

    进程描述符(process identifier,PID)

    1. fork() 系统调用fork()用于创建新进程
    2. wait() 调用wait()延迟自己的进程进行
    3. exec() 给定可执行程序的名称(如 wc)及 需要的参数(如 p3.c)后,exec()会从可执行程序中加载代码和静态数据,并用它覆写自己的代码段(以及静态数据),堆、栈及其他内存空间也会被重新初始化。这个命令并没有创建新进程,而是直接将当前的程序替换为不同的运行程序

    6.机制:受限直接执行

    关键问题:操作系统如何高效可控地虚拟化CPU

    通过受限的直接执行可以让程序运行地尽可能快,直接在CPU上运行程序即可。当 OS 希望启动程序运行时,它会在进程列表中为其创建一个进程条目,为其分配一些内存,将程序代码(从磁盘)加载到内存中,找到入口点(main()函数或类似的),跳转到那里,并开始运行用户的代码。

    在这里插入图片描述

    为了安全高效地进行上述的步骤,我们需要解决

    1. 如果我们只运行一个程序,操作系统怎么能确保程序不做任何我们不希望它做的事,同时仍然高效地运行它?
    2. 当我们运行一个进程时,操作系统如何让它停下来并切换到另一个进程,从而实现虚拟化 CPU 所需的时分共享?

    第一个问题:

    我们引入用户模式和内核模式,可以实现权限的管理,为了让有些用户模式可以访问内核,引入trap指令,该指令同时跳入内核并将特权级别提升到内核模式。

    为了在操作系统发出从陷阱返回指令时能够正确返回,必须确保存储足够的调用者寄存器。

    内核在启动时会设置陷阱表,来实现一些前置的“规定”,例如在出错时调用什么代码?根据需要配置的是哪个硬件,哪个硬件可以访问哪个不能随意访问?

    在这里插入图片描述

    第二个问题:

    在进程中切换:一个进程在CPU中运行时,操作系统就没有运行,那么操作系统如何重新获得CPU控制权来实现进程间切换?两种方式:协作方式,非协作方式。

    1. 协作方式:有些文件会进行yield系统调用
    2. 非协作方式:使用时钟中断来让操作系统运行中断处理程序,操作系统会重新获得CPU控制权。在启动过程中,系统必须先开启启动时钟。

    为了保存切换时的前后两个程序的内容,操作系统会执行一些底层汇编代码,来保存通用寄存器、程序计数器,以及当前正在运行的进程的内核栈指针,然后恢复寄存器、程序计数器,并切换内核栈,供即将运行的进程使用。
    在这里插入图片描述

    在这个例子中,进程A正在运行,然后被中断时钟中断。硬件保存它的寄存器(在内核栈中),并进入内核(切换到内核模式)。在时钟中断处理程序中,操作系统决定从正在运行的进程 A 切换到进程 B。此时,它调用 switch()例程,该例程仔细保存当前寄存器的值(保存到 A 的进程结构),恢复寄存器进程 B(从它的进程结构),然后切换上下文(switch context),具体来说是通过改变栈指针来使用 B 的内核栈(而不是 A 的)。最后,操作系统从陷阱返回,恢复 B 的寄存器并开始运行它。

    7.进程调度:介绍

    我们使用公平,响应时间和周转时间来比较不同的调度策略。响应时间是指任务首次运行的时间-任务到达的时间。周转时间指进程的完成时间-进程的到达时间。

    基本的调度方法:

    先进先出(FIFO,FCFS)可能遇到先到的任务运行很久,平均周转时间过长

    最短任务优先(SJF,shortest job first)因为它是非抢占形式的,可能在运行一个很长时间的任务的时候到达运行时间短的任务,导致平均周转时间降低

    最短完成时间优先(STCF,shortest time-to-completion first)在SJF中引入抢占机制,更短运行时间的可以抢占资源

    轮转调度(RR,Round-Robin)在一个时间片内运行一个工作,然后在下一个时间片切换到队列中的下一个任务,反复执行,知道所有任务完成。响应时间很低,但是周转时间很高。

    8.调度:多级反馈队列

    多级反馈队列(MLFQ,multi-level feedback queue):关注进程的一贯表现,然后区别对待。

    • 规则 1:如果 A 的优先级 > B 的优先级,运行 A(不运行 B)。
    • 规则 2:如果A的优先级 = B的优先级,轮转运行A和B。
    • 规则 3:工作进入系统时,放在最高优先级(最上层队列)。
    • 规则 4:一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次 CPU),就降低其优先级(移入低一级队列)。
    • 规则 5:经过一段时间 S,就将系统中所有工作重新加入最高优先级队列。

    9.调度:比例份额

    彩票调度,步长调度;这两种方式都不能很好地适合 I/O;其中最难的票数分配问题并没有确定的解决方式

    彩票调度:彩票数(ticket)代表了进程(或用户或其他)占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比,就是它占有资源的份额。通过不断定时地(比如,每个时间片)抽取彩票,彩票调度从概率上(但不是确定的)获得这种份额比例。

    步长调度:步长调度也很简单。系统中的每个工作都有自己的步长,这个值与票数值成反比。在 上面的例子中,A、B、C 这 3 个工作的票数分别是 100、50 和 250,我们通过用一个大数分别除以他们的票数来获得每个进程的步长。每次进程运行后,我们会让它的计数器 [称为行程(pass)值] 增加它的步长,记录它的总体进展。

    10.多处理器调度(高级)

    13.抽象:地址空间

    一个进程的地址空间包含运行的程序的所有内存状态。例如:程序代码;当程序在运行的时候,利用栈(stack)来保存当前的函数调用信息,分配空间给局部变量,传递参数和函数返回值。堆(heap)用于管理动态分配的、用户管理的内存(调用new获得的内存,静态初始化变量)。

    虚拟内存系统负责为程序提供一 个巨大的、稀疏的、私有的地址空间的假象,其中保存了程序的所有指令和数据。操作系统在专门硬件的帮助下,通过每一个虚拟内存的索引,将其转换为物理地址,物理内存根据获得的物理地址但获取所需的信息。操作系统会同时对许多进程执行此操作,并且确保程序之间互相不会受到影响,也不会影响操作系统。

    14.插叙:内存操作API

    内存包括堆和栈两种形式,程序运行需要内存的分配和释放两个步骤,在哪一步出错都可能导致程序的崩溃。

    一般来说,系统中实际存在两级内存管理:

    第一级是由操作系统执行的内存管理,操作系统在进程运行时将内存交给进程,并在进程退出(或以其他方式结束)时将其回收。

    第二级管理在每个进程中,例如在调用 malloc()和 free()时,在堆内管理。 即使你没有调用 free()(并因此泄露了堆中的内存),操作系统也会在程序结束运行时,收回进程的所有内存(包括用于代码、栈,以及相关堆的内存页)。无论地址空间中堆的状态如何,操作系统都会在进程终止时收回所有这些页面,从而确保即使没有释放内存,也不会丢失内存。

    15.机制:地址转换

    在实现CPU虚拟化的时候,一般准则为受限直接访问(LDE)。LDE 背后的想法很简单:让程序运行的大部分指令直接访问硬件,只在一些关键点(如进程发起系统调用或发生时钟中断)由操作系统介入来确保“在正确时间, 正确的地点,做正确的事”。

    为了实现高效的虚拟化,操作系统应该尽量让程序自己运行, 同时通过在关键点的及时介入(interposing),来保持对硬件的控制。高效和控制是现代操作系统的两个主要目标。

    将虚拟地址转换为物理地址,这正是所谓的地址转换(address translation)技术。

    这种地址转换实现的方式是动态重定位,首先,CPU需要两个寄存器:基址寄存器,界限寄存器。

    基址寄存器通过记录基址,当程序计数器(例如128)被设置后,硬件获取这个地址后,就加上基址寄存器里的值(例如是32kb:32768),最终得到实际的物理地址32896。

    界限寄存器提供访问保护,当进程访问超过边界或者访问负的虚拟地址时,CPU就会触发异常。

    基址寄存器配合界限寄存器的硬件结构是芯片中的(每个CPU一对),我们将CPU负责地址转换的部分称为内存管理单元(MMU)

    除此之外,操作系统还需要记录哪些空闲内存没有使用,我们使用空闲列表(free list)来实现。

    操作系统在内核模式下可以通过特权指令修改这两个寄存器。操作系统和硬件进行配合,实现了简单的虚拟内存。

    操作系统介入的过程:

    1. 创建进程时,为进程的地址空间找到内存空间(利用空闲列表标记空闲或已经使用)
    2. 进程中之时,操作系统回收内存,更新空闲列表
    3. 切换进程时,操作系统保存当前两个寄存器的值(保存在进程控制块PCB中)
    4. 异常发生时,操作系统提供应急行动

    重定位会发生内存资源浪费的情况,因为被界限寄存器保护起来的内存无法被其他进程访问,如果这个进程使用的内存很少,资源就浪费了,所以要引入分段的概念。

    16.分段

    分段可以更高效的虚拟内存,避免了地址空间中的逻辑段之间的内存浪费,而且算法实现很容易,可以实现代码共享的功能。

    用15节里面的例子可能存在栈和堆之间的空间没有被使用却占用了大量内存的问题,将进程分为代码段,栈段,堆段,分别将之放到不同的物理内存上,,这样就避免了虚拟地址空间中未使用部分占用物理内存。

    进行分段之后,仍然需要确认当前的地址引用的是哪个段,可以使用显式方式,用虚拟地址的开头几位来表示不同的段,例如前两位00,01,10,11分别对应代码段,栈段,堆段;有时也用一位来判断(堆,栈当作一位)

    栈的处理方式特殊些,它的增长方式是反向的,段寄存器中有一个专门的字段记录是否反向增长。除此之外,各个段之间有时为了提高效率还要进行地址空间的共享,所以在段寄存器中又加入了保护信息,来判断代码段的权限。

    在这里插入图片描述

    加入保护信息后,界限寄存器功能需要升级,不仅需要检查虚拟地址是否越界,还需要检查特定访问是否允许。

    分段执行之后,在物理内存中会存在很多较小的未分配内容的空间,这样会造成很大的资源浪费,虽然可以使用紧凑物理内存,最接近匹配,最坏匹配,首次匹配等等方法缩小这种资源浪费,但是无法完全解决这个问题,所以要引入分片。

    17.空闲空间管理

    基本策略:

    1. 最优匹配:遍历整个空闲列表,找到最接近的空闲块
    2. 最差匹配:遍历后找到最大的空闲块
    3. 首次匹配:找到第一个足够大的块
    4. 下次匹配:首次匹配的策略下加入指针,指向上次查找结束的位置,为了将空闲空间的查找操作分散在整个地址空间

    离奇的策略:

    1. 分离空闲列表:将一部分内存拿出来专门满足某种大小的请求,碎片就不会再成为问题了。这种方法省去了列表查找过程,特定大小的内存分配和释放都很快

    2. 伙伴系统:将空闲空间递归的一分为二,知道刚好可以满足请求,这种方法优秀在内存释放时,直接向上合并就可以了。

    18. 分页:介绍

    将空间分割成固定长度的分片就是分页,相应地,我们把物理内存看成是定长槽块的阵列,叫作页帧(page frame)。

    页表是一种数据结构,用于将虚拟地址映射到物理地址上。VPN为虚拟页号,PFN为物理帧号。

    页表项中可能包含很多不同的位:例如有效位(标记当前物理内存是否可用),保护位(标记当前物理内存是否可读可写),存在位(当前页在物理存储器还是在磁盘),脏位,参考位等等。
    在这里插入图片描述

    页表会造成机器访问很慢(很多内存访问用来访问页表),内存浪费(内存大量存储页表)

    19. 分页:快速地址转换(TLB)

    对每次内存访问,硬件先检查 TLB,看看其中是否有期望的转换映射,如果有,就完成转换(很快),不用访问页表(其中有全部的转换映射)。

    TLB(地址转换旁路缓冲存储器)会将最近转换过的VPN记录在缓存中,由于软件存在两种局限性(时间局限性,空间局限性),所以软件大概率在一段时间内,访问相近的一段内存,所以TLB就可以大展身手了。然而缓存不能设计的太大,只有很小的TLB才可以实现快速的缓存。

    正在运行的进程生成虚拟内存引用(用于获取指令 或访问数据),在这种情况下,硬件将其转换为物理地址,再从内存中获取所需数据。

    硬件首先从虚拟地址获得 VPN,检查 TLB 是否匹配(TLB 命中),如果命中,则获得最终的物理地址并从内存中取回。这希望是常见情形,因为它很快(不需要额外的内存访问)。

    如果在 TLB 中找不到 VPN(即 TLB 未命中),则硬件在内存中查找页表(使用页表基址寄存器),并使用 VPN 查找该页的页表项(PTE)作为索引。如果页有效且存在于物理内存中,则硬件从 PTE 中获得 PFN,将其插入 TLB,并重试该指令,这次产生 TLB 命中。

    在上下文切换的时候,TLB还会遇到两个相同的虚拟地址对应不同的物理地址的情况,这时候不作区分就会乱套,TLB也不知道该怎么映射了。

    简单的解决方法是切换进程的时候,将之前TLB的内容清零,但是也会出现很多次未命中的问题。所以一些系统增加了硬件支持,加入ASID地址空间标识符来作区分。

    TLB满了之后会需要替换策略,可以使用简单的最近最少使用策略LRU(n+1个页被访问,大小只有n,LRU就乱套了),随机策略。

    20. 分页:较小的表

    页表总是占据极大的内存,简单的数据结构(基于数组)效率太低了。

    多级页表能很好的解决问题,普通的线性表中存在很多无效空间,但是都分配了该页的页表,多级页表仅将两页标记为有效。

    在这里插入图片描述

    线性页表通常很大,线性表是按VPN索引的PTE数组,需要连续驻留在物理空间中;有了多级结构,我们增加了一个间接层 (level of indirection),使用了页目录,它指向页表的各个部分。这种间接方式,让我们能够将页表页放在物理内存的任何地方。

    多级页表的缺点在于,TLB未命中,就需要从内存加载两次,这样会造成时间的浪费(空间换时间的典型);同时页表查找也会很复杂。

    21. 超越物理内存:机制

    为了支持更大的地址空间,操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。一般来说,这个地方有一个特点,那就是比内存有更大的容量。增加交换空间让操作系统为多个并发运行的进程都提供巨大地址空间的假象。交换空间位于硬盘驱动器上,它比进入物理内存要慢。

    硬件判断页是否在内存中的方法是通过页表的存在位,如果不存在,存在位为0,这时候会出现页错误。页错误通常由操作系统进行处理,操作系统通过PTE中的某些位来找到当前进程所对应的硬盘地址,然后发送请求给硬盘,将页读取到内存中。页表I/O完成后,操作系统会更新页表,这页就标记为存在,I/O运行中,操作系统仍然可以运行其他的进程

    内存访问TLB未命中会遇到很多情况:

    1. 该页存在且有效,TLB未命中页也可以从PTE中获取PFN,然后重试指令就可以命中了
    2. 存在位为0,页错误处理程序运行
    3. 访问页为无效页,硬件捕获这个非法访问,操作系统陷阱处理程序运行,可能会杀死程序

    22. 超越物理内存:策略

    当操作系统中的空闲内存不够时,出于内存压力操作系统必须要换出一些页为常用页留下空间,我们应该踢出哪个页?

    问题:内存中只包含系统中所有页的子集,因此可以将其视为系统中虚拟内存页的缓存,我们的目标是在缓存选择替换策略时,让缓存命中更多,如何做?

    因为内存访问的速度比磁盘访问速度快很多很多,所以即使是小概率的未命中也会严重影响效率。

    最优策略

    替换内存中在最远将来才会访问到的页。

    虽然不切实际(我们无法预测未来),但是可以作为一个标准来和其他方法进行对比,

    FIFO 先入先出 & Random 随机策略

    先入先出虽然简单,但是因为根本无法确定页的重要性,即使经常使用的页也会将其踢出,所以命中率会很低

    随机策略在内存满了的时候随机选择一个页进行替换,命中率全凭运气

    这两种方法都有可能踢出重要的页,而这个页马上就又要被引用

    LRU 利用历史数据

    局部性原则:程序倾向于频繁地访问某些代码例如(循环)和数据结构(例如循环访问的数组)。

    局限性:空间局限性,时间局限性

    LRU方法就是找到最近使用最少的页将它踢出,但是这种方法很难实现,因为一台机器会有上百万页,如果遍历寻找,性能代价太大了

    在局部性:80%的引用是访问 20%的页(“热门”页)。剩下的 20%是对剩余的 80%的页(“冷门”页)访问时,LRU会有更好的表现

    在这里插入图片描述

    这展示了缓存较小导致的FIFO和LRU在性能方面的瓶颈。

    近似LRU

    增加一个使用位的概念,当最近使用了这个页,硬件就会将当前页的使用位设置成1。

    当必须进行页替换时,操作系统检查当前指向的页 P 的使用位是 1 还是 0。如果是 1,则意味着页面 P 最近被使用, 因此不适合被替换。然后,P 的使用位设置为 0,时钟指针递增到下一页(P + 1)。该算法一直持续到找到一个使用位为 0 的页,使用位为 0 意味着这个页最近没有被使用过(在最坏的情况下,所有的页都已经被使用了,那么就将所有页的使用位都设置为 0,周期性地清除使用位可以防止这个问题出现)。

    clock算法不如完美的LRU,但是比无记忆的方法好多了

    因为踢出一个已经被更改过的页需要将它重写回磁盘,这很昂贵,我们称这种页为脏页;但是如果没有被修改过,这就是干净的页,脏位就是为了记录这个页修改了么,每次写入页时都会设置此位,因此可以将其合并到页面替换算法中。例如,时钟算法可以被改变, 以扫描既未使用又干净的页先踢出。无法找到这种页时,再查找脏的未使用页面,等等。

    当内存被超额请求,操作系统只能不停地换页才能满足需求,一般的解决方式就是杀死其中的内存密集型进程来控制内存请求。

    23. VAX/VMS虚拟内存系统

    VAX-11为每个进程提供了32位的虚拟地址空间,虚拟地址由23位VPN和9位偏移组成,VPN高两位勇于区分页所在的段。

    代码不会访问第0页,这一页被设置为不可访问,以方便空指针的检测(对调试的支持)

    并发

    26.并发:介绍

    多线程程序会有多个执行点(多个程序计数器,每个都用于取指令和执行),每个线程类似于独立的进程,但是线程之间共享地址空间,能够访问相同的数据

    两个线程运行在同一个处理器上,进行线程切换时,我们将状态保存在线程控制块(Thread Control Block TCB),进程是保存在PCB中。然而线程之间的切换地址空间保持不变,不用切换当前使用的页表。

    除此之外,进程线程另一个区别在栈,每个线程都有一个自己的栈

    在这里插入图片描述

    27. 插叙:线程API

    好吧,我其实不咋喜欢看这种章,一堆代码😷,跳过了,以后再看。

    28. 锁

    锁出现的目的主要是为了解决希望实现并发编程的原子性的问题,在源代码中加锁,放在临界区周围,保证临界区能够像单条原子指令一样执行

    锁就是一个变量,它有两种状态,可用与被占用,当线程发现锁是可用的,那么该线程获得锁,进入临界区,这时候其他线程会发现锁的状态是被占用的,所以无法进入临界区。

    锁让又操作系统调用的混乱状态变得可控。

    锁的评价标准有什么?

    1. 能否有效

    2. 公平性,线程之间对锁的竞争是否公平?是否有线程会一直竞争失败?

    3. 性能,使用锁之后使用锁增加的开销如何?

    使用最简单的关闭打开会出现的问题:

    1. 有可能存在恶意程序滥用权利一直使用lock占据所有资源
    2. 不支持多处理器,线程可以通过其他处理器进入临界区
    3. unlock指令如果丢失,操作系统只能永久等待
    4. 代码执行效率低

    自旋锁(testAndSet实现)

    自旋锁运行起来的效果就是,当前线程如果发现flag为0,就直接获得锁;如果发现flag为1,就循环等待,直到flag为0才会获得锁。

    首先我们写一个testAndSet函数,函数功能为将目前的flag设置为返回值,将1设置为当前的flag值

    在实际运行中会出现两种情况

    第一种情况原本的old_ptr(flag值)为0,这时线程的old被设置为0并且返回,但是指针设置为1(告诉别的进程锁已经被占用了)

    第二种情况原来的flag为1,程序在lock函数中循环while等待,知道testAndSet函数返回0,才可以获得锁,否则一直循环等待。

    完整的代码:

    另外,我们可以使用compare-and-swap比较并交换指令实现自旋锁,代码为:

    代码表示检测ptr指针当前指向的值是否和expected相等,如果相等则更新指针的值为新值,否则无行动。无论如何都会返回当前的值,以告诉使用者程序在正常运行。

    将compare-and-swap替换上问的lock函数,就可以实现自旋锁

    自旋锁的评价:满足正确性,不提供任何公平性保证,单CPU情况下性能开销很大,多CPU下性能开销可以接受

    使用fetch-and-add可以实现一种类似于排队的策略,每个线程拥有自己的ticket,当全局lock模块的turn等于某个线程的ticket时,这个线程获得lock,ticket锁实现如下:

    如果线程希望获取锁,首先对一个 ticket 值执行一个原子的获取并相加指令。这个值作为该线程的“turn”(顺位,即 myturn)。根据全局共享的 lock->turn 变量,当某一个线程的(myturn == turn)时,则轮到这个线程进入临界区。unlock 则是增加 turn,从而下一个等待线程可以进入临界区。

    虽然可以使用yield()在线程将要自旋的时候让出CPU进入就绪态,以节省CPU资源(只有两个线程的时候很好用!),但是这种方法仍然会造成资源浪费,因为如果锁一直在别的线程手中,等待线程就会一直运行,yield()让出,运行,yield()让出……

    linux使用的是两阶段锁,第一阶段先自旋一段时间(实际中固定自旋的次数),希望可以获取锁,这一阶段如果没有获得锁,这个线程就会进入第二阶段:睡眠,直到锁可用

    29.基于锁的并发数据结构

    对于特定数据结构,如何加锁才能让该结构功能正确?

    拿一个简单的计数器来举例,简单加锁之后的计数器性能相对于不加锁的来说,可扩展性极差,性能下降极大。

    使用懒惰计数器可以解决问题,懒惰计数器的原理是利用全局计数器和局部计数器实现的,一个CPU配一个局部计数器,一个机器配一个全局计数器,不同CPU上的线程不会竞争,更新操作的可扩展性会好很多。

    具体原理是以S为阈值更新,当某个局部变量到达了阈值就将数据同步给全局计数器,局部计数器清零。阈值越大,花费时间就越少,精确度也越低,所以需要做一个平衡的阈值。

    在这里插入图片描述

    30. 条件变量

    多线程程序中,一个线程如何等待某些条件完成再执行?最简单的方法是写一个while自旋等待,但是这种方法效率很低

    生产者/消费者方案

    pthread_cond_t c;,这里声明c是一个条件变量(注意:还需要适当的初始化)。条件变量有两种相关操作:wait()和 signal()。线程要睡眠的时候,调用 wait()。当线程想唤醒等待在某个条件变量上的睡眠线程时,调用 signal()。

    生产者线程等待条件变量 empty,发信号给变量 fill。相应地,消费者线程等待 fill,发信号 empty。这样做,从设计上避免了上述第二个问题:消费者再也不会唤醒消费者,生产者也不会唤醒生产者。

    生产者只有在缓冲区满了的时候才会睡眠(p2),消费者也只有在队列为空的时候睡眠(c2)

    31.信号量

    sem_wait : 将信号量s的值减1;如果信号量s的值为负,则等待

    sem_post : 将信号量s的值加1;如果有一个或多个线程在等待,唤醒一个

    二值信号量(锁)

    就是锁的概念,用sem_post和sem_wait将临界区环绕起来,通过信号量来判断当前进程是等待还是运行

    生产者/消费者(有界缓冲区)问题

    在上一节中的有效方案中,如果缓冲区MAX的值大于1,那么就会有两个生产者同时调用put的情况,这种情况下,如果有一个生产者刚写入了数据,但是被中断了,还没来得及更新fill,那么新的生产者就会重写刚才的生产者的值,这就会造成数据丢失的问题。

    使用二值信号量来加锁(代码中的sem_wait(&mutex)),将put和get操作的临界区保护起来,但是注意不能把锁的作用域放在刚才的有界缓冲区外面,否则会出现死锁的现象

    因为只有插入操作才会影响结构,所以我们可以并发的执行多个查找操作,读者-写者锁就使用了这个思想。这个锁有一个缺点就是只有读者释放了锁,写者才可以进行写入,所以读者会多的情况下,写者可能会饿死。另外这种复杂的方法性能会比较差。

    哲学家就餐问题

    假定有 5 位“哲学家”围着一个圆桌。每两位哲学家 之间有一把餐叉(一共5把)。哲学家有时要思考一会,不需要餐叉;有时又要就餐。而一位哲学家只有同时拿到了左手边和右手边的两把餐叉,才能吃到东西。

    如何实现 getforks()和 putforks()函数,保证没有死锁,没有哲学家饿死, 并且并发度更高(尽可能让更多哲学家同时吃东西)。

    解决方法是其中四个哲学家都是用下面的方法

    而最后一个哲学家使用这种方法

    这样就解决了所有哲学家都拿起了左手的叉子形成死锁等待的问题

    32. 常见并发问题

    这章比较重要,单独画一个思维导图

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zg6fhSwg-1628338979109)(/Users/lizhihan/Library/Application Support/typora-user-images/image-20210801140522362.png)]

    非死锁缺陷

    违反原子性:

    举例来说,就是在线程1中通过了if条件,但是在使用if条件中的值时,线程2更改了if条件中的值,导致了空指针的引用。

    确保每个proc_info字段都有自己的锁就可以解决问题

    违反顺序缺陷:

    举例来说,就是代码执行顺序和预期不符,可能存在某个变量没有被初始化就直接被引用了

    解决方法就是使用信号量强行决定进程的运行顺序

    死锁缺陷

    当线程 1 持有锁 L1,正在等待另外一个锁 L2,而线程 2 持有锁 L2,却在等待锁 L1 释放时,死锁就产生了。

    死锁的发生是很常见的,在模块化的方式编程情况下,很可能不相关的两个模块会相互影响

    死锁产生的条件:

    互斥:线程对于需要的资源进行互斥的访问(例如一个线程抢到锁)。

    持有并等待:线程持有了资源(例如已将持有的锁),同时又在等待其他资源(例如,需要获得的锁)。

    非抢占:线程获得的资源(例如锁),不能被抢占。

    循环等待:线程之间存在一个环路,环路上每个线程都额外持有一个资源,而这个资源又是下一个线程要申请的。

    死锁的预防:

    针对循环等待,我们可以设计特定的获取锁的顺序,使用全序和偏序(全序表示所有锁都按规定顺序,偏序表示指定部分锁的顺序)

    针对持有并等待,可以设计一个prevention锁,保证原子性地抢锁。这个方案的思路就是保证我们准确知道需要哪些锁,并且都提前抢到,这样才能实现。但是这也就降低了并发,因为拿到锁的时候并不是真正需要的时候

    针对非抢占,可以设计一个trylock()函数,trylock函数会尝试去获得锁,或者返回-1,然后打开自己的锁,之后再去获得自己的锁,然后尝试这个过程

    然而这样会遇到活锁的问题,如果两个进程共同重复这个过程,两个进程都去拿对方的锁失败,然后重复这个过程,解决方法也很简单,让一个进程等一会再执行就好了。

    这种方法存在封装的问题,如果某些资源或者某些内存都已经被占用,但是仍然要返回之前的步骤,这种跳回操作就很难实现。

    针对互斥,可能使用无等待数据结构的思想,通过硬件指令,不需要锁来实现。

    另外,使用调度的方法也可以实现死锁的避免,例如合理地安排线程的运行,错开他们共同需要某个锁的时间,就可以避免死锁的发生(银行家算法)

    最后还可以使用检查和恢复的方法处理死锁,最简单的方法:关机重启

    33. 基于事件的并发(进阶)

    使用单个 CPU 和基于事件的应用程序,并发程序中发现的问题不再存在。具体来说, 因为一次只处理一个事件,所以不需要获取或释放锁。基于事件的服务器不能被另一个线程中断,因为它确实是单线程的。因此,线程化程序中常见的并发性错误并没有出现在基本的基于事件的方法中。

    当事件循环阻塞时,系统处于闲置状态,因此是潜在的巨大资源浪费。因此,我们在基于 事件的系统中必须遵守一条规则:不允许阻塞调用。

    持久性

    36. I/O设备

    输入输出设备如何集成到系统中?

    越快的总线造价越高,越快的总线越短,高性能的内存总线没有足够空间连接过多设备。

    所以需要高性能的总线的设备会连在离CPU近的地方,低性能的设备离CPU远。

    一个标准设备包含两部分:硬件接口,内部结构。

    硬件接口包含三个寄存器:状态寄存器,命令寄存器,数据寄存器

    在每次等待设备执行完成命令时会浪费大量CPU时间,所以引入中断的概念。中断在某些运行很快的设备中反而效果不好,所以有时使用混合策略,先轮询,再中断。

    I/O 支持是必需的。中断、DMA 及相关思想都是在快速 CPU 和慢速设备之间权衡的结果

    中断:利用中断并允许重叠,操作系统就可以在等待磁盘操作时运行其他的进程,否则操作系统只能简单自旋,不断轮询设备状态,直到完成I/O操作

    DMA:DMA可以协调完成内存和设备间的数据传输,不需要CPU介入。如果不使用DMA,数据的拷贝工作阶段仍然是需要CPU的,这会降低效率。

    硬件如何与设备通信?

    1. 明确的I/O指令:这些指令规定了操作系统将数据发送到特定寄存器的方法,从而允许构造协议
    2. 内存映射I/O:硬件将设备寄存器作为内存地址提供。当需要访问设备寄存器时,操作系统装载(读取)或者存入(写入)到该内存地址;然后硬件会将装载/存入转移到设备上,而不是物理内存。

    设备驱动程序:

    设备驱动程序完美的知道设备如何工作,和设备交互的细节都封装在设备驱动程序中,驱动程序有时会因为不了解设备的特殊功能而失效,且因为插入系统的设备都需要各自的驱动程序,所以操作系统中的大部分代码其实都是设备驱动程序代码。

    37. 磁盘驱动器

    简单的磁盘驱动器包含了一个单磁道,一个磁道有12个扇区,每个扇区的大小是512字节,用0-11表示,必须等待需要的扇区转到磁头下面,才可以实现写入读取操作,这需要等待,且往往是I/O服务时间的重要组成部分

    正常我们使用的磁盘驱动器都是有百万的磁道,未来进行读取或写入操作,我们需要先寻道,然后等待转动延迟(这期间盘片已经完成了旋转),最后传输。

    所以我们有公示

    I/O的成本是非常高的,操作系统在磁盘I/O顺序上面发挥作用来提高效率

    SSTF:最短寻道时间优先,但是如果有很多内圈的请求,那么外圈的磁道就会饥饿

    C-SCAN电梯算法:该算法从内圈扫到外圈,再从外圈扫回内圈,仍然遵守较近的优先

    SPTF:最短定位时间优先,现在的机器查找和旋转的速度是相当的,所以SPTF算法经常在驱动器内部执行(因为驱动器比操作系统更懂磁道边界,磁头位置)

    现代操作系统较为复杂,而且很精准,可以准确实现SPTF,操作系统会选择它认为的几个最好的请求,并将他们全部发送到磁盘。

    除此之外,调度程序执行还会执行I/O合并,相近的扇区共同进行请求,这样可以降低开销;发出I/O之后,操作系统通常会等一段时间,这样整体效率会提高很多。

    38. 廉价冗余磁盘阵列(RAID)

    RAID由多个磁盘、内存(包括易失性和非易失性)以及一个或多个处理器来管理系统。硬件 RAID 非常像一个计算机系统,专门用于管理一组磁盘。

    RAID并行使用多个磁盘可以大大加快I/O时间,且容量较大,通过冗余的方式还可以容许损失磁盘保持运行,除此之外,RAID拥有很好的透明性,很轻松就可以部署,不必担心兼容性问题

    评估RAID的方法:容量,可靠性,性能

    RAID 0级:条带化

    基本思想:以轮转方式将磁盘阵列的块分布在磁盘上。

    在这里插入图片描述

    评估条带化的容量、可靠性和性能。从容量的角度来看,它是顶级的:给 定 N 个磁盘,条件化提供 N 个磁盘的有用容量。从可靠性的角度来看,条带化也是顶级的, 但是最糟糕:任何磁盘故障都会导致数据丢失。最后,性能非常好:通常并行使用所有磁 盘来为用户 I/O 请求提供服务。

    磁盘可以在连续工作负载下以 S MB/s 传 输数据,并且在随机工作负载下以 R MB/s 传输数据。

    RAID 1级:镜像

    保留两个物理副本就是典型的镜像系统

    在这里插入图片描述

    存在一致更新的问题,可能在一个磁盘写入,另一个备份磁盘没有写入,导致不一致,所以需要记录日志来保证同步

    容量方面N/2,可靠性来说表现很好,容许任何一个磁盘故障,性能方面顺序读取只有N/2·S的带宽,随机写入是N/2·R,但是随机读取为N·R

    RAID 4级:通过奇偶校验节省空间

    对于每一条数据,我们都添加了一个奇偶校验(parity)块,用于存储该条块的冗余信息。例如,奇偶校验块 P1 具有从块 4、 5、6 和 7 计算出的冗余信息。

    在这里插入图片描述

    磁盘4可以使用奇偶校验的方法进行异常的监控

    在这里插入图片描述

    有效容量为N-1,可靠性方面,也仅仅允许一个磁盘故障,连续性能为(N-1)·S,相比于上面的级别,4级为了更新磁盘4,写入时的性能会较差

    RAID 5级:旋转奇偶校验

    在这里插入图片描述

    随机读写性能比4级稍好一些,增加一些并行性

    总之,如果你严格要求性能而不关心可靠性,那么条带显然是最好的。但是,如果你想要随机 I/O 的性能和可靠性,镜像是最好的,你付出的代价是容量下降。如果容量和可靠性是你的主要目标,那么 RAID-5 胜出,你付出的代价是小写入的性能。最后,如果你总是在按顺序执行 I/O 操作并希望最大化容量,那么 RAID-5 也是最有意义的。

    40. 文件系统的实现

    考虑文件系统时,我们需要考虑两个方面:文件系统的数据结构,访问方法

    构建文件系统的磁盘分区如下:
    在这里插入图片描述

    很大面积用于存放用户数据,这些磁盘区域称为数据区域;inodes结构用于存放每个文件的信息(给定文件的元数据的结构:长度,权限,组成块的位置);i和d分别表示inode位图和数据位图,用于指示对象/块是否空闲;S表示超级块,保存该特定文件系统的信息

    41. 局部性和快速文件系统

    一个老旧的文件系统如下所示,虽然简单,但是它的问题也很多,例如它会将磁盘随机存储,每次访问内存的定位成本太高,在逻辑上连续的块可能在这个文件系统上分离,性能太差。

    FFS(快速文件系统)提供了解决方法:将磁盘划分为一些分组,称为柱面组,如果在同一个组中放置两个文件,FFS可以确保先后访问两个文件不会导致磁盘长时间寻道。

    每个组中需要分配文件和目录,每个组中都有超级块的副本以防灾,inode位图和数据位图(ib,db)记录组的inode和数据块的分配

    FFS文件创建超级复杂,因为如果更新了一个目录下的一个文件,这个子文件的inode以及data都要更新,那么记录信息的ib,db以及父目录的ib,db也都需要更新!

    FFS的原则是相关的东西放在一起:目录的放置方法为寻找分配数量少的柱面组,这是为了跨组平衡目录;文件的放置需要确保文件和它对应的inode分配在相同的组中,以防止长时间寻道,然后再将同一目录中的所有文件都放在它们所在目录的柱面组中。

    然而,在遇到大文件的时候,FFS会出现填满当前组的问题,FFS的解决方法是将大文件分布在磁盘上进行存储,分布的内容为inode指针指向的内容,虽然这样可能损害顺序读取的性能,但是在大块足够大的情况下,这种损害是比较小的。

    另外FFS在处理小文件上也有所创新:引入子块,一个子块512字节,一个块一般是4kb,小文件攒够8个才变成一个大块,但是这样有些慢,所以使用缓冲写入,凑够4kb再写入文件系统;防止子块转过了,例如读取0完了想读1但是磁盘转多了,只能再转一圈,引入新的布局;

    42. 崩溃一致性:FSCK和日志

    举例来说,如果我们希望向磁盘中写入信息,需要至少三次:位图写入,inode写入,数据块写入。当这三个写入没有全部完成的时候发生了崩溃,这就是崩溃一致性问题。

    为了解决这个问题有以下的几种方式

    1.文件系统检查程序

    典型的如FSCK,它的思路是让不一致的事情发生,查找不一致的内容然后删除,但是这种方法需要扫描整个磁盘,查找已经分配的块并读取目录树,这是不合理的,仅仅修复三个块的更新引入的问题而扫描整个磁盘

    2.日志/预写日志

    日志的思路借鉴自数据库管理系统,基本思路是在更新磁盘时,覆写操作之前,先写下一些标注,放入一个结构中,这样就构成了日志。崩溃发生之后只要读一下日志的内容,重试就好了。

    写入日志的操作顺序如下:

    1. 日志写入:将事务的内容写入日志
    2. 日志提交:将事务提交块写入日志
    3. 加检查点:将待处理的元数据和数据更新写入文件系统中的最终位置
    4. 释放:一段时间后,更新日志超级块,在日志中标记该事务为空闲

    在开始和结束块中加入日志内容的校验和,可以提高写入日志的效率

    文件系统利用日志进行恢复:崩溃发生在事务写入日志前,跳过等待执行的更新即可;加检查点期间发生崩溃,文件系统需要扫描日志,找到已经提交磁盘的事务,重放这些事务,再次尝试将事务中的块放入自己最终的磁盘位置。

    为了提高效率,也可以使用元数据日志的方法,不将Db写入日志,而是将数据在日志写入之前就写入最终位置

    3.其他方法

    软更新:利用系统保证每次写入都不会导致不一致发生,这种方法需要对文件系统数据结构非常了解,系统会很复杂

    乐观崩溃一致性:尽可能多的向磁盘发出写入,利用事务校验和的一般形式或其他方式检测不一致。这样可以大幅提高效率

    43. 日志结构文件系统

    写入磁盘时,LFS 首先将所有更新(包括元数据!)缓冲在内存段中。当段已满时,它会在一次长时间的顺序传输中写入磁盘,并传输到磁盘的未使用部分。LFS 永远不会覆写现有数据,而是始终将段写入空闲位置。由于段很大,因此可以有效地使用磁盘,并且文件系统的性能接近其峰值。

    LFS为了实现大量连续写入,使用写入缓冲的办法,写入磁盘之前,LFS会跟踪内存中的更新,收到足够数量更新后,才会立即将他们写入磁盘,从而确保有效使用磁盘。下图表示LFS将两组更新缓冲到一个段中。

    在LFS系统中,查找inode号会比较困难,因为我们将inode分散在整个磁盘上,而且我们不会覆盖,最新版本的inode会不断移动。

    通过一个inode映射imap作为一个中间层,imap驻留在写入新信息的位置旁边,更新数据块时,向文件加入imap,inode以及数据块。imap告诉LFS inode位于的位置,inode告诉LFS数据块所在的地址。

    LFS在磁盘上有一个检查点区域(checkpoint region),包含了inode映射片段的指针(地址),可以通过检查点区域来找到imap,检查点区域定时更新,不影响整体性能。

    LFS会不断的将新版本的文件写入磁盘的新位置,这样磁盘的中间位置就会存在很多垃圾,解决方法是定时清理,将现有的段打包到新段中,然后释放旧的段,这样才能保证LFS的大段写入机制。通过段中的摘要块可以判断当前块的死活,例如版本更新的时候就可以直接更新摘要块,这样就可以省略判断指针目前情况的时间。

    关于何时清理,一些论文指出可以多清理更新少的死块,少清理更新多的死块,因为更新多的块会有越来越多的块被覆盖,被释放;但是这个问题仍然在被研究中。

    检查点区域CR的更新为了保证不产生崩溃影响,在LFS中保留了两个CR,位于磁盘的两端,除此之外,还使用了先写出头,再写出主体,再写出最后一部分的方法来更新CR,每个部分都含有时间戳,这样实现了CR的一致更新;LFS使用前滚技术保证CR的更新,因为CR更新期间可能发生崩溃(每30s一次的那个),我们检查最后一个检查点区域,找到日志的结尾,用它来读取,并检查其中的更新

    LFS的这种写入磁盘未使用部分,清理回收旧空间的方法,在数据库中称为影子分页,文件系统中称为写时复制。

    44. 数据完整性和保护

    单块故障包括潜在扇区错误和块讹误,磁盘扇区或扇区组出现问题导致磁盘内容不正确叫做潜在扇区错误,磁盘固件可能会产生问题,导致写入错误位置,这叫做块讹误。

    潜在扇区错误的解决方法相对简单,因为这种错误很容易检测到,然后就可以用RAID的副本,通过奇偶校验来找到出错位置进行重建

    块讹误的问题在于检测的困难,因为恢复只需要和以前一样找到副本就可以了。我们使用的校验方法为检验和,校验和就是一个函数的结果,该函数以一块数据(例如 4KB 块)作为输入,并计算这段数据的函数,产生数据内容的小概要(比如 4 字节或 8 字节)。

    一个最简单的方法就是异或运算,对二进制字节每四个进行一次异或运算,得到一个十六进制结果,这种方法在有两个二进制数字一起更改的时候会失效;加法也是简单的检测方法。另外还可以使用CRC循环冗余校验,校验和的存储一般是在每个块上,驱动器制造商来将512字节的扇区多加8字节来实现存储,没有这种功能的扇区,只能开辟一个空间来进行校验和的存储

    还存在错误写入的问题:在校验和中加入当前块的磁盘和扇区号(物理id)辅助判断就可以进行解决了

    如果设备通知上层已经写入完成,事实上却还未持久化,磁盘留下的仍然是旧内容,这种问题如何解决?很多解决方法,例如在文件系统的其他位置加入校验和

    文件系统应该按时使用一下校验和来进行检查,以保证数据的可靠性,这叫做磁盘擦净

    校验和的空间开销很小,但是时间的开销很大

    分布式

    如何构建在组件故障时仍然可以正常工作的系统?

    47. 分布式系统

    通信总是不可靠的,会以很多种不同的方式丢包。

    使用校验和技术可以进行数据完整性检验,但是这也不是一定可以检验出来的。

    构建可靠的分布式系统最主要的抽象是基于远程过程调用(Remote Procedure Call,RPC),RPC中有两部分:存根生成器,运行时库

    存根生成器:自动化将函数参数和结果打包成消息,并优化此类代码

    运行时库:运行时库处理RPC系统中的大部分繁重工作,处理大多数性能和可靠性问题

    48. Sun的网络文件系统(NFS)

    分布式文件系统如下:客户端通过网络访问服务器磁盘上的目录和文件,这样做有很多好处,客户端之间可以轻松的共享数据;集中管理很方便,备份也仅仅通过少数机器就可以实现;安全,服务器一般在上锁的机房中

    服务器故障时,我们可以利用幂等性(多次重复操作得到的结果是一样的)来处理故障,所以处理故障时我们一般进行重试就可以了

    客户端中引入缓存的概念来增加利用的效率,因为网络传输总是很昂贵的。但是这就会出现一致性的问题,可能当前缓存的内容已经在服务器中被更新了,那么这要怎么办?

    首先要在每次客户端关闭时,将缓存更新一遍,以保证其余节点进行访问时看到的是最新的版本。此外,客户端在使用缓存时还会对比服务器的版本以确认当前使用的是最新版本

    49. Andrew文件系统(AFS)

    AFS和NFS不同的地方在于一开始就考虑合理的,用户可见的行为。

    AFS的基本原则是调用open()时,每个客户端的本地磁盘进行全文件缓存,最终close()操作之后,如果文件被修改,则写回服务器。

    这样的系统存在两个问题:每次服务器查找路径都要很久,服务多个客户端的时候会浪费大量资源按目录路径找文件;客户端会发出很多test信息来判断是否文件被修改了。这两个问题影响了AFS的可拓展性,每次服务20个客户端就是上限了

    AFSv2是AFS的改进版,引入了回调的概念,客户端缓存的文件被修改时,服务器会通知客户端,这样客户端就不用询问这个文件是否有效了;引入了文件标识符的概念,类似于缓存的概念,指定客户端感兴趣的文件,以减少查找的次数

    举例来说:在不同的计算机之间,AFS 让更新在服务器上可见,并在同一时间使缓存的副本无效, 即在更新的文件被关闭时。客户端打开一个文件,然后写入(可能重复写入)。当它最终关闭时,新文件被刷新到服务器(因此可见)。然后,服务器中断任何拥有缓存副本的客户端的回调,从而确保客户端不再读取文件的过时副本。在这些客户端上的后续打开,需要从服务器重新获取该文件的新版本。

    服务器崩溃的成本非常高,因为可能服务器也不知道哪个客户端的版本是最新的,所以可能需要客户端告诉服务器自己的版本是可用的,这样才可以恢复,所以客户端经常需要知道服务器是否挂了

    AFSv2扩展性好很多(50个),且AFS考虑了系统管理,使得系统管理员可以简单的管理服务器

    下载链接

    链接: https://pan.baidu.com/s/11p5nVg2L1q61LECjlh1ryw 密码: p2hq
    如果失效请私信联系我~

    2022/4/13 更新
    链接: https://pan.baidu.com/s/1X9yTMsfaPfpsoWoBDqQxEg 密码: o54h

    展开全文
  • 操作系统导论第26章课后答案 26.1 开始,我们来看一个简单的程序,“loop.s”。首先,阅读这个程序,看看你是否能理解它:cat loop.s。然后,用这些参数运行它: ./x86.py -p loop.s -t 1 -i 100 -R dx 这指定了一个...

    操作系统导论第26章课后答案

    26.1

    开始,我们来看一个简单的程序,“loop.s”。首先,阅读这个程序,看看你是否能理解它:cat loop.s。然后,用这些参数运行它:
    ./x86.py -p loop.s -t 1 -i 100 -R dx
    这指定了一个单线程,每 100 条指令产生一个中断,并且追踪寄存器%dx。你能弄清楚%dx 在运行过程中的价值吗?你有答案之后,运行上面的代码并使用-c 标志来检查你的答案。注意答案的左边显示了右侧指令运行后寄存器的值(或内存的值)。

    loop.S试图修改寄存器%dx的值,将寄存器%dx的值减一后,再测试其是否为0,如果大于等于0则跳转至top处。从运行结果来看,线程在第一轮减1操作后便终止了程序,所以可以推断出%dx的原值为0;

    ?0

    ?-1

    ? -1

    ? -1

    ? -1

    image-20211112101945421

    加上-c标志,验证正确

    image-20211112103721614

    26.2

    现在运行相同的代码,但使用这些标志:

    ./x86.py -p loop.s -t 2 -i 100 -a dx=3,dx=3 -R dx
    这指定了两个线程,并将每个%dx 寄存器初始化为 3。%dx 会看到什么值?使用-c 标志验证你的答案。多个线程的存在是否会影响计算?这段代码有竞态条件吗?

    可以看到看到线程T0进行4轮减1操作后,%dx的值为-1,然后终止了程序。此时发生中断,恢复上下文,线程T1再次进 行4轮减1操作后终止程序。所以最终结果并没有受到影响。

    image-20211112104310522

    加上-c标志,可以看到中断时间大于线程执行时间,不存在竞态条件

    image-20211112110037895

    26.3

    现在运行以下命令:
    ./x86.py -p loop.s -t 2 -i 3 -r -a dx=3,dx=3 -R dx
    这使得中断间隔非常小且随机。使用不同的种子和-s 来查看不同的交替。中断频率是否会改变这个程序的行为?

    可以看到,两个线程之间频繁地发生中断。但是两个线程的行为未改变,都是进行了4轮减1操作后终止。所以中断频率并不会改变程序的行为。

    image-20211112110339370

    加上-c标志, 可以看到,计算结果的确未收到影响,因为线程0和线程1修改的不是共享变量

    image-20211112111454021

    26.4

    接下来我们将研究一个不同的程序(looping-race-nolock.s)。
    该程序访问位于内存地址 2000 的共享变量。简单起见,我们称这个变量为 x。使用单线程运行它,并确保你了解它的功能,如下所示:
    ./x86.py -p looping-race-nolock.s -t 1 -M 2000

    在整个运行过程中,x(即内存地址为2000)的值是多少?使用-c 来检查你的答案。

    looping-race-nolock.s将X加1后回存到内存2000,然后再将bx寄存器的值减一后,再检测bx%是否大于0,如果大于0则再次循环,否则终止程序。

    因为不知道内存地址2000初始值,无法推断出x的值。

    .main
    .top	
    mov 2000, %ax  # get 'value' at address 2000
    add $1, %ax    # increment it
    mov %ax, 2000  # store it back
    sub  $1, %bx  
    test $0, %bx
    jgt .top	
    halt
    

    image-20211112112224072

    加上-c标志,可以看到x的初始值为0,执行程序后,x的值变为1

    image-20211112114556739

    展开全文
  • 问题4 生成不同的中断频率,运行结果会不同,仍然存在竞态。 问题5 程序test-and-set.s .var mutex .var count .main .top ....acquire # 获取锁 ...xchg %ax, mutex # atomic swap of 1 and mutex ...
  • 操作系统导论第八、九章课后习题

    千次阅读 2022-03-13 19:43:05
    操作系统概论第八、九章课后习题 8.1 只用两个工作和两个队列运行几个随机生成的问题。针对每个工作计算 MLFQ 的执行记录。限制每项作业的长度并关闭 I/O,让你的生活更轻松。 执行命令行 python2 mlfq.py -j 2 -n 2...
  • 操作系统导论英文主页 代码Github地址
  • 操作系统导论第五章

    2019-09-25 01:23:39
    操作系统导论 第五章 编码作业作业 categories: 操作系统导论 操作系统导论第五章:进程API UNIX的系统调用 UNIX采用一对系统调用:fork()函数和exec()函数,非常有趣的创建新进程。 父进程还可以通过...
  • } 由此可以分析标志flag的值的变化,与模拟结果是一致的 28.3 题目描述 分析及解答 通过第一题中对汇编代码的分析,我们可以知道,这个程序对count进行循环加1操作,并且锁保护的方案为“细粒度”方案(将锁上在循环...
  • 答案Github库 https://github.com/jzplp/OSTEP-Answers 问题 1 答案 [testjz@localhost vm-freespace]$ ./... 问题 6 答案 P越高,分配操作越多,剩余空间越少呀。 问题 7 答案 进行很多很多分配操作,且不free即可。
  • 问题 1 答案 汇编代码尝试使用书类似中图28.1代码的方式来设置锁。 问题 2 答案 ...[testjz@localhost threads-locks]$ ./x86.py -p flag.s -R ax,bx -M flag,count -c ...ARG interrupt frequenc
  • 目录前言一、15.1题目描述:分析与解答:二、15.3题目描述:分析即解答: 前言 内容仅作记录,请谨慎参考 一、15.1 题目描述: 分析与解答: 通过计算机底层的地址转换机制我们可以知道,CPU会先将虚拟地址VA与...
  • 操作系统导论第四章作业解题报告

    千次阅读 2019-09-24 18:08:56
    title: 操作系统导论第四章作业解题报告 tags: 操作系统导论 第四章 模拟作业 categories: 操作系统导论 操作系统导论第四章:进程 定义 进程就是运行中的程序 一台机器上如何同时运行多个程序? 这里的...
  • 问题 1 答案 还是只需要一个寄存器即可。 问题 2 答案 结果太长,这里仅仅给出命令。..../paging-multilevel-translate.py -s 0 -c ./paging-multilevel-translate.py -s 1 -c ./paging-multilevel-translate...
  • 问题 1 答案 [testjz@localhost vm-mechanism]$ ./relocation.py -s 1 -c ARG seed 1 ARG address space size 1k ARG phys mem size 16k Base-and-Bounds register information: ... Base : 0x0000363c (decimal ...
  • 问题 1 答案 [testjz@localhost vm-segmentation]$ ./segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 0 -c ARG seed 0 ARG address space size 128 ARG phys mem size 512 Segment register ...
  • 虚拟化(virtualization) 并发性(concurrence) 持久化(persistence) 重要概念 参考资料 该系列文章主要为《操作系统导论》(Operating Systems: Three Easy Pieces) 的学习笔记,同时期间会穿插一些便于理解的资料。...
  • 问题 1 答案 [testjz@localhost cpu-sched-mlfq]$ ./mlfq.py -j 2 -m 10 -M 0 -n 2 -q 3 -c Here is the list of inputs: OPTIONS jobs 2 OPTIONS queues 2 OPTIONS allotments for queue 1 is 1 ...
  • 目录前言22.1题目描述分析及解答FIFOLRUOPT22.2题目描述分析及解答22.3题目描述分析及解答22.4题目描述分析及解答 前言 内容仅作记录,解答有参考别人的地方,请谨慎参考 22.1 题目描述 分析及解答 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,769
精华内容 9,907
关键字:

操作系统导论

友情链接: C#绘制波形图Demo.zip