Posted Updated Course2 days read (About 335761 words)

2023春季学期 操作系统 期中期末复习笔记

3-2

API App Programming Interface

BI 二进制接口

ABI 应用程序可以使用的OS提供orAEE提供的服务

SBI 操作系统可以使用的硬件服务

EE 执行环境 HAL硬件抽象层

图片

左：类似遥控器、蓝牙耳机，非常简单的小设备，不需要通用性。不需要操作系统直接工作在硬件提供的AEE环境中

中：传统的基于操作系统的架构

右：多os服务器，基于虚拟机

简单小设备，专用（蓝牙耳机、遥控器）Mmode写死——嵌入式设备，需要偶尔更新，独立性（信用卡刷卡机）U+M——移动电话USM——数据中心服务器USHM Hypervisor

硬件线程 Hart 相当于处理器的一个core

图片

User 基本计算，不能用硬件、特权，不能影响其他app

Supervisor|Kernel 足够的硬件操纵能力；限制APP执行访问；kernel特权级，影响应用程序

Hypervisor|VM 限制OS的访存；影响OS

Machine|PM 控制物理内存、关机；LibOS实验的编程模式；BootLoader BIOS 影响上层软件

csr寄存器

最多4096个CSR

三态编程

怎么实现断点和单步跟踪的调试？？？

3-3 批处理操作系统

把APP和OS彻底隔离开，APP执行完后让os知晓并引导加载下一个app。

LIBOS

  • 隔离应用和硬件
  • 简化应用访问硬件的难度和复杂性
    8040是用户库入口，初始化后进入app主程序

LabNotes

Lab1

syscall通用

syscall_write 指定调用id和安排寄存器等等

lib中进一步封装为write，像是std

console中通过宏直接包装成println

在加载用户态程序到80400000时，由于修改了Imem部分的内存。Icache以为其对应的指令部分内存是不能改变的，但是这里我们注入新app指令导致必须清空icache。否则导致缓存和数据不一致

更改内存时候一定刷新对应cache的内容

异常处理

  • alltraps 保存上下文
  • rust traphandler

0414-0417 Midterm Review

Lect1

控制：给app提供服务，防止错误，方便用户

资源管理：管理 服务 解决访问冲突

并发、共享、虚拟、异步

个人电脑不那么重视CPU利用率，而是与用户交互的友好

分布式系统，关注系统利用率、网络存储计算效率 走向网络

MS-DOS 应用系统混杂，汇编

单体分层：硬件驱动到用户界面

微内核：尽可能把内核功能移到用户空间，内核提供基础服务，即对端的高层实现。用户模块用消息传递通信，灵活但是性能差。里面都是LPC和HAL

外核：保护与控制分离，应用管理资源，功能都交给APP实现？？？

虚拟机：VMM平台上面跑很多虚拟机，是计算机的副本

fork创建进程返回子进程PID，如果自己是子进程返回0

exit|wait等待子进程

kill getpid

sleep exec不返回，用这个新文件取代当前进程，丢弃当前data和instr

可以forkexec

sbrk 增加进程内存n个字节，返回新内存的开始addr

open write read close dup

pipe创建管道相当于两个fd，fd1写入 fd2读取

chdir更改当前目录

man命令 1查shell命令 2查系统调用 后面跟名字

fork中

Lect2

LibOS以库形式提供给应用程序

批处理：内存单道但自动加载一个个

多道：内存多道，依次执行

分时多任务：轮流执行

地址空间抽象：内存空间隔离 超越物理内存

进城抽象：动态创建 多处理器并行

文件抽象：便捷持久存储

2-3 硬件软件启动BOOT

qemu bios一小段汇编初始化

开机进入bootloader即rustsbi-qemu.bin 加载os

loader target即开机用bootloader家在什么东西，加载到80200000开始的地方

2-4 LibOS

以库的形式实现OS，上面是APP

栈帧最开始一般是ra和prev fp上一个栈帧的起始地址。

进入某函数先在栈中保存ra，属于prologue

Lect3 特权级隔离与批处理

3-1

硬件和OS中间是指令集和寄存器，系统调用是os和app的边界——安全

隔离的好处：程序监控破坏另一程序；程序破坏系统；恶意程序病毒bug

每个程序不影响其他程序和os的执行和信息，但也需要共享数据和资源，建立边界

软件|硬件|网络的隔离；控制|数据|时间|破坏隔离——特权级|地址空间|中断处理|异常处理

异步中断，同步异常，中断可以不来自运行的某一条指令，来自外设、时钟等

中断，执行完当前指令后转移到中断处理，然后去下一条指令。用户透明

异常，处理后恢复到本条指令

系统调用，同步异步都行，恢复到下一条指令，属于广义的（同步）中断，但是硬件上为异常的处理

3-2 OS看RV

APP ABI OS SBI SEE HAL Hardware

Umode 非特权级模式

Smode 特权级模式，足够的硬件控制能力，可以限制APP，影响app执行

Hmode 限制OS的内存空间，影响OS

Mmode 限制一切os和软件 bootloader或者bios 最主要是拦截处理中断异常 要求精确异常处理，之前完整执行+之后没执行

高特权可以委托低特权模式软件处理中断

CSRs非特权指令不可访问 4096个最多 用户态大部分不可访问

tvec 向量表，指示跳转目标

epc 发生trap的地址

cause 种类：是否中断+code

ie 中断使能

ip 中断请求（等待处理）

tval trap的value附加信息

scratch用于存放信息

status 跟踪记录当前硬件线程的状态；保存全局中断和其他状态。比如之前的特权级，控制全局中断的禁用和恢复

fence.i 非特权指令

中断标记 硬件设置，调用服务。软件保存，处理，清楚标记后恢复

开销：建立中断异常和对应服务；内核堆栈建立；验证系统调用参数；内核态用户态数据拷贝；内存状态改变后刷新TLB和Cache

硬件响应

默认都导向Mmode，但是M可以重新导向Smode。RV可以直接中断异常委托机制来把一些中单直接交给S绕过M。如mideleg和medeleg 设置1就把对应的中断异常直接委托S

  • 存epc（异常指令or应跳转到的位置），跳转到tvec

  • 设置mcause 设置mtval比如出错地址

  • status的MIEorSIE为0禁用中断保证原子操作，MPIE留之前的。记录之前的权限到MPP或者SPP
    satp

  • mode 开启分页 页表级数

  • ASID 可选，避免进程切换刷新TLB

  • PPN 根页表物理页号

3-3 实践 批处理操作系统 ch2 BatchOS

自动加载运行多个程序

硬件特权级保护来保护os

ebreak指令专门产生异常来调试，断点陷入异常

应用程序地址从8040开始

加载应用程序后必须清理icache

内核栈与用户栈，换栈

使用scratch作为中转

Trap上下文

CTX：32个通用寄存器 status和sepc

  • 在ecall之后瞬间改变了sepc等几个csr，进入traphandler

  • 在__alltraps瞬间换到内核栈

  • 保存除了sp和tp之外所有reg到内核栈，以及sepc和status，然后是scratch中的usersp，把此sp指向ctx作为a0参数调用traphandler分发执行

  • 在内核栈上处理此trap

  • __restore恢复ctx后sret回去
    应用切换 runnextapp

  • 构造一个trapctx 其中sepc为8040，sp设置为用户栈

  • 把以上ctx压入当前的内核栈并传入restore的顶指针，其实就是栈顶

  • restore恢复并换栈

    • 栈顶设为a0
    • 从内核栈载入status和sepc，把用户栈sp存入scratch
    • 恢复除了sp tp之外的reg，释放sp
    • 换为用户栈
    • sret

Lect4 10-12

4-1 进程和进程模型

内存驻留多个各执行程序共享cpu，协作调度（yield）os不会打断；抢占式：进程被动放弃，时间片轮转使用，硬件中断

进程==任务！=Job

Task = 程序+执行状态（控制流 数据 上下文），需要cpu+内存

TCB任务控制块orPCB进程控制块

进程状态：未初始化 就绪空闲 执行中 已退出

4-2 实践 多道和分时多任务 ch3 MultiProgOS

每个应用的addr都不同，大概是base+0x20000*index

在内核初始化的时候就被加载到这些base处

TaskCTX 保存执行状态的上下文，包括ra sp callee saved，并不存在stack中而是在memory 数据段，非动态分配的。这里的ra是switch的返回地址即上次任务切换发生的指令

这里的sp是task对应的内核栈

switch不涉及特权级切换，一直在Smode，只保存calleesaved

使用switch切换，kernel会切换trap控制流，和普通函数的区别是会换栈，相当于usercodes中间call switch函数…

为什么call switch的时候sp在内核栈上？？？——这时候存的寄存器都是trap后的？

  • 保存信息到TCB的task ctx，存到a0对应的位置上，包括把sp和ra以及12regs存进去
  • 读取下一个taskctx指向的taskB，恢复这个ctx的ra sp和s0与s11
  • 之后sp已经指向了B的kernelstack ret到ra
    普通控制流：程序执行序列

异常控制流：os程序员，控制流突变，执行环境切换Trap

控制流会对应上下文ctx，如函数调用在userstack存栈帧，trap处理在内核栈存trapctx，任务切换在osdata存taskctx

时钟中断和计时器，硬件提供了settimmer在某个时刻发生中断的功能。

Lect5 物理内存管理12-14

5-1地址空间

逻辑地址：CPU执行指令时的地址，编程地址

LA ——段内存转换——VA——页内存转换——PA

作用：抽象方便；保护安全；共享；更大虚拟化；外存缓存高效；隔离简化

编译-加载-执行三次生成地址，编译时假设base已知，如果未知生成可重定位代码。加载时生成绝对（虚拟）地址

ALU等cpu内部需要逻辑地址，MMU转换PA，总线上是PA请求

MMU地址|权限检查，产生异常

5-2内存分配

静态分配——编译时分配，全局or静态变量和代码

动态——运行时分配，局部变量，malloc和free。隐式分配语言编译器会自动帮你释放free掉不同的malloc内存如java。

栈是编译器管理，隐式，拿起来用不用还，编译时确定

堆是程序员需要显式管理的，alloc和free需要等量成对使用

连续内存分配 如malloc

内存碎片：外碎片 分配单元间未被使用 内碎片 分配单元内

动态分区分配：分配进程指定大小可变的连续内存块block。操作系统需要维护分配的分区和空闲分区

策略

  • 最先匹配：空闲分区按地址顺序排序；分配时候够了就分配；释放时检查附近的空闲分区合并
    • 简单快；高地址有大块空闲区
    • 很多外碎片；大块分配很慢需要往高检索
  • 最佳匹配：按大小排序组织；查找合适的分区；释放时合并临近分区
    • 小尺寸申请密集，效果好；避免大分区被拆分；减小外碎片；简单
    • 外碎片仍然有；释放分区慢（组织复杂）；无用小碎片多
  • 最差匹配：按大小排序，优先给最大分区；释放时合并相邻并调整顺序
    • 中等大小表现好；小碎片少
    • 释放分区慢；外碎片多；破坏大空闲分区
      伙伴系统分配

快速分配释放并不产生外碎片，组织成二维数组，其实是每个块标记长度和起始地址，随时被二分。空闲块和分配块各是一个按addr有序的vector

合并条件：等长相邻且合并后对齐

非连续内存分配

  • 即使不连续的物理页也通过页表变成连续的虚拟页，解决碎片

  • 一般申请较大的内存空间，很难连续分配

  • 提高效率和灵活性——非连续；可共享；动态加载链接
    段式管理：内核管理段表，对应进程

  • cpu给出逻辑地址包含段号+段内偏移

  • 查找os段表找到该段baseaddr和length，check合法
    页式管理：内核管理页表，对应进程，需多次访存 TLB+Cache加速

多级页表来减小页表长度

基于hash的反置页表

根据物理地址来生成页表项，每个页表项对应一页物理地址。需要进程号表示地址空间以及存储虚页号。索引通过pid+vpn来哈希找offset

容易产生hash collision，用next字段来解决，一直next直到正确vpn图片

段页式内存管理：段表找页号，页表找pa

完整例子

  • usercode malloc
  • userlib会管理内存池？？？
    • 如果有空间直接分配给app
    • 如果没空间使用syssbrk申请扩展自己的内存池，os申请几片新的物理内存映射到自己的连续虚存然后分配给lib库

5-3 实践地址空间OS ch4 ASOS

不同app统一entry addr

app地址空间，有关联但不一定连续的逻辑段segment

跳板页

app和kernel的跳板部分，VA相同，映射相同，放置trapS

特权级过渡时CPU到alltraps入口切换页表仍然平滑运行，包括restore也换页表但不影响正常运行

这时需要换页表和换栈，通过scratch中转什么？

  • 如果还是中转两个栈：则换栈之后，在app页表下查内核栈地址错误
  • 中转用户栈和页表base：获取内核栈需要破坏genreg
  • 用户栈/Trapctx：保存regs到ctx？？？需要看实现这里如何在用户地址空间查找ctx，读出内核页表base和traphandler，换页表并跳traphandler

应用地址空间

linker的时候base0x10000

虚地址0x0开始text… 注意bss和stack中间有guard防止越界。最高4k是跳板，次高一页是自己的trapcontext，也就是trapctx在内核和用户空间都有映射。

内核地址空间

页表中含有所有cpu能看到的内存

80000000-88000000除了内核代码和数据，剩下以页帧形式管理起来，随时分配回收采用连续内存动态分配，alloc

SV39三级页表，每个节点在一个物理页中，即单个页表可以4k大小pte为8B下可以控制512个页，即1个页管理512页。两种映射方式，恒等和随机，

TCB中保存：

  • MemorySet地址空间
    • 若干MapArea逻辑段
      • 连续VPN范围
      • VPN-PPN映射kv，属于页表子集
      • 映射类型，恒等or随机
      • 此段的permission
    • PageTable页表，该set中任何vpn对应的ppn的kv
      • rootppn根节点物理页号
      • 实际页表页…

以上set一共占用的位置：此管理结构属于内核数据（被PCB内管理），然后页表占用页+页表管理的已分配页。前者被pagetable释放，后者被maparea释放！

新建set：创建页表，创建逻辑段向量。新建基本逻辑段压入页表：申请新页-更新页表项-更新maparea映射页帧

实现ASOS

  • 创建内核地址空间、内核页表。但内核地址空间低的几块都是identical映射，涉及不到申请。

  • 内核地址空间的控制数据结构set属于内核的全局数据段，保存在内核vadata也就是padata（identical）

  • 空闲物理内存按照类似heap进行分配管理，？？？区分heap和frameallocator

  • 这之前的操作是直接对物理地址进行操作的

  • 启用内核地址空间即激活satp
    切换特权级时借助跳板来平滑切换地址空间和栈

  • 跳板代码在全局pa的text段，但是在任何set中都是最高vpn虚页

  • sp切换到scratch即自己的次高页？Trapcontext

  • 在此ctx中保存regs和status epc

  • 读出kernel satp，va_sp和va_traphandler

  • 切换地址空间，切换内核栈

  • 跳转traphandler（物理页可能还在kernel的某个text段低位置）

    • 此时如果call，因为alltraps和traphandler都在物理内存的text低段。被编译器直接优化为偏移量寻址pc自增。而此时va自增并不对，这里的pa和pa虽然间隔小可以offset寻址但是va相隔很大（text和跳板）
      Trapctx：

  • 32gen regs status sepc

  • 内核页表pa 需要写入satp

  • app内核栈kernel va

  • traphandler的入口kernel va
    内核态下sscratch存放的是上次从app切换过来的时候的用户set下用户栈，用户态下存放自己的次高页即traphandler

TCB

  • taskctx

  • status

  • memoryset

  • trap context ppnTrap上下文的物理页？？？

  • base size应用数据大小？？？
    如何创建PCB即初始化app执行环境

  • 根据elf构造基础的虚拟地址空间，在tcb memset中

  • 建立内核栈？？？在哪建立

  • 建立TCB

  • 在用户地址空间构造Trap上下文？？？
    所以trapctx并不是在双空间都有映射，只在用户地址空间有。内核态想要访问需要去查用户页表

包括系统调用需要访问用户内存时，都要类似syswrite一样手动查页表找到物理页号，然后在内核页表中翻译为内核态虚地址。之后可以正常访问…

Lect6 虚拟存储——虚拟内存和交换空间，缺页

6-1 虚拟存储

一开始是程序员手动or os以程序为单位自动

虚存：os以页为单位自动换，在小内存上运行很大的程序

覆盖技术：程序分为功能独立的程序段，不要求同时装入内存的程序段组成一组共享主存的同一块区域。常用代码数据常驻，可选的需要时装入，按需求覆盖替换原来的。以模块函数为单位

程序调用关系中，root是最常用的，一个path需要同时驻留——需要程序员划分定覆盖关系，太复杂。时间换空间，装入的时候更慢

交换技术 OS自动换，以程序为单位，整个set都换出换入。考虑时机（内存不足）and重定位（保证正确寻址即可）为swap分区+

虚存的基础——程序具有局部性

  • 时间：指令数据的多次访问，都集中在某段短时间内

  • 空间：当前指令和一段时间内的指令or数据都在小区域内

  • 分支：跳转的两次执行大概率跳到相同内存位置
    装载只装载当前指令需要的部分页面段；缺页缺段则os调入；暂时不用的保存到外存；——虚拟页虚拟段来实现

  • 不连续，物理内存分配不连续；虚拟地址空间使用不连续？？？

  • 用户空间大与实际物理内存

  • 部分交换：只对部分虚拟地址空间调换
    在页式管理基础上：

  • 装载只装部分页面就启动，需要才调入

  • 需要但不在内存时候发起缺页异常（页表无效）——os调入内存使继续运行

    • OS查找外存对应内容
    • 物理页有空闲则直接调入
    • 否则用置换算法换出，valid0的ppn为外存的地址
    • 修改页表为有效以及对应物理页映射
    • 返回app重新执行异常指令

  • 内存不足时把部分页换出（页面置换）
    EAT 有效存储访问时间 = 不缺页率访存t + 缺页率访盘时间（1+写回概率即替换概率，缺页还需要先换出的时候）

6-2 局部页面置换 当前进程的物理页

减少换入换出 减少缺页 短期不用的调出，规定空闲内存上下限

下限开始回收，上限停止回收。

frame locking常驻内存的逻辑页，OS关键|要求速度的代码数据|页表中lock bit

OPT

tar 未来最长时间内不访问的页面；

imple 缺页时计算内存逻辑页的下一次访问时间

analysis 理想 不能实现 无法预测

FIFO

内存驻留最长被替换

维护内存逻辑页链表即队列，排着进排着出

简单；性能差（调出很经常的）；分配物理页多但缺页不减少（belady小聪明大糊涂）；不怎么用

LRU 最近许久没用

记录上一次访问时间，近似最优

  • 维护一个最近一次访问的链表，首节点是刚使用的。每次访存都移动到链表头；开销大
  • 活动页面栈：访问时压入并弹出所有同页号的，栈底为最少访问，开销大

Clock时钟页面置换

大致统计访问，是fifo和lru的折中 不调整但做标记，不访问的像LRU一样

imple pte中有acess访问位，页面成环形链表，指针指向最早调入的页面；访问的时候标记access，缺页替换从指针开始查找未被访问的页面，把访问位重置并挪动指针直到找到0的就换，指针也往前挪一个。

改进时钟置换

减少修改页的缺页开销，增加dirty修改位，描述写情况。因为dirty位需要写回。dirty了一定access了。这里描述有大问题

即保护a1d1的页面两轮才被置换：

  • a0d0立即置换标记10，指针后移
  • a1d0 - a0d0
  • a1d1 - a0d1 - a0d0

LFU最不常用置换

置换访问次数最少的

实现访问计数，访问+1，查找最小计数

开销大；开始狂用后面不用的页很难换；LRU关注时间 LFU关注次数

Belady

FIFO与动态特征矛盾，被换出去不一定是近期不用的

LRU动态调整，不存在belady

6-3 全局页面置换 所有可换出的物理页

为进程分配可变数目的物理页：进程对内存的需求动态变化；分配给进程的内存也应该变化；全局置换要确定分配给进程的物理页数目

程序运行和cpu利用是反对钩

工作集算法

W(t, △) 当前时间和工作集窗口（往前的窗口时间长度，τ为访存次数比如10就往前倒10次访存的逻辑页）

图片

常驻集：实际驻留内存的页面集合

工作集是固有性质，常驻集取决于os分配和置换算法。

工作集是常驻的子集时缺页少；工作集过渡期缺页多；常驻集达到一定数目后缺页率不会明显下降

换出不在工作集中的页面——维护窗口内访存页链表：访存和缺页置换都更新，也就是记录τ次访问的逻辑页，其他都被换出了

缺页率算法

缺页/访存 or 缺页间隔时间的倒数

看缺页率来调整进程常驻集，可以用缺页间隔T

访存设置访问标志即access1

缺页时计算上次到这次的缺页间隔，如果大于窗口则只保留last到current闭区间内访问过的页

如果小于等于窗口，则增加缺页到常驻集，直接加页

抖动问题

物理页太少不能包含工作集，大量缺页频繁置换，巨慢——因为进程太多物理页不够

高并发和缺页率平衡tradeoff

Lect7 16-20

7-1 进程管理

提高开发和执行效率——用户请求来创建执行暂停停止app——刻画os中程序运行的动态规律and管理调度多个程序的执行和资源使用

进程抽象给app：独占cpu，独占addr 资源占用和执行过程

一个程序的执行过程or执行程序的实例；具有一定独立功能的程序在某数据集合上的一次执行和资源使用的动态过程。。。

和Task的不同：simple process is task

  • 进程在过程中创建子进程fork waitpid getpid、用新程序内容覆盖已有内容（加载执行）exec

  • 执行中申请、使用、释放资源的载体
    进程控制块PCB

  • 进程上下文

    • trap上下文
    • 任务上下文
    • 地址空间管理
    • 进程内核栈

  • 进程id

  • progress status

  • 父子关系

  • 退出码
    os结构：

  • forkexec

  • helloworld

  • user_shell（输入forkexec helloworld？）

  • initproc（fork+exec shell waitpid等待shell）

  • OS Kernel
    fork：复制老爹的所有变量和内存，地址空间，赋值所有寄存器除了

wait属于系统调用，主动放弃处理器并返回子进程exit的值。os处理当有自己成存活时父进程主动放弃，等待结果。子进程exit后唤醒父进程返回给wait

僵尸：exit了但是没被父进程wait回收，wait时会立即返回

孤儿：父进程先退出没人回收了，由root回收

exit释放大部分资源但保留结果的值，检查父进程是否存活，如果没存活定位root父亲变孤儿，否则变僵尸

nice调用指定初始优先级，优先级会随时间降低

ptrace一个控制另一个进程执行，设置breakpoint，查看reg等

sleep的实现？？？

创建 就绪 运行 等待（sleep和wait） 退出五大状态转换

fork开销大，大部分伴随exec所以复制意义不大——vfork轻量fork让子进程赶紧exec

7-2 单处理器调度算法

处理机调度

调度器：挑选就绪队列中进程的内核函数，依据什么准则？

何时调度？

  • 进程运行到等待or就绪

  • 进程被kill

  • 进程主动放弃

  • 中断响应完成
    比较不同调度算法：一般低延迟-高带宽的tradeoff

  • CPU使用率

  • 吞吐量（单位时间完成进程数）

  • 周转时间：进程从初始化到结束（包括等待）的总时间

  • 就绪等待时间：就绪进程在队列中的总时间——高带宽

  • 响应时间：提交请求到响应的总时间（时间和波动）

  • 公平：进程占用等量的资源

先来先服务FCFS

进入就绪状态排列成队列，就绪队列下一个进程得到cpu，

指标是周转时间时，明显发现大任务堵在前面平均周转时间变长

简单

平均等待的波动大；短作业排在长进程后面很亏；IO资源和cpu资源利用率低（cpu密集进程导致io_idle也等待）

短作业优先调度SJF

选择队列执行时间最短的进程占用cpu，按照时间升序排序

好：最短平均周转时间！

坏：饥饿不公平，大任务无法获得资源；需要预知未来即任务规模，最简单就直接问用户，不能骗我否则kill你；历史预测：之前n次运行的加权平均，n次时间权重a之后每个都乘1-a的权重….其实是n次时间和上次预估的加权平这图没道理啊

最短剩余时间SRT

支持抢占 如果新就绪进程服务时间小于当前剩余时间就转

最高响应比优先算法HRRN

高响应比

7-3 实时调度

7-4 实践 进程操作系统

？？？

  • 用户态能执行哪些特权级指令？能禁用中断or异常吗
  • 软件中断是什么？

  • Lab1 20-22

ch2batch 在batch时候内核和用户栈是唯一的，都在kernel的bss部分互相换

ch3多道

每个应用都有自己的内核栈和用户栈了…

Lab2 22-24

ch4 数据段只存elf，需要load的时候申请物理页创造应用的memoryset

用户程序加载的时候创建app memset时候把elf里面的section都申请并映射了出来，同时申请创建了用户栈，申请创建了TrapCTX专用的页？创建后返回这个地址空间，返回用户栈以及入口地址用来创建PCB

在trapCTX加入

  • kernel_satp 表示内核地址空间的 token ；
  • kernel_sp 表示当前应用在内核地址空间中的内核栈栈顶的虚拟地址；
  • trap_handler 表示内核中 trap handler 入口点的虚拟地址。

用户栈<->TrapContext的虚地址

  • traps

    • 取得TrapCtx虚地址，开存所有regs和sepc status
    • 获取satp 内核handler
    • 换内核栈，换地址空间（刷TLB），jr handler

  • restore（参数为用户trapctx的虚地址次高页+用户地址usersatp）

    • 换用户空间，刷TLB
    • 写入scratch为Trapctx虚地址
    • sp = trapctx开始回复寄存器
    • 恢复用户栈
    • sret
      PCB：

  • taskstatus

  • taskctx

    • regs，ra，内核栈
      • 地址空间

  • trapctxppn物理页号

  • 应用数据大小

写Lab看课件

Ch9 文件系统

9-1 文件和文件系统

unix文件系统ufs语义：

对打开文件的写入内容，立即对打开文件的其他用户可见。共享文件指针允许多用户同时读取写入

打开文件的维护：

  • 进程级文件描述符表，非负整数获得文件指针。指针中是最近读写位置（文件偏移量）
  • 系统级，当前所有打开的文件表。
    • 打开计数，为0后系统关闭
    • 文件偏移量
    • 状态标志
      • 系统fs级，inode表
  • 指向具体文件内容
    文件系统：命名，存储（分配、管理、安全、可靠），检索

目录文件

特殊文件，数据中包括文件索引表和指向文件的指针

硬链接，多个相同文件项（inode）指向相同数据块

软链接，只存文件名，需要找一遍索引

9-2 文件系统设计实现

虚拟文件系统在高层下面可以挂载不同文件系统甚至remote。抽象出所有文件系统相同通用接口。

文件系统的存储：

  • superblock超级块，文件卷控制块。整个文件系统的信息，块大小，剩余块数，block和inode总量等等。挂载，写入，检验等等
  • inode/dnode bitmap Inode 的占用情况
  • vnode inode 128B文件控制块，大小，数据块指针。访问控制（群组用户rwx）各种时间信息
  • dir entry 目录项，在内存中缓存来表示目录，把目录项编码为树形结构
    • 父目录
    • 子目录和文件表，指向他们的inode
    • /home??
    • 指向自己的inode
  • datablock 4KB数据块
    • 目录的数据块
      • 目录内的东西，给一群inode…

注：文件名在目录的datablock

虚拟页式存储，把文件数据块映射为内存页，直接访问内存即可。

分配方式

连续分配 文件头指定起始数据块和长度然后往后写（最先 最佳 最差…高效的顺序和随机读） 碎片多，append开销巨大

链分配 容易创建增加缩小，几乎没碎片；随机访问低效需要循过去。破坏一点后面全丢。inode存头尾块，中间在dnode用指针连

  • 显式连接：直接搞一个FAT文件分配表，连接物理块的指针放在表里常驻内存。根据数据块查到下一块。支持随机访问？？？只需记录文件的起始块
  • 隐式：数据块保存下一块的指针。记录头尾块
    索引分配：文件头包含索引数据块指针，可以随机访问但是索引开销可能很大（对于大量小文件）。巨大文件可以链式索引inode或者多级inode索引..

多级索引下，每个Inode可以搞10个dnode加1个一级索引inode 一个2级索引 一个三级索引，再往下…

磁盘分区分卷之后，每个区有独立文件系统

9-3 崩溃一致性的文件系统

dbitmap inode dblock三个都要写，崩溃后写一部分

fsck 文件检查，重启的时候修复

  • 检查超级块，超级块多副本。如果不合理可以启用备份回复
  • 扫描位图和inode 的一致性，不一致更信任inode。看起来像是在用的inode一定标记ibitmap
  • 检查inode内的损坏，如果可疑就被清除并更新inode位图
  • inode链接计数，检查特定文件的引用链接数量
    • 从root开始扫描目录树并为文件系统中每个文件和目录构建链接计数。
    • 如果与inode不一致通常修复inode
    • 如果已分配但没引用则移动到lost found
  • 重复inode，清楚错误inode
  • 检查坏块指针。比如某个指针明显超过有效范围
  • 目录检查，目录的.和..都置顶。每个inode已分配，目录引用不能2次及以上
    fsck太慢了，可能丢东西

日志文件系统

WAL 预写日志，先写点注释。崩溃后查看注释可以重试

开始符号，Inode更新信息，bitmap更新信息，db信息，结束符号

写日志要注意先不写TXB结束符write，等事务内容写入后再写TXEcommit。然后写真数据checkpoint

优化

维护日志的超级快journal superblock

  • 批处理更新日志
  • 有限的循环日志
    一段时间后free日志

正常日志包含元数据和db，如果只记录元数据呢？要求先写data

元数据日志什么时候写入Db？

  • Data write
  • Journal metadata write
  • journal commit
  • checkpoint metadata
  • free
    图片

Ch10 进程间通信

10-2 支持IPC的OS

扩展文件抽象引入Pipe，文件形式交换

0607-0613 Final Review

Lect7 进程管理与单处理器调度 6.7

7-1 进程管理

需求：

动态交互控制

需要命令行和图形界面

提供给程序：控制和数据的独立抽象，独占cpu和内存

包括数据结构+动态操作数据结构，是程序占用资源的集合

进程相对任务的进步：创建子进程、覆盖内容、动态申请释放资源

fork 除了a0之外的所有寄存器和内存、变量

exec

exit 释放文件、内存等资源但保留大部分进程相关的数据结构检查父亲存活情况

waitpid / wait

getpid

nice优先级 ptrace一个进程控制另一个的执行，设置断点与查看寄存器

僵尸进程 孩子exit父亲没有wait

孤儿 父亲先exit孩子由root回收

PCB

进程上下文：Trapctx Taskctxmemset 内核栈

状态，父子关系，退出码 下图？？

Processor 有一个 idle 控制流，功能是尝试从任务管理器中选出一个任务来在当前 CPU 核上执行，有自己的CPU启动内核栈上

图片

initproc pid0初始化然后fork exec shell为pid1

进程切换：暂停当前运行进程，调度另一个进程从ready到running，也需要保存恢复上下文

进程状态：创建、就绪、运行、等待wait 不在就绪队列中、退出

fork思考

fork的内存复制与fd传递——无用，孩子大部分会exec

vfork 轻量级，不复制内存，子进程尽快exec COW

fork是事故发明，只有unix还在用并且很长一段时间会用

7-2 单处理器调度

挑出下一个占用cpu的进程，挑出使用的cpu

使用率、吞吐量、周转时间（初始化~结束）、就绪等待时间、响应时间、公平

低延迟vs高带宽

FCFS 先来（就绪）排前面的得到服务

公平；简单

波动大；短任务排后面；IO与cpu利用率低（一个密集另一个idle）；平均等待很长（后来就得等）

SJF 选最短的

最优平均周转；最优平均等待

大任务饥饿；需精确预知未来困难（询问、欺骗、历史估计。某次估计值等于上次实际值和上次估计值的加权平均）

SRT 抢占）最短剩余时间，最快能干完剩下的工作量

改进SJF 但仍饥饿

HRRN 最高响应比优先 是FCFS+SJF

基于SJF，不可抢占

响应比 = w+s / s

RR 时间片轮转 辅以其他算法切换进程默认FCFS，每次等待n-1个片

开销大（上下文切换）；时间片过长为FCFS；太小产生大量切换开销；开销1%以内

公平但等的太长

多级队列调度MQ

一堆子队列，同优先级在同队列，每个队列有单独调度方案如前台进程RR后台FCFS。队列间固定优先级（先前台，饿死后台）非均匀RR

高优先级运行，同优先级公平轮转RRorFCFS

多级反馈队列MLFQ

不预知外来但优化周转，降低响应。知识不完备——学习历史

先进最高优先级，时间片结束后降级但中间主动yield不降级（若干次yield后用光也降级）；高级队列时间片小（高级对延迟敏感，低级为慢慢算）；每隔一段时间重新加入最高优先级

cpu密集迅速下降 IO密集持续高优先

CPU密集饥饿，恶意留高优先级

FSS 公平共享调度

控制用户访问系统资源，按用户优先级分配，垃圾用户不垄断，未使用的资源按比例分。

7-3 实时调度

实时操作系统：正确性依赖于其时间和功能两方面——实时响应处理外界事件数据、并反作用与生产过程。比如测控、机床

性能最重要是及时，速度和平均吞吐不重要，

特性：时间约束可预测，约束是可预测的，几秒内完成转弯？

强、硬实时——必须在ddl内完成

周期实时任务：周期p请求 e时间完成

静态：执行时优先级不改变

静态 抢占 速率单调调度 RM Rate Monotonic

周期安排优先级，周期短优先（频率高优先）

有的任务会错过期限！本来能完成被不紧要的任务耽误

动态 最早截止时间 EDF

DDL早优先

优先级高一定被先执行？延误！共享资源被占用需先干完一个

动态 最低松弛度优先LLF

任务紧急松弛程度，紧急的优先级高。加入干了多少的概念

松弛 = DDL - 仍需 - 当前 即 相对剩余 - 仍需。假设这个完成能剩下多少时间给别人，剩不下的优先

优先级反置

基于优先级的可抢占：高优先级长时间等待低优先级现象

3占用S 1在运行时申请S被挂起 2开始疯狂运行。。。

最低优先级早早占上共享资源导致高优先级拿不到，但最低级的运行机会少导致高优先级一直被挂起，共享资源迟迟不释放

优先级继承

占共享资源的低优先级进程继承申请自愿的高优先级进程的优先级。即高优先级因资源被阻塞时候，给占用者高prio

优先级天花板协议

占用资源的优先级 = ceiling/max（所有可能申请的进程prio，“可能”不管是否block都提升其优先级）

只要高于所有锁定资源的prio上限，任务甚至不会被阻塞！希望临界区快点释放所以优先级最高

7-4 Lab3 实践

对os来说进程是应用程序的一次执行过程（示例），拥有资源

loader分析linkapp.S，用全局只读向量APPNAMES顺序保存了所有app的名字，供exec使用

fork

建立新页表复制地址空间

创建新Trap CTX

内核栈

Task CTX

父子关系

设置fork返回a0

suspend_current_and_run_next 正常放弃、切换被调度出去

Lect8 多处理器调度 6.7

8-1 对称多处理与多核架构

多处理机器

超线程 CPU内闲置资源充分调动，寄存器、程序计数器独立，算数计算硬件共用。比如可以同时运行整数运算+浮点运算。

多核处理 纯纯多RF 多ALU 同bus

cache一致性

SMP or UMA

所有cpu共享bus对资源的访问资格相同、地位相同，访问同一mem

内存冲突多 CPU浪费

NUMA架构 非一致内存访问

多个node，node有自己独立的内存空间，node内共bus 共mem

访问远节点更慢

cpu独有cache 通过监控内存访问来嗅探 作废自己或更新自己

8-2 多处理器调度概述

SQMS 单队列多处理器调度

复用queue，轮着喂core即可

可扩展性差：cpu多需要调度程序上锁的原子操作，锁和缓存争用增加

缓存亲和性：1在1工作下次被调度到2上工作… 4cpu5任务模型

MQMS 多队列多处理器调度

多个不同规则的调度队列

加入时按启发规则放入某个调度队列

cpu调度独立

可扩展：cpu多队列多，锁征用无关

缓存亲和好

负载不均？——支持进程迁移。进程反复横跳？进程少的队列偷看其他队列，显著更多的时候就偷一些过来

8-3 Linux O1调度

调度器考虑：数据结构、进程运行时间、判断进程类型、动态优先级、适配多处理器

On调度器

遍历整个链表队列，一个大锁Global runnable queue 各个core竞争使用

分成时间片epoch

  • 计算进程动态优先级；进程优先级映射为缺省时间片；选择最高优先级
  • 被调度后不受打扰的运行该epoch
  • 如果没用完，剩下的增加到进程的下一片中
    进程多性能降低，竞争访问同一个queue没有scalability

O1调度器

per cpu runnable queue 全局优先级 实时进程0-99 普通100-139

有active 和 expired 数组；一共140种优先级

用长度140bitarray表示这个优先级队列下面有进程，找位图中最高位1的bit即可即leftmost bit；每个优先级都对应一个FIFO queue，新来的插入队尾

pull：

  • 找到最高位对应的x位置

  • 在APA活跃数组找到对应队列APA【x】并pop出一个进程
    时间片耗尽后push：

  • 执行完的进程计算优先级放入EPA【y】的队列，检查这个expired bitarray如需要置1

  • 如果active bit array全0则和expired bitarray互换
    多核SMP支持

周期性分析cpu负载，负载轻的多pull拉取新的而不是push扔回去旧的

8-4 Linux CFS调度 Completely Fair Scheduler

划分每个调度周期确定的固定时间片，结束被重新分配epoch O1本质是MLFQ

根据进程运行判断是计算orIO密集再奖励or惩罚——动态时间片，每次调度的时间片都变化

  • 每个进程nice值，共40等级每个差10%是静态prio
  • 把CPU视为资源，记录进程使用情况——调度时调度器选择消耗资源最少的运行
  • 按照权重分配CPU资源
    • 运行时间 = 调度周期 * 进程权重 / 所有进程权重和
      • 周期：所有running态都调度一遍的时间
      • 后面是权重占比
  • 虚拟时间vruntime：记录进程已经运行的时间
    • vruntime = 实际运行 * 1024 / 权重
    • = 调度周期 * 进程权重 / 所有进程权重和 * 1024 / 权重
    • = 调度周期 * 1024 / 所有进程权重和
    • nice0的标准权重1024，从[-20,20)
    • nice正的进程vruntime是缩小实际时间的
    • 所以vruntime在所有进程都相同，与权重无关。实际运行不一致但在vruntime下是完全公平的。
    • vruntime较小占用太短，下一个选他运行

CFS实现

红黑树记录vruntime，多核的就多个红黑树，找最小的vruntime节点即logN

40个nice对应权重，大nice小权重，有prio_to_weight转换

新权重的vruntime？为0则狂跑不公平

维护min_vruntime 新进程的值

休眠进程？休眠进程以min再给予补偿；休眠后有能力抢占cpu是大概率且符合目标，交互式进程等待用户输入总休眠，然后快速响应 主动休眠进程也有补偿但不要求快速响应，如果总抢占影响整体性能。WAKEUP_PREEMPT标识标识禁用唤醒抢占

进程cpu迁移？每个cpu的min vruntime不同，作为自己的基准值。出来的时候减自己然后加上另一个core的基准值

uint32溢出回0？比较的时候同时减去某个数再比，让0的回到那个大数

8-5 Linux FressBSD BFS调度

Brain Fuck Scheduler 脑残调度器 RR变种

  • 多处理机共享一个就绪队列（双向链表）增加互斥访问开销但减少负载均衡开销
  • 103个prio：100个静态实时优先 3个普通优先级（交互、普通、低优先）
  • 按优先级排队，同优先级的每个进程有时间片长度和虚拟截止时间
  • 固定时间片默认6ms，找虚拟截止VDDL。进程等待长这个ddl就早
    • 时间片用尽后重新计算截止时间后插入队列
    • 事件等待结束后vddl不变以抢占，or插入就绪队列
    • 亲和：不同cpu的vddl加一个权重
  • VDDL = 当前时间niffies + rr_interval * prioratio[prio] * scaling factor
    • nice小 prioratio小 VDDL早
  • 使用O1的bitarray有103个queue。如果queue bit 1则遍历queue找vddl最小的
    在核少时效果不错

Lect9 文件系统 6.8

9-1 文件和文件系统

文件系统存储设备上组织文件的方法和数据结构

一切皆文件，字符设备，网络也都是文件，统一接口

读文件：数据块内对应部分

写文件：获取数据块，修改并写回

数据块是基本操作单位

用户|组|所有人 RWX

Unix FS：对打开的文件写入，立即对其他打开同文件用户可见，共享文件指针允许多用户同时读取和写入

UFS中进程有文件描述符表，然后所有进程共享系统文件表。只有先打开文件再fork的会文件偏移量指针。其他情况都出现覆盖（独立的偏移量）？？

文件描述符

图片

VFS虚拟文件系统，抽象统一接口下面是一堆其他fs和其他IO驱动

分层文件系统：目录是特殊的文件，存文件索引表<文件名 - 指向文件的指针> 指向inode吗？

目录实现线性表太慢；哈希表？有冲突

链接

  • 硬 多个文件项指向同一个inode！别名！
  • 软 存储名称然后现解析
    目录循环？允许链接文件但不允许链接子目录，增加链接时用检测算法

9-2 文件系统设计与实现

inode叫索引节点

数据块中有目录项有传统文件项

层级：硬盘驱动 实际文件系统 虚拟文件系统 内核抽象 用户库 用户程序

图片

数据结构

超级块文件系统信息，块大小，剩余块，block总量inode总量挂载时间，最近a w fsck检验的时间

Inode | DataBlock Bitmap i d的使用情况，用来分配

128B索引节点Inodes大小 位置 管理若干db，访问控制，拥有群组|用户，时间信息，链接数，文件名在目录的db

数据块4KB？？在我们的easyfs中：目录项、正常文件项

  • 目录数据块固定有. ..的inode号，然后一堆文件名hash值与inode号，每一项叫dir_entry。就是文件名+inode号

文件缓存

  • 可能预读
  • 读过的块被缓存，写操作可能被缓存和延时写入
    • 页式缓存: 统一缓存数据块和内存页。在应用地址虚拟空间中，虚拟页面映射到本地的外存中。即一个虚拟页对应外存，需要时和主存对换上来。页置换需要考虑虚拟存储和页缓存
  • fd table - sys open file table - inode

文件分配

连续 策略；高效的顺序和随机读 碎片多 写开销大

链式容易增删改；没碎片；随机访问慢；依赖强，一个坏后全坏

  • 隐链接：inode存第一个和最后一个块号，数据块每个末尾向后指针

  • 显链接：FAT表，每个块一项对应下一块号
    索引inode指向文件头，头块为索引块指各个后续数据块指针。增删容易；几乎没碎片；随机访问也行；文件小的时候索引开销太大！

  • 链式索引，索引块之间链表

  • 多级索引，索引块分级

    • inode直接指：直接索引
    • 指向索引块再指向数据：1级间接索引
      图片

找空闲块扫描数目： 总数/空闲块

操作最终以写inode结尾！

5次已有open 读到inode即可，不写

3次read 读inode 读dnode 写inode

创建open 读到目录项之后，读inode bitmap 然后写ibitmap 写inode 写目录项 写目录项inode，共写四个东西，此时未分配dnode

write 读写dbitmap

图片

分区多个分区，有独立的文件系统

9-3 支持崩溃一致性的文件系统

需要原子性的状态变迁

但硬盘一次提交一个写入，更新间可能断电

write本来也被os延迟在内存，必要时才写磁盘

新加dnode场景需要write三个，崩溃场景讨论：

  • only dnode 没人管理 找不到 未曾写入
  • only inode 读dnode的垃圾数据
  • only dmap 空间泄露，占用但没人管理
  • dmap & inode 垃圾数据
  • inode dnode 和位图不一致导致被覆盖等
  • dmap dnode 无人管理

fsck fscheck

发生不一致然后重启后修复，慢的一比也可能丢数据

  • 检查superblock，是否启用备用老版本块
  • imap inode一致性检查，信任inode
  • 检查inode是否损坏，inode如果无法修复则删除，更新imap
  • 链接计数检查，从头计数修复indoe。如果计数为0移动到lost found目录
  • 重复inode指针，两个inode引用同一个块：明显错误
  • 坏块（坏指针）检查，超出自己的有效范围则删除
  • 目录检查，。和。。都在前面，引用的inode已经分配。目录引用小于等于一次

日志文件系统

WAL | journaling 注记指示如何恢复错误，增加更新工作量，大大减小恢复工作

Data journaling

TxB开始 Inode更新 Dmap更新 Dblock更新 TxE结束

先写数据日志，然后写真实数据，但注意TxE标识日志项的完结，所以需要检查前面写完成才发出最终TxE Commit。即TxE一定是最终安全状态的日志

1 写日志 2 提交日志 3 checkpoint写真正更新内容（先data再metadata） 在3崩溃会导致W太多慢

日志优化

  • journal superblock 单独存储、批处理日志更新、循环日志回收复用
    • 加一个4free 更新日记账，标记为空闲
  • Metadata Journaling
    • 仅包含元数据的日志记录，不包含dnode
    • （ordered mode）1 datawrite 2 journal metadata write 3 commit 4 checkpoint metadata 5 free 先写数据块保证永远不指向垃圾，数据块在日志提交前写入。
    • writeback mode 不保证顺序，快

9-4 Lab4 FSOS 霸王龙OS

userapp userlib userfs?? kernel_syscall VFS EasyFS

syscall OSInode VFS easyfs BlockCache BlockDrive

fdtable是OSInode数据

OSInode对操作系统的Inode最高层抽象，可读可写标识和偏移位置、下层Inode

Inode

DiskInode getblockid获取自己的第blockid个数据块编号

  • size
  • 直接索引
  • 一级间接索引
  • 二级间接索引
    BlockCache 512B字节缓存，某个blockid，记录脏位

Lect10 进程间通信 6.8-6.9

10-1 IPC概述

共享内存是直接通信不需要通过内核

管道 消息队列 信号 套接字 文件 都是间接通信

缓冲方式：无限buffer发送方不等；有限链路缓冲队列满了就不能发；0容量无缓冲，发送方必须等待接收方接受

匿名管道

有方向有大小的字节队列，不同fd表示，读写分别的fd+一段内核空间内存，单向通信！

仅支持有关系的进程通信，比如父子兄弟，父进程创建管道子进程继承fd后执行。一般约定两进程各关闭一个fd

mkfifo创建命名管道（阻塞单向），支持任何两个进程。然后用open打开，同时有读打开和写打开才会正常工作

任何一方可读写，半双工？需要读写同时打开命名管道才能写入和读取

消息队列

FIFO规则的结构化数据的队列，有专门类型标识

按照类型标识划分队列，同类同队

  1. ftok，通过进程PID获得唯一标识，消息队列名字key
  2. msgget通过key flag尝试获取队列标识符msgid，创建消息队列
  3. msgsnd通过标识符msgid发送数据，flg控制。msg前面要有4B的type字段，size不包含这个type
  4. msgrcv type可以简单接受，0队列第一条 >0消息等于type的消息 <0 小于等于abstype
  5. .msgctl可以溶质删除

共享内存

快速方便但需要同步机制

ftok()

shmget创建key size flg返回shm id

shmat映射到进程空间，可以手动指定地址，返回一个指向该共享空间的指针

shmdt取消映射

shmctl控制

信号signal 异步通知

B在内核注册信号（主要是注册信号处理函数）

A给B发送信号内核中转，在返回用户栈前发现有信号处理，压入用户栈sighandler，修改返回地址。

B返回用户态直接跳到handler处理中断处理信号 ，handler返回到B恢复中断继续

KILL(pid_t signal_id) 是发送信号的

SIGKILL 内核杀进程

SIGPIPE 读管道出错，读关闭fd

SIGINT ctrl C终止外设中断

SIGHUP 断开shell连接

SIGQUIT 产生core的错误退出

SIGABRT abort函数

10-2 IPCOS实践

扩展文件抽象：Pipe，Stdout, Stdin

pipe、signal是进程控制块的资源

pipe设计实现

基于文件抽象 维护在PipeRingBuffer Pipe是？？

exec修改为可以获取args，a0指示参数个数argc，a1是argv[0]的栈上地址

sys_dup 重定向，纯纯分配新fd然后复制文件描述符

对A|B ？？图片

信号设计实现

sigaction 设置信号处理程序？？读一读 信号，新老action*，oldaction是用来送回去的。

  • signalaction包含handler地址和信号掩码
    sigprocmask 设置阻止？？的信号

kill 发送信号

sigreturn 清除堆栈从信号处理func返回

TCB中含

  • signals 等待响应信号
  • mask屏蔽信号
  • 正在处理的信号
  • 信号处理表，各个信号跳哪里，一堆action
  • bool杀死
  • bool冰冻
  • 打断的backup trapctx
    图片
    图片

Lect11 线程与协程（协程不考）6.9

11-1 线程

进程难以并发；难IPC，地址隔离；还是粒度太大——将程序分解成可并行运行的多个顺序控制流，多条控制流一起。性能高，共享数据方便，管理方便

对比进程：

线程是cpu调度单位，独享寄存器和栈；拥有就绪 阻塞 执行基本状态；减少并发的开销；共享地址空间和文件（堆共享）；C系一个线程崩溃进程崩溃。。。

线程概念

进程用来分配资源；线程用来调度执行；

pthread_create(pthread_t , const attr, void start从哪开始,void *传参)成功ret0，

pthread_join pid，**retval

线程设计实现

实现方式

  • 用户态管理用户态运行，内核不可见、绿色、有栈、纤线程，内核空间只有PCB。用户级的线程库函数完成管理。
    • 控制简单，内核无要求，控制开销小，允许进程自定义线程调度灵活，线程利用的表空间和堆栈更多，只有一个线程能运行
    • 线程仍然会单阻塞；不支持抢占；按进程分配时间；多处理机下线程只能时分复用没有真正并行
  • 内核态管理用户态运行，内核可见
    • 内核系统调用实现，维护内核TCB，单线程不阻塞其他线程。Linux单进程只有单线程，Win core都支持多线程
    • 线程切换开销大类似进程切换；传统进程管理矛盾如fork
    • 多线程fork：
      • race condition 共享资源变量，同时写同一个文件？
      • 死锁，子进程无法获得锁。fork只复制某个线程时，等待锁而死
      • 内存占用，子进程复制父进程相同的内存、寄存器等
      • 性能巨慢，大量子进程时
  • 内核态管理内核态运行，内核线程
    • Linux内核线程，内核的分身，维护PCB等，常并行处理周期性任务BufferCache定期写回；虚页交换；FS事务日志
  • 混合管理运行，混合线程，轻量进程LWP
    • 一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持——像独立进程一样享有专门的中断！
    • 与用户线程关系，用户线程由用户线程管理库管理，内核只识别内核线程|进程调度 与用户线程管理库交互
      • 1：1 Linux JVM 用户态不管理，内核管理
      • N：1 多个用户线程，内核态管理包含多线程的进程；用户态线程运行时管理线程 与OS无关的Green Thread
      • M:N 协同管理 Solaris OS, Go runtime
    • 最灵活最复杂
      同进程内线程上下文切换，虚拟内存共享，只切换私有资源

11-2 协程 stackless 是普通函数的泛化

类似用户线程，操作系统不可见，随意切换的多个执行点？即协程函数中间可以随时yield来正常执行其他函数，等IO阻塞结束后切回来？

进程：页表，堆，栈，寄存器

线程：栈，寄存器

协程：寄存器，不换栈

大规模并发IO下：大量线程占内存总量大 管理开销大 共享数据易错

异步函数 相比普通函数，协程的函数体可以挂起并在任意时刻恢复执行，是普通函数的泛化

与线程 内存小，多线程下明显；不需要锁，没有写冲突，只需判断状态，高效

协程的核心思想：控制流的主动让出与恢复

11-3 实践

用户态管理的用户线程，类似老的简略TCB 有pid stack taskctx state等

state Available特指tcb没用了？？,     Running,     Ready,

Runtime？？::new 多线程找RUNTIME全局量获取线程相关数据

  • 设置主线程running

  • 设置调度队列

  • 设置当前线程id 0
    调用spawn创建新用户线程

  • 查找TCB有无available的控制块，初始化其上下文

  • x1为老返回地址guard函数——意味着f已经返回，线程已经完成，标注available

  • nx1新返回地址 f

  • x2新栈地址
    runtime.t_yield 切换线程

  • 找一个ready，把状态改掉，current改掉

  • 调用switch

    • 切换pc 换栈 换regs
      线程|进程资源回收？？cyk bilibili

  • 子线程退出

  • 主线程waitpid回收

    • 清空PCB 全部清空线程资源

  • 主线程退出，进程回收
    创建线程

  • 用户、内核栈

  • 跳板页

  • 线程上下文

Lect12 同步互斥 6.10

12-1 同步互斥概述

临界区：进入section 临界section需要互斥的代码 退出sec 剩余sec

等待进入临界区的线程不能无限期等待

不能进入临界区的线程，应释放CPU（如转换到阻塞状态）

  • 禁用硬件中断
    • 没有打断，没有并发，延迟处理到启用之后。
    • 线程无法停止，其他饥饿，临界区很长，不适多核
  • 基于软件

    • 全局变量控制，如果某个不需要进入则无法给后面创造

    • 两个flag——全卡or全进

    • peterson turn+flag，我进了flag，该你了。等待条件是该他且他进了图片

    • dekkers

    • N线程：turn和N个flags

  • 更高级抽象
    • 锁
    • 原子操作TestandSet TAS来lock
      • Compare and Swap 如果是old就换ret true否则不换ret false
      • 用CAS改共享变量存在ABA问题，即被改了多次恰巧满足原来条件——增加版本号

12-2 信号量

P为减少，可能阻塞。默认有wait queue

对应生产者消费者问题，单个时刻只有一个生产、消费者访问缓存区。空时等生产；满了等消费；

用信号量描述每个约束

二进制信号量mutex 二进制信号量

计数信号量fullBuffers 0

计数信号量emptyBuffers n

图片

评价

  • 忘记占用信号
  • 忘记释放
  • 死锁

12-3 管程与条件变量

条件变量配合mutex

管程

不好读，不好改，正确性难；死锁——面向对象的程序结构，任何时刻最多一个线程执行管程代码

  • 模块化，是基本程序单位
  • 有数据有代码，特殊的数据类型
  • 半透明
    管程中的共享变量在管程外部是不可见的

管程操作：进入enter, 离开leave, 等待wait, 唤醒signal

  • 入口等待队列：只有一个线程能在管程中
  • 条件等待队列：为资源占用等待
  • 紧急等待队列：唤醒使用，T1唤醒T2转移访问权限？T1挂起进入紧急等待队列，优先于条件变量等待队列
    T.enter过程：线程T在进入管程之前要获得互斥访问权(lock)

T.leave过程：当线程T离开管程时，如果紧急队列不为空，唤醒紧急队列中的线程，并将T所持锁赋予唤醒的线程；如果紧急队列为空，释放lock，唤醒入口等待队列某个线程

T.wait(c)：1)阻塞线程T自己，将T自己挂到条件变量c的等待队列；

2)释放所持锁； 3)唤醒入口等待队列的一个或者多个线程；

T.signal(c)：1)把条件变量c的等待队列某个线程唤醒；

  • 被唤醒的先执行 Hoare
      1. T1 进入管程monitor
      1. T1 等待资源 (进入等待队列wait queue)
      1. T2 进入管程monitor
      1. T2 资源可用 ，通知T1恢复执行， 并把自己转移到紧急等待队列
      1. T1 重新进入管程monitor并执行
      1. T1 离开monitor
      1. T2 重新进入管程monitor并执行
      1. T2 离开管程monitor
      1. 其他在entry queue中的线程通过竞争 进入管程monitor
  • 唤醒者先执行 Mesa重新竞争访问权限真实os java Hansen
    2)把线程T所持lock给被唤醒的线程；

3)把线程T自己挂在紧急等待队列

12-4 同步互斥实例

哲学家就餐

  • 直观用信号量，在就餐前尝试拿左右叉子？——死锁
  • 拿叉子前用mutex锁上，然后尝试——每次只有一个人吃
  • 奇偶分左右，避免死锁
  • and型信号量，两个叉子都在才能进餐——一个原语中申请整段代码需要的多个临界资源
  • 图片
    没有死锁 最大并行度 饥饿是试图拿叉子的状态

读者写者问题

  • 信号量方案 设置读写互斥mutex和读者计数变量，以及读者计数互斥修改——读者优先
  • 管程 Condition okToRead okToWrite 活跃and等待的读写者数量

12-5 死锁

可重用资源（Reusable Resource） 一个线程使用，释放后立即其他重用——死锁：占用一部分请求其他资源

可消耗资源：中断信号消息等；互相等对方的消息

死锁条件：互斥；持有等待；非抢占（只能自愿释放）；循环等待

预防：不会进入

破坏互斥；只有同时获得才分配，不许先分配（） 释放原有资源；按顺序请求资源

避免：只允许不死锁进程请求

声明最大数目；限制资源数量；动态检查分配状态图片

检测恢复

通常OS忽略死锁，app负责

Rcore银行家？？

12-6 Lab5 实践

总结内容

进程控制块PCB

  • pidhandle

  • //kernel_stack

  • inner:

    • trap ctx ppn
    • user stack sp(base_size)
    • task ctx
    • task status
    • memory set
    • parent
    • children
    • exit code
    • //tasks
    • //task_res_allocator RecycleAllocator 通用分配器分配PID和Kstack
      线程控制块TCB

  • process 弱连接PCB

  • kstack 线程内核栈

  • inner

    • Task User res 线程用户态资源？？
    • trap ppn
    • task ctx
    • task status
    • exit code

所有资源与回收总结

  • PCB 父进程回收后释放
    所有上下文、存储位置与切换时机总结

临界区访问规则

空闲则入 忙则等待 有限等待 让权等待

死锁必要条件

互斥 非抢占 循环等待 持有并等待

图片

两个线程可以访问同⼀个栈上的变量

线程中访问临界资源的⼀段需要互斥执⾏的代码

Follow

Links

Categories

Recents

Archives

×