admin管理员组

文章数量:1588999

暑期结束到现在，回归学习（之前被一些事情缠的不可脱身！）

Os小白入门
本章最后我会说明我为什么选择这门课作为os的入门。

清华大学 操作系统原理

  • 第二章：操作系统基础操作
    • 2.1操作系统的启动基本概念知识
    • 2.2中断/异常和系统调用
  • 第三章：连续式内存分配
    • 3.1 计算机体系结构及内存分层体系
    • 3.2 地址空间与地址生成
    • 3.3 连续内存分配：内存碎片与分区的动态分配
    • 3.4 连续内存分配：压缩式与交换式碎片整理
  • 第四章：非连续式内存分配
    • 4.1 非连续内存分配：分段
      • 4.1.1分段Segmentation：更好的分离和共享
    • 4.2 非连续内存分配：分页
      • 4.2.1 分页地址空间
      • 4.2.2 物理地址部分：页帧
      • 4.2.3 逻辑地址部分：页
    • 4.3 非连续内存分配：页表-概述/TLB
      • 4.3.1 页表概述
      • 4.3.2 转换后备缓冲区/快表TLB
    • 4.4 非连续内存分配：页表-二级/多级页表
    • 4.5 非连续内存分配：页表-反向页表inverted page table
      • 4.5.1 传统页表的缺点
      • 4.5.2 反向页表的实现：基于页寄存器page registers的方案
      • 4.5.4 反向页表的实现：基于哈希查找hash的方案
  • 第五章： 虚拟内存
    • 5.1 虚(拟)(内)存(管理)技术
  • 第六章：页面置换算法
    • 局部页面置换算法
      • 6.1 最优页面置换算法
      • 6.2 先进先出算法
      • 6.3 ==最近最久未使用算法==
      • 6.4 时钟页面置换算法
      • 6.5 二次机会法
      • 6.6最不常用算法
      • 6.7 Belady现象，LRU，FIFO，Clock的比较
      • 6.8 局部页替换算法的问题，工作集模型
    • 6.9 == 全局页面置换算法==
      • 工作集页置换算法
      • 缺页率页面置换算法
      • 6.10 抖动问题
  • 第七章：进程和线程
    • ==进程==
      • 7.1 进程的定义
      • 7.2进程的组成
      • 7.3进程与程序的联系
      • 7.4 进程与程序的区别
      • 7.5进程的特点
      • 7.6进程的描述-pcb
        • 7.6.1PCB包含信息
        • 7.6.2PCB的组织方式
      • 7.5 进程的生命周期管理
        • 7.5.1进程挂起
        • 7.5.2进程的状态管理
      • 进程的上下文切换
        • 进程的创建
        • 进程的加载
        • 进程等待与退出
    • ==线程==
      • 线程的概念
      • 线程的实现
        • 用户线程
        • 内核线程
        • 轻量级进程(lightweight process)
  • 第八章：CPU调度
    • 8.1 背景 CPU调度
      • 8.1.1上下文切换：
      • 8.1.2 CPU调度：
      • 8.1.3 在进程/线程生命周期的什么时候进行调度？
        • 8.1.4 内核运行调度程序的条件
    • 8.2 调度原则
    • 8.3 调度算法
      • 8.3.1 FCFS先来先服务
      • 8.3.2 SRT短剩余时间优先
      • 8.3.3 HRRN最高响应比优先
      • 8.3.4 Round robin轮循
      • 8.3.5 Multilevel feedback queues多级反馈队列
      • 8.3.6 fair share scheduling 公平共享调度
    • 8.4 实时调度
      • 8.4.1实时系统
      • 8.4.2实时调度算法
        • RM(Rate Monotonic)速率单调调度
        • EDF(Earliest Deadline First)最早期限调度
    • 8.5 多处理器调度与优先级反转
      • 8.6.1 多处理器调度的原因
      • 8.6.2 优先级反转
  • 第九章：同步
    • 9.1背景引入
      • 9.1.1临界区的访问规则
      • 9.1.2临界区的实现方法
  • 第十章：信号量和管程
    • 10.1信号量
    • 10.2信号量的使用
      • 10.2.1生产者-消费者模型
      • 10.2.2 生产者-消费者模型实现策略
    • 10.3信号量的实现
      • 10.3管程monitor
      • 10.3.1管程的实现
        • 管程解决生产者消费者问题
        • 大佬的办法
    • 10.4读者写者问题
      • 基于信号量的读者优先
      • 基于管程的写者优先
    • 10.5哲学家就餐问题
  • 第十一章 死锁
    • 10.1 死锁的情况
    • 10.2 预防死锁的方法
      • 10.2.1避免死锁的算法-------银行家算法
    • 10.3 死锁检测
    • 10.4 死锁恢复
    • 10.5进程通讯IPC
      • 10.5.1 直接通信
      • 10.5.2间接通信（通过内核传递消息）
      • 10.6常用的进程通信手段
        • 信号
        • 管道—数据交换
        • 消息队列-数据传输的一种机制
  • 第十二章 文件系统
    • 12.1基本概念
      • 文件和文件系统
      • 文件系统的功能
      • 文件和文件块（头）
      • 文件描述符
          • 访问模式
      • 12.2 目录
        • 目录的操作
      • 12.3文件系统
        • 12.4虚拟文件系统
        • 文件系统基本数据结构：
      • 12.5文件缓存
        • 基于分页的缓存方式
      • 12.6打开文件的数据结构
      • 12.7文件空间分配
      • 12.8空闲空间的管理
      • 12.9多磁盘管理-RAID
      • 12.10磁盘的调度

第二章：操作系统基础操作

2.1操作系统的启动基本概念知识

(1)

  • CPU, I/O, 内存通过总线连接。
    (2)
  • DISK:存放OS；
  • BIOS：基本I/O处理系统( basic I/O system);
  • Bootloader: 加载OS到内存中。
    (3)
  • 当电脑通电时，段寄存器CS和指令寄存器IP能够确定一个内存地址，例如CS:IP = 0xf000:fff0.（bios从这个位置开始执行）
    (4)POST(加电自检)，寻找显卡和执行BIOS。(主要是检查各个外设的驱动，显示器，键盘…是否正常)。
    (4）
    步骤：
  • BIOS: 将Bootloader从磁盘的磁盘的引导扇区(bootloader占512字节)加载到内存的0x7c00地址（跳转到CS:IP=0000:7c00的内存区域）
  • Bootloader：将操作系统os的代码和数据从硬盘disk加载到内存中；跳转到操作系统的起始地址。

2.2中断/异常和系统调用

(1)中断/异常处理机制
中断是外设的事件，异常是CPU的事件；中断/异常迫使CPU访问一些被中断和异常服务访问的功能。

(2)中断处理机制
硬件：设置中断标记(CPU初始化)

  • 将内部/外部事件设置中断标记；
  • 中断事件的ID(程序访问的中断向量地址)
    软件(操作系统)：
  • 保存当前处理状态
  • 中断服务程序处理
  • 清除中断标记
  • 恢复之前保存的处理状态

(3)异常处理机制
异常：异常编号

  • 保存现场
  • 异常处理：杀死产生异常的程序；重新执行异常指令
  • 恢复现场

(4)系统调用

  • 一条指令会触发一个系统调用

  • 程序访问主要是通过高层次的API接口而不是直接进行系统调用。

  • 通常情况下，存在与每个系统调用相关的序号，系统调用接口根据这些序号来维护表的索引。

  • 系统调用接口调用内核态中预期的系统调用，并返回系统调用的状态和其它任何返回值。

  • 用户不需要知道系统调用是如何实现的，只需要获取API和了解操作新系统将什么作为返回结果。操作系统接口的细节大部分都隐藏在API中，并通过运行程序支持的库来管理。

  • 用户态：应用程序在执行的过程中，CPU执行的特权级的状态(很低，不能访问特殊机器指令和IO)。

  • 内核态：应用程序在执行的过程中，CPU执行的特权级的状态(高，操作系统可以执行CPU任何一条指令)。

  • 系统调用时涉及到特权级从用户态到内核态的转换，应用程序和操作系统有各自的堆栈，这两个变化比函数调用的开销更大，但更安全和可靠。(而程序调用是在一个栈空间实现参数的调用和返回)。

  • 跨越操作系统边界的开销

    • 在执行时间上超过程序调用
    • 开销包括：
      • 建立中断/异常/系统调用号与对应服务例程映射关系的初始化开销；
      • 建立内核堆栈(操作系统和应用程序的堆栈不一样，维护两个堆栈的开销)；
      • 验证参数(操作系统会检查应用程序返回的请求数据)；
      • 内核态映射到用户态的地址空间，更新页面映射权限(内存拷贝开销)；
      • 内核态独立地址空间TLB。

第三章：连续式内存分配

3.1 计算机体系结构及内存分层体系

  • 操作系统在内存管理要完成的目标
    • 抽象：逻辑地址空间
    • 保护：独立地址空间
    • 共享：访问相同内存
    • 虚拟化：更多的地址空间
  • 操作系统实现内存管理目标的手段
    • 程序重定位
    • 分段
    • 分页
    • 虚拟内存
    • 按需分页虚拟内存

3.2 地址空间与地址生成

(1)地址空间的定义

  • 物理地址空间：硬件支持的地址空间
  • 逻辑地址空间：一个运行的程序所拥有的内存范围
    两者的映射关系是由操作系统来管理的

(2)地址空间的生成

  1. c语言的.c文件通过编译生成汇编文件.s
  2. .s文件再汇编成为.o文件，这个linux用户很熟悉
  3. 一个.o文件再拆成多个.o文件然后变成.exe执行文件
  4. 最后在内存中载入执行

(3)应用程序的逻辑地址是如何映射到物理地址
=>CPU方面
a.运算器ALU需要在逻辑地址的内存内容(CPU要逻辑地址)
b.内存管理单元MMU寻找在逻辑地址和物理地址之间的映射(MMU找逻辑和物理地址的关系)
c. 控制器从总线发送在物理地址的内存内容的请求(关系找到后，去找对应物理地址)
=>内存方面
e.内存发送物理地址内存内容给CPU(物理地址找到了，给CPU)
=>操作系统方面
f.建立逻辑地址和物理地址之间的映射(确保程序不相互干扰)
(4)地址安全检查

3.3 连续内存分配：内存碎片与分区的动态分配

(1)内存碎片问题： 空闲内存不能被利用

  • 外部碎片：在分配单元间的未使用内存
  • 内部碎片：在分配单元中的未使用内存

(2)简单的内存管理方法：

  • 当一个程序准许运行在内存中时，分配一个连续的区间
  • 分配一个连续的内存区间给运行的程序以访问数据

(3)分区的动态分配策略
三种适配算法

  • 首次适配
    • 内容：现在想分配n字节，从低地址开始找，碰到的第一个空间比n大的空闲块就使用它。
    • 要想实现首次分配，需要满足以下条件：
      • 需要存在一个按地址排序的空闲块列表
      • 分配需要找一个合适的分区
      • 重分配需要检查，看看自由分区能不能与相邻的空闲分区合并(形成更大的空闲块
    • 优点
      • 简单
      • 易于产生更大的空闲块，向着地址空间的结尾
    • 缺点
      • 外部碎片的问题会加剧
      • 不确定性
  • 最佳适配
    • 内容：为了分配n字节，使用最小的可用空闲块，以致块的尺寸比n大。
    • 目的：避免分割大的空闲块；最小化外部碎片产生的尺寸。
  • 要想实现最佳分配，需要满足以下条件：
    • 按尺寸排列的空闲列表
    • 分配需要寻找一个合适的分区
    • 重分配需要搜索和合并于相邻的空闲分区，若有
  • 优点：大部分分配是小尺寸时很有效；简单
  • 缺点：外部碎片；重分配慢；易产生很多没用的微小碎片。
  • 最差适配
    • 内容：为了分配n字节，使用最大的可用空闲块，以致块的尺寸比n大。
    • 目的：避免太多的微小碎片
    • 要想实现最差分配，需要满足以下条件：
      • 按尺寸排列的空闲列表
      • 分配很快(获得最大的分区)
      • 重分配需要合并于相邻的空闲分区，若有，然后调整空闲块列表
    • 优点：假如分配时是中等尺寸效果最好
    • 缺点：重分配慢；外部碎片；易于破碎大的空闲块以至大分区不能被分割

3.4 连续内存分配：压缩式与交换式碎片整理

(1)压缩式碎片整理(紧致)

  • 重制程序以合并空洞
  • 要求所有程序是 动态可重置的
  • 问题：何时重置，开销。

    （2）交换式碎片整理
  • 运行程序需要更多的内存
  • 抢占等待的程序或回收它们的内存(把暂时不用的内容挪到磁盘里)

第四章：非连续式内存分配

4.1 非连续内存分配：分段

  • 连续内存分配问题：内外碎片问题，内存利用率低，连续的物理内存
  • 非连续内存分配的优点：
    ->分配给一个程序的物理内存是非连续的
    ->更好的内存利用和管理
    ->允许共享代码和数据(共享库等)
    ->支持动态加载和动态链接
  • 非连续内存分配的缺点
    ->如何建立虚拟地址和物理地址之间的转换
    ->软件方案(只用硬件的话，开销大)
    ->硬件方案 ：分段；分页

4.1.1分段Segmentation：更好的分离和共享

  • 分段寻址的方案
    (1)段访问机制：一个段指一个“内存块”，是一个逻辑地址空间。
    程序根据段访问机制访问内存地址需要一个二维的二元组(s段号，addr端内偏移)

    x86就是段寄存器+地址寄存器
    (2)段访问机制的硬件实现方案：

4.2 非连续内存分配：分页

4.2.1 分页地址空间

（划分大小固定）
划分物理内存至固定大小的帧

->大小是2的幂，e.g.512，4096，8192

-划分逻辑地址空间至相同大小的页

->大小是2的幂，e.g.512，4096，8192

  • 建立方案：转换逻辑地址为物理地址(pages to frames)

->页表Page Table
->MMU/TLB(快表)

4.2.2 物理地址部分：页帧

(1)页帧:物理内存被分割为大小相等的帧(物理地址部分)

  • 一个内存的物理地址是一个二元组(f,o)，f:帧号(它是F位的，因此意味着一共2F个帧)；o：帧内偏移(它是S位的，因此意味着每帧有2S字节)；物理地址=2^S x f + o。

4.2.3 逻辑地址部分：页

页：一个程序的逻辑地址空间被划分为大小相等的页(逻辑地址部分)

  • (逻辑地址的)页内偏移量=(物理地址的)帧内偏移量
  • (逻辑地址的)页号大小可能不等于(物理地址的)帧号大小

  • 页号和帧号不是相等的！！
  • 页寻址机制的实现
    页表实际上就是一个大的数组/hash表。它的index是 页号，对应的value是 页帧号，首先根据逻辑地址计算得到一个 页号，也就是index，再在页表中找到对应的 页帧号，最后根据 页帧号 计算得到物理地址；由于他们的页/帧内偏移相等，所以页表不需要保存这个数据。通过这种方式能够根据逻辑地址找到对应的物理地址。

4.3 非连续内存分配：页表-概述/TLB

4.3.1 页表概述

(1)通过标志位来判断当前页号的性质

例子：
逻辑地址空间是16位64kB，物理地址空间是15位32kB，并不是对等的，但是一页和一帧的大小是一样的，都是10位，1kB。

4，从页表下面从上数，01234

  • 逻辑地址(4,0),页号4对应的二进制是100，它的位置对应着flags。根据上图，可知它的dirty bit是1，resident bit（标志位）是0，clock/reference是0；因此可以知道逻辑地址(4,0)在物理地址中实际是不存在的。如果CPU访问这个逻辑地址会抛出一个内存访问异常；
  • 逻辑地址(3,1034),页号3对应的二进制是011，它的位置(也就是页号的位置)对应着flags。根据上图，可知它的dirty bit是0，resident bit是1，clock/reference是1；因此可以知道逻辑地址(3,1034)在物理地址中存在。再复习一下，页表里存放的是什么。因为由于逻辑地址的页内偏移和物理地址的帧内偏移是一样的，所以页表不需要保存偏移。根据页表，页号3对应的页帧号是4，再加上它们的偏移量相等，所以逻辑地址(3,1034)对应的物理地址是(4,1023)。
    这个页表是由操作系统维护。

分页机制的性能问题(缺点)
空间代价和时间代价：

  • 访问一个内存单元需要2次内存访问：一次获取页表项；一次是访问数据。
  • 页表可能会非常大(页表的长度等于2^页号位数)
    举例，64位机器，如果一页是1024KB，那么页表是多大？
    1.假如页号是n位的，那么页表的长度等于2^ n，一页是1024KB，所以页内偏移是10位，一个逻辑地址的长度等于计算机位数，也就是64位，因此剩下的54位是留给页号的；因此页表的长度是2^54，明显CPU装不下。
    2.一个程序一个页表，n个程序n个页表，就更大了。
    3.CPU装不下，只能装在内存里；如果这样，需要访问2次内存，一次访问页表，一次访问程序。
    (4)解决办法
  • 缓存caching
  • 间接访问indirecion

4.3.2 转换后备缓冲区/快表TLB

TLB实际上是CPU的MMU内存管理单元保存的一段缓存，这段缓存保存的内容是 页表的一部分，是经常访问到的那部分页表，其余不常用的页表内容保存在内存中。
TLB未命中，也叫TLB miss，这种情况比较少见，因为一页很大，32位系统一页是4K，如果采用局部性原理，那么访问4k次才会遇到一次TLB miss。

把内存中的页表放进快表的操作，可以通过cpu进行，也可以通过os来进行。

4.4 非连续内存分配：页表-二级/多级页表

本节介绍如何优化页表的空间开销问题，解决方法是 多级页表。
虽然增加了内存访问次数和开销，但是节省了保存页表的空间(时间换空间，然后在通过TLB来减少时间消耗)。

逻辑地址中，页号部分分成了2部分，p1和p2。
p1存放着二级页表的起始地址，p2的作用就是之前的p。
p1找二级页表，p2找页，o找地址。
这里体现了二级页表的另一个好处，就是p1对应的位置是flags，假如说resident bit是0，那么整个二级页表都不用在内存中保存，这个是一级页表无法实现的！
9

(2)多级页表
例如64位系统采用5级页表。

4.5 非连续内存分配：页表-反向页表inverted page table

反向页表：
页表来表示物理地址(页帧)号，而不是之前的逻辑地址(页号)，能够减少页表尺寸，但是给映射关系的建立带来点困难。

4.5.1 传统页表的缺点

(1)对于大地址空间，前向映射页表变得繁琐(例如64位系统采用5级页表)。
(2)逻辑地址空间增长速度快于物理地址空间，所以反向页表，也就是index是物理地址，value是逻辑地址，它的大小会小于传统页表。

4.5.2 反向页表的实现：基于页寄存器page registers的方案

  • 每一个帧和一个寄存器关联，它包括：
    • residence bit：此帧是否被占用；
    • occupier：对应的页号p；
    • protection bit：保护位；
  • 页寄存器的优点：
    转换表的大小相对于物理内存来说很小；
    转换表的大小跟逻辑地址空间的大小无关。
  • 页寄存器的缺点：
    需要的信息对调了，如何根据帧号找到页号呢；
    需要在反向页表里去找想要的页号。

------------------------上述方法开销太大！---------------------------------

4.5.4 反向页表的实现：基于哈希查找hash的方案


上述方法可能导致一个key出现2个以上的value对应。
这种方式仍然需要把反向页表放在内存中，做hash计算的时候还需要在内存中取数（不断去计算匹配的hash值），仍然需要多次访问内存。 （hash实际就是通过一个函数去计算位置）

第五章： 虚拟内存

5.1 虚(拟)(内)存(管理)技术

实际的存储器：

解决覆盖技术给程序员负担大和交换技术处理器开销大的问题。
(1)虚存技术的目标

  • 像覆盖技术一样，不是把程序的所有内容都放在内存中，因而能够运行比当前的空闲内存空间还要大的程序。但做得更好，能由操作系统自动完成，无需程序员介入
  • 能像交换技术那样，能够实现进程在内存和外存之间的交换，因而获得更多的空闲内存空间。但能做得更好，只对进程的部分内容在内存和外存之间进行交换。

    p3程序只需要两个内存单位，其他都放在虚拟内存里面
    (2)程序的局部性原理(principle of locality)
    指程序在执行过程中的一个较短时间，所执行的指令地址和指令的操作数地址分别局限于一定区域，表现为：
  • 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短的时间里
  • 空间局部性：当前指令和领近的几条指令，当前访问的数据和领近的几个数据都集中在一个较小区域内
    程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该能够取得一个满意的效果的。


方法1是按行访问，也就是每跳过1024个访问一个，考虑到4k只能放1024个数字(一个int占32位，4个byte)，所以每次访问都会换入换出，不满足空间局部性。
(3)虚存技术的基本特征

(4)虚拟页式内存管理


第六章：页面置换算法

局部页面置换算法

6.1 最优页面置换算法

  • 功能目标
    功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。
  • 目标：尽可能减少页面的换入换出次数(即缺页中断的次数)。把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理的指导下依据过去的统计数据来进行预测。

页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法是，在页表中添加锁定标志位(lock bit)。

1.最优页面置换算法
基本思路：当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。
不过，这只是一种理想情况，在实际中无法实现，因为操作系统无法知道每一个页面要等待多长时间以后才会被再次访问。
可用作其它算法的性能评价的依据(在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法)。
d是下一等待时间最长访问的页，所以把d置换出去

6.2 先进先出算法


belady现象就是，调出的页面是经常访问的页面，因此，很容易产生缺页中断现象。

6.3 最近最久未使用算法



6.4 时钟页面置换算法


这里主要看used bit，如果为1，则置0，如果为0，则代表可以置换出去。时钟走一圈就可以看出哪个是相对最久的页面。

6.5 二次机会法


如果是一次写操作，dirty bit会设置为1.说明内存访问这部分数据时是有写入操作的，和硬盘上原数据不一样，所以要写入硬盘，如果是0，对这部分内存没有写操作，那么说明内存和硬盘上内容是一样的，直接丢掉即可。
目的就是减少对硬盘的写操作。

替换原则：
如果used和dirty bit都是0，那么替换掉；如果其中一个是1，那么把这一位设置为0，指针往下走；如果都是1，那先把used换为0，说明有2次机会
（1，1->0,1->0,0）。

这里要注意，如果是读操作，放进来就是10，写操作放进来是11。

6.6最不常用算法

6.7 Belady现象，LRU，FIFO，Clock的比较

Belady是个科学家名字


FIFO再这里表面，有可能页数越多，缺页也是越多的

同等情况下，LRU的效果好很多

---------------------------------------总结对比---------------------------------------------


CLOCK利用标志位去模拟逼进开销

6.8 局部页替换算法的问题，工作集模型


分配不同固定大小的物理页帧对算法的效果影响很大，例如上图，3个页帧产生9次缺页，而4个页帧产生1次缺页

  • 工作集模型



!](https://img-blog.csdnimg/7a22e459c6d044848c72c17d5c5693e8.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAa3dldA==,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center)



最理想就是常驻集和工作集相重合，这样就不会发生缺页中断

6.9 == 全局页面置换算法==

工作集页置换算法

大概意思:
即使没有发生缺页，也要把时间窗口超过的页面给置换出去，如果是只读的就直接释放，如果是写的就重新写入磁盘中。

缺页率页面置换算法





eg：
当发生中断的时候，考虑和上次中断产生的时间间隔是否大于2，如果大于2，就把这两个时间段访问的页面保存，其他的都清出去。

与工作集置换算法的区别

  • 对页的调整时机不一样。这个方法只在缺页中断时判断是否更改，而后者是在每次换入换出时都做判断。
  • 都与局部页置换算法不一样。这两种涉及到工作集大小的调整。而局部只是在工作集满了之后才考虑换入换出。
  • 全局页置换算法效果比局部页置换算法要好。

6.10 抖动问题



当大量程序开启时 ，cpu都在进行I/O操作，浪费时间
N i/o点最优！

第七章：进程和线程

进程

7.1 进程的定义

一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

7.2进程的组成

(1)一个进程应该包括：

  • 程序的代码
  • 程序处理的数据
  • 程序计数器的值，指示下一条将运行的指令
  • 一组通用的寄存器的当前值，堆，栈
  • 一组系统资源(如打开的文件，网络，内存等)
    总之，进程包含了正在运行的一个程序的所有状态信息。

7.3进程与程序的联系

程序是产生进程的基础

  • 程序的每次运行构成不同的进程，（不同的运行次数，产生不同数据和结果）
  • 进程是程序功能的体现
  • 通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。程序与进程是多对多的关系

7.4 进程与程序的区别

  • 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行，进程有核心态/用户态
  • 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存
  • 进程与程序的组成不同：进程的组成包括程序，数据和进程控制块(进程的状态信息)

7.5进程的特点

  • 动态性：可动态地创建，结束进程
  • 并发性：进程可以被独立调度并占用处理机运行（目前计算机都是多核，可以实现并发并行）
  • 独立性：不同进程的工作不互相影响（通过页表的管理使不同的进程访问不同的内存空间）
  • 制约性：因访问共享数据/资源或进程间同步而产生制约

7.6进程的描述-pcb

进程控制块(process control block, PCB): 描述进程的数据结构，操作系统管理控制进程运行所用的信息集合。
操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息，PCB是进程存在的唯一标志。

7.6.1PCB包含信息

1. 进程标识信息:

  • 如本进程的标识，本进程的产生者标识(父进程标识)；用户标识

2. 处理机状态信息保存区，保存进程的运行现场信息:

  • 用户可见寄存器，用户程序可以使用的数据，地址等寄存器
  • 控制和状态寄存器，如程序寄存器(PC)，程序状态字(PSW)
  • 栈指针，过程调用/系统调用/中断处理和返回时需要用到它。

3. 进程的控制信息:

  • 调度和状态信息：用于操作系统调度进程并占用处理机使用；
  • 进程间通信信息：为支持进程间的与通信相关的各种标识，信号，信件等，这些信息存在接收方的PCB中；
  • 存储管理信息：包含有指向本进程映像存储空间的数据结构；
  • 进程所用资源：说明由进程打开，使用的系统资源，如打开的文件等；
  • 有关数据结构等连接信息：进程可以连接到一个进程队列中，或连接到相关的其它进程的PCB。
7.6.2PCB的组织方式

(动态插入删除)链表：统一状态的进程其PCB成一脸表，多个状态对应多个不同的链表，各状态的进程形成不同的链表，例如就绪链表和阻塞链表
索引表：同一状态的进程归入一个index表(由index指向PCB)，多个状态对应多个不同的index，各状态的进程形成不同的索引表，例如就绪索引表，阻塞索引表。

7.5 进程的生命周期管理

进程创建->进程运行->进程等待->进程唤醒->进程结束

  1. 进程创建
    引起进程创建的三个主要事件情况：系统初始化->用户请求创建一个新进程->正在运行的进程执行了创建进程的系统调用
  2. 进程运行
    如何选择进程，涉及后续的调度算法的问题
  3. 进程等待 （堵塞）
    进程等待只能由自身去发起
  • 请求并等待系统服务，无法马上完成；
  • 启动某种操作，无法马上完成；
  • 需要的数据没有到达。
  1. 进程唤醒
  • 被阻塞进程需要的资源可被满足；
  • 被阻塞进程等待的事件到达；
  • 将该进程的PCB插入到就绪队列中。
  1. 进程结束
  • 正常退出(自愿)
  • 错误退出(自愿)
  • 致命错误(强制性)
  • 被其它进程所杀(强制性)


这里从running——>Ready的状态切换是受到os给进程分配的时间片影响

7.5.1进程挂起

进程挂起是一种合理且充分地利用系统资源的方式。挂起时，进程没有占用内存空间，处于挂起状态的进程映像在磁盘上。挂起就是把一个进程从内存转到磁盘。（这里回忆下前面讲的内存的时候，如果内存空间不够，这时候把一些进程从内存从移到磁盘中，给别的内存让座。）

  • 挂起状态
    阻塞挂起状态(blocked-suspend):进程在外存并等待某事件的出现，进程本身就是阻塞。
    就绪挂起状态(ready-suspend):进程在外存，但只要进入内存，即可运行，进程本身就是就绪。

7.5.2进程的状态管理


进程的上下文切换

上下文切换上停止当前运行的进程(从运行态改变成其它状态)并且调度其它进程(转变成运行态)。
上下文切换需要储存的内容：

  • 例如寄存器(PC/SP/…)，栈指针，CPU状态，…
  • 一些时候可能会费时，所以需要尽量避免。

操作系统为活跃进程准备了PCB；
操作系统将PCB放置到一个合适的队列里。

  • 就绪队列
  • 等待队列
  • 僵尸队列
进程的创建

b站指路
这块讲fork函数缺少了视频，所以我看了另一个清华的os的课程。突然发现这个课程更好，有代码提供，更加具体



进程的加载

进程等待与退出



僵尸状态就是子进程退出在等待父进程把它结束这段状态！

exec()在running和ready以及block状态都有可能

线程

线程的概念

实体间能够并发地执行；实体之间共享相同的地址空间 ——线程
与进程相区分，进程的内存空间都是独立的


这里重新把进程和线程的关系进行了梳理，线程单纯指执行的，不包含资源


线程之间在同一个空间共享资源，因此运行起来都很快

线程的实现

  • 用户线程：在用户空间实现，例如POSIX Pthreads, Mach C-threads, Solaris threads。
  • 内核线程：在内核中实现，例如Windows, Solaris, Linux。
  • 轻量级线程：在内核中实现，支持用户线程，例如Solaris。
用户线程

在用户空间实现的线程机制，不依赖于操作系统的内核；
由一组用户级的线程库来完成线程的管理，包括创建/终止/同步/调度；
优点：

  • 不需要操作系统内核了解用户线程的存在，可用于不支持线程技术的多进程操作系统；
  • 每个进程都需要它私有的线程控制块TCB列表，来跟踪记录它各个线程的状态信息(PC/栈指针/寄存器),TCB由线程库函数来维护；
  • 用户线程的切换由线程库函数实现，无需 用户态/核心态切换，所以速度快；
  • 允许每个进程有自定义的线程调度算法。

缺点：

  • 如果一个线程发起系统调用而阻塞，则整个进程都在等待；（线程的状态会影响进程的状态，因为os只能看到进程）
  • 如果一个线程开始运行，除非它主动交出CPU控制权，否则该线程所在进程的其它线程都无法运行；
  • 由于时间片分配给的是进程，所以与其它进程相比，在多线程执行时，每个线程得到的时间片较少，执行会较慢。
内核线程

指在操作系统的内核中实现的一种线程机制，由操作系统的内核来完成线程的创建，终止和管理

  • 由内核维护进程和上下文信息，也就是进程/线程控制块PCB/TCB；
  • 线程的创建/终止/切换都是通过系统调用或内核函数来实现(用户态和内核态的切换)，所以系统开销大；
  • 在一个进程中，如果某个内核线程发起系统调用而阻塞，不会影响其它内核线程的运行；
  • 时间片分配给线程，多线程的进程能获得更多的CPU时间；
  • Windows NT/2000/XP 支持内核线程。
轻量级进程(lightweight process)

内核支持的用户线程。一个进程可以有一个或多个轻量级进程，每个轻量级进程由一个单独的内核线程来支持(Solaris/Linux)。

第八章：CPU调度

8.1 背景 CPU调度

8.1.1上下文切换：

  • 切换CPU的当前任务，从一个进程/线程转换到另一个进程/线程；
  • 但是切换之前要保护现场，保存当前进程/线程在PCB/TCP中的执行上下文(也就是CPU的状态)；
  • 切换任务，当然要读取下一个进程/线程的上下文。

8.1.2 CPU调度：

  • 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程；
  • 需要调度程序(挑选进程/线程的内核函数)；
  • 需要考虑的问题是 调度的时机

8.1.3 在进程/线程生命周期的什么时候进行调度？

从一个状态到另一个状态的时候会发生调度。

8.1.4 内核运行调度程序的条件

8.2 调度原则

评价指标

  • CPU使用率：CPU处于忙状态所占时间的百分比；
  • 吞吐量：在单位时间内完成的进程数量；
  • 周转时间：一个进程从初始化到结束，包括所有等待时间所花费的时间；
  • 等待时间：进程在就绪队列中的总时间；
  • 响应时间：从一个请求被提交到产生第一次响应所花费的时间。
    (4)吞吐量vs延迟
  • 对快的评价指标：传输文件时的高带宽；玩游戏时的低延迟(这两点相互独立)；
  • 减少响应时间：及时处理用户的输出并尽快将输出提供给用户；
  • 减少平均响应时间的波动：在交互系统中，可预测性比高差异/低平均更重要；
  • 增加吞吐量：减少开支(操作系统开支/上下文切换)；系统资源的高效利用(CPU，I/O设备)；
  • 减少等待时间：减少每个进程的等待时间。

低延迟调度增加了交互式表现(个人电脑)：
如果移动了鼠标，希望屏幕迅速反馈光标的移动。

操作系统保证吞吐量不受影响(服务器)：
若想结束长时间的编程，所以操作系统必须不时进行调度，即使存在许多交互任务。

吞吐量是操作系统的计算带宽；响应时间是操作系统的计算延迟。

公平的目标
e.g. 保证每个进程占用相同的CPU时间(并不公平，因为一个用户可能比其它用户运行更多进程)；保证每个进程都有相同的等待时间
公平通常会增加平均响应时间

8.3 调度算法

8.3.1 FCFS先来先服务

优点：简单；
缺点：平均等待时间波动较大(没有抢占)；
花费时间少的任务可能排在花费时间长的任务后面；
可能导致I/O和CPU之间的重叠处理(CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待)。

8.3.2 SRT短剩余时间优先

SPN(SJF)短进程优先(短作业优先)的意思是 选择下一个最短的进程(短任务优先)，即按照预测的完成时间排序将任务入列；
注意，它可以是抢占的也可以是不抢占的，对于抢占类型的，才是SRT短剩余时间优先。
优点：平均周转时间最少

缺点：
可能导致饥饿(连续的短任务流会使长任务饥饿；
短任务可用时的任何长任务的CPU时间都会增加平均等待时间)；

因此就需要预知未来，
但是怎么预估下一个CPU突发的持续时间是一个问题；(你咋知道下一个进程是长是短呢？？？)
其中一个简单的解决办法：询问用户；
如果用户欺骗就杀死进程；
但是用户不知道怎么办？
根据历史时间分配预估未来时间的分配(也就是根据之前该进程所花的时间来预测它将要花多少时间)：

8.3.3 HRRN最高响应比优先

  • 在SPN调度的基础上改进(考虑了等待时间，改善饥饿现象)；
  • 不可抢占；
  • 关注进程等待了多长时间；
  • 防止无限期推迟；R = (w + s) / s (选择R值最高的进程) ，其中
    w:waiting time等待时间 s:service time执行时间
    优先调度R值大的进程

8.3.4 Round robin轮循

在一个叫做 量子(或时间切片)对离散单元中分配处理器；如果时间片结束了，那么就接换到下一个准备好的进程
举一个例子来理解，如下图，先设置一个时间片，例如20，那么就让进程轮流分享这个时间片。先P1执行，用完20后，让出CPU给P2；但是P2只有8，用完直接给P3；同样，P3只用20；以此类推。

(1)优点：公平；
(2)缺点：
额外的上下文切换花销；
如果时间片太大，则等待时间过长，极限情况下退化成FCFS；
如果时间片太小，虽反应迅速，但是开销大；吞吐量由于大量的上下文切换开销而受到影响；
(3)目标：
选择一个合适的时间片；
经验规则：维持上下文切换开销处于1%以内。

8.3.5 Multilevel feedback queues多级反馈队列



根据不同的任务，来确定队列的优先级，eg：交互类i/o操作优先级较高，后台计算类的优先级较低

8.3.6 fair share scheduling 公平共享调度

站在用户的角度实现公平共享CPU资源。因为有的用户可能开的进程多，有的用户进程少。
它考虑了以下情况：
一些用户组比其他用户组更重要；
保证不重要的组无法垄断资源；
未使用的资源按照每个组所分配的资源的比例来分配；
没有达到资源使用目标的组获得更高的优先级。

8.4 实时调度

8.4.1实时系统

定义：正确性依赖于其时间和功能两方面的一种操作系统；
性能指标：时间约束的及时性(deadlines);速度和平均性能相对不重要；
主要特性：时间约束的可预测性；
强实时系统：需要在保证的时间内完成重要的任务，必须完成；
弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须；



可调度性：表示一个实时系统是否可以满足deadline要求，
决定实时任务执行的顺序：

  • 静态优先级调度：运行之前优先级就是确定的；
  • 动态优先级调度：优先级在运行中是动态变化的；

8.4.2实时调度算法

RM(Rate Monotonic)速率单调调度
  • 最佳静态优先级调度
  • 通过周期安排优先级
  • 周期越短，优先级越高
  • 先执行周期最短的任务
EDF(Earliest Deadline First)最早期限调度
  • 最佳的动态优先级调度
  • Deadline越早，优先级越高
  • 先执行Deadline最早的任务

8.5 多处理器调度与优先级反转

8.6.1 多处理器调度的原因

多处理器的CPU调度更加复杂
(多个相同的单处理器组成一个多处理器；它的优点是负载共享)；
对称多处理器(SMP)
(每个处理器运行自己的调度程序；需要在调度程序中同步)；

8.6.2 优先级反转

优先级反转可以发生在任何基于优先级的可抢占的调度机制；
当系统内的环境强制使高优先级任务等待低优先级任务时发生。

解决方法：
优先级继承，低优先级任务即成高优先级任务的优先级，这个依赖于他们共享的资源。此时T3的优先级会动态的得到提升

第九章：同步

9.1背景引入


确保只有一个进程在临界区执行

9.1.1临界区的访问规则

  • 空闲则入
  • 忙则等待（临界区有一个进程时，其他进程在外面等待）
  • 有限等待（等待进入临界区的进程不能一直等待）
  • 让权等待（可选），不能进入临界区的进程，释放cpu资源，转换成阻塞状态

9.1.2临界区的实现方法

  1. 禁止硬件中断
  • 没有中断，没有上下文切换，因此没有并发
    • 硬件将中断处理延迟到中断被启用之后
    • 现代计算机通过指令实现禁用中断
  • 进入临界区
    • 禁止中断，进入临界区，保存标志
  • 离开临界区
    • 使能中断，恢复标志

  1. 软件方法
    这里软件方法就不详细叙述了，下面给个总结

  2. 更高级的抽象

    TEST and SET和EXCHANGE都被封装成机器指令，因此执行的时候就是成为一条原子指令。


改进：通过把等待进程移入等待队列，实现无忙等待

exchange方式去实现



第十章：信号量和管程

10.1信号量


10.2信号量的使用

信号量必须是整数，初始值一般是大于0；
信号量是一种被保护的变量(初始化后，唯一改变一个信号量值的方法只能是P()和V()；操作只能是原子操作)；
P()能阻塞，V()不会阻塞；
信号量假定是公平的(采用FIFO先进先出算法去唤醒；如果一直有V()操作，则不会有进程被P()所阻塞);

信号量包括两种类型：

  • 二进制信号量：0或1；
  • 计数信号量：任何非负整数；
  • 可以用上面这两种类型任意一个表示另一个。

信号量可以用在2个方面：

  • 临界区的互斥

  • 条件同步(采用调度约束实现一个线程等待另一个线程的事情发生)

10.2.1生产者-消费者模型


正确性要求：

  • 在任何一个时间只能有一个线程操作缓冲区(互斥)；
  • 当缓冲区为空时，消费者必须等待(调度/同步约束)；
  • 当缓冲区满了时，生产者必须等待(调度/同步约束)；

10.2.2 生产者-消费者模型实现策略

  • 利用一个二进制信号量实现互斥，也就是锁的功能；
  • 用一个计数信号量fullbuffers来约束生产者；
  • 用一个计数信号量emptybuffers来约束消费者；

    这段代码讲解可以去看视频讲解B站

10.3信号量的实现


注意，sem>0，说明计算机能满足所有需求，不需要把线程弄到等待队列里。
P():
标记减一，如果标记小于0了，说明资源不够，需要把线程加入队列；
V():
标记加一，如果标记小于等于0，说明等待队列中有元素，唤醒一个队列中的元素并执行；

信号量的用途：互斥和条件同步(注意等待的条件是独立的互斥)；
信号量的缺点：读/开发代码困难；容易出错(使用的信号量被另一个线程占用，完了释放信号量)；不能够处理死锁；

10.3管程monitor


管程：

  • 一个锁：指定临界区
  • 0个或者多个条件变量：等待/通知信号量用于并发访问共享数据

管程的目的：分离互斥和对条件同步的关注。

管程的定义：一个锁(临界区)加上0个或若干个条件变量(等待/通知信号量用于管理并发访问的共享数据)。

管程实现的一般方法：收集在对象/模块中的相关共享数据；定义方法来访问共享数据。

一开始，所有进程在右上角的排队队列中，排队完后进行wait()操作，等到signal()操作唤醒后，执行这个进程的代码。

10.3.1管程的实现

(1)wait():

  • numWaiting就是计数器，统计有多少个线程处于等待队列中；
  • release()因为当前线程在睡眠，就必须把锁打开一下，以便就绪状态的线程去执行，如果不release可能会造成死锁；
  • schedule()的意思是，当前线程在wait()了，在队列里睡眠了，此时就需要选择一个就绪态的线程去执行；就绪态的线程执行完毕后就可以再上锁。
    (2)signal():
  • 如果等待队列中有元素，那么就把队列的头元素取出来(并删掉)并唤醒wakeup（把sleep转换成ready），此时这个线程就是就绪状态了，它的下一步操作就是wait()里的schedule()，执行这个线程。
    注意，signal仅在等待队列中有元素的时候才对numberWaiting执行(减法操作)。而信号量不一样，在P()和V()一定会有对信号量的加减操作的。
管程解决生产者消费者问题


这段看了好几遍，才看懂

(1)Deposit() 生产者:
根据管程定义，只有一个线程能进入管程，所以一开始就上锁，在最后才解锁(紫红色字)；这里和信号量是不一样的，信号量的互斥是紧紧靠着信号量的，而管程的互斥是在头和尾 注意，这个lock是管程的lock。
如果buffer没有满，就可以先不看红字，Deposit是要往buffer里加商品，加的时候需要上锁保证对buffer操作的互斥(紫色，一次只运行一个线程操作)；直到buffer的计数器为n，装满了；
但是需要提前判断一种情况，就是容器是不是满的(红字部分)，如果是满的，就把加入商品这个操作使用条件变量notFull，给notFull传入的参数就是那个管程的lock。此时重点来了，还记得管程条件变量定义里的wait()操作吗?那里面有一个release操作，释放的就是紫红色标记的lock->acquire()；这里表示，加入商品这个线程可以进入睡眠状态了（因为buffer满了），就把锁打开，让给别人。要不然就会变成死锁。
只有释放了这个lock，现在处于就绪状态(就是在notFull.signal()操作中被唤醒)的线程才能执行(就是wai()里面的schedule()操作)，否则就会死锁；等到就绪状态的线程执行完了，再上锁，恢复原样！

现在再看看notEmpty.release()是不是就好理解了？因为我每进行一次deposit操作，buffer里面就会多一个商品，那么就多一个东西被消费者使用，此时就可以唤醒一个取商品操作的线程，这个就是靠notEmpty.release(lock)实现，此时就有一个取商品线程处于就绪态，他会在remove()操作里的notEmpty.Wait()操作中被执行！！ notfull.signal 是相互提醒线程进行notfull.wait操作
(2)Remove():
和上面就一样啦，我就不解释了。

大佬的办法
  1. Hansen（采用）：直到发出唤醒的程序自身进入等待状态，才让唤醒的程序执行 高效
  2. Hoare ： 一旦发出唤醒的操作，就让程序执行，自身去睡眠

10.4读者写者问题

基于信号量的读者优先

目的：

  • 共享数据的访问；

使用者类型：

  • 读者(不需要修改数据)；
  • 写者(读取和修改数据)。

问题的约束：

  • 允许同一时间有多个读者，但是任何时间只能有一饿写者；
  • 当没有写者时，读者才可以访问数据；
  • 当没有读者和其他写者时，写者才能访问数据；
  • 在任何时候只能有一个线程可以操作共享变量。

共享数据包括：

  • 数据集；
  • 信号量CountMutex(初始值为1，约束读者)；
  • 信号量WriteMutex(初始值为1，约束写者)；
  • 读者数量Rcount(整数，初始值为0)。


(1)写者：
sem_wait(WriteMutex)相当于P()操作；
write；
sem_post(WriteMutex)相当于V()操作；这俩其实就是锁。我们知道，二进制的P/V操作就是锁。
确保一个时间只有一个写者在挥洒笔墨。
(2)读者：
在read的再之前，因为要实现对Rcount的保护，所以首先给读者上锁；如果当前没有读者，此时给写者上锁(P()操作)不许写者进来，然后我就可以读了；因为进来了一个读者，所以Rcount++；给读者解锁；
在read的再之后，读完了，因为要实现对Rcount的保护，所以首先给读者上锁；读者走一个，所以Rcount–-；如果最后一个读者也读完了，把写者的锁释放；给读者解锁。

  • 基于读者优先的方法，只要有一个读者处于活动状态，后来的读者都会被接纳。如果读者源源不断的出现，那么写者会饥饿。
  • 基于写者优先的方法，一旦写者就绪，那么写者会尽可能快的执行写操作。如果写者源源不断的出现，那么读者就始终处于阻塞状态。

基于管程的写者优先

注意，有两类写者，一种是正在创作的写者，另一种是在等待队列中的写者。只要有一种写者存在，读者都要等待。


Database::Read():
要等待以上2种写者完成后；之后才能read；read完以后，唤醒在等待队列中的写者；
Database::Write():
只需要等待正在读或者正在写的人完成，没有人正在操作就可以write；唤醒其他人。
管程的数据：
AR/AW活着的读者和写者个数；WR/WW等待着的读者和写者的个数；
条件变量：okToRead可以去读了；okToWrite可以去写了。

读者的代码
写者代码

这里唤醒全部读者

10.5哲学家就餐问题



方案一，造成死锁


第十一章 死锁

资源的分类


资源和进程之间可以形成一个图（和数据结构连起来了）
这里资源的框框中每个点点代表实例

不会死锁，因为p3不需要资源，p3free以后，后续进程会得到资源满足

10.1 死锁的情况

10.2 预防死锁的方法




10.2.1避免死锁的算法-------银行家算法

银行家算法

不安全状态！=死锁

  1. 初始化的时候finish[i]=false 代表线程都要申请资源，只有申请到资源并执行完成才可以变成ture
  2. need 的i进程需要的资源要小于剩余的空闲资源数量
  3. 进程 i 的完成以后，把资源释放，因此work 就加上allocation。finish[i]=ture
  4. request<Need i,则拒绝


例子1

max：所有进程需要资源情况
need：当前进程的资源情况
available：剩余资源
allocation:已经占用的资源
resource R:全部资源状态

从图中看到
need_p2 < available,所以，当p2结束，p2占有的资源全都释放回available里面所以，available的资源变成 6 ，2 ，3
再看回need表，此时，p1和p3都小于available，所以，此时p1占用的资源释放回available里面，available就变成7 ， 2 ， 3
再看p3，重复上面过程，available变成 9 ， 3， 4
再看p4，重复上面过程，available变成 13 ， 5， 4

以上，所有进程可以实现执行，是个安全状态
----------************************************************----------------------------
例子2

当p1请求R1和R3各一个实例时候，available就变成0 1 1
这里原来的视频有问题，这里我看学堂在线的。


此时， 0 1 1无法满足任意一个线程的need，因此是不安全状态！

10.3 死锁检测



10.4 死锁恢复

10.5进程通讯IPC

10.5.1 直接通信

10.5.2间接通信（通过内核传递消息）



这里的队列意思相当于缓冲区，这里把缓冲区分成3种情况。

10.6常用的进程通信手段

信号


传输的信号量很小，通常都是bit

这里的内核发送信号，实际就是发送函数的地址；通过修改用户态的堆栈，使信号处理函数可以执行

管道—数据交换


stdin 输入;stdout;输出;stderr错误输入输出

shell 本身是一个进程，当它看到 ls|more就明白创建两个子进程，ls 和 more；
然后shell设置stdout为管道的输入端，stdin为管道（buffer）的输出端。管道里面的空间是有限的

消息队列-数据传输的一种机制

* 与管道的区别：管道是父进程帮子进程建立的通道，如果两个进程之间没有关系，那个管道无法工作
* 消息队列是可以多个不相干的进程通过一个消息队列来传递数据
* 消息队列里面的数据可以是结构化的字节流，可以表示复杂信息
* 消息队列里面也是有空间限制的
  • 共享内存
    直接通讯方式
    如何让两个进程共享同一段内存？
    把同一块内存的物理地址映射到不同的进程的空间地址里面

    同步数据读写就要引入同步互质的机制

第十二章 文件系统

12.1基本概念

文件和文件系统

文件系统的功能

文件和文件块（头）

文件描述符

os内核里面包含一个表，是一个文件打开表。文件描述符是文件打开表的index

管理文件需要的数据：


访问模式


文件的结构

12.2 目录

目录的操作


读写都是应用发出请求，由os去完成

12.3文件系统

12.4虚拟文件系统


文件系统基本数据结构：


vol卷控制块，dir目录节点，file文件控制块

文件系统的数据结构都会映射到磁盘的扇区。

12.5文件缓存


基于分页的缓存方式

这里的替换也需要算法去完成

12.6打开文件的数据结构


  1. 查找文件再把文件控制块放进内存中，然后把信息放进文件表里面
  2. 然后打开进程的文件表，找到index，找到一个项
  3. 根据这个项，再去打开系统文件表，再去找到文件/目录
  4. 在disk找到文件数据后，文件系统把数据放入内存中的缓冲区，最后程序从缓冲区读取

文件锁的保护机制

12.7文件空间分配

分配方法：

  • 连续分配

    修改文件空间困难

  • 链式分配

  • 索引分配

    只要把索引块调入内存中，就可以找到相应的文件位置；
    索引会增加开销，如果文件过大，就需要多级索引

评价指标：

  • 存储空间利用
  • 访问速度

12.8空闲空间的管理

位图管理法

扫描开销=n/r

为了保证位图的一致性，防止位图的01表示和实际的操作不符合

先磁盘再内存

12.9多磁盘管理-RAID

第一代做法

改进

避免对parity disk 的频繁读写，继续改进，把校验均匀地分布在每个盘，基于block来校验，不是bit

12.10磁盘的调度

这块感兴趣的可以自己去了解

—****************************************************************************************************--------
理论部分完结撒花！
我选这门课的原因就是这门课适合小白入门，如果你是有相关基础的，我觉得可以直接上手lab去实现这样更加深刻，比如南京大学蒋老师的操作系统涉及与实现，真的硬核，第二节就讲代码。或者是可以参考操作系统真相还原这本书籍来直接敲（csdn有很多资料可以参考）。接下来，我应该会把清华的这个课程lab给尝试实现一下，再去学下哈工大老师的操作系统课程。因为我不喜欢配环境，有时候，配环境一个下午都没弄好，就挺烦的。

最后：我这里大部分内容都是搬运这位前辈的博客内容但是他后面缺失了一部分。

本文标签： 清华大学入门操作系统课程

版权声明：本文标题：操作系统入门—参考清华大学的课程 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1728047327a1143317.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。