绪论

OS作为用户和计算机硬件间的接口
OS作为用户与计算机系统资源的管理者
OS作为扩充器

时间线

1. 无操作系统
2. 单道批处理
3. 多道批处理
4. 分时/实时

解释一下是， 分时的话是多终端连接到主机，对每一个终端来讲都有独占的感觉， 实时的话一般是专用系统中， 对于该系统能够忍受的时差内做出反应的系统

基本特征

1. 并发
   并发: 多个事件在同一时间段内发生
   并行：多个事件在同一时刻发生
   并发实现的效果就是宏观上有多道程序同时运行, 而微观上是交替分时的进行

2. 共享
   多个计算任务对系统资源共同使用
   共享会造成一些问题

3. 虚拟
   虚拟式把一个物理实体变为逻辑上的对应物

   其实计算机里对于不好解决的问题很多时候是通过加一层中间层来实现

4. 异步性
   其实异步的概念一直不是很会用言语说出来
   这里的异步大概是说如果因为某些情况阻塞掉了某些进程那么不需要等她, 等到时机成熟, 会有人来唤醒
   异步其实常常和回调联系在一起

主要功能

1. 处理器管理
2. 存储器管理
3. 设备管理
4. 文件管理
5. 用户接口

前四点应该都算是资源管理， 最后一点是提供接口

进程管理

程序顺序执行的特征

1. 顺序性
2. 封闭性
3. 可再现性

进程特点

1. 动态性
2. 并发性
3. 独立性
4. 异步性

进程是进程实体运行的过程, 是系统进行资源分配和调度的独立单位

进程的基本状态

1. 就绪
2. 执行
3. 阻塞

还有一种状态是挂起
那挂起和阻塞的区别在哪里
挂起的话其实好像是直接把这个进程调到了外存里, 这样子的话, 如果好像挂起属于中级调度, 而阻塞的话, 进程还在内存中, 只在内存中的话, 这个调度还算是低级调度吧

进程控制块

PCB(进程控制块), 是进程存在的唯一标识, 进程控制块位于操作系统内核

进程控制

1. 创建
   用户登录 作业调度 提供服务 应用请求

2. 撤销

3. 阻塞
   进程阻塞是自己阻塞掉自己, 然后再由其他人唤醒, 像是一个异步回调的过程(不知道算不算是)

• 请求资源
• 等待操作完成
• 新数据还未达到
• 等待新任务

1. 唤醒

进程同步

感觉比较复杂的一块
简单说通常就是由于资源共享造成的问题

两种制约形式

1. 间接相互制约
   共享某种系统资源

2. 直接相互制约
   主要源于进程间合作

概念

临界资源: 一次只能为一个进程所用的资源

• 硬件: 打印机
• 软件：内存 指针 数组

临界区：访问临界资源的代码段

进入区
临界区
退出区

其实感觉进入区的设计很关键…不然的话可能就造成…
有的语句, 在高层比如C语言里看到是一条语句, 其实编译后很多条, 就不是原子的

同步机制遵循原则：

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

过去的解决方法

软件
Peterson算法, 其实不是很理解…就是说自己不能很快写出

#define FALSE 0
#define TRUE 1 
#define N 2

int turn;
int interested[N];

void enter_region(int process) {
    int other;
    other = 1 - process;
    interested[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE);
}

void leave_region(int process) {
    interested[process] = FALSE;
}

硬件

1. TSL指令
2. SWAP指令
   硬件解法的特点在于….这个

信号量机制

这个是比较好的解决方案, 由Dijkstra提出

定义

1. 整数信号量S
   原子操作：

• wait(P)

  void wait(int S) {
    while(S <= 0) ;
    S -= 1;
  }
  

• singal(V)

  void Signal(int S) {
    S += 1;
  }
  

1. 记录型信号量S
   由于整数型信号量里的while(S <= 0) ;不符合让权等待
   现在推出了这个记录型的信号量

typedef struct{
    int value;
    struct process_contorl_block *list;
}semaphore;

void wait(semaphore * S) {
    S -> value--;
    if(S -> value < 0)
        block(S -> list);
}

void signal(semaphore * S) {
    S -> value++;
    if(S -> value <= 0)
        wakeup(s -> list);
}

下面有等于0, 是因为

S -> value >= 0代表可用资源数量， S -> value < 0代表阻塞队列中进程的数量

信号量作用

主要两个作用吧, 就是互斥和同步, 就是这样子

1. 用于互斥, 即同一时刻只能同一个人使用资源

int top = -1;
int stack[n];
semaphore mutex; 
mutex.value = 1;

void proc1(int x) {
    // 进程1
    wait(mutex);    // 进入

    top = (top + 1) % n;
    stack[top] = x;

    signal(mutex);  // 退出
}
void proc2(int y) {
    // 进程2
    wait(S); //进入

    top = (top + 1) % n;
    stack[top] = y;

    signal(mutex);  //退出
}

1. 用于同步
   这个说的是那种合作的进程…
   比如生产者消费者问题应该是就算这种的
   生产者消费者共享缓冲池, 其实对于生产者消费者分别相当于是, 空位置和非空位置是资源
   而且生产和消费不能同时进行
   而且下面的例子是那个,,,单消费者单生产者多缓冲区

这里就写伪代码了…

// Producer:
nextp = produce();

wait(empty);
wait(mutex);

Buffer[in_ptr] = nextp;
in_ptr = (in_ptr + 1) % n;

signal(mutex);
signal(full);

// Customer:
wait(full);
wait(mutex);

nextc = buffer(out_ptr);
out_ptr = (out_ptr + 1) % n;

signal(mutex);
signal(empty);

注意的点在于上面不光是有full/signal这个….还同时有mutex…为什么呢
这个mutex是设定了同时只有生产者或者消费者在运作,就是使得在生产的时候不能消费,在消费的时候不能生产,即一个互斥的关系
这个full/signal的话就是说对资源的同步….

如果我们改变这个问题呢….
比如

1. 多生产者, 单消费者, 多缓冲区
   其实和上面的单生产单消费多缓冲一样的

2. 多生产者, 多消费者, 单缓冲
   单缓冲的话, 其实就不需要mutex了,这个时候full和signal就代替了mutex的作用

3. 单生产者, 单消费者, 单缓冲
   感觉只要是单缓冲的话, 就很简单了, 和几个生产几个消费好像没关系了, 就是和上一个应该是完全相同的

4. 允许生产者写的时候消费者读
   这个时候, 第一想到就是不需要mutex了,其实不然…只是可以Producer和Customer一起进行了, 但同类之间还是互斥的,这个时候, 解决方法是设置mutex_Producer和mutex_Customer…程序大概变成了这个样子

// Producer:
wait(empty)
wait(mutex_Producer)
// 生产
singal(mutex_Producer)
singal(full)

// Customer:
wait(full)
wait(mutex_Customer)
// 生产
singal(mutex_Customer)
singal(empty)

1. 调整wait/signal顺序
   生产者的wait调换的话, 缓冲区为满时候生产者继续运行时候会产生死锁
   消费者的wait调换的话, 缓冲区为空时候消费者继续运行时候会产生死锁

而signal的话是可以互换的…不会有问题, 但有的地方有这样子的话:对任何信号量的wait与signal操作必须配对。同一进程中的多对wait与signal语句只能嵌套，不能交叉, 不太懂

所以总结出来就是那个. wait的话,一定要先wait一个资源型信号量, 然后再wait互斥型的

暂时先看其他的, 先挖个坑

经典问题

1. 生产者消费者问题
   上面已经说到的

2. 读者写者问题
   这个和消费者生产者不太一样的地方在于,这个没有明确资源是什么…就是不需要考虑full和empty的问题, 只是要考虑

3. 写者写的时候不允许其他写者写或者读
4. 但允许多个读者同时访问资源
5. 并没有产品产品/缓冲区的概念, 也就不需要说先写出东西来再去读取

拿到问题后一种想法就是, 我们好像只要有一个互斥量wmutex就可以了,当第一个读者开始读取时候wait一个, 最后一个读者离开时候signal一下…每个写者都要独自的wait和signal
所以初步写出程序大概

// 读者
if(readcount == 0)
    wait(wmutex);

readcount += 1;
// 读操作
readcount -= 1;

if(readcount == 0)
    signal(wmutex);

// 写者
wait(wmutex)
// 写操作
signal(wmutex)

表面上看起来很和谐, 其实有个问题就是这里的readcount也是一个临界变量不能由多个read来访问…所以应该在readcount修改前后也变成临界区

// 读者
wait(rmutex);
    if(readcount == 0)
        wait(wmutex);
    readcount += 1;
signal(rmutex);

// 读操作

wait(rmutex);
    readcount -= 1;
    if(readcount == 0)
        signal(wmutex);
signal(rmutex);

1. 哲学家进餐问题
   关键在于资源申请的时候如果每个人都先申请同一只手的筷子的话…就很容易死锁, 所以应该有个人反着拿

// philosopher[0..3]
wait(chopsticks[i]);
wait(chopsticks[(i + 1) % 5]);
// eat
signal(chopsticks[i]);
signal(chopsticks[(i + 1) % 5]);

// philosopher[4]
wait(chopsticks[(i + 1) % 5]);
wait(chopsticks[i]);
// eat
signal(chopsticks[i]);
signal(chopsticks[(i + 1) % 5]);

进程通信

1. 共享存储器系统
2. 消息方式
3. 管道方式

线程

引入线程后, 进程仍然作为资源分配的基本单位…但线程作为调度分配的基本单位
线程之间共享进程中的大部分资源, 少部分像堆栈, 寄存器, TLS是独有的…

好处

• 统一进程内的线程共享内核和文件, 相互通信无须调用内核
• 创建一个新的线程花费时间少
• 两线程切换花费时间少

类型

• 内核级线程
• 用户级线程
  既然用户级线程没法分配到独立的处理机, 那这种线程的意义在于哪里

特权指令一般能引起CPU系统态和用户态的转变

处理机调度

三个调度等级

1. 低级调度
   决定哪个进程获得处理机, 这里的话其实有抢占式和非抢占式两种

2. 中级调度
   中级的话其实就是挂起操作, 把暂时不需要的进程调到外存上…
   实际上就是传说中内存管理中的对换

3. 高级调度
   把外存上处于后备队列的作业调入内存, 并且为其创建进程, 分配资源, 然后把新的进程丢到那个就绪队列上, 准备执行

评价标准

对于某个特定进程说

1. 周转时间, 包括

• 作业在后备队列的等待时间
• 进程在就绪队列的等待时间
• 进程在CPU上的执行时间
• 进程等待IO的时间

1. 对于操作系统

• 平均周转时间
  各个进程周转时间的均值

• 平均带权周转时间
  每个进程时间带上权值

   W = 1/n * (\sum_{i=1}^n T_i / T_{si})   //我就这样子乱写了...
  

  这个T_i是第i个作业周转时间, 包括上面的四个过程
  T_{si}是第i个作业的要求服务时间, 只包括周转时间的第三第四个过程

调度算法

调度实际上就是资源分配

先来先服务(FCFS)

用于作业调度/进程调度

短作业/短进程优先(SJF/SPF)

用于作业调度/进程调度
困难的点在于难以估计执行时间

高优先权优先

又分为

• 动态优先权
• 静态优先权

其实上面说的先来先服务, 短作业都是分别把到来时间, 执行时间作为优先权的高优先权优先算法, 而下面的高响应比优先相当于把响应比作为优先级

高响应比优先

只是用于作业调度

响应比 = 响应时间 / 要求服务时间 = (等待时间 + 要求服务时间) / 要求服务时间

时间片轮转

时间片选择: 一般是略大于完成一次典型交互需要的时间

多级反馈队列

无心学习…累

实时系统的调度

死锁

这一块的核心在于这里的银行家算法
定义: 由于资源分配造成的一种僵局…陷入僵局..僵局
死锁的进程处于阻塞状态, 但仅靠自己, 无法继续运行

就像我们前面的生产者消费者问题当调换wait操作, 如果先申请互斥, 然后申请资源, 就可能造成死锁
还有哲学家进餐, 如果每个人都同时拿左手/右手边筷子就可能死锁

死锁特征

1. 互斥条件

2. 请求和保持
   就是进程占有一个资源的同时, 请求另外的资源

3. 不可剥夺
   进程的资源在使用完之前不能剥夺….也就是说被占有就被占有了不能转让

4. 环路等待

存储器管理

寄存器和主存称可执行存储器
其实程序从编译到运行, 经历了
编译, 装载, 运行
而链接根据不同的链接方式可能发生在不同的时候

链接

• 编译时链接
• 装载时链接
• 运行时链接

分区分配算法

• 首次适应算法
• 循环首次适应算法
• 最佳适应算法
• 最坏适应算法

基本分页存储管理

由于这个分区分配方案存在碎片问题

基本分段存储管理

由于分页式存在的问题:

• 信息共享和保护不方便
• 编程不方便(哪里不方便)

分段式的话, 把具有相同功能的程序段放在了一起, 这样子可以很方便的设置每一段的权限之类的, 所以说感觉分段更适合逻辑地址空间的管理

分段的特点:

• 分段是一段有意义的信息集合, 所以也容易实现信息保护
• 分段的划分由程序员来完成
• 分段长度不定
• 指令不存在跨分段情况

这四个特点其实就是分段和分页的不同之处, 对吧

但分段的问题在于, 存在碎片…

段页式存储管理

综合分段和分页的优点
做法大概是, 先分段, 之后在分的段上再把他分成一页一页的, 这样子零头就小于一页了….

虚拟存储器管理

内存管理的两个问题

• 大作业在小主存上运行
• 在给定大小的主存上运行更多的程序

这个时候就向不把所有代码同时装入主存, 等需要时候再装入, 这样子的话就能实现我们的目的, 之所以可以这样做, 是因为程序运行的局部性原理
这样子形成的虚拟存储器就好像拥有更大的存储空间一样

虚拟存储器定义:
指的是具有请求调用和置换功能, 能从逻辑上对内存容量进行扩充的一种存储器
逻辑容量接近于内外存之和, 速度接近内存, 价格接近外存

其实从这样子看的话, CPU里的Cache和主存其实也构成了类似的结构

特点:

• 多次性
• 对换性
• 虚拟性

分别在分页, 分段, 段页式的基础上进行虚拟化, 就得到了三种虚拟存储器
请求分段, 请求分页, 段页式虚拟

抖动现象

页面置换算法

• 最佳置换算法( OPT算法)
• 先进先出算法( FIFO算法)
• 最久未使用页面置换算法( LRU算法)
• Clock置换算法

硬件支持

设备管理

这里就是说的I/O系统的管理

控制方式

• 程序轮询
• 中断
• DMA方式
• 通道

设备分配

设备分类

• 独占设备
• 共享设备
• 虚拟设备
  虚拟设备是通过某种技术把一台独占的设备编程能供若干用户共享的设备

设备独立性

用户程序独立于具体使用的物理设备, 其实是通过加了一层虚拟层来实现的
应用虚拟技术,让我们建立虚拟设备, 并且之后的操作可以都通过操作虚拟设备来实现

SPOOLing技术

磁盘

磁盘访问时间 T = Ts + Tr + Tt, 其中
Ts: 寻道时间 Ts = 8 ~ 10ms
Tr: 旋转延迟 Tr = 1 / (2r)
Tt: 传输时间 Tt = b / (rN)
r: 转速; N: 每磁道字节数; b: 传输字节数
并且有: Ts > Tr >> Tt

时间耗费主要是在寻道上, 所以磁盘调度的目标在于使得平均寻道时间最短

磁盘调度算法

• 先来先服务FCFS
• 最短寻道时间优先SSTF
• SCAN 某同扫描算法
• CSCAN 这个是循环扫描
  这个CSCAN是单向的, 只在一个方向上满足磁道访问请求

其实发现调度算法最常见的两种就是先来先服务和短时间优先

文件管理

操作系统接口