操作系统

进程管理

进程与线程的区别

进程:是程序的一次执行,是操作系统分配资源的基本单位.

线程:是操作系统调度的基本单位.

区别与联系:

  • 进程拥有操作系统分配的资源,但线程没有分配,只能使用它所属进程的资源.
  • 线程是调度的基本单位,线程的切换不会引起进程的切换,消耗比进程切换小
  • 线程之间的通信可以借助进程中的资源,而进程之间的通信需要借助IPC

进程的状态

  • 创建态:进程正在被创建,PCB
  • 就绪态:进程已经获得了除CPU以外的所有资源,当分配到时间片时就可以执行
  • 运行态:进程获得了时间片,正在运行
  • 阻塞态:进程正在等待某一资源而暂时挂起,必须要等待该资源才可以继续切换到就绪态
  • 结束态:进程从操作系统中退出

僵尸进程和孤儿进程

**僵尸进程:**如果子进程退出了,当它的父进程并没有处理该进程的相关状态信息,那么操作系统会为该进程保留进程描述符信息,这样的进程就是僵尸进程.

**孤儿进程:**如果父进程在子进程之前退出了,那么这个进程就是孤儿进程

**孤儿进程的处理:**unix中孤儿进程会交给init进程来管理,回收信息.

僵尸进程的危害与处理:

危害:当系统中存在大量的僵尸进程,就会占用大量的进程描述符,进程ID,操作系统因此受限无法继续创建新的进程.

处理:僵尸进程出现的根本原因在于它的父进程不作为,不回收它的信息.因此我们只要想办法找个靠谱的父进程来回收它的信息就行了.因此我们把产生僵尸进程的进程也就是僵尸进程的父进程杀死,那么这样这些僵尸进程就成为了孤儿进程,然后孤儿进程是会被init进程所接管的.

init进程会例行调用wait()来检查其子进程,清除所有与其相关的僵尸进程.

进程调度

  • 先来先服务(FCFS)

    按照请求顺序依次执行.对于短作业可能需要等待长作业的长时间运行.

  • 短作业优先(SJF)

    非抢占式,按估计的最短时间顺序允许.长作业可能出现饿死的情况,一直得不到执行

  • 最短剩余时间优先

    当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。长作业可能饿死.

  • 时间片轮换

    将进程按FCFS顺序排列,每次为队首进程分配一个时间片,当队首进程执行完时间片后,调换到队尾.

    时间片的大小设置很重要.过小会引起进程之间频繁的切换,过大不能保证进程的实时性.

  • 优先级调度

    为每一个进程分配优先级,按优先级调度

  • 多级反馈队列

    设置多级队列,越往下的队列优先级越低,时间片大小越大.每一级的队列都是按照FCFS的顺序执行进程

    每个新进程进入都是插入第一级队列的队尾,若它在一个时间片内未执行完,则调度到下一级队列中.

    对于每一级队列,只有当它的上级队列中没有任务执行时,才会执行这一级队列中的任务.

进程通信

  • 匿名管道

    半双工的缓冲区,只能在父子进程或兄弟进程之间通信

  • 有名管道FIFO

    有名管道的文件形式存在于文件系统中,只要能访问该文件的进程,都可以实现相互之间的通信

  • 消息队列

    存放在内核中的消息链表,每个消息队列由消息队列标识符表示.

    消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达.

    消息可以随机查询.

  • 信号

    信号可以在任何时候发给某一进程,用于通知接收进程某个事件已经发生

  • 信号量

    信号量是一个计数器，用于多进程对共享数据的访问

    它不以传送数据为主要目的，它主要是用来保护共享资源，使得资源在一个时刻只有一个进程独享

  • 共享内存

    多个进程可以可以直接读写同一块内存空间

    需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥

  • 套接字

    主要用于不同机器之间的进程通信

    支持 TCP/IP 的网络通信的基本操作单元

进程同步

  • 信号量

    它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量,PV操作

  • 互斥量

    信号量取值为0/1时就成为互斥量,同一时间只允许一个进程访问

  • 管程

    一种用于多线程互斥访问共享资源的程序结构

    引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程

死锁

死锁的四个必要条件

  • 互斥:资源一次只能被一个进程使用,其他进程申请被使用进程必须等待
  • 请求和保持:进程持有资源,但又请求了其他资源,请求的资源被其他进程占有,因此该进程被挂起等待,但不释放自己已经占有的资源
  • 不可抢占:进程申请的资源在未使用完前,不能被其他进程抢占,只能由该进程主动释放
  • 循环等待:资源的循环请求链,链中的每一个进程都在等待下一个进程占有的资源

死锁的预防

  • 破坏互斥:将互斥的资源改为共享可用

  • 破坏不可抢占:

    • 当某个进程请求的资源得不到满足的时候,必须立即释放保持的所有资源
    • 当某个进程请求的资源被其他进程占有的时候,可由操作系统将请求的资源强行剥夺

  • 破坏请求和保持条件:

    静态分配:进程在运行前,一次申请完全部需要的资源,如果资源不满足,则不运行,一旦运行这些资源就归该进程

  • 破坏循环等待条件:

    为资源进行编号,进程在请求资源的时候只能按照资源编号递增的顺序请求资源.

死锁的检测和恢复

检测:

  • 每种类型一个资源

    将进程和资源构建一个资源分配有向图,然后检查该有向图中是否存在环.

    若存在环则存在死锁,反正则不存在

  • 每种类型多个资源

    构建现有资源矩阵E,可用资源矩阵A,当前分配矩阵C以及请求矩阵R

    从R中寻找一个请求的资源满足A的进程,然后将C的该进程的资源加到A上.(这一步的意思是从请求中寻找一个可用满足运行条件的进程,为其分配资源然后运行,运行结束后将资源),然后标记该进程

    最后,所有未被标记的进程都是死锁进程.

恢复

  • 抢占恢复:将占有的资源分配给另一个进程
  • 回滚恢复:将进程恢复到一个更早的时间点,然后将资源分配给其他进程
  • 杀死进程

鸵鸟算法

不管死锁的发生和解除死锁,直接重启