操作系统笔记-进程

1、中断

由于某些硬件或操作是需要操作系统进行调用的，保证安全所以防止用户直接进行操作，而当用户要操作的只有操作系统能够调用的操作的时候，此时需要通知操作系统，而此时则是产生中断，中断实际上就是设置中断寄存器的标识位，cpu会在每个指令后检查其中断寄存器是否发生中断，如果发生则需要执行对应的中断程序。

中断分为内中断和外中断，外中断一般是指用户自己发起的或者说通过输入设备发起的，如键盘，麦克风以及一些其他io设备。而内中断则是操作系统自身因为某些操作导致的或者说是系统调用时必须要进行的中断。

2、系统调用

由于安全上的考虑，操作系统就是做到一个承上启下的，其中某些操作是用户不能直接进行的，需要借助操作系统，而由于是操作系统进行的，那么此时我们可以称之为内核态，而对于用户能直接操作的称之为用户态，用户态到内核态需要进行切换，而内核态到用户态的切换会产生中断以及保存现场，恢复现场，所以一般我们说没有产生用户态到内核态的程序执行效率高于发生用户态到内核态进行切换的程序

3、什么是进程

进程是操作系统分配资源的基本单位，而线程是操作系统调度的基本单位，一个进程可以由一个或多个线程构成，简单的理解就是在系统上能够直接被用户执行的程序，例如windows上的exe程序。

3、进程的结构特征

3.1 进程控制块（PCB）

进程控制块用于存放进程id、以及发生中断后保存现场信息，如寄存器信息，程序计数器中的信息。操作系统也是通过pcb来确认进程的。对于PCB是存放在内存中的，同时CPU运行的时候会将当前进程的PCB放入到内存，如果进行进程切换的时候，此时PCB中需要记录其当前进程的寄存器信息以及程序计数器执行到哪儿了。

3.2 进程PCB的存储方式

3.2.1 链接方式

操作系统准备多个队列，切中每一个队列中存放相应的PCB，阻塞队列中存放当前处于阻塞状态的进程PCB，而就绪状态的进程的PCB就存放在就绪状态队列中。通过对队列进行出队或入队来实现进程状态的变化。

3.2.2 索引方式

索引方式就是将原来的队列转换为索引表，每一个状态对应一个索引表，而索引表中对应具体的PCB信息。

3.3 进程数据段

数据段用于存放进程在执行期间动态分配的内存，以及存储全局变量和静态变量信息。

3.4 进程程序段

程序段用于存放进程执行时所需要的指令（二进制形式）

3、进程的状态

3.1 创建

创建状态的进程会分配PCB以及将程序状态赋值为新建状态，磁盘上的进程还没有加载到内存中，并且还没有被CPU调度也没有进入到就绪队列中，此时的进程是没有被OS给调度的。

3. 2就绪

一旦进程被创建后分配了PCB以及更改状态后，即该准备的都准备好了后，此时是可以被操作系统调度的，但是不是直接被调度，而是进入就绪队列，等待OS的调度，而进入到就绪队列并更改状态为就绪状态后，此时叫就绪状态。

3.3 运行

当OS执行当前进程的时候，即当前进程拿到CPU的调度的时候，此时进程的PCB中的状态变更为运行状态，运行状态只能从就绪状态变更到运行状态，即使阻塞后恢复，此时也是先进入到就绪状态。

3.4 阻塞

当进程的时间片执行完毕后，此时CPU需要去执行其他的进程，此时原来的进程需要被暂停此时为挂起状态，当进程操作IO的时候，此时CPU也会暂停执行当前的进程，此时我们PCB中的状态变更为阻塞状态，此时为进程的阻塞状态。

3.5 销毁

当进程正常执行结束后，或者用户强制关闭某个进程，或者进程发生异常的时候，此时进程整个生命周期结束，为销毁，此时OS需要回收进程的资源以及PCB数据段程序段的信息。

4、进程通信

由于进程和进程之间是不能直接相互访问对方的内存地址即进程的数据段，而某些情况又需要这样的操作，所以操作系统提供了如下的几种通信方式。

4.1 共享存储

操作系统为通信的进程之间开辟一块共享的空间，需要写的进程写入到共享空间，而需要读的进程从共享空间直接读取，共享存储空间必须是互斥的即只能一个进行读或写，如果进程A在写的时候进程2是不能读的。

4.2 消息传递

消息传递是将数据封装为对应的消息体，包含消息头和消息体。

4.2.1 消息传递-直接通信

直接通信是指在操作系统会给每一个进程开辟一个队列，进行通信的时候如果需要写则写入到对方进程队列的队尾，而对于读取则是直接读取自己进程对头的数据。

4.2.2 消息传递-间接通信

间接通信类似于一个信箱，进程根据发送原语或接受原语进行，发送原语会将数据发送到对应的内存空间中即对应的信箱中，而接受原语则从对应的内存或信箱中读取跟自己相关的数据。

4.3 管道通信

管道通信是开辟一个缓冲区，然后管道只能进行半双工即某一时间段只能单向进行传输，如果要实现双向则需要多个通道，同时管道只能是满了才能进行读，空了才能写，如果没有写满并不是就读取不到，所谓的非空不写，非满不读，是指操作系统发现缓冲池满了或者空了产生中断去通知对方进行读或者写，而对于不满的也可以进行读，用户可以自行进行系统调用进行读取。

4.3.1 无名管道

有名管道是指只能在父子进程之间进行通信的管道

4.3.2 有名管道

无名管道是指可以在任意进程之间进行通信的管道

5、线程、多线程模型

5.1 产生多线程的原因

早期操作系统调度的最小单位是进程，每一个进程的代码只能串行执行，此时并发度很低，而引入了线程以后，一个进程可以由多个线程进行执行，此时可以大大的提升并发度。

5.2 线程和进程的区别

线程是CPU调度的最小单位，进程是CPU分配资源的最小单位，线程和进程一样有状态；线程的粒度小于进程，一个进程中可以有多个或一个线程，是一个一对多的关系。

5.3 线程实现的方式多线程模型

5.3.1 用户级线程

用户级线程可以是在用户级别上用多个线程，而对于内核来说实际上就只有一个线程，相当于多对一的关系，用户级线程的切换都是由用户态中的线程库发起的。

用户级别线程实际上就是一对多模型好处在于对于线程的切换是用户级别的，而非内核级别，能够减少其用户态到内核态的开销。但是一旦用户线程阻塞的时候，此时对应的内核线程也会阻塞，而对于其他的用户线程相应的也没办法使用。并发度不高，只是减少了线程切换。

5.3.2 内核级线程

内核级线程就是指用户线程和实际上操作系统对应的线程是一一对应的，如果发生线程切换是需要进行用户态到内核态的转变的。

一对一模型，实际上就是一个用户线程对应一个内核线程，对应的解决了单个用户线程阻塞的问题，此时可以使用其他的用户线程，提高了并发度，但是相应的如果线程切换，必须由用户态切换到内核态进行。

5.3.3 组合方式

相比用户线程来说，一个内核线程对应多个用户线程，线程切换由线程库进行控制，如果一个用户线程阻塞，那么相应的还有其他的内核线程可以使用，同时对于线程切换的问题也是由用户态执行的，此时即可以减少用户态到内核态，也可以增加其并发度。

6、进程调度

6.1 调度时机

1、运行过程中发生异常

2、进程正常结束

3、进程主动请求阻塞或io操作

4、对应的时间片用完

5、有更高优先级进程进入就绪队列

6、发生IO

6.2 不允许发生调度的时机

1、在管程的临界区中，或者说正在执行锁中对应的数据

2、发生中断的时候

3、执行原子操作的时候。因为原子操作是做了关中断，要保证原子，此时也不允许进程切换，否则不能满足原子性。

6.3 调度的方式

6.3.1 非剥夺方式

非剥夺式只允许进程主动放弃处理机，不允许在运行过程中在运行过程中被其他进程抢占其处理机，实现相对简单，但是无法实现进程切换即多任务并发执行。

6.3.2 剥夺式方式

在执行过程中可以被更加紧急的进程占用其处理机，但是会发生进程饥饿，即一直都是紧急的进程。导致自己无法被执行。

6.4 进程的挂起状态

因为内存中PCB占用过多空间，导致内存不够使用，此时需要唤出一部分进程，此时的进程就会被挂起，其PCB依然在内存中，然后PCB中指向其外存中进程的进程号等以及当时进程的寄存器信息，当需要执行的时候则通过PCB中的外存地址找到其PCB详细的信息。

6.5 调度算法

6.5.1 先来先服务

先来先服务的调度算法，是指先到来的进程会被优先调度，且进程在被调度的过程中是不允许被抢占的，即一定是先来先服务，不会根据机制发生非公平式的运行，实现简单，对于短时间的进程是不利的，因为必须遵从先来先服务，对于短时间运行的也必须排队，不能进行插队。

6.5.2 短作业优先

根据当前到达的进程，且根据运行时间进行排序，最短时间的优先进行运行，同时是抢占式的即就绪队列中的进程会根据运行时间进行排序，优先的可能会中断正在被调度的进程，从而发生不公平，每次都需要进行排序，需要一定的排序时间，能够让短时间的优先处理，但是会造成饥饿，即长运行时间的进程可能会被一直插队。

6.5.3 高相应比优先

根据当前到达的进程高相应时间进行排序进行调度，是非抢占式的，即一个进程必须运行完毕或主动放弃执行权，一旦进程结束后此时根据高相应比进行排序调度，同样会产生饥饿，响应时间=（等待时间+运行时间）/运行时间。

6.5.4 时间片轮转调度

进程到来后给每一个进程分配一个时间片，同时进入就绪队列，然后从就绪队列中进行调度，一旦时间片执行完以后，此时发生进程切换即被抢占，原本的进程进入就绪队列。时间片是操作系统分配的，且有些情况下是能够进行动态调整的。响应快，不会产生饥饿，适用于分时操作系统，不区分任务紧急程度有，进程的切换有一定的开销。

6.5.5 优先级调度

会给进程分配一个优先级，然后根据其优先级大小进行调度，优先级调度算法可以是抢占式也可以是非抢占式的，抢占式的是一旦就绪队列中的顺序发生变化，即有优先级高的到来时此时会抢占其被调度的进程，而非抢占式的是每次进程执行时不允许被其他进程给抢占，同时优先级调度可以分为动态和静态的优先级，即优先级能够动态调整，能够处理更紧急的进程，会产生饥饿，排序需要一定的开销。

6.5.6多级反馈队列调度

用多个就绪队列，满足先进先出，然后每级队列根据优先级从高低排序，时间片从小到大进行排序，新进程进入就绪队列时优先进入第一级队列，由于第一级优先级最高会被优先调度，如果第一级没有处理完进程的时间片，此时进入第二级，如果第二级没处理完进入第三级，高的优先级是会被优先调度的，如果到达末级别依然没有时间片用完，此时会重新在此级别重新入队。

每一个进程都能够被调度，适用于分时操作系统，对于需要主动放弃执行权的进程能够让其从新入队到当前级队列，可能会产生饥饿即一直有新的进程进入，一直为高优先级的，低优先级的不能被调度。可以动态的改变其进程的时间片以及其优先级别。

7、进程同步

7.1 进程互斥软件实现方式

7.1.1 单标志(了解)

通过一个标志位来表示当前是那个进程进入了临界区，每次进入临界区的时候都需要判断标志位的进程号是不是自己，如果不是则死循环一直判断，而对于进入临界区的进程退出时将标志位设置为下一个需要进入临界区的进程号。单标志如果并发执行会出现第一次设置标志位的时候会有问题，进程设置自己后进入临界区然后进程2又会设置自己，所以必须在第一次设置标志位的时候满足其只有第一个到达的才能进行设置。

7.1.2 双标志(了解)

双标志法是通过一个数组，数组中每一个槽位表示其进程是否进入临界区，初始值都是false，然后判断对方是否为false，如果是则把自己设置为true，进入临界区，此时其他线程检查到已经有人进入临界区就无法进入。并发执行时，发生线程切换，此时可能都会判断对方是false，此时都设置自己进入临界区。

7.1.3 双标志后检查(了解)

双标志后检查是指在原来的双标志基础上将设置自己进程的标志位提前设置即在判断前先设置，但是依然会有问题，如果两个线程都设置了自己标志位为true，然后判断的时候都无法进入临界区。

7.1.4 Peterson(皮特森)算法

皮特森算法是一种互相谦让的算法，同时需要一个数组用于记录意愿进入临界区的进程，然后使用标志位来表示让那个进程进入临界区。皮特森算法能够保证不会出现多个进程进入临界区，同时不会出现死锁，但是必须保证数组以及标志位对于多个进程之间是可见的，类似于volatile。

无论是单标志、双标志、双标志后检查、皮特森算法都会出现忙等，即cpu一直在工作，即死循环，而不会让出cpu调度。

7.2、进程同步硬件实现方式

7.2.1 中断屏蔽方法

使用中断方式，即直接关闭中断，一旦关闭中断后就不会发生进程切换以及被中断，但是关闭中断后会导致需要请求中断的进程无法进行中断，同时中断需要内核才能发起，所以用户需要使用必须要从用户态到内核态，需要一定的开销。

7.2.2 TestAndSet指令(TSL)

TSL指令是通过硬件实现的，执行过程中不允许被中断，首先会用一个变量记录上一次的状态或者说当前锁的状态，使用TSL指令的时候每次将原来的lock变量赋值给一个old变量，设置lock变量为true，并返回原来的lock变量，即只有返回false的时候才表示加锁成功。TSL指令是通过硬件实现的。

7.2.3 Swap指令(Exchange指令)

swap指令原理和TSL指令类似，首先定义一个全局的锁状态，默认false，然后加锁的时候实际上就是不断去进行调用swap，然后swap每次会返回交换后的值，即全局锁的值，只有返回为false的时候就表示加锁成功，由于全局锁状态为true后，后续的交换都只是true和true的交换就不会出现false。和TSL指令类似，Swap指令也是硬件实现的，同时也会出现忙等。swap整个方式是硬件实现的，且不允许中断所以是原子的，不会出现两个线程同时改变其全局锁状态为true，即两个都加锁成功。

private static volatile boolean lock = false; public static void main(String[] args) { boolean key = true; do{ //将key值兑换，除非当前的lock为false的时候就可以跳出循环 key = swap(key); }while (key!=false); //执行临界区代码... //lock = false退出临界区 lock = false; } public static boolean swap(boolean param){ boolean temp = lock; lock = param; param = temp; //将替换的param参数回调回去 return param; }

7.2.4 信号量

信号量使用一个整型或其他类型来记录可以同时操作临界区的进程的数量有多少，信号量分为P、V操作，其中P主要的含义是对信号量数量进行减1，而V则是加1或者说唤醒正在等待的进程，信号量相比TSL或Swap能够很好的解决CPU忙等的问题，使用记录型信号量能够解决忙等。

wait操作相当于P，而singnal相当于V，如果信号量不够此时直接死循环等待，需要注意的是信号量是原子操作，所以对于S的变更以及S的判断是原子的，不存在并发的问题。

而对于其记录型信号量则是使用一个队列，即阻塞队列，一旦信号量不够的时候，直接将其阻塞即让出cpu，并加入到队列中，后续信号量释放后从队列头部获取一个进行唤醒。所以记录型信号量能够解决CPU忙等问题。同时信号量能够实现其互斥功能，设置一个信号量即可，也可以实现进程的同步，即限制其异步代码的执行顺序。

8、哲学家进餐问题

哲学家进餐问题是指有5个哲学家，同时每个哲学家左右都有一支筷子，共5支筷子，每个哲学家必须拿起两只筷子才能进行吃饭，哲学家进餐问题会产生死锁。

如果所有哲学家都同时拿起自己的左边筷子或右边筷子，那么此时会造成都无法吃饭，都需要右边的筷子，但是都不会将自己的筷子让给别人，即死锁。

9.哲学家问题的解决方案

1、只允许4个哲学家同时进行拿筷子，此时总有一个哲学家能进行吃饭

2、奇数的哲学家只能先拿左边的筷子再拿右边的筷子，而偶数的哲学家只能先拿右边的筷子再拿左边的筷子，如果奇数哲学家先没有拿到左边就不允许再拿右边，而偶数哲学家如果先没有拿到右边就不允许再拿左边。

3、每个哲学家在拿左右的时候保证其原子性，即拿左右的时候每次只能有一个哲学家进行拿，在拿左右的时候进行加锁。

10、管程

管程是将对应的信号量或者锁进行一定的封装，而用户不需要关心其具体的时候，只需要直接使用就能简单的实现其线程的互斥，例如Java中的synchronized完全不需要关注加锁的过程以及解锁的过程，只需要使用synchronized提供的具体api的用法就能实现其单个程序访问临界资源。

11、死锁

11.1 死锁

死锁是指都想拿到对方的锁，但是都不会进行谦让和释放，从而导致循环等待的结果。

11.2 饥饿

进程或线程长时间得不到执行，例如调度中的运行时间短优先，一直被插队，无法得到调度。

11.3 死循环

一个进程或线程执行一段死循环代码，导致cpu一直忙碌，但是却并没有执行到有效的程序，且还不会放弃调度。

11.4 死锁的必要条件

1、互斥条件，只有存在即只能一个线程访问临界区，没有互斥就没有等待的存在，所以就不会存在死锁

2、不可剥夺，每一个线程或进程拿到锁以后都不会释放自己的锁，如果能被他人剥夺就不会存在互相等待。

3、请求和保持，自己拥有锁以后，不释放锁，但是有需要拿到别人的锁。

4、循环等待，两个或多个进程或线程，要进行相互等待即加锁的顺序不一样的。

只要死锁的必要条件中不满足其中一种，都能打破死锁。