1、FCFS算法(先来先服务算法):算法每次从后备作业队列中选择最先进入该队列的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。FCFS调度算法的特点是算法简单,但效率低;对长作业比较有利,但对短作业不利(相对SJF和高响应比);有利于CPU繁忙型作业,而不利于I/O繁忙型作业。
2、SJF算法(短作业优先算法):从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。SJF调度算法的平均等待时间、平均周转时间最少;但对长作业非常不利。
3、HRN算法(最高响应比优先算法):该算法是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时,先计算后备作业队列中每个作业的响应比,从中选出响应比最高的作业投入运行。
响应比R计算公式: 响应比R = 作业周转时间/作业处理时间 = 1+(作业等待时间/作业处理时间)
4、HPF算法(优先数调度算法):每次从后备作业队列中选择优先级最髙的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。
根据新的更高优先级进程能否抢占正在执行的进程,可将该调度算法分为:
而根据进程创建后其优先级是否可以改变,可以将进程优先级分为以下两种:
5、均衡调度算法:基本思想是首先根据系统运行情况和作业属性将作业分类,轮流从不同的作业类中挑选作业;目的是力求均衡地利用各种系统资源,发挥资源利用效率。
1、最佳置换算法(OPT):算法所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。
2、先进先出置换算法(FIFO):优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。
3、最近最久未使用置换算法(LRU):选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。
先来先服务算法:根据进程请求访问磁盘的先后顺序进行调度。
最短寻道时间优先算法:总是执行查找时间最短的那个磁盘请求。
扫描算法:每次总是选择沿臂的移动方向最近的那个柱面。如果这个方向没有访问请求,就改变移动方向,然后处理所遇到的最近的I/O请求。非常类似电梯的调度规则。
循环扫描算法:移动臂总是从0号页面至最大页面顺序扫描,然后直接返回0号柱面重复执行。
银行家算法是一种用于死锁的避免的经典算法,算法描述如下:
信号量是用来解决进程同步的,不是用来解决死锁问题的。
P原语操作的主要动作是:
V原语操作的主要动作是:
分页式例题:
某虚存的用户空间有24个页面,每页1KB,内存16KB。假设某时刻系统为用户的第0,1,2和3页分配的物理快号为5,10,4,7,试将虚拟地址0A5C变化为物理地址。
0A5C:0000 1010 0101 1100 -> 因为每页1KB,所以前6位是页号,后10位是页内地址。页号为2转换为物理块号为4,页内地址不变。答案:0001 0010 0101 1100
分段式例题:
根据下面段表,写出对应的物理内存地址:
段号 | 段首址 | 段长 |
---|---|---|
0 | 400 | 600 |
1 | 1300 | 400 |
2 | 100 | 200 |