[原]进程调度与死锁

吕子健 18/04/14 22:18:09

1.进程调度的功能
记录系统中所有进程的状态、优先数和资源的需求情况
确定调度算法。决定将CPU分配给哪个进程及多长时间
分配处理机给进程

2.进程调度方式
非抢占式 :直到进程完成或因为某时间而不能运行时,才将CPU分配给其他进程 。通常用在批处理系统中。主要优点是简单、系统开销小
抢占式 :当一个进程正在执行,系统可以基于某种策略剥夺CPU给其他进程。剥夺的原则有:优先权原则、短进程优先原则和时间原则。主要用于分时系统和实时系统,以便及时响应各进程请求

3.引进进程调度的时机
正在执行的进程正确完成/由于错误终止运行(陷阱和中断)
执行的进程提出I/O请求,等待其完成
分时系统中,进程时间片用完
按照优先级调度时,有更高的优先级进程变为就绪时(抢占方式)
发生阻塞(执行的进程执行了wait、阻塞原语和唤醒原语时)

4.进程调度算法的评价准则
1)面向系统的调度性能准则
吞吐量 处理及利用率 各个设备的均衡利用
2)面向用户的调度性能准则
周转时间 响应时间 截止时间 公平性 优先级
3)调度算法本身的调度性能准则
易于实现 执行开销比


多级反馈队列算法(多列轮转法)
设置多个就绪队列,分别赋予不同的优先级,队列1的优先级最高,其他逐渐降低,每队列分配不同的时间片,规定优先级越低时间片越长
(1)新进程就绪后,先投入队列1的末尾按FCFS算法调度(先进先出调度算法,按进程进入就绪队列的先后次序,分派cpu,当前进程占用cpu,知道执行完或阻塞,才出让cpu(非抢占方式),在进程唤醒后(如i/o操作完成),并不立即恢复执行,通常等到当前进程出让cpu),(2)若一个时间片未能执行完,则降低投入到队列2的末尾,(3)以此类推,降低到最后的队列,则按时间片轮转算法(通过时间片轮转,提高进程并发性和响应时间特性,从而提高资源利用率。将就绪进程按FCFS原则,排成一个队列,每次调度时cpu分派给队首进程,执行一个时间片,时间片结束时,暂停当前进程的执行,将其送到队尾,并通过cpu现场切换执行当前队首进程。进程可以未使用完一个时间片,就让出cpu,比如阻塞)直到调度完成。(4)进程由于等待事件而放弃cpu后,进入等待队列,一旦等待的事件发生,回到原来的就绪队列。
仅当较高优先级的队列为空,才调度较低优先级的队列中进程执行。如果进程执行时有新进程进入较高优先级的队列,则抢先执行新进程,被抢先的进程被投入到原队列末尾
为适应一个进程在不同的时间段的运行特点,I/O完成时,提高优先级;时间片用完时,降低优先级


CPU调度过程
保存现场:顺序保存,最后一步保存PSW(程序状态)
选择要运行的程序
如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其他进程时,该进程一直运行,在执行过程中可接受中断
恢复现场:最后一步恢复选中进程的PSW


闲逛进程——idle进程

idle 进程,也就是0号进程,不参与schedule机制,当系统中没有任何进程可以调度(就绪队列为空),cpu会进入该进程。多cpu系统中每个cpu一个idle。
void cpu_idle (void)
{

while (1) {
void (*idle)(void) = pm_idle;
if (!idle)
idle = default_idle;
while (!current->need_resched)
idle();
schedule();

}

内核初始化后,所有core都会进入该函数。pm_idle为电源管理idle函数不讨论。
所以使用

`default_idle`。
#define safe_halt()             __asm__ __volatile__("sti; hlt": : :"memory")

进入default_idle后,会执行hlt, 也就是硬件停机,处于该状态时cpu不能执行任何指令,只有通过中断请求才能唤醒。
中断函数中设置need_resched就会进入schedule又开始正常进程调度。否则继续idle。

系统空闲进程,一般优先级最低,系统没事干的时候就执行它。实际上在某些系统会在idle中处理一些内存回收之类的事情。其存在的原因是为了让调度器有事情做,要不然所有的进程全挂起了调度器会很郁闷的。


产生死锁的原因:
1)竞争资源引起死锁
永久性资源:可以给多个进程多次使用(可再用资源)——剥夺兴资源(CPU,内存),非剥夺性资源(磁带机、打印机)
临时性资源:只可使用一次的资源(可消耗性资源);如信号量,中断信号,同步信号
2)进程推进顺序不当
对资源采取“申请——分配——使用——释放”模式,由于推进不当两进程都要申请对方的资源
进程争夺资源有可能产生死锁,但不一定就会死锁,其取决于进程推进的速度和对资源的请求的顺序。死锁是一种与时间有关的错误

产生死锁的必要条件:
1)互斥条件:一个资源每次只能给一个进程使用
2)不可剥夺条件:资源申请者不能强行的从资源占有者中夺取资源,资源只能由占有者资源释放
3)请求和保持条件:在申请新的资源的同时保持对原有资源的占有
4)循环等待条件:存在一个进程—等待资源环形链

死锁的预防
预防死锁的方法是破坏死锁的四个必要条件之一

死锁的避免
允许进程动态的申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换,便可将资源分配给进程;否则不分配资源,进程必须阻塞等待。从而避免发生死锁
避免死锁的实质是使系统不进入不安全状态

作者:weixin_36888577 发表于 2018/04/14 22:18:09 原文链接 https://blog.csdn.net/weixin_36888577/article/details/79944997
阅读:3