|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
处理器调度通常分为三级调度，即高级调度、中级调度和低级调度。
|
|
|
|
1）高级调度。高级调度也称为作业调度。高级调度的主要功能是在批处理作业的后备作业队列中选择一个或者一组作业，为它们建立进程，分配必要的资源，使它们能够运行起来。
|
|
|
|
2）中级调度。中级调度也称为交换调度，中级调度决定进程在内存、外存之间的调入、调出。其主要功能是在内存资源不足时将某些处于等待状态或就绪状态的进程调出内存，腾出空间后，再将外存上的就绪进程调入内存。
|
|
|
|
3）低级调度。低级调度也称为进程调度，低级调度的主要功能是确定处理器在就绪进程间的分配。
|
|
|
|
作业调度主要完成从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。作业调度算法有：
|
|
|
|
（1）先来先服务（First Come and First Served，FCFS）。按作业到达的先后次序调度，它不利于短作业。
|
|
|
|
（2）短作业优先（Short Job First，SJF）。按作业的估计运行时间调度，估计运行时间短的作业优先调度。它不利于长作业，可能会使一个估计运行时间长的作业迟迟得不到服务。
|
|
|
|
（3）响应比高者优先（Highest Response_ratio Next，HRN）。对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。响应比R的定义如下：
|
|
|
|
|
|
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。
|
|
|
|
（4）优先级调度。根据作业的优先级别，优先级高者先调度。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
CPU即中央处理器，它是计算机系统的核心部分。刚才所列的系统性能评价指标都是围绕CPU的。当然，这些指标的评价结果是建立在CPU与其他系统部件（如内存）的协同工作的基础上的。单就CPU而言，考察它在系统中的工作性能要关注CPU利用率、队列长度、每秒中断次数，等。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
任务调度的第二个问题是调度的方式，主要有两种方式：不可抢占调度和可抢占调度。
|
|
|
|
（1）不可抢占方式（non preemptive）。如果一个任务被调度程序选中，就会一直地运行下去，直到它因为某种原因（如I/O操作或任务间的同步）被阻塞了，或者它主动地交出了CPU的使用权。在不可抢占的调度方式下，当出现调度时机当中的前三种情形时，即新任务创建、任务运行结束及任务被阻塞，都有可能会发生调度。而对于第四种和第五种情形，即发生各种中断的时候，虽然也会有中断处理程序，但是它并不会去调用调度程序。因此，当中断处理完成后，又会回到刚才被打断的任务继续执行。
|
|
|
|
（2）可抢占方式（preemptive）。当一个任务正在运行的时候，调度程序可以去打断它，并安排另外的任务去运行。在这种调度方式下，对于调度时机当中的所有五种情形，都有可能会发生调度。另外，在其他的一些情形下，假设调度算法是按照任务的优先级来进行调度，那么一旦在就绪队列当中有任务的优先级高于当前正在运行的任务，就可能立即进行调度，转让CPU。
|
|
|
|
实时操作系统大都采用了可抢占的调度方式，使一些比较重要的关键任务能够打断那些不太重要的非关键任务的执行，以确保关键任务的截止时间能够得到满足。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
常用的进程调度算法有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。
|
|
|
|
（1）先来先服务（FCFS）。FCFS按照作业提交或进程成为就绪状态的先后次序分配CPU，即进程调度总是将就绪队列队首的进程投入运行。FCFS的特点是比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。FCFS算法主要用于宏观调度。
|
|
|
|
（2）时间片轮转。时间片轮转算法主要用于微观调度，其设计目标是提高资源利用率。通过时间片轮转提高进程并发性和响应时间特性，从而提高资源利用率。时间片的长度可以从几毫秒到几百毫秒，选择的方法一般分为固定时间片和可变时间片两种。
|
|
|
|
（3）优先级调度。该算法是让每一个进程都拥有一个优先数，数值大的表示优先级高，系统在调度时总选择优先数大的占用CPU。优先级调度分为静态优先级和动态优先级两种。
|
|
|
|
（4）多级反馈调度。多级反馈队列调度算法是时间片轮转算法和优先级算法的综合与发展。其优点有三个方面：第一，照顾了短进程以提高系统吞吐量，缩短了平均周转时间；第二，照顾I/O型进程以获得较好的I/O设备利用率和缩短响应时间；第三，不必估计进程的执行时间，动态调节优先级。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
小波变换的基本思想是将信号展开成一族基函数的加权和，即用一族函数表示或逼近信号或函数。这一族函数是通过基本函数的平移和伸缩构成的。
|
|
|
|
小波变换用于图像编码的基本思想就是把图像进行多分辨率分解，分解成不同空间、不同频率的子图像，然后再对子图像进行系数编码。小波变换本身并不具有压缩功能，之所以将它用于图像压缩，是因为生成的小波图像的能量主要集中于低频部分，水平、垂直和对角线上的高频部分则较少，可以将这一特性与一定的编码算法相结合，达到高效压缩图像的目的。小波变换作为一种多尺度、多分辨率的分析方法，由于小波具有很好的时频或空频局部特性，特别适合于按照人类视觉系统特性设计图像压缩编码方案，也非常有利于图像的分层传输。实验证明，图像的小波变换编码在压缩比和编码质量方面优于传统的DCT变换编码。
|
|
|
|
|
|
|
|
|
|
|
|
|
