操作系统之进程、线程

一、进程

1、进程是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

2、特性：

• 动态性：进程的实质是程序的一次执行过程，进程是动态产生，动态消亡的。 
• 并发性：任何进程都可以同其他进程一起并发执行 
• 独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位； 
• 结构性：进程由程序、数据和进程控制块三部分组成。 进程控制块(PCB):包含进程的描述信息和管理控制信息，包括有：进程标识符，进程的状态以及调度和存储区管理信息（优先级，在内外存的地址等）、使用的资源信息、CPU现场保护区（程序计数器，程序状态字，通用寄存器，堆栈指针）等

3、进程的几种状态

• 创建态:刚刚被创建，还没有正式提交给处理机进行调度
• 就绪态:已获得了除CPU以外的全部资源，等待系统分配CPU
• 运行态:正在CPU上执行的进程的状态
• 阻塞态：当一个进程因等待某个事件发生，如等待I/O完成或等待接收一个消息，而不能运行的状态
• 终止态：进程正常完成或因故障终止，不再受处理机调度管理

4、进程的上下文：操作系统为运行进程设置的相应的运行环境和进程的实体，组成：

• 用户级上下文：进程的实体中的程序和数据、
• 寄存器级上下文：CPU现场信息、
• 系统级上下文：进程控制块，进程运行时的系统环境，包含进程的状态以及存储区管理信息。

5、进程调度算法

1. 先来先服务调度算法：系统维护一个FIFO队列，每次调度都是从后备作业（进程）队列中选择一个或多个最先进入该队列的作业（进程），将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。容易被大作业进程垄断。
2. 短作业(进程)优先调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业（进程），将它们调入内存运行。对运行时间短的进程有利，进程平均等待时间最佳
3. 响应比高者优先调度算法：定义了响应比（（已等待时间＋要求运行时间）/ 要求运行时间），兼顾了运行时间短和等待时间长的作业，系统计算开销比较大
4. 优先级调度算法：该算法是把处理机分配给就绪队列中优先权最高的进程，又分静态优先和动态优先，静态优先：进程的优先级在创建时确定（系统的进程>用户，申请资源少的>多的），优先级确定了就不变了，动态优先：创建时先确定一个优先级，随着执行时间变化，动态调整（Unix系统会根据进程占用CPU的时间或等待CPU时间）
5. 时间片轮转法：轮流的调度就绪队列中的所有进程。每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。多用于分时系统
6. 多级反馈队列调度算法：综合前面多种调度算法，通常设置多个就绪队列，优先级不同，采用前后台运行的方式，前台队列采用RR法调度（优先级越高的时间片越短），后台队列采用FCFS法，前台进程优先级大于后台。

在这些调度算法中，有抢占式和非抢占式的区别。

1. 非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
2. 抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，系统可以基于某种策略剥夺cpu给其他进程，比如出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

二、线程

　　线程，也被称为轻量级进程(Lightweight Process，LWP），CPU调度和执行的基本单位，它被包含在进程之中，是进程中的实际运作单位。每一个进程都至少有一个线程，一个进程可以有多个线程，可以并发执行，线程依赖于进程而存在，多线程共享该进程拥有的所有资源。线程由线程ID，当前程序计数器(PC），寄存器集合和堆栈组成。

进程和线程的区别：

• 进程是系统资源分配的基本单位，而线程是任务调度和执行的基本单位。
• 拥有的资源：进程有自己的独立地址空间，包含代码段、数据段，打开的文件描述符，进程ID等；线程自己只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。
• 调度：进程的上下文切换需要较大的时间和空间开销。而线程是共享进程中的数据的，其上下文切换只需要交换线程仅有的一小部分资源，
• 通信：线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。
• 并发性：引入线程后，系统的并发执行度会更高
• 安全性：进程之间是互相独立的，进程有自己独立的地址空间，一个进程死掉并不会对另外一个进程造成影响，多线程程序只要有一个线程死掉，整个进程也死掉了，且线程可以改变另一线程使用的数据导致错误发生。多进程会比多线程更安全。

三、进程的同步与通信

1、同步与互斥

同步：多个进程因为合作完成一个任务产生的同步关系，直接制约关系，使得进程有一定的先后执行关系。

互斥：对资源的共享引起的互斥关系，间接制约关系，多个进程在同一时刻只有一个进程能进入临界区。

临界资源：一次仅允许一个进程使用的系统中的一些共享资源

2、进程间同步的方式--信号量

• 临界区：并发线程访问临界资源必须互斥执行的那段代码称为临界区。
• 信号量：类似计数器，表示资源的可用数量，可以用来控制多个进程对共享资源的访问。
• 信号量用于实现进程间的互斥与同步。信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值 S 与相应资源的使用情况有关。当 S 大于 0 时，表示当前可用资源的数量；当 S 小于 0 时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由 PV 操作来改变。
• 如果信号量的初值为1，那么就成为了 互斥量（Mutex）

3、进程的通信方式

1. 管道/匿名管道(Pipes) ：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
2. 有名管道(Names Pipes) : 有名管道严格遵循**先进先出(first in first out)**。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
3. 信号(Signal) ：信号是一种比较复杂的通信方式，用于通知进程某个事件已经发生；
4. 消息队列(Message Queuing) ：消息队列是消息的链表,存放在内核中并由消息队列标识符标识，管道和消息队列的通信数据都是先进先出的原则，消息队列可以实现消息的随机查询,也可以按消息的类型读取.
5. 信号量(Semaphores) ：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。信号量用于实现进程间的互斥与同步。
6. 共享内存(Shared memory) ：使得多个进程可以访问同一块内存空间。往往与一些同步操作配合，如互斥锁和信号量等。最高效的进程间通信方式。
7. 套接字(Sockets) : 网络中不同主机之间进行通信。

四、线程同步/通信

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

1、信号量

2、互斥量（互斥锁）

• 采用互斥对象机制。只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。

3、读写锁允许多个线程同时读共享数据，而对写操作是互斥的。

4、条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

5、临界区，在任意时刻 只允许一个线程对共享资源进行访问，互斥量、信号量可以跨进程使用，临界区只能在进程内部使用。

6、全局变量、静态变量

五、死锁

一组进程在执行过程中，每个进程都在等待其他进程所占有的资源而造成了互相等待，此时系统产生了死锁

1、四个必要条件：

（1）互斥条件：每个资源都是不可共享的

（2）请求保持条件：进程因请求资源而阻塞时，而且该进程不会释放已经占有的资源；

（3）不可剥夺条件：进程已获得的资源，不可被其他进程剥夺；

（4）环路等待条件：多进程之间形成一个循环的等待关系链。

2、原因：系统资源不足或推进顺序不当，导致对不可剥夺资源的不合理分配

3、死锁的预防

破坏四个必要条件之一：

1. spooling技术
2. 资源一次性分配，从而解决请求保持的问题
3. 可剥夺资源：当进程新的资源未得到满足时，释放已有的资源；
4. 资源有序分配：资源按序号递增，进程请求按递增请求，释放则相反。

4、死锁的避免

银行家算法：在资源分配之前系统预先判断此次分配是否会导致系统进入不安全状态，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。

5、死锁的检测与恢复

定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。

检测：系统进程资源图的方式检测环路

恢复：故障终止进程、资源剥夺

六、C/C++ 多线程

多线程最难的地方其实在于线程之间的数据共享和同步

C/C++ 多线程 pthread 库相关函数说明

pthread_t 线程结构体

1、调用 pthread_create()函数就可以创建一个线程。它的函数原型如下：

#include <pthread.h>
extern int pthread_create (pthread_t *__restrict __newthread,
			   const pthread_attr_t *__restrict __attr,
			   void *(*__start_routine) (void *),
			   void *__restrict __arg) 

pthread.h 是它的库。

参数说明：

第一个参数是 pthread_t* 也就是代表线程实体的指针

第二个参数为了设置线程的属性，一般为 NULL

第三个参数是线程运行时的函数，这是个函数指针。

第四个参数也是一个指针，它是用来将数据传递进线程的运行函数

pthread_join用来等待一个线程的结束，主线程阻塞等待子线程结束，然后回收子线程资源

pthread_detach()即主线程与子线程分离，子线程结束后，资源自动回收

https://blog.csdn.net/weibo1230123/article/details/81410241

pthread_mutex_t 互斥锁

pthread_mutex_lock

pthread_mutex_unlock

pthread_cond_t 条件变量

条件变量是利用线程间共享的全局变量，进行同步的一种机制，主要包括两个动作：一个线程等待"条件变量的条件成立"而挂起；另一个线程使"条件成立"(给出条件成立信号)。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。

而条件变量则通过允许线程阻塞并等待另一个线程发送唤醒信号的方法弥补了互斥锁的不足，它常和互斥锁一起使用。

/**
 * 使用__cond_attr初始化条件变量，__cond_attr设置为NULL，将使用默认属性初始化条件变量。
 * @param __cond 要初始化的条件变量
 * @param __cond_attr 属性
 * @return 如果成功返回0，失败返回错误码
 */
int pthread_cond_init (pthread_cond_t *__cond, 
                       const pthread_condattr_t *__cond_attr);

/**
 * 催毁条件变量。
 * @param __cond 要催毁的条件变量
 * @return 如果成功返回0，失败返回错误码
 */
int pthread_cond_destroy (pthread_cond_t *__cond);

/**
 * 唤醒一个用条件变量__cond等待的线程。
 * @param __cond 目标条件变量
 * @return 如果成功返回0，失败返回错误码
 */
int pthread_cond_signal (pthread_cond_t *__cond);

/* Wake up all threads waiting for condition variables COND.  */
/**
 * 唤醒所有用条件变量__cond等待的线程。
 * @param __cond 目标条件变量
 * @return 如果成功返回0，失败返回错误码
 */
int pthread_cond_broadcast (pthread_cond_t *__cond);

/**
 * 等待条件变量__cond的一个信号或者广播。调用该函数之前你应该确保已经用
 * __mutex上锁。
 * @param __cond 目标条件变量
 * @param __mutex 配合__cond的锁
 * @return 如果成功返回0，失败返回错误码
 */
int pthread_cond_wait (pthread_cond_t * __cond,
                       pthread_mutex_t * __mutex);
/**
 * 在指定时间内等待条件变量__cond的一个信号或者广播，调用该函数之前你应该确保已经用
 * __mutex上锁。
 * @param __cond 目标条件变量
 * @param __mutex 配合__cond的锁
 * @param __abstime 绝对时间
 * @return
 */
int pthread_cond_timedwait (pthread_cond_t * __cond, 
                            pthread_mutex_t * __mutex,
                            const struct timespec * __abstime);

进入等待状态前应该先上锁pthread_mutex_lock，pthread_cond_wait/pthread_cond_timedwait内部会自动解锁，但在返回前，函数内部一定会自动重新上锁。然后pthread_mutex_unlock

为了防止“虚假唤醒”，该函数一般放在while循环体中。例如

pthread_mutex_lock(mutex);//加互斥锁
while(条件不成立)//当前线程中条件变量不成立
{
      pthread_cond_wait(cond, mutex);//解锁，其他线程使条件成立发送信号，加锁。
}
...//对进程之间的共享资源进行操作
pthread_mutex_unlock(mutex);//释放互斥锁

为什么要配合互斥锁使用？

pthread_cond_wait()需要传入一个已经加锁的互斥锁，该函数把调用线程加入等待条件的调用列表中，然后释放互斥锁，在条件满足从而离开pthread_cond_wait()时，mutex将被重新加锁。

也就是说条件变量本身就是一个竞争资源，所以用一个mutex来保证: 对于某个cond的包括(判断,修改)在内的任何有关操作某一时刻只有一个线程在访问