并发

两个概念

并发：两个活动在起始时间和终点时间有交叠，就叫并发执行
并行：两个程序在在同一时间运行在不同的处理机上

并发可能是伪并行，也可能是真并行，并行一定是并发

并发执行的特点

如果只有一个处理器，并发是间断性的，具有“执行-暂停-执行”这种间断性规律
非封闭性：系统中的资源由多个程序共享，资源的状态由多个程序来改变，导致程序之间互相影响
不可再现性：相同的程序可能执行出不同的结果，主要由非封闭性导致

伯恩斯坦条件

只要两个程序不会同时修改程序，他们就可以并发。是并发程序结果可再现的充分条件。

优点

提高整体资源利用率，缩短整体运行时间

进程

定义

进程是一个程序及其数据，在处理机上顺序执行时所发生的活动

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

从上面两个定义我们可以得到一些结论：进程是一个动态的执行过程，是静态的程序与数据在处理机上运行时的动态表现；操作系统将进程视为一个独立的实体，用于分配资源和调度任务，进程是操作系统管理的基本单位。

进程的特征

动态性，上面说过了，这里不再赘述
并发性，多个进程是能够在一段时间内同时存在于内存当中的
独立性，进程是独立运行的基本单位
异步性，进程以各自独立的不可知的速度向前推进

进程的结构特征

一个进程主要由以下几部分构成：

PCB控制块
代码段：存储程序的可执行代码
数据段：包含.bss段和.data段
堆：用于动态内存分配（如 malloc 或 new）
栈：用于存储局部变量和函数调用的上下文

PCB也是一种数据结构，是操作系统用来管理进程使用的。其内容包括：

进程标识符：每个进程都有一个唯一的标识符，在Linux中是一个整形数
程序和数据的地址：把PCB与进程的程序和数据联系起来
进程状态（就绪、运行、阻塞…）：系统会将相同状态的进程组成一个队列，以便于管理
现场保护区：当进程由于某种原因不能继续占用CPU时，就会释放CPU，这时必须将CPU的各种状态存储在PCB中，当下次该进程再次得到CPU时，能够恢复CPU的各种运行状态，让进程继续运行，其中包括了程序计数器，寄存器状态（保存进程运行时的寄存器的值），内存管理信息（包括进程的内存分配情况，如页表）等内容。

程序段就是能被CPU执行的代码，程序可能被多个进程共享

数据段存储着进程需要加工处理的原始数据或进程执行过程中产生的中间数据。进程中的不同线程可以共享进程中的全局数据段，其中包含进程的全局变量与静态变量。不同线程也可以通过指针访问进程堆上的数据。

进程的状态与控制

进程控制的实现

进程控制是由操作系统内核实现的，主要任务是实现进程的创建、撤销以及状态转换。由于进程控制操作通常涉及到多个步骤，为防止并发带来的竞争或死锁等问题，进程控制主要依赖原语来实现。

原语是操作系统内核中一种特殊的函数，其执行过程不可被中断这样能够保证每个控制操作的原子性。

进程的创建

允许一个进程创建另一个进程，我们称进程的创建者为父进程，被创建的进程为子进程，子进程可以继承父进程拥有的资源。创建成功的进程被插入就绪队列，等待被调度运行。

在Linux中，所有的进程创建都是由fork进行的，因此要了解Linux的进程创建，我们必须了解fork都做了什么。

父进程的状态被复制。父进程整个地址空间都会被复制，其中包括了代码段、数据段、堆、栈，父进程中所有线程的状态（包括线程的栈、寄存器状态、线程局部存储等）也会被复制到子进程中。由于fork在复制时采用写时拷贝技术，因此在刚刚复制时，我们能够保证父进程中所有变量与子进程中所有变量的虚拟地址与物理地址相同。然而一旦子进程需要对某一个变量进行写操作，那么系统就会“真的”复制一个新的变量出来，这时，两个进程中变量的虚拟地址仍然相同，但物理地址就不同了。
子进程中只有一个线程是活动的。父进程中的其他线程在子进程中不会继续执行。换句话说，子进程只继承了调用 fork 的线程的状态，而其他线程的状态被复制但不会继续运行。

进程的阻塞

当一个正在执行的进程发现自己“期待的某些事情没有发生”，就会自主调用阻塞原语使自己的运行状态从执行变为阻塞，可见阻塞是进程自身的主动行为，也只有执行态的进程才能转变为阻塞状态。

当被阻塞进程“期待的事件发生了”，“期待事件“的线程会去通过唤醒原语唤醒被阻塞的线程。

进程的状态与演进

就绪状态，进程已经获得除了处理机以外的所需资源只等处理机资源
执行状态，占用处理机资源
阻塞状态，正在执行的进程由于发生某种事件而暂时无法执行，于是放弃处理机

flowchart TD
    A(执行状态) -->|时间片到| B(就绪状态)
    B --> |调度| A
    C --> |某事件发生| B
    A --> |等待某事件| C(阻塞状态)

进程间通信 IPC

进程通信的方式主要有三种：管道、共享内存、消息系统

管道及命名管道

管道，也即无名管道（Pipe），只能用于父子进程或兄弟进程之间的通信（即具有亲缘关系的进程）。它构成一种独立的文件系统，对于管道两端的进程而言就是一个文件，但它进存在与内存当中，且不属于任何其他文件系统。管道机制类似于生产者-消费者模型，其文件大小是固定的，类似与定长的等待队列，只要管道非满，那么写进程就能一直向管道里写数据，只要管道非空，读进程就能一直从管道中读数据。另外值得注意的是，管道真的就像一个管道一样，写入的内容每次都被添加在管道缓冲区的末尾，而每次都从缓冲区的头部读出内容，即遵循先进先出原则

有名管道（FIFO）提供一个路径名与之关联，使得能够承担没有亲缘关系的进程之间通信的任务。同样的，FIFO也遵循先进先出原则~~（你看它都叫这个名字了对吧）~~

消息传递

进程通过操作系统提供的send()和receive()两个原语进行数据交换，这种方式隐藏了实现细节，对用户友好。

其分为直接通信方式和间接通信方式：直接通信指发送进程直接将信息发送给接受进程，并将信息挂在接受进程的消息缓冲队列上，接收进程从缓冲队列中获取信息。间接通信指发送和接受进程通过一个中间实体进行信息传递。

共享内存

共享内存是最快的IPC方式，因为其避免了其他IPC方式的开销巨大的缓冲复制。共享内存的实现与写时复制相似：其将同一块物理内存映射给A，B两个进程，他们可以同时读取共享内存中的数据，但不能同时进行写操作。共享内存区域保存至进程通信完毕为止。

进程上下文切换与陷入内核

进程上下文切换：

上下文其实就是PCB中现成保护区保存的那些东西，当操作系统需要将一个进程从CPU中切换出去，并将另一个进程调度到CPU上执行时，操作系统就需要保存这个进程的上下文、并恢复下一个进程的上下文信息，这一过程称之为进程上下文切换。

陷入内核：

由中断、异常、系统调用引起
也需要保存现场，因为内核程序也可能破坏用户进程的内容

线程

进程与线程

一个进程在一个时间内只能干一件事，并且只能独享一块地址空间，如果想要在进程内部再引入并发，就需要一个新的类型的实体，他们可以共享相同的地址空间。这种实体就叫线程。

进程同时包含资源拥有者和可执行单元两种概念，而线程只有可执行单元一种概念，将资源边界交给进程管理。由于线程的引入，我们之后可以这样理解进程和线程：

进程是资源分配的基本单位，线程是处理机调度的基本单位

线程基本不拥有资源，只有线程栈上的资源，因此线程的创建速度比进程快10-100倍。这也是引入线程的另一个重要原因，即减小并发时所付出的时空开销，提高操作系统的并发性能。

举个例子，假设一个进程开启了多个线程，那么这些线程共享了哪些资源？独占了哪些资源？

共享：进程中的代码段、数据段（全局变量与静态变量）、进程堆（存储动态分配的内存）、打开的文件描述符；

独享的：栈上的资源（局部变量、函数调用信息）、寄存器状态（PC、SP指针）

线程的实现

用户级线程：有关用户级线程的所有操作都由应用程序在**用户空间（用户态）**内完成，不需要操作系统内核级的干预。线程的上下文切换较快，不需要转到内核空间，。

了解POSIX Pthreads，（是一种标准接口），最好进行一些实验
- 优点：线程切换与内核无关；线程的调度由应用决定，容易优化；可运行在任何操作系统上
- 缺点：很多系统调用会引起阻塞，内核会因此阻塞所有相关的线程；内核只能将处理器分配给进程，每次只给一个进程分配一个CPU，即使有多个处理器也无法实现一个进程中的多个线程并行执行
内核级线程：让kernel进行分身，可以对每个非同步时间产生一个分身来处理
- 优点：内核能在一个处理器上调度一个进程的多个线程同步并发执行；阻塞发生在线程级别；
- 缺点：线程切换需要内核参与，线程的切换涉及到两个模式的切换，降低效率。
混合线程实现方式：取各家所长

同步和并发

主要讨论多个进程之间的关系

同步与互斥问题

临界资源与临界区

临界资源与临界区：将一次仅允许一个进程访问的资源成为临界资源，每个进程中访问临界资源的那段代码成为临界区。

一般来说，临界区中的代码会被entry section和exit section保护起来，以保证同一时间只有一段代码“进入临界区”。

同步与互斥

这里有必要解释一下同步与互斥的概念。互斥指某一资源在同一时间只允许一个访问者对其进行访问，具有唯一性和排他性。而同步是一种进程间的直接的制约关系。例如在生产者-消费者模型中的生产者进程与消费者进程，他们需要相互合作才能完成生成-消费这一任务，而这样的合作带来了进程之间的协调问题，导致了进程之间的等待、阻塞，形成了制约关系。一般来说，只要是同步的关系就应该是互斥的关系。

基于忙等的互斥算法

首先要明确什么样的互斥算法是正确的。它必须实现以下三点要求，原则上遵循第四点要求：

空闲让进。当临界区空闲，允许任一请求进入临界区
忙则等待。当有进程访问临界区，任何进程不能再进入临界区
有限等待。对申请访问临界区的进程，应让其等待有限时间
让权等待。若进程不能进入临界区，应当立即释放处理器，防止进程忙等

那么显然，基于忙等的互斥算法是无法满足第四点的。

软件算法

在顺序执行指令的条件下，利用软件实现忙等的互斥算法

Peterson算法

// P0                           // P1
flag[0] = true;                 flag[1] = true;
turn = 0;                       turn = 1;
while(flag[1] && turn == 0);    while(flag[0] && turn == 1);
critical section;               critical section;
flag[0] = false;                flag[1] = false;

如何验证一个算法的正确性？就是一次检查该算法能否满足上面提到的三点要求。

首先看”空闲让进“，当临界区空闲，假设该时刻只有一个进程申请进入临界区，那么flag[i] = true, turn = 1，此时flag[j] = false，因此无需进入while循环等待，可直接进入临界区。

假设该时刻和同时申请进入临界区，那么两个flag都被置true，而对于turn变量，它在极短时间内会被赋值两次，但最终它的值只能有一种可能，因此两个线程不可能同时进入while循环，必定有一个成功进入临界区。当该进程从临界区出来后，对应的flag被置false，那么另一个进程也能够进入临界区了。因此，”空闲让进“是满足的。

对于”忙则等待“和”有限等待“，在第二个假设时已经被分析过了，都是满足的。

这种算法本质都是精心的设计了赋值语句的先后顺序。所以先后顺序非常重要，其中蕴含了因果关系。

硬件算法

中断屏蔽：关闭中断，使得指令流的执行不被打断。过于粗暴
test and set指令：

不停的检查lock的值，如果lock为false就可以进入临界区，同时无论lock初值为何，都为lock置true


bool test_and_set(bool *lock) {
  bool old;
  old = *lock;
  *lock = true;
  return old;
}

aquire(lock) {
    while(test_and_set(&lock) == 1);
}

/* critical section */

release(lock) {
    *lock = 0;
}

swap指令

为每个临界区设置一个lock，为每个进程设置一个key，不停的检查该进程的key是否为true，如果为true就需要等待，同时与lock交换值。其实逻辑与TS非常相似，都是查看lock的旧值，并为lock上锁

忙等是浪费CPU时间的，并且不区分进程优先级，如果低优先级任务先进入临界区，可能导致高优先级进程一直进行忙等，导致死锁

基于信号量的方法

信号量机制

记录型信号量不存在忙等问题。信号量需要一个整形变量value，以及一个进程链表，用于存储所有等待中的进程。

信号量只能通过初始化和两个标准的原语来进行操作。他们的语义分别为：

typedef struct {
  int value;
  struct Process *L;
} semaphore;

void P(sempaphore s) {
  s.value--;
  if (s.value < 0) {
    block(s.L)
  }
}

void V(semaphore s) {
  s.value++;
  if (s.value <= 0) {
    // <=0是因为需要看++前是否<0
    wakeup(s.L);
  }
}

物理含义：S.value > 0时表示资源的个数，S.value < 0时表示等待进程的个数。P操作表示分配一个资源，如果无法分配则阻塞wait，V操作表示释放资源，如果有等待进程则唤醒signal。

基于信号量实现进程互斥

init(S) = n; // 一次允许n个进程进入临界区

P(S) -> 临界区 -> V(S);

P(S) -> 临界区 -> V(S);

这种实现就像获取了n把锁中的一把，从临界区出来后再释放掉锁

PV操作优缺点：
- 优点：表达能力强
- 缺点：不够安全，可能出现死锁

基于信号量实现进程同步

假设现在有两个进程需要进行写作，要求进程1先执行完语句x，进程2再执行语句y，那么可以通过如下代码实现：

semaphore s = 0;
P1() {
  x;
  V(s);
  // ...
}

P2() {
  P(s);
  y;
  // ...
}

进程1执行完x后执行V，相当于生产出一个产品等待进程2去消费，线程2等待到了产品，执行P进行消费，之后执行y。又或者，进程2执行了P，发现没有产品能够消费，只能进行等待，这是进程1执行完了语句x并通过V操作生产了产品，同时通知了进程2，进程2进行消费，之后执行语句y。

经典进程同步与互斥问题

生产者消费者问题

蕴含两个隐藏条件：消费者和生产者数量不固定，消费者和生产者不能同时使用缓存区

信号量设置：

1
2
3

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

mutex其实就是一个锁，保证生产者和消费者不同时进行读写，empty代表一个空位，当empty为0时，说明buffer已经“没有空位”，即满了，那么此时生产者不能再生产，需要等待。full代表一个填充位，如果full为0则说明队列“没有填充位”，即空了，此时消费者无法进行消费，必须等待生产者进行生产。

Producer() {
  P(empty);   // 消耗一个empty，如果empty为空则等待
  P(mutex);
    buffer.add(object);
  V(mutex);
  V(full);    // 释放一个full
}

Consumer() {
  P(full);    // 消耗一个full，如果full为空则等待
  P(mutex);
    buffer.remove();
  V(mutex);
  V(empty);   // 释放一个empty
}

需要注意的是，P(empty)和P(mutex)的顺序不能颠倒，因为我们必须先判断是否需要等待empty，如果不需要等待才可以去获得mutex锁，否则，如果先获得mutex锁再去判断empty，这时如果需要等待empty，线程将无法释放mutex锁，导致消费者就无法去消费，造成死锁。

读者写者问题

对于共享资源的读写操作，任意时刻“写者”只能有一个，而读者允许有多个。

举例来说，在12306买火车票时，所有查票的用户都是读者，而买票的用户就是写者，因为买票操作需要改变剩余票数等信息。

基于信号量的读写锁

对于第一个读者，需要获取写锁，后面的读者无需获取写锁。对于最后一个读者，需要释放写锁，其他读者不能释放写锁。

对于每个写者，均需要获取、释放写锁。

由于并非所有读者都要对写锁进行操作，因此我们需要一个记录读者数量的变量count，这也是读写者模型的关键。而对于每一个读者来说，他们都需要访问count变量来判断自己是第几个读者，因此count又是一个在读者间共享的变量，所以我们需要加一个mutext来保护count。我们可以得到如下伪代码：

int count = 0;
semaphore mutex = 1;
semaphore rwLock = 1;

writer() {
  P(rwLock);
  writing();
  V(rwLock);
}

reader() {
  P(mutex);
  // 获取count的保护锁以访问count
  if(count == 0) {
    // 第一个读者需要获取写锁
    P(rwLock);
  }
  count++;
  V(mutex);

  reading();

  P(mutex);
  // 获取count的保护锁以访问count
  count--;
  if(count == 0) {
    // 最后一个读者，需要释放写锁
    V(rwLock);
  }
  V(mutex);
}

但这样的读写锁对于写者是不公平的，因为一旦有一个读者开始进行读操作，就算后面的写者来的再早，也必须等所有读者完成读操作。

写者优先

int w_cnt = 0, r_cnt = 0;
r_lock = semaphore(1);
w_lock = semaphore(1);
r_mutex = semaphore(1);
w_mutex = semaphore(1);

writer() {
  // writeSwtich.lock(noReaders);
  P(w_mutex);
    if(w_cnt == 0) P(r_lock);
    w_cnt++;
  V(w_mutex);

  P(w_lock);
  write();
  V(w_lock);

  // writeSwitch.unlock(noReaders);
  P(w_mutex);
    w_cnt--;
    if(w_cnt == 0) V(r_lock);
  V(w_mutex);
}

reader() {
  P(r_lock);
  // readSwitch.lock(noWriter);
  P(r_mutex);
    if(r_cnt == 0) P(w_lock);
    r_cnt++;
  V(r_mutex);
  V(r_lock);

  read();

  // readSwitch.unlock(noWriter);
  P(r_mutex);
    r_cnt--;
    if(r_cnt == 0) V(w_lock);
  V(r_mutex);
}

上述代码中，写者没有附加条件的直接进行了写模式的lightswitch，而读者需要先获取读锁才能进行读模式的lightswitch，这意味着如果写者先进行了写模式的lighswitch，读者只能在lightswitch外等待，如果读者先进行了lightswitch，此时来了一个写者，写者直接进行lightswitch，使得后续的读者无法继续进入临界区，而当临界区中的所有读者出来后，写者就可以开始写操作了。

所谓的lightswtich，其目的在我理解就是为了构造了一个“蓝方自由进出，红方不得进入”的区域，因此如果蓝方使用了lightswitch对mutex上了锁，那么相应的红方应该在mutex上睡觉。而这样一个区域就自然而然的让蓝方获得了优先权，因为一旦一个蓝方来了，后面的红方无论到的多早，都需要等后续所有蓝方从临界区出来，才能访问临界区。

公平读写锁
那么想要公平也很简单，让双方在最开始公平的竞争另外一把锁即可。

汇点问题

假设我们有一个回合点，当N个人都到达了这个点后，才能进行下一步操作，且下一步操作必须一个一个人来。

int cnt = 0;
mutex = semaphore(1);
barrier = semaphore(1);
next_step = semaphore(1);

P(mutex);
  cnt++;
  if(cnt == N){
    for i in 1 to 5:
      V(barrier);
  }
V(mutex);

P(barrier); // 集合点

P(next_step);
// do something
V(next_step);

总的来说，前面N-1个到达的人都在P(barrier)上这个集合点睡觉，当第N个人到的时候，他不用睡了，并且唤醒所有睡觉的人，进行下一步。

需要注意的是，这个集合点在V(mutex)之后，因为如果在其之前，第一个到达的人还没有释放mutex就睡觉的话，第二个就无法进行cnt的计算，造成死锁

哲学家就餐问题

5个哲学家围坐一张桌子，桌子上放5支筷子，每个哲学家有就餐和思考两个动作，其中就餐动作必须在获得左手和右手两支筷子后才能进行

如果采用传统的信号量方法：

P(chopstick[i]); 
P(chopstick[(i+1)mod 5]); 
eat();
V(chopstick[i]); 
V(chopstick [(i+1)mod 5]); 
think();

可能会有：所有哲学家均获得了自己左手边的筷子，而无法获得右手边的筷子，导致死锁。

解决思路也有很多：

至多只允许四个哲学家同时（尝试）拿起筷子进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。

mutex = semaphore(n-1);

P(mutex);
P(chopstick[i]); 
P(chopstick[(i+1)mod 5]); 
eat();
V(chopstick[i]); 
V(chopstick [(i+1)mod 5]); 
V(mutex);
think();

对筷子进行编号，奇数号先拿左，右；偶数号相反。
同时拿起两根筷子，否则不拿起。（基于AND信号量集）

理发师问题

进程：理发师，顾客
行为：理发师->理发，顾客->接受理发

管程

定义一种数据结构，用这种数据结构来封装我们需要共享的资源，而将对该数据结构进行的操作定义为一组过程。进程对共享资源的申请、释放等操作都必须通过这组过程来实现，则组过程又可以根据资源情况，接受或阻塞金策会给你的访问，从而确保同一时间只有一个进程使用共享资源。可以进行这样一种类比：管程就像一个类，管程内的共享数据是private的，只能通过管程提供的方法来进行访问。

管程由局限于管程的共享变量说明、对管程内的数据结构进行操作的一组过程（操作原语）、条件变量、以及对局限于管程的数据设置初始值的语句（初始化代码）组成

管程中的每个条件变量保存了一个等待队列，用于记录所有因该条件变量而阻塞的进程。对条件变量的操作只有wait和signal两种。当某进程执行x.wait时，如果x对应的条件不满足，那么该线程就会被阻塞，并加入到x的阻塞队列中。当另一个进程执行x.signal时，就会唤醒一个因x条件而阻塞的队列。

CPU调度问题

CPU调度问题有三个层次：

高级调度（作业调度），是内存与辅存之间的调度，通常仅在多道批处理系统中出现；
中级调度（内存调度），将暂时不能运行的进程调度至外存进行等待，并修改进程状态为“挂起态”，当进程的运行条件得到满足时，又将进程重新调入内存，并修改进程状态为“就绪态”，挂在就绪队列中。中级调度的目的是提高CPU的吞吐量和内存利用效率。
低级调度（进程调度），指按照某种算法决定如何从就绪对列中取出进程，并将CPU分配给它

进程调度又可以分为非抢占式的和抢占式的。

进程调度策略

调度策略性能准则

用户要求：

周转时间：作业从提交到完成（得到结果）的时间，包括在收容队列中等待的时间、CPU执行时间、阻塞等待时间等。其计算方式为：

$周转时间作业完成时间作业提交时间$

为了避免大型作业的周转时间过长导致周转时间计算不公平的问题，引入带权周转时间，将CPU执行时间作为权重，且权重作为分母，即：

$带权周转时间作业周转时间作业实际运行时间$

响应时间：从用户输入一个请求到系统首次进行响应的事件。是对于交互系统的重要评价指标
截止时间：开始截止时间（最早开始）和完成截止时间（最晚结束）时间

类似于deadline

操作系统要求：

吞吐量：单位时间内完成的作业数。与调度算法本身特性和作业本身大小都有关系：长作业需要消耗较长的CPU时间，导致吞吐量降低，短作业只消耗较短CPU时间，导致吞吐量增加。需要注意的是，由于并发执行的作业在时间上可以重叠，吞吐量并非平均周转时间的倒数
CPU利用率，计算方式如下：

$利用率有效工作时间有效工作时间空闲等待时间$

抖动：进程数量增加，导致进程频繁的被调入调出，使得每个进程的执行时间增长，称为抖动。值得注意的是，要解决抖动问题，不光要关注于进程调度策略，也应当关注内存调度策略。

调度策略实现时需要考虑的问题

进程队列组织形式
占用CPU的方式：抢占式或不可抢断式
进程分类
时间片：如何选择时间片大小？太大，成了批处理系统，进程不主动放弃时间片就不会退出；太小，会导致进程频繁切换，造成时间浪费

批处理调度算法

先来先服务（FCFS）：

与缓存替换策略中的FIFO类似，按照进程到来的顺序分配CPU使用权。
不抢断
特点：
- 利于长作业，不利于短作业（因为不抢占）
- 利于批处理

最简单但也是效率最低的算法，一般不用在分时系统和实时系统中，但会和其他算法结合使用，例如在使用优先级作为调度依据的算法中，当两个作业优先级相同，可使用FCFS进行调度

短作业优先（Shortest Job First）：

对预计执行时间短的作业优先分配CPU
不抢断
特点：
- 能够改善周转时间和带权周转时间，提高系统吞吐量
- 对长作业不利，可能导致长作业饿死
- 由于作业时间实际运行时长难以估算，可能导致调度不准确

注意：SJF的平均等待时间和平均周转时间是最优的

我们可以证明这个结论：假设有一个非SJF的调度序列，则该序列中一定存在一个长作业位于短作业前，考虑交换这个两个作业的顺序

短作业的等待时间变短长作业的执行时间

长作业的等待时间变长了短作业的执行时间

其他作业的等待时间不变

因此所有作业的总等待时间变短了，那么重复这样的交换，我们就能将一个非SJF序列变为SJF的。

由于周转时间 = 等待时间 + 执行时间，而无论执行顺序如何，所有作业的总执行时间不发生变换，因此SJF的平均周转时间也是最短的

最短剩余时间（SRTF）：

将短作业优先改为抢断式，就是SRTF，即一个新就绪的进程比当前正在运行的进程具有更短的完成时间，那么打断当前进程，执行新的进程
对长作业更不利，因为会被频繁打断

最高响应比优先（HRRF）：

该算法是对FCFS和SJF的综合考虑，同时考虑了作业的等待时间和预计运行时间。响应比的计算方式如下：

$等待时间请求运行时长请求运行时长$

特点：
- 等待时间相同时，请求时间越短，优先级越高（利于短作业，类似SJF）
- 请求时长相同时，等待时间越长，优先级越高（类似FCFS）
- 通过等待时间与优先级的正相关关系，一定程度上缓解了长作业饥饿的现象

交互式系统调度算法

时间片轮转算法

将系统中所有的就绪进程按照FCFS原则，排成一个队列
每次调度时将CPU分派给队首进程，让其执行一个时间片
一个时间片结束时发生时钟中断
调度程序将当前执行的进程送到就绪队列末尾，进行上下文切换后，执行就绪队列队首的时间片
进程可以主动让出未使用完的时间片（如阻塞）

多级队列算法

前面的所有算法都只有一个调度队列，多级队列算法，顾名思义，就是设置了多条调度队列，将不同类型或具有不同性质的进程放入不同的队列中。每个队列可以采用不同的调度算法，同一队列中的进程可以有不同的优先级，不同的队列本身也可以有优先级之分

多级反馈队列

可以说是前面多种算法的集大成者。具体怎么集的呢？

首先，它设置了多个调度队列，每个队列的优先级不同。具体来说，第1级队列的优先级最高，之后的队列优先级逐一降低
每个调度队列中进程能够被分配到的时间片长短不同，级数越低、优先级越高的队列时间片越短，例如第级队列的时间片比第级队列的时间片短1倍
对于每一个新到来的进程，将其放入第1级队列中。在每个队列内部使用FCFS算法。当一个进程被执行时，如果它能够在给定的时间片内执行完，则撤离系统，如果不能，则将其加入到下一级的队列中等待执行，如此循环直至执行完成
队列之间的调度策略采用可抢断的优先级调度：只有当第级队列为空时才调度第级队列中的进程，若CPU正在执行第级队列中的进程时，此时有新的进程被加入到第1级队列中，那么此时必须立即将正在执行的进程放回第级队列，CPU立即开始执行新的进程

实时系统调度算法

实时系统中，计算机必须在一个确定的时间范围内恰当做出反应。对于这种系统，正确但迟到的应答往往比没有答案还要糟糕

我们规定任务的周期为，执行时间为，截止时间为，CPU利用率用表示

单调速率调度 RMS

优先级静态固定分配：优先级与周期成反比，周期越短优先级越高

高优先级任务可抢占低优先级任务的执行

对于RMS，并不是任务集利用率小于1就是可调度的，任务集可调度必须满足
最早截止期优先 EDF

任务的绝对截止时间越早，其优先级越高，优先级最高的任务最先被调度。如果两个任务优先级一样，随机选择一个进行调度

调度条件为：
LLF

优先级倒置

现象：先到来的低优先级进程获得了临界资源的锁，导致高优先级进程被阻塞

解决方法：

优先级置顶：将低优先级进程置为高优先级，使得该进程尽早结束。该方法在临界区短且少的情况下有效，如果临界区非常长，原本高优先级的任务依然要等待很长时间

优先级继承：当一个高优先级进程需要去获取锁时，将持有该锁的进程的优先级置为高优先级进程的优先级

死锁

所谓死锁，指多个进程互相等待对方手里的资源而造成的一种僵局

进程可能还存在一些与死锁不同但类似的状态：

活锁：进程没有被阻塞，但由于某些条件没有被满足，导致一直进行“尝试、失败、尝试”的循环。与死锁不同，活锁进程处于执行状态而非阻塞状态
饥饿：某些进程可能由于资源分配不公平导致长时间的等待。进程可能处于就绪状态，但由于调度算法的缺陷，长期得不到CPU，也可能处于阻塞状态，但条件长期无法被满足（这里的“无法满足”并非由其他线程造成，而是外部不可抗力导致的，例如长期得不到IO设备）

必要条件

产生死锁必须满足一下4个条件：

互斥条件：指进程对分配的资源进行排他性使用
请求且占有条件：进程在获得一定资源后又请求新的资源，无论是否获得新的资源，已持有的资源不会被释放，换句话说就是，进程在等待状态依然持有已获得的资源
不可剥夺条件：进程已经获得的资源在未使用完前不能被剥夺，只能在使用完后自主释放
环路等待条件：存在一个资源循环等待链，链中的每个进程都在申请下一个进程所持有的资源。形式化的来讲，存在一个等待态进程集合，其中等待的资源被占有，等待的资源被占有。然而对于一个系统来讲，不一定所有进程都位于该集合中，如果对于上述集合，存在一个进程不在集合中，等待的条件既可以从获得又可以从获得，那么当释放了资源，该等待环路就会被打破。因此我们说，环路等待条件只是死锁的必要条件。

充分条件

假设我们有个进程，第个进程需要的资源数量为，如果，那么此时一定发生死锁。该表达式描述的情况是：所有的线程距离能够运行只差1个资源，但是此时已经没有剩余资源了，因此每个进程都不能正常运行。这是最极端的情况，我们通常根据该表达式求得不发生死锁所需要的最少资源数量或最大进程数量。

处理方法

死锁预防 Deadlock Prevention
死锁避免 Deadlock Avoidance
死锁检测 Deadlock Detection

死锁预防是一种静态的策略，通过消除四个死锁的必要条件中的一个，使得死锁不会发生；死锁避免是一种动态的策略，它需要在每一次进程发出对资源的请求时检查该请求是否会导致潜在的死锁风险，如果有风险，则要避免这一风险，那么就拒绝进程的请求；死锁避免需要保证进程在之后的运行过程中始终不出现死锁，因此需要知道进程从开始到结束的所有资源请求，而死锁检测只检测某个时刻是否发生了死锁，只需要知道对应时刻的资源请求

死锁预防

既然死锁的发生必须满足4个必要条件，那么可以通过破坏其中一个条件，达到预防死锁的效果。

打破互斥条件：允许进程同时访问某些资源，但是有些资源本身就是不能被同时访问的，因此可行度较低
打破申请且占有条件：一种方法是采用预先静态分配方法，只有当进程的全部资源被满足时，才一次性的将所有资源分配给进程。但这样做缺点也是很多的：进程需要的资源通常是动态的、不可预测的，同时要么资源利用率低，要么会降低进程的并发性。对上述方法进行改进，允许进程只获得初期运行所需要的资源后便开始运行，但只有在运行过程中逐步释放完所有获得的资源后，才能请求新的资源。
打破不可剥夺条件：当一个进程请求新的资源而得不到满足时，必须释放当前已经获得的资源，即进程能够剥夺某一个进程已经占有的资源
打破循环等待条件：把资源事先编号，所有进程在申请资源时必须严格按照资源序号递增的顺序进行申请，即一个进程只有在已经占有小编号资源的前提下才能申请大编号资源。但也有缺点：由于对资源分配的过程进行了一定限制，对于每个进程来说，能够得到资源的可能性就降低了。

死锁避免

每发生一次申请时要进行一次动态的死锁检查。

安全序列

一个进程序列是安全的，是指若对于每一个进程，它需要的附加资源可以被系统当前可用资源加上其之前的所有进程占有的资源之和所满足，则称该进程序列是安全的

举例来说：

最大需求	已分配	可用
3	9	3
2	4
2	7

此情况下可以得到一个安全序列，即先将可用的3个资源分配给，执行完成后释放4个资源，共有5个可用资源，将其全部分配给，执行完成后释放7个资源，再分配给

需要注意的是，如果系统存在这样一个安全序列，那么一定不会出现死锁，如果系统不存在这样一个安全序列，那么系统是不安全的，但不安全并不一定意味着出现死锁。

银行家算法

假定顾客借款分成若干次进行，并在第一次借款时说明他的最大借款额。顾客的借款操作按顺序进行，直到全部操作完成。银行家对当前顾客的借款操作进行评估，计算其安全性（当前借款操作是否会导致资金周转不灵）

假设有个进程和种资源，定义如下数据结构：

可利用资源向量：维向量，其中每一个元素代表一类可用资源数目，其初值是系统中所配置的该类全部可用资源数目。如果，表示此时系统中有个类资源可以使用
最大需求矩阵：矩阵，表示每一个进程对每一类资源的最大需求
分配矩阵：矩阵，表示每个进程当前已分得的每一资源数目
需求矩阵：矩阵，表示每个进程接下来还需要多少资源。

上述矩阵有关系：

假设Request[i]是进程的请求向量，我们有如下对于算法描述的伪代码：

# step 1
for j in range(m): 
  if Request[i][j] > Need[i][j]:
    # 该进程需要的资源数超过了其宣布的最大值
    return false

# step 2
for j in range(m):
  if Request[i][j] > Available[j]:
    # 该进程需要的资源数超过了可用资源数
    return false

# step 3
Available = Available - Request
for j in range(m):
  Allocation[i][j] = Allocation[i][j] + Request[i][j]
  Need[i][j] = Need[i][j] - Request[i][j]

# step 4
if isSafe():
  return true
else:
  # 本次试探分配作废，恢复原来的资源分配状态
  recover()

isSafe()是安全性计算函数，其本质就是一个寻找安全序列的过程：首先设置一个工作向量Work = Available，从Need矩阵中寻找“不在安全序列且小于等于Work向量”的行，将其加入安全序列，且使Work = Work + Allocation[i]（注意是加Allocation，因为其假设为该进程执行完成，释放了所有占有的资源）。重复这一过程，直到安全序列里有所有进程，此时就找到一个系统的安全序列，即系统处于安全状态，isSafe()返回true，否则系统处于不安全状态，可能出现死锁，函数返回false。

死锁检测

资源分配图（RAG）算法：

图中从进程到资源的有向边称为请求边，表示该进程申请了一个单位的该资源；从资源到进程的有向边为分配边，表示该类资源已有一个资源分配给了该进程

资源框中画的资源个数应为资源总数，而非当前可用资源数

如何通过该图判断是否存在死锁？

首先明确，一类资源的空闲资源数量为它的资源数量减去已被分配出去的资源数量，即该类资源的出度。

接下来，在图中找到一个不阻塞不孤立的进程，且对于其申请的所有种类的资源，申请资源的数量小于等于空闲资源的数量（说明该进程能够执行完成），那么消去它所有的请求边和分配边使其孤立。反复进行这一个过程，如果最终能消去图中所有边，那么称该图是可完全简化的。为死锁的条件当且仅当的资源分配图是不可完全简化的，称为死锁定理。

死锁解除：

实质：如何通过释放资源让系统中的进程能够继续运行

一定会有牺牲

带星星的表格

原则	资源分配策略	不同方案	主要优点	主要缺点
预防	保守的；预提交资源, 导致资源闲置	一次性请求所有资源	- 对执行一连串活动 (突发式处理) 的进程非常有利 - 不需要抢占	- 低效, 延迟进程的初始化 - 须知道未来的资源情况 - 资源利用率低
预防	保守的；预提交资源, 导致资源闲置	抢占	- 对状态易于保存和恢复的资源非常方便	- 可能导致过于频繁的抢占
预防	保守的；预提交资源, 导致资源闲置	资源排序	- 可在系统设计时解决, 在编译时实施。	- 不便灵活申请新资源
避免	是“预防”与 “检测” 的折衷	通过资源需求检查以发现至少一条安全路径	- 不需要抢占	- 须知道未来资源的需求 - 进程可能被长时间阻塞
检测	宽松的；只要可能，请求的资源都允许	周期性地调用以检测死锁	- 不会延迟进程的初始化 - 易于在线处理	- 通过抢占解除死锁, 可能造成损失

Loading...

OS-进程与线程

并发