OSTEP阅读笔记

OSTEP-操作系统笔记

操作系统笔记

冯诺依曼结构:代码和数据隔离,指令顺序执行
easy to use

三个部分:

  • 虚拟化:最大化利用硬件,共享硬件
    • 虚拟化cpu :将单个或者多个cpu虚拟化成无数个cpu,供多个进程同时使用。
    • 虚拟化内存:内存是以字节为单位的数组,每个进程需要独立的虚拟地址空间(Virtual Address Space)
    • 虚拟化磁盘
  • 并发
  • 持久性(Persistence)

Alt text

Alt text

Tips:硬件驱动:跟特定的硬件通信
Tips:指令的执行过程:

  1. 内存读取到寄存器
  2. 执行指令,操作寄存器
  3. 保存结果回内存

设计指标

  • 性能开销(节能)
    • 时间和空间
  • 安全:沙箱隔离
  • 可移植性

虚拟化CPU

将单个或者多个物理CPU虚拟化成无数个CPU,每个进程单独占有一个虚拟cpu

进程

The process:a running program
程序本身没有生命力

创建进程

  1. 硬盘上的程序和数据读取到内存

    • 早期OS会一次把所有程序代码读入内存
    • 现代OS则是按需读取
  2. 分配栈和堆

    • 栈是程序静态分配的空间,比如函数名,函数变量
    • 堆则用于动态分配,例如调用malloc函数,以及链表,树,哈希表等数据结构
  3. I/O初始化设置

    • unix每个进程默认有标准输入,输出,错误日志三个文件标识符

Tips

  1. paging是以页为单位,进程内的交换
  2. swaping则是以进程为单位的交换

进程状态

  • Running
  • Ready
  • Block

Alt text

进程数据结构

OS本身是程序,为了追踪每个进程的状态,需要一个进程列表的数据结构(process list)
主要用以保存进程的相关寄存器内容

进程API

fork:把当前进程的情况拷贝一份,
在原进程返回1,子进程返回0,返回值小于0则表示fork失败
wait:等待子进程完成
exec:调用其他程序

Tips

wc命令,显示一个文件的字节数。

限制直接执行

在达到效率要求的同时要保证OS安全,是实现OS的主要一个点
安全和效率

直接执行

!direct
上图中注意两点:

  1. 如何保证系统的安全
  2. 如何实现进程切换

用户模式和内核模式

  1. 内核模式可以控制整个系统和获取所有资源
  2. System call也是procedure call在system call后面隐藏着trap instruction

Alt text

进程切换

当程序运行的时候,OS是block模式的,OS如何重新获取对系统的控制?

  1. yield
  2. 时钟中断

Alt text

OS在处理中断的时候发生了另一个中断?

  1. 处理中断时禁止中断
  2. 锁机制?

调度系统

假设

  1. Each job runs for the same amount of time.
  2. All jobs arrive at the same time.
  3. Once started, each job runs to completion.
  4. All jobs only use the CPU (i.e., they perform no I/O)
  5. The run-time of each job is known.

度量标准

周转时间=完成时间-到达时间,即单个任务的执行时间

Alt text

周转时间是性能指标
另外一个标准是公平性指标:
响应等待时间,(任务到达到开始执行的等待时间)

FIFO

先进先出调度,或者FCFS(first come,first served),先来先服务

Alt text

Shortest Job First (SJF)

假设所有进程同时到达则
最小执行时间优先

Alt text

Alt text

假如A比BC先到

Alt text

Shortest Time-to-Completion First (STCF)

进程不是同时到达的,最小完成时间优先

Alt text

Round Robin

周期执行,考虑度量标准——响应等待时间,

Alt text
RR以设定的时间切片执行一个进程,一个切片后换另一个进程
影响性能的主要因素是进程间切换时的上下文环境切换
一个解决的方法是:增加时间切片的长度,
Tips

时间切片的长度一定是时间中断的整数倍

Alt text

结合I/O

去掉假设4,
进程在处理I/O时,出于Block状态,此时其他进程可占用CPU

Alt text

多级反馈队列调度算法

Multi-Level Feedback Queue(MLFQ)

1.最优化整个进程的执行时间(每个进程执行时间未知)
2.减少等待时间

MLFQ是“基于过去学习,learn from history”典例

基本规则

  1. 进程在单独一个队列
  2. 每个队列拥有不同的优先级
  3. 相同优先级的进程执行RR规则(拥有较好的相应时间)

重点在于

如何在进程间分配优先级

类似基于进程行为特征的机器学习

  1. 长时间占用cpu的进程优先级低
  2. 频繁让出cpu的进程优先级会被提高,例如等待输入的进程
  3. cpu事先不知道进程要持续的时间,先假定是短时间进程,给予最高优先级执行完一个时间切片后,优先级降一级以此类推,直至到最低级

基本调度规则

  • Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
  • Rule 2: If Priority(A) = Priority(B), A & B run in RR.
  • Rule 3: When a job enters the system, it is placed at the highest
    priority (the topmost queue).
  • Rule 4a: If a job uses up an entire time slice while running, its priority
    is reduced (i.e., it moves down one queue).
  • Rule 4b: If a job gives up the CPU before the time slice is up, it stays
    at the same priority level.

两个问题

1.最低优先级的进程被饿死
2.程序会恶意不断获取最高优先级

  • Rule 5: After some time period S, move all the jobs in the system
    to the topmost queue.(周期性的将所有进程的优先级重置到最高级)
  • Rule 4: Once a job uses up its time allotment at a given level (regardless
    of how many times it has given up the CPU), its priority is
    reduced (i.e., it moves down one queue).

其他问题

MLFQ的参数化需要进行大量的实验,
比如:优先级低的队列拥有更长的时间切片

总结

• Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
• Rule 2: If Priority(A) = Priority(B), A & B run in RR.
• Rule 3: When a job enters the system, it is placed at the highest
priority (the topmost queue).
• Rule 4: Once a job uses up its time allotment at a given level (regardless
of how many times it has given up the CPU), its priority is
reduced (i.e., it moves down one queue).
• Rule 5: After some time period S, move all the jobs in the system
to the topmost queue.

Alt text

其他调度系统

进程公平共享CPU调度

彩票调度

其基本思想是向进程提供各种系统资源(如CPU时间)的彩票。一旦需要做出一项调度决策时,就随机抽出一张彩票,拥有该彩票的进程获得该资源。在应用到CPU调度时,系统可以掌握每秒钟50次的一种彩票,作为奖励每个获奖者可以得到20ms的CPU时间。

多处理器调度

传统程序都是正对单个cpu的,并没有对多核处理器做优化

单核架构和多核架构硬件cache的不同

Alt text

Alt text
硬件cache基于局域(locality)的概念

  1. 临时局域性
    • 程序可能会重复访问一些内存
  2. 空间局域性
    • 程序可能会访问曾经访问过内存的周边内存数据

某些变量在cache中改变后并不一定同步到内存在中,此时发生中断,且程序被转移到另外一个cpu,将会发生错误——cache coherence(缓冲不一致)

解决办法,各个核心的cache相互监控,一旦发现其他cache中的的变量值发生改变,则使自身cache中相应的变量作废——(bus snooping)“总线窥探”

同步问题

加锁

缓存同步(cache affinity)

进程有一些状态变量,比如TLBs等等寄存器,换cpu后,这些都需要重新载入,拖慢速度
最好的解决办法是一个进程保持在一个处理器核心运行

单队列调度(singal-queue multiprocessor shceduling——SQMS)

有点:简单
缺点:

  1. 不灵活,缺少扩展性
    • 为了确保单队列,需要在调度系统上加锁,从而性能受到影响
  2. 缓存同步问题:

Alt text

Alt text
解决办法,SQMS有将进程保持在同个cpu运行的机制

Alt text

multi-queue multiprocessor scheduling(MQMS)

两个调度系统是独立的,
MQSQ拥有更好的扩展性

Alt text

Alt text

负载均衡
假设Q0当中的c完成,

Alt text

Alt text
不同的队列会查看其他的队列的工作量,若比自身更加full,则从对应的队列转移一些过来
过多的查看会导致开销太大

Alt text

linux 多核调度

  1. O(1)
    • MQ
    • 优先级制度
  2. CFS
    • MQ
    • 确定比例分享
  3. BFS
    • single queue

虚拟化内存

给每个进程都提供足够大,隔离,私有的内存地址空间

地址空间

每个进程都拥有似有独立的虚拟地址空间(Virtual Address Space),简称地址空间(Address space)
一个程序的内存主要分为三块:

  1. code
    • 程序指令
  2. stack
    • 用于分配变量和函数调用地址
  3. heap
    • 堆由运行中的程序创建,用于动态分配,比如malloc函数

操作系统如何准确的映射内存,即内存虚拟

设计目标

  1. 透明
    • 程序可见的内存地址都是虚拟地址
  2. 高效
  3. 保护

内存API


    • 自动分配,比如函数,静态变量等

    • malloc():void *malloc()

常见错误

  1. 忘记分配内存空间
char *src = "hello";
char *dst; // oops! unallocated
strcpy(dst, src); // segfault and die
  1. 没有分配足够大的内存空间
    • 直接造成缓冲区溢出
char *src = "hello";
char *dst = (char *) malloc(strlen(src)
strcpy(dst, src); // work properly
  1. 忘记释放内存
    • 内存泄漏
    • 内存泄漏主要来源是长期运行的程序,服务器,数据库等

地址转换(翻译)

  1. 高效率
  2. 灵活
  3. 安全(可控)

基于硬件的地址转换
每个进程拥有自己的地址空间,实际上是共享物理内存的

两个假设

  1. 进程的地址空间是连续的
  2. 进程的地址空间比实际的物理内存小
void func() {
int x;
x = x + 3; // this is the line of code we are interested in

128: movl 0x0(%ebx), %eax ;load 0+ebx into eax
132: addl $0x03, %eax ;add 3 to eax register
135: movl %eax, 0x0(%ebx) ;store eax back to mem

Alt text

Alt text

Tips

编译时加上-g选项,使用objdump反汇编可以
把c代码和汇编代码穿插起来显示
-S选项只生成汇编代码

动态重定位

(ddynamic relocation)
两个寄存器:

  1. 基址寄存器
  2. 边界寄存器

    • 保证进程不越界访问
    • 两种实现方式
      1,记录最大内存的大小
      2,记录物理内存边界地址

    physical address = virtual address + base

寄存器是MMU的单位,memorymanagement unit (MMU);

因为地址转换发生在运行时,进程启动后也可以移动地址空间,所以称为动态重定位
静态重定位基于软件,安全性无法保证。

(硬件)总结

Alt text

操作系统Issue

  1. OS在进程创建时需要寻找足够的空闲地址空间
  2. 进程被结束时,OS需将所有资源(内存空间)回收
  3. 进程间切换需要额外的操作
    • 保存基址和边界寄存器
  4. 异常处理机制
    • 比如发生越界访问