OS考点（一）https://developer.aliyun.com/article/1498390

调度算法

目标和相关定义

• 运行时间:占用cpu运行的时间
  周转时间=等待时间+运行时间周转时间 = 等待时间 + 运行时间周转时间=等待时间+运行时间
  响应时间在等待时间里面
  带权（归一化）周转时间𝑾=Tt/Ts，其中Tt𝑾 = T_t/T_s，其中T_tW=Tt/Ts，其中Tt 是进程的周转时间，TsT_sTs 是该进程接受服务的时间（即运行时间）
  

先来先服务,排队算法

FCFS (Fisrt Come Fisrt Serve) 或 FIFO (First In First Out)

• 缺点:周转时间长 I/O型进程必须等待计算型进程用完CPU，将导致 设备使用率低，对短作业不公平

最短作业优先

SJF(Shortest Job First) 或 Shortest Process Next- 在目前的假设条件下，可以证明，SJF调度算法的平均 T周转时间是**最优（optimal）**的

• 缺点:作业可能在任何时刻到达,周转时间也会变长

最短剩余时间优先

SRT(Shortest Remaining Time)或STCF(Shortest Time-to-Complete First-

新来作业产生中断，重新调度

缺点

• 可能产生饥饿(starvation) 在上面的例子中，从10时刻起，如果源源���断有短进程到来，则作业A始终得不到执行

• SJF也可能饥饿，比如0时刻到来10和100作业，之后不断有10作业到来
• 由于允许抢占，SRT比SJF更容易饥饿
• 对长作业不公平

• 算法的实现更困难，开销更大

• 必须支持中断处理（抢占）
• 需要计算“已运行的时间”
• 每次中断都要调度

轮转（轮询）调度算法

响应时间比上面三种都要好

RR（ Round Robin ），又称时间片调度

• 每运行一个时间片（time slice, scheduling quantum，时钟周期的倍数）产生时钟中断，并重新调度
  
• 公平，长短作业都能兼顾，不会饥饿
  
• 调度时算法简单（可仅用FCFS）
  

时间片大小的选取

缺点

• T周转T_{周转}T周转是各种调度算法中较差的，甚至可能还不如FCFS

高响应比优先

短作业尽快响应，长作业也能照顾到，平均周转作业时代的一个折中方案

响应比（Response Ratio） 𝑹𝒓𝑹_𝒓Rr𝑹𝒓=(等待时间+运行时间)/运行时间𝑹_𝒓 = (等待时间 + 运行时间)/运行时间Rr=(等待时间+运行时间)/运行时间=周转时间/运行时间 = 周转时间/运行时间=周转时间/运行时间当等待时间同样长，短作业的响应比高，优先执行

一般来说，没有抢占，即等待时间 == 响应时间

随等待时间的增加，响应比会上升，从而照顾到长作业

终极解决方案-MLFQ

多级队列(静态优先级)调度：

多级=多个队列，各有不同的优先级（Priority） 具体怎样实现是机制(mechanism ，战术)，如：

• 应该定多少个优先级？
• 每级队列使用什么调度算法（FCFS、RR）？
• 每级队列应该分多大的时间片？
• 当用完时间片，降多少级？
• 满足什么条件提升优先级？提升多少？
• 上述内容用什么方式实现？（查表、数学公式……）

规则

1. if Priority(A)>Priority(B)，运行Ａ（不运行B），大于小于号要具体确定
2. if Priority(A)=Priority(B)，以RR方式运行A和B
3. 新来的作业的优先级定为最高
4. 如果一个作业（在一定时间S内累计）用完了它的时间片，则降低其优先级
5. 如果作业在时间片前释放CPU，则保持不变
6. 一定时间S后，将所有作业提升为最高优先级

缺点：

• 对未知进程难以确定优先级；
• 饥饿；
• 误判：假如一个进程刚开始是计算型的，但随着时间变化为交互式的，却因为降级而永远不能被平等对待
• 博弈问题：吃透了规则的计算型进程，对普通计算型进程不公平

公平共享调度

• 优先级调度的目标：优化周转时间、响应时间、资源利用率
• 公平调度的目标：让每个任务都能获得一定份额的系统资源

Lottery调度（摆烂调度）

• 为每个进程提供至少一张彩票
• 更重要的进程获得较多彩票
• 每次调度时，随机选取一张，握有该票的进程运行
• 可在需要时将彩票交给合作进程

调度算法总结

进程同步

海森堡bug：不可重现的bug。如果程序重启，bug就可能不再出现。

可能原因：

1. 调试器本身影响了bug的产生；
2. 编译器的不恰当优化；
3. 未��始化变量的值；
4. 时间敏感的bug：常在多进程/多线程并发的程序发生

对共享变量的并发写操作（读没关系），有必要互斥共享变量，如果不做相关保护措施，会有极大的可能造成bug

在实现同步之前，进/线程：

• 可能在任何时间被暂停与重启；
• 一旦暂停，其等待的时间未知；
• 多个进/线程可能以任意顺序运行；

进程同步的基本概念

• 竞争条件（race condition）：多个进程在操作一个共享数据时，结果取决于多个进程的指令执行顺序
• 同步（ Synchronization ）: 协调多个进程的执行次序，确保并发的进程之间按照一定的规则共享系统资源，很好的相互合作，使程序的执行具有可再现性。
• 互斥（ Mutual Exclusion ）:当某进/线程正在做某件事时，不允许其它进/线程也做这件事
• 临界资源（Critical Resource）：操作系统中一次允许一个进程访问的资源

• 如：打印机、文件、全局变量……
• 对临界资源应采用互斥方式共享

• 临界区（ Critical Section ）: 一次只有一个进程以执行的那段代码。即进程中访问临界资源的那段程序。

• 实现了互斥，也就有了临界区

• 锁（ Lock ）: 防止其它进程进入的工具

• 进入临界区前上锁
• 离开后解锁
• 如果已有锁，则在临界区外等待

进程同步的准则

原子操作

所有动作要么全做，要么全不做，操作过程中不能被打断又称原语（Primitive）

实现互斥的软件方法

忙等: 不能进入临界区的进程，一直占用CPU等待进入

• 等待中的进程白白占用处理机周期
• 拿着锁的进程的时间被无效的等待进程占用
• 优先级反转（priority inversion）

例外：

• 在多核CPU系统中，对于只占用很少时间的临界区，忙等 反而可以节约上下文切换的开销。

Peterson算法

• 当Note && turn 的条件不满足，进入忙等
• 代码必然让线程PA，PB都至少执行到了给turn复制的一步（哪个线程还没到，另一个就会等待）
• 完成后，就是看谁先执行turn赋值，谁先进入临界区，另一个仍然在等待
• 先执行的线程完成后，收走自己的纸条，让另一个线程运行，实现了互斥

软件同步的局限

纯软件方法利用最低限度的原子操作支持（Load和Store），也可以实现同步，但是

1. 算法的设计和实现都很困难
2. 在现代计算机架构下可能失效

• 编译器/CPU可能使指令乱序执行（需内存屏障） 所以很少使用纯软件同步方法，多是操作系统配合硬件实现同步，封装成各个api函数给程序员使用，所以不能直接调用。

硬件同步

设法实现两个原语（原子操作）

Lock() – 加锁，当无人用锁时获得锁；若多人同时尝试拿锁，则只有一人能拿到，其余人等待；

Unlock() – 解锁，唤醒在等待的人

cpp

复制代码

Lock(); //进入区
if (noPaper) {
    buy Paper; //临界区
}
Unlock(); //退出区

需要硬件提供更多的原子操作。

关中断

进程切换

• 内因：进程做了某事(系统调用或异常)，自己释 放了CPU
• 外因：中断导致内核介入，进程失去CPU

如果关闭了中断，无论内因外因均不再响应，则可以避开进程切换

关中断方案，又称屏蔽(mask)中断

问题

• 不能允许用户使用这种锁！只可能内核使用
• 由于临界区的代码运行的时间未知，不能保证实时性；更重要任务发生时，系统也无法响应（死循环关闭中断）
• 仅能关闭单个CPU，不适合多核CPU

读-修改-写型原子操作swap

可以用于多核处理器的指令

Test-and-Set

锁

上述硬件原语通常不直接给程序员使用，于是操作系统和高级语言将它们封装为各种接口，供程序员使用。最常见的一类工具就是“锁(locks)”。

• 锁是原子操作，多个进程同时lock，最终须依次执行
• 最先执行lock的进入临界区并加锁，后来的无法进入临界区
• 进不去的进程有两种选择：忙等，或睡眠

• 非忙等——互斥锁——重量级（悲观）锁
• 忙等——自旋锁——轻量级（乐观）锁

信号量

并发问题分为两类：

1. 互斥（Mutual Exclusion）：确保临界资源被互斥的使用

• 工具：锁（Lock）
• 程序员只需识别出临界区
• 竞争共享资源，用mutex=1，P、V操作成对出现

2. 同步（Synchronization）：确保进程按照期望的先后顺序运行

• 工具：条件变量（condition variable）
• 不满足条件的进程等待(wait)，直到条件满足，才通知(signal)其执行
• 控制进程间的先后顺序，初值根据具体情况设置，P、V分开在不同的进程使用对每个约束设置一个信号量

信号量是一种抽象数据类型

• 由一个整形变量（Sem）和两个原子操作（P, V）组成
• P——wait()——等待，信号量值-1（可以负数）
• V——signal()——唤醒，信号量值+1

用法

1. 实现进程互斥，信号量mutex
2. 实现进程间前趋后继（又称同步）关系，可以让进程之间相互等待

生产者和消费者问题

问题描述：

• 一个或多个生产者将产品放入一个共享的缓冲区
• 多个消费者从缓冲区中取出使用
• 生产者和消费者之间并发运行，保持同步

以自动售货机为例，约束条件包括：

• 每次只允许一个人对售货机进行操作（互斥约束）
• 当饮料已售空，消费者必须等待生产者（同步约束）
• 当饮料已放满，生产者必须等待消费者（同步约束）

用信号量实现问题时的准则：

对每个约束条件，各使用一个单独的信号量

• Semaphore mutex; //互斥的约束
• Semaphore drinkSlots ； //消费者的约束
• Semaphore emptySlots; //生产者的约束

生产者和消费者的工作并不需要互斥。

生产者每次只能一个（互斥），消费者同样

因为buffer的容量只有1，PV操作在实现信号量同步，保持生产者消费者之间的关系时，也天然实现了互斥，最多只有一个访问共享条件。

• P表示等待这个条件

OS考点（二）https://developer.aliyun.com/article/1498394