操作系统总结（二）

进程
- 进程是资源分配的基本单位
- 进程控制块（process control block，PCB）描述进程的基本信息和运行状态，所谓的创建进程和撤销进程都是对PCB的操作。
线程
- 线程是独立调度的基本单位
- 一个进程中可以有多个线程他们共享进程资源。
- QQ和浏览器是两个进程，浏览器进程里有很多线程，例如HTTP请求线程，事件响应线程，渲染线程等，线程的并发执行使得在浏览器点击一个新连接从而发起HTTP请求时，还可以响应用户的其他事件。
进程和线程区别
- 拥有资源
  - 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
- 调度
  - 线程是独立调度的基本单位，在同一进程内线程的切换不会引起进程的切换，从一个进程中的线程切换到另一个进程中的线程会引起进程的切换。
- 系统开销
  - 由于创建和撤销进程时，系统都要为之分配或回收资源，如内存空间，I/O设备等，所付出的开销远大于创建或撤销线程时的开销。类似的在进行进程切换时，涉及当前执行进程CPU环境的保存及新调度进程CPU的环境的设置，而线程切换的时候只需要保存和设置少量的寄存器内容，开销很小。
- 通信方面
  - 线程间可以通过直接读写同一进程中的数据进行通信，但是进程需要借助IPC。
进程状态的切换

初始状态（created）
就绪状态（ready）等待被调度
运行状态（running）
阻塞状态（waiting）等待资源
结束状态（Terminated)

注意：

只有就绪态和运行态之间可以相互转换，其他的都是单向转换。就绪状态的进程通过调度算法从而获得CPU时间，转为运行状态；而运行状态的进程，在分配给它的CPU时间片用完之后就会转换为就绪状态等待下一次调度。

阻塞状态是缺少需要的资源（I/O）从而由运行状态而来的，但是该资源不包括CPU时间缺少CPU时间会从运行态转换为就绪态。

进程调度算法
- 不同环境的调度算法不同，因此要针对不同的环境调度不同的算法。
批处理系统
- 批处理系统没有太多的用户操作，在该系统中，调度算法的目标是保证吞吐量和周转时间（从提交到终止的时间）
先来先服务（first-come first-service,FCFS）
- 非抢占式的调度算法，按照请求的顺序进行调度。
- 有利于长作业，不利于短作业，因为短作业必须等待前面的长作业执行完毕之后才能执行，而长作业有需要执行很长的时间，造成了短作业等待时间过长。
短作业优先（shortest job first SJF)
- 非抢占式的调度算法，按照估计的运行时间最短的顺序进行调度
- 长作业有可能饿死，处于一直等待短作业执行完毕的状态，因为如果有短作业到来，长作业永远不会被执行。
最短剩余时间优先（shortest remaining time next (SRTN))
- 最短作业优先的抢占式版本，按照剩余运行时间的顺序进行调度，当一个新作业到达时，其整个运行时间与当前进程的剩余时间作比较，如果新进程短，则挂起当前进程，运行新进程，否则新进程等待。

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速响应。
时间片轮转
- 将所有的就绪进程按照FCFS的原则排成一个队列，每次调度时，把CPU时间分配给队首进程，该进程可以执行一个时间片，当时间片用完时，由计时器发出时间中断，调度程序就停止该进程的执行，并把它放到队尾，同时继续把CPU时间分配给队首进程。
- 时间片轮转算法的效率和时间片的大小有关。
  - 因为进程切换要保存进程进行并载入新进程的信息，如果时间片太小，就会频繁的进行切换，在进程切换就会花太多的时间。
  - 而如果时间片太长，那么实时性就不能得到保证
优先级调度
- 为每个进程分配一个优先级按照优先级进行调度。
- 为了防止低优先级进程永远得不到调度，可以让优先级随着等待时间变长而增加。
多级反馈队列
- 一个进程需要执行100个时间片，如果采用时间片轮转算法就要交换100次
- 多级队列是为这种需要连续执行多个时间片的进程考虑，他设置了多个队列，每个队列的时间片大小都不同，例如1,2，4,8...，进程在第一个队列没执行完就会被移到下一个队列，这种方式之前的进行只需要交换七次。
- 每个队列的优先权也不同，最上面的优先权最高，因此只有上一个队列没有进程在排队，才能调用当前队列的进程。
- 可以将这种调度算法看成是时间片轮转调度算法+优先级算法的结合。

实时系统

实时系统要求一个请求在一个确定时间内得到响应

分为硬实时，和软实时，前者必须满足绝对的截止时间，后者可以容忍超时。

进程同步

临界区
- 对临界资源进行访问的那段代码称为临界区
- 为了互斥访问临界资源，每个进程在进入临界区之前都要进行检查
  - // entry section // critical section; // exit section
同步与互斥
- 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的执行顺序。
- 互斥：多个进程在同一时刻时只有一个进程能进入临界区。
信号量
- 信号量（Semaphore）是一个整型变量，可以对其进行down，和up操作也就是常见的P,V操作。
- down：如果信号量大于0，执行-1，如果信号量等于0，进程睡眠等待信号量大于0.
- up:对信号量执行+1操作，唤醒睡眠的进程让其完成down操作
- down操作和up操作需要被设计成原语，不可分割，通常的做法是在执行这些操作时，屏蔽中断。
- 如果信号量的取值只能为0,1，那就成为了互斥量，0表示临界区已经加锁，1表示临界区解锁。
使用信号量实现生产者-消费者问题
- 问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品，只有缓冲区不为空消费者才可以拿走物品
- 因为缓冲区属于临界资源，因此需要一个互斥量mutex来控制对缓冲区的互斥访问。
- 为了同步生产者和消费者行为，需要记录物品的数量，数量可以使用信号量来进行统计，这里需要两个信号量：empty记录空缓冲区的数量，full记录满缓冲区的数量，其中empty信号量在生产者进程中使用，当empty不位0时，生产者才可以放入物品；full信号量在消费者进程中使用，当full不为时，消费者才可以取走物品。
- 注意不能先对缓冲区进行加锁，在测试信号量，也就是说不能先执行down（mutex）操作，在执行down（empty）如果这么做了，有可能会出现
- 生产者对缓冲区加锁后，执行down（empty），发现empty=0，此时生产者睡眠，消费者不能进入临界区，因为生产者对缓冲区加锁额，消费者就无法执行up（empty）操作，empty就永远是0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100 typedef int semaphore; semaphore mutex=1; semaphore empty=N; semaphore full=0; void producer(){ while(true){ int item=produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); } } void consumer(){ while(true){ down(&full); down(&mutex); int item=remove_item(); consume_item(item); up(&mutex); up(&empty); } }

管程

使用信号量机制实现生产者消费者问题需要客户端代码做很多控制，而管程把控制代码独立出来，不仅不容易出错，也使得客户端调用更加容易。
c语言不支持管程，面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。
- - monitor ProducerConsumer integer i; condition c; procedure insert(); begin // ... end; procedure remove(); begin // ... end; end monitor;
管程有个重要特性：在一个时刻只能有一个进程使用管程，进程在无法继续执行的时候不能一直占用管程，否则其他进程永远不能使用管程。
管程引入了条件变量以及相关的操作，wait和signal来实现同步，对条件变量执行wait操作会导致调用进程阻塞，把管程让出来给另一个进程持有，signal操作用于唤醒被阻塞的进程。
使用管程实现生产者消费者问题

// 管程 monitor ProducerConsumer condition full, empty; integer count := 0; condition c; procedure insert(item: integer); begin if count = N then wait(full); insert_item(item); count := count + 1; if count = 1 then signal(empty); end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count - 1; if count = N -1 then signal(full); end; end monitor; // 生产者客户端 procedure producer begin while true do begin item = produce_item; ProducerConsumer.insert(item); end end; // 消费者客户端 procedure consumer begin while true do begin item = ProducerConsumer.remove; consume_item(item); end end;

经典同步问题

哲学家进餐问题
- 五个哲学家围着一张圆桌，每个哲学家面前放着食物，哲学家的生活有两种交替活动：吃饭和思考，当一个哲学家吃饭的时候，需要先拿起自己左右两边的筷子，并且一次只能拿一根筷子。
- 错误解法：所有哲学家同时拿起左手的筷子，就形成了死锁，都在等待对方先放下筷子。

#define N 5 void philosopher(int i) { while(TRUE) { think(); take(i); // 拿起左边的筷子 take((i+1)%N); // 拿起右边的筷子 eat(); put(i); put((i+1)%N); } }

为了防止死锁，可以设置两个条件：

必须同时拿起左右两根筷子

只有在两个邻居都没有进餐的时候才允许进餐

#define N 5 #define LEFT (i + N - 1) % N // 左邻居 #define RIGHT (i + 1) % N // 右邻居 #define THINKING 0 #define HUNGRY 1 #define EATING 2 typedef int semaphore; int state[N]; // 跟踪每个哲学家的状态 semaphore mutex = 1; // 临界区的互斥，临界区是 state 数组，对其修改需要互斥 semaphore s[N]; // 每个哲学家一个信号量 void philosopher(int i) { while(TRUE) { think(i); take_two(i); eat(i); put_two(i); } } void take_two(int i) { down(&mutex); state[i] = HUNGRY; check(i); up(&mutex); down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去 } void put_two(i) { down(&mutex); state[i] = THINKING; check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了 check(RIGHT); up(&mutex); } void eat(int i) { down(&mutex); state[i] = EATING; up(&mutex); } // 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行 void check(i) { if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) { state[i] = EATING; up(&s[i]); } }

读者-写者问题

允许多个进程同时对数据进行读操作，不允许读和写，以及写操作同时发生。

一个整型变量count记录在对数据进行读操作的进程数量，一个互斥量count_mutex用于对count加锁，一个互斥量data_mutex用于对读写的数据加锁。

typedef int semaphore; semaphore count_mutex = 1; semaphore data_mutex = 1; int count = 0; void reader() { while(TRUE) { down(&count_mutex); count++; if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问 up(&count_mutex); read(); down(&count_mutex); count--; if(count == 0) up(&data_mutex); up(&count_mutex); } } void writer() { while(TRUE) { down(&data_mutex); write(); up(&data_mutex); } }

进程通信：

进程同步和进程通信的区别：

进程同步：控制多个进程按照一定顺序执行
进程通信：进程间传输信息

进程通信是一种手段，进程同步是一种目的，也可以说为了达到进程同步的目的需要进行进程通信，传输一些进程同步需要的信息。

管道
1. 管道是通过调用pipe函数创建的，fd[0]用于读，fd[1]用于写。
2. #include <unistd.h> int pipe(int fd[2]);
3. 具有以下限制：
  1. 只支持半双工通信（单向交替传输）
  2. 只能在父子进程或者兄弟进程中使用
FIFO
1. 也称为命名管道，去除了管道只能在父子进程中使用的限制
2. #include <sys/stat.h> int mkfifo(const char *path, mode_t mode); int mkfifoat(int fd, const char *path, mode_t mode);
3. FIFO常用于客户-服务器应用程序中，FIFO用作汇聚点，在客户进程和服务器进程之间传递数据。

3.消息队列

相比于FIFO，消息队列具有以下优点