操作系统高级课程-笔记

Posted on | Post modified: | In | | Visitors:

This is my notes on OS course, if there’s any kind of privacy issues or legal problems, please contact me to take it down.

引言

Course Introduction

operating systems advanced class
会比本科的操作系统更难，进阶
建议本科没学过操作系统的同学选修
研究生阶段 - 补充短板，打好基础

系统能力培养

程序性开发能力→系统性设计能力
解决复杂工程问题的基本能力
综合能力 >> coding
系统：若干相互关联的部件有机结合在一起，具有一定功能。

三个层次：

  1. 本课：基础系统
  2. 专门系统 计算机领域系统
  3. 应用系统

问题：

缺乏整体系统整体能力，缺少知识关联，实践能力差

教学目的：

  1. 深入理解操作系统：阅读源码
    1.1. 全局结构
    1.2. 内部工作方式
    1.3. 数据结构和算法
    1.4. 发现问题，解决方案
    1.5. 典型技术和应用
    e.g. 数据结构-进程控制块PCB

    PCB包括：（以Linux为例）
    1）进程标识符（内部，外部）
    2）处理机的信息（通用寄存器，指令计数器，PSW，用户的栈指针）。
    3）进程调度信息（进程状态，进程的优先级，进程调度所需的其它信息，事件）
    4）进程控制信息（程序的数据的地址，资源清单，进程同步和通信机制，链接指针）
    能够提出问题、解决方案、折中

  2. 动手完成一个很小的模拟操作系统
  3. 提高总结凝练的能力

教学计划：

进程线程，运行机制，同步机制，虚存机制，文件系统
XV6源代码阅读
实例：Windows，Linux
实验 Nachos
华文慕课

课程环节：

Nachos实习笔试(5.20 开卷-编程+简答)、期末Nachos实习面测(选)，期末笔试
分值：
Nachos实习报告24(格式规范、按时提交、内容质量，注重个人心得体会，注重实作) Nachos笔试10 (可选面测弥补) XV6代码阅读报告16 课堂参与10
期末40闭卷
创新实践、特色实践+1~10 (可选题目，加到平时分)

参考书：

教材（选用哪一本都可以）
•Modern Operating System Andrew S. Tanenbaum
•现代操作系统（第4版）陈向群等译机械工业出版社
相关参考书目
•Windows内核原理与实现潘爱民电子工业出版社
•Linux内核设计与实现[美] R.Love著，陈莉君译机械工业出版社
•深入理解计算机系统[美]R.E. Bryant等著龚奕利雷迎春译机械工业出版社

Nachos操作系统

UC Berkeley教学用操作系统 使用C++编写，也可以用java（改写5.0j）PintOS（C,可运行于x86-硬件需要C语言）
使用3.4稳定版本 latest 4.1
（JOS by MIT 也是教学用操作系统）
不真正运行于硬件，模拟了一个==MIPS模拟器==
可拓展功能，可移植到其它架构（可以真正运行于硬件上）

e.g. 线程切换

（Nachos中只有线程）实际只是命名问题
关键：保存和恢复线程的上下文环境(context)(使用的寄存器-CPU中) e.g. PC, PSW (程序状态字/程序状态寄存器, Program Status Word)…
使用汇编编写完成-与硬件打交道需要汇编，高级语言难以实现

1
2
movl x,x #保存现场
movl x,x #恢复现场

Nachos体系结构

Linux宿主机上的一个进程，一个应用程序
分为3层：MIPS模拟器，Nachos操作系统，Nachos应用程序（C程序，在x86平台上交叉编译-MIPS指令集）
不涉及真正硬件）底层为Host OS和真正硬件

实习要求

0环境+6+7,8附加

Nachos系统源代码树结构

见PPT0 page31

XV6

能够真正运行于硬件的简单操作系统，基于x86架构，Unix-like
本课需要阅读源代码，小组每周讨论

课程目标

典型名词术语

高速缓存 vs TLB vs 块高速缓存(Linux)/文件缓存(Windows)

  1. 高速缓存
    CPU Cache(高速缓存) 分级为 L1 L2 L3
    （多核CPU中，可能每核具有L1 L2，L3共用 ==correct me if I’m wrong==）
    依次命中
  2. TLB
    = Translation Lookaside Buffer 传输后备缓冲器
    是内存管理单元MMU用于改进虚拟地址到物理地址转换速度的缓存，位于MMU中
    MMU中包含页表地址寄存器，记录了页表本身的存放位置，位于CPU中；页表位于物理内存中，由很多页表项组成，页表项并不是包含具体物理地址的单元，此页表项只是给出页表描述符的地址，描述符当中给出物理地址的部分内容，再加上虚拟地址当中的部分内容就得到了具体的物理地址；TLB位于MMU中。

    MMU是，在中央处理器CPU中用来管理虚拟存储器、物理存储器的控制线路，同时也负责虚拟地址映射为物理地址，以及提供硬件机制的内存访问授权，多用户多进程操作系统。

在计算机技术中，把内存中的程序段复制回辅存的做法叫做“换出”，而把辅存中程序段映射到内存的做法叫做“换入”。经过不断有目的的换入和换出，处理器就可以运行一个大于实际物理内存的应用程序了。或者说，处理器似乎是拥有了一个大于实际物理内存的内存空间。于是，这个存储空间叫做虚拟内存空间，而把真正的内存叫做实际物理内存，或简称为物理内存。
一个应用程序从编写到被执行，需要进行两次映射。第一次是映射到虚拟内存空间，第二次时映射到物理内存空间。在计算机系统中，第两次映射的工作是由硬件和软件共同来完成的。承担这个任务的硬件部分叫做存储管理单元MMU，软件部分就是操作系统的内存管理模块了。
在映射工作中，为了记录程序段占用物理内存的情况，操作系统的内存管理模块需要建立一个表格，该表格以虚拟地址为索引，记录了程序段所占用的物理内存的物理地址。这个虚拟地址/物理地址记录表，即页表便是存储管理单元MMU把虚拟地址转化为实际物理地址的依据。
Yngz_Miao https://blog.csdn.net/qq_38410730/article/details/81036768

  1. 块高速缓存
    为了解决读取物理存储（盘）较慢的问题，在内存中设置块缓存，存储经常读取的磁盘内容。==correct me if i’m wrong==

    与内存页相比，块不仅比较小（大多数情况下），而且长度可变的，依赖于使用的块设备（或文件系统）。随着日渐倾向于使用基于页操作实现的通用文件存取方法，块缓存作为中枢系统缓存的重要性已经逐渐失去。主要的缓存任务现在由页缓存承担。另外，基于块的I/O的标准数据结构，现在已经不再是缓冲区，而是struct bio结构。
    bullbat https://blog.csdn.net/bullbat/article/details/7306178

  2. Web Page Cache
    同样地，Web Server中，网页存储在磁盘中，读取速度较慢。在内存中开辟 Web page cache存取访问量大的网页。==correct me if i’m wrong==

    其它典型名词术语 E.G.

    Multiprogramming
    PCB
    Starvation 进程调度-饥饿算法
    Page replacement
    Time-sharing
    Context switch
    Preemptive
    Temporal locality
    Booting
    Thread
    Priority
    Programmed I/O
    Protection
    Multithreading
    Deadlock
    DMA
    Privileged instruction
    Scheduling
    Wait-for graph
    Buffer
    Exception
    Synchronization
    Virtual memory
    RAID
    Fault
    Data race
    Paging
    Disk cache
    System call
    Mutual exclusion
    Virtual address
    File
    Interrupt
    Critical section
    Swapping
    Directory
    Process
    Atomic operation
    Page table
    Device driver
    Execution state
    Lock
    TLB
    Pagefault
    Address space
    Semaphore
    Shared address space
    Spatial locality

    回顾知识点

    •存储器层次结构
    •局部性原理
    Cache，在内存缓存磁盘块，Web Cache
    •异常控制流
    中断、陷阱、故障、系统调用、内核/用户模式
    •进程、线程
    •并发：同步与通信机制、死锁
    •虚存
    页表、TLB、地址翻译（地址转换）、Page fault
    内存映射

    操作系统

    地位

    应用程序 👈终端用户
    系统功能调用 👈应用软件设计者
    操作系统 👈应用软件设计者
    计算机硬件 👈操作系统设计者

    名称

    软件越来越重要，从Monitor(Supervisor)→Operating System

    Helloworld 程序运行时操作系统作用

  3. 用户告诉操作系统执行HelloWorld程序
    键盘输入指令(./filename) / 可视化界面下双击执行？==correct me if i’m wrong==

  4. 操作系统：找到helloworld程序的相关信息，检查其类型是否是可执行文件；并通过程序首部信息，确定代码和数据在可执行文件中的位置并计算出对应的磁盘块地址
    Linux/Unix 中可执行文件为 elf 类型（Windows中为PE）

    ELF(Executable and Linking Format)是一种对象文件的格式，用于定义不同类型的对象文件(Object files)中都放了什么东西、以及都以什么样的格式去放这些东西。它自最早在 System V 系统上出现后，被 xNIX 世界所广泛接受，作为缺省的二进制文件格式来使用。可以说，ELF是构成众多xNIX系统的基础之一。
    ELF文件有三种类型：

    • 可重定位的对象文件(Relocatable file) 由汇编器汇编生成的 .o 文件
    • 可执行的对象文件(Executable file) 可执行应用程序
    • 可被共享的对象文件(Shared object file) 动态库文件，也即 .so 文件

PE是目前Windows平台上主流的可执行文件格式，包括常见的可执行程序EXE文件、动态链接库DLL文件等。

Linux/Unix 文件开头几个字节为Magic Number，在每种特定文件类型中是唯一的

Magic numbers are the first few bytes of a file which are unique to a particular file type.

  1. 操作系统：创建一个新进程，将HelloWorld可执行文件映射到该进程结构，表示由该进程执行helloworld程序。
    创建数据结构(PCB)并填写==correct me if i’m wrong==

(3.5. 调度程序-看不见的手
进程创建成功后控制权属于调度程序，等待调度后才可执行）

  1. (调度程序选中HelloWorld后) 操作系统：为helloworld程序设置cpu上下文环境，并跳到程序开始处。

  2. 执行helloworld程序的第一条指令，发生缺页异常
    程序未被读入内存中

6操作系统：分配一页物理内存，并将代码从磁盘读入内存，然后继续执行helloworld程序

7helloword程序执行puts函数（系统调用），在显示器上写一字符串

8操作系统：找到要将字符串送往的显示设备，通常设备是由一个进程控制的，所以，操作系统将要写的字符串送给该进程

9操作系统：控制设备的进程告诉设备的窗口系统，它要显示该字符串，窗口系统确定这是一个合法的操作，然后将字符串转换成像素，将像素写入设备的存储映像区

10视频硬件将像素转换成显示器可接收和一组控制数据信号

11显示器解释信号，激发液晶屏

作业

复习本课内容，下载XV6源码，完成Lab0（环境搭建，阅读源码，编写程序）

处理器调度

三个层次

3种调度位置

  1. 短程调度(进程调度)

    从就绪队列(内存用户态区)调度到CPU

    CPU调度是短程调度-选进程,送入CPU-最底层

  2. 中程调度(交换调度)

    调整进程在内存中的存在数量和时机,将处于外存交换区中的就绪状态或等待状态的进程调入内存,或把处于内存就绪状态或内存等待状态的进程交换到外存交换区

    一般是挂起状态进程的调度

  3. 长程调度(作业调度,高级调度)

    从外存(可能)批量,为其建立进程,调度到内存

    三级调度

处理器调度

基本认识:按一定调度算法,选一个,给CPU使用权

若无就绪进程,系统空闲进程/闲逛进程/idle进程,不属于用户,执行空指令-占座-CPU周而复始运作

调度程序:内核函数,决策-挑选就绪进程

  1. What 调度算法
  2. When 调度时机
  3. W

CPU调度时机

事件:进程运行过程中有很多事件

事件发生后→进程暂停→硬件机制响应→进入操作系统-内核处理相应事件→处理完后-格局变化(可能进程状态改变,可能创建了新进程)

4种调度时机-总结:内核对中断/异常/系统调用处理后返回用户态时

进程切换

可能是刚刚暂停执行的进程/新进程

被换入的进程:事件发生后,当前进程的内容context被放入内核栈(系统栈)中-栈是临时存储,PCB是长久存储-数据结构

若恢复该进程,从栈中弹出,否则若切换另一个进程,将栈中内容放入PCB中

新选入进程的上下文context在PCB中,若被选中,将其内容取出

  1. 切换全局页目录

    每个进程有不同地址空间,加载新地址空间

    全局页目录:指向地址空间的物理地址的指针(Intel中CR3)

  2. 切换内核栈和上下文

步骤

(A下CPU,B上CPU)

  1. 保存进程A上下文到PCB中
  2. 更新A的PCB
  3. 将A移到合适对垒

上下文切换开销

寄存器存取时间

  1. 直接开销

    内核完成切换的CPU时间:保存恢复寄存器,切换地址空间

    (不同指令的代价不同-时间也不同

  2. 间接开销

    高速缓存cache,缓冲区缓存buffer cache,TLB(进程页表的部分表项)清空

    肯定不会命中,所以开销大

    了解Cache工作原理

调度算法

不同操作系统-不同难易-需要考虑完成的任务不同

需要在PCB中记录跟CPU调度有关的信息-用于调度

优先级和优先数

优先数并不一定是越大越高,只是指标,所以一般说优先级-是更显著的指标

优先级:动态-过程中动态变化;静态-运行过程中不变

就绪队列组织

抢占&非抢占

抢占:有更高优先级就绪,系统就强行剥夺CPU

靠中断-异常-系统调用,实际就是切换 具体是由调度程序执行

非抢占:进程不想下CPU就可以不下CPU

I/O密集型/CPU密集型进程

一般操作系统对IO密集型更友好

时间片

长/短 固定/可变

不同调度算法

  1. 短作业优先SJF

    可以抢占(有更短的立刻上CPU)/非抢占(在就绪对列中选短)-各有利弊

    所以进程同时可运行时SJF可得到最短平均等待时间

  2. 最高响应比优先HRRN

    计算响应比R,抢占+非抢占折中

  3. 时间片轮转RR

    周期性切换-时间片

    时间片长短-

    对不同大小进程-有利

    对相同大小的进程(2*100ms)-切换失去意义: 平均为199.5ms;若FCFS则平均150ms

  4. 虚拟轮转VIRTUAL RR

    原本:时间片到-回到就绪;等待IO-回到等待队列-IO好了之后回到就绪队列

    优待IO型进程(主动放弃CPU),将IO等待的进程专开一个队列,先从这个队列中选择进程上CPU(认为可能还会主动放弃CPU

  5. 最高优先级

    系统>用户

    前台>后台

    IO密集>CPU密集

    静态/动态优先级

    饥饿问题

    可能会优先级反转

    优先级反转/反置

    抢占式会出现

    L进入临界区操作(原语),被抢占,但是临界区中不可打断,因此H被阻塞,M反而上CPU执行,若M为CPU密集,LR都不能执行

    e.g. 美国火星探测器天气预报为M,地面重启系统

    解决

    1. 优先级天花板协议
    2. 优先级继承:低优先级提升
    3. 使用中断禁止-低优先级临界区中不可被打断

  6. 多级队列

    多级反馈队列

    重点

    多个就绪队列-级别依次降低,进队都是进第一个,用完时间片下CPU后下降一级;由于阻塞下CPU会原级队列(可以队首/队尾),重上CPU时上次时间片的处理(可以保留/抛弃)(均是设计者对IO型的友好程度)

    总是对IO密集型友好

    不同级队列时间片长度不同,级别高-时间片短

    优先调第一级

    各级队列按时间片轮转

  1. 最短进程≈段作业

一个例子

最短剩余时间优先-最适合此例

典型系统

Windows

很像 多级反馈队列

时间配额≈时间片,大小可变

区别多级反馈队列-其队列是按照进程优先级分配的

线程优先级:

  1. 实时优先级

    不可变

调度策略:

  1. 主动切换

    主动转到阻塞态

  2. 抢占

    高优先级的从阻塞态中唤醒-抢占

    则低优先级被强占的回到原优先级队列队首,若实时优先级,重置完整配额;否则执行其剩余时间

优先级提升&时间配额调整

漏洞/瑕疵:饥饿等问题

  1. IO操作完成

    提升值写在文件中

    且时间配额每次-1

  2. 饥饿线程

    排队>300时间周期 平衡集管理器(还有其他工作)1s写一次,扫描一次就绪队列,将优先级提到最高15,时间配额为正常值*4,用完时间配额后优先级恢复原状

Linux CFS

中断/异常

态:

用户态/内核态

在x86中对应R0/R3(操作系统只需要两个,可能虚拟机等需要…)

中断向量表:

操作系统

  • 对下 依据硬件 物理机器界面
  • 对上 提供接口 虚拟机器界面

异常控制流 ECF

指令上CPU后就会顺序执行,传统程序都是顺序的,后来加入分支/循环-均属于异常控制流,再后来加入函数调用-就是控制流改变

ECF是使整个系统转起来的关键,理解整个系统如何工作

用户应用程序不断调用OS(系统调用)完成任务,在再返回

异常/中断有区别

CPU

平时声明的变量是内存-用寄存器更快

寄存器:用户可见/控制和状态(仅OS可用

硬件机制:防止OS具有所有权限? CPU需要支持特权状态(硬件机制)

CPU的不同状态2/3/4 PSW中的一位

e.g. x86中EFLAGS寄存器 IO PL记录特权级, IF TF辅助位

操作系统只需要两个态:用户态,内核态

开关中断,内存清零,修改程序状态字都是特权指令

仿管指令=陷入指令(maybe int/trap/syscall/…),提供给用户程序的接口,用于调用OS的功能重要但是都需要访问? 非特权指令

状态转换

中断/异常/陷入机制 用户态进入内核态的唯一路径

调度(决定是否需要换状态),设置程序状态字PSW 用内核态回用户态

中断/异常机制

  • 中断,为了支持CPU和设备之间的并行操作(CPU启动设备后,设备可以独立工作

  • 异常:CPU执行指令时本身出现的问题,系统调用,page fault,…

(也可能分别叫外中断/内中断)

通过硬件与软件结合实现

现在应该叫中断/异常机制 CPU对系统发生的某个事件作出的一种反应,保留现场,自动转去(硬件的机制实现-OS与硬件紧密结合的约定)执行相应的事件的处理程序,处理完后返回断点继续执行调度,在以后某个时刻,等待被调度上后继续执行

中断

陷入trap: 返回到下一条

故障fault: 返回原指令?

执行完一条指令,(会对中断进行检查,若有中断将中断码送入PSW相应位,设置中断向量),在响应下一条指令前-响应中断,响应后(被重新调度后)回到下一条指令

中断向量

内存单元,放入中断处理程序的入口地址和程序运行所需的处理机状态字,指向一段对应的中断处理程序

硬件完成-按中断码,找中断向量表(一般在内存低地址位置-硬件知晓)(linux中系统调用在128)

中断响应

栈分为 用户栈,内核栈-只有一个栈指针,出于什么态就指向哪里

硬件将中断先放入中断装置中,CPU在执行完指令后检查中断,

硬件保存现场(发生中断时,硬件将PSW和PC推入栈中,其他的由软件负责推入栈)

硬件根据中断码查表,PC变为处理程序的入口地址,把中断处理程序…硬件将CPU控制权交给中断处理程序

中断处理程序由软件(前面都是硬件)完成

…

中断处理程序

(设计OS时就编写好的)

保存相关寄存器信息(堆栈),分析原因(根据状态码),执行处理,恢复现场继续执行(要等调度后,若直接调度到-从栈中取/若没被调度,放入PCB)

I/O中断:正常(完成)/异常(错误)

x86的中断处理

中断:硬件信号引发的 有中断码,异步处理

异常:指令执行引发的 无编码,但x86中对有些异常会产生硬件出错码

中断向量/中断描述符/门描述符(-linux,只用中断门()进来后禁止中断,关门)&陷阱门(不会关门))都是数据结构,相似东西

系统调用:异常的一种,用户态进入内核态的唯一入口

保护模式:寻址-全局描述符表中段描述符中的基地址+中断描述符中(16+16)偏移量???

系统调用

用户编程时可以调用的操作系统的功能,从用户态->内核态

应用程序可以直接调系统调用,也可以通过库函数/API调用系统调用

内核函数:可能对应多个系统调用

e.g. printf()->系统调用的write()

可能有很多系统调用,但都通过中断向量表中的某一行进入-选择一条特殊指令作为陷入指令-每个系统调用具有编号和参数-每个系统调用的服务代码有入口地址,位于

参数传递

  • 只有一个指令进入系统调用,由这个陷入指令携带的参数长度有限

  • 所以用通用寄存器-用户可见寄存器,用户内核可访问,好方法

  • 内存中开辟专门堆栈区-麻烦

编号放在一个专用寄存器中,eax存放,还有其他参数推入寄存器

  1. int $0x80 特殊陷入指令:硬件保护现场,硬件查中断向量表-其中填写的是系统调用的总入口程序

  2. 系统调用总入口程序:软件保护现场(内核堆栈) 根据eax查系统调用表

  3. 执行系统调用
  4. 恢复现场…

15 陷阱门,不关门,还可以进来新的系统调用

3

栈指针,四级,每级都有SS ESP栈指针,用哪级就从TSS中装哪个

system_call 系统调用总入口,

eax回去的时候存返回值

crl+C 中断 其实就是向进程发信号-Q(uit)

need_resched 是否需要重新调度-信号

Nachos

Makefile

规定了依赖关系,顺序,把Makefile基本看懂

Nachos框架

  1. 内核几部分-全局变量
  2. 添加HelloWorld测试?
  3. 启动的流程 函数mian initi threadtest…
  4. 线程

…

下次课

文件系统

0%