建设工程主管部门网站,番禺做网站企业,大理州建设局门户网站,海创网站建设概念
在Linux中#xff0c;O(1)调度算法是一种进程调度算法。O(1)表示算法的时间复杂度是常数级别的#xff0c;与系统中的进程数量无关。 运行队列结构
他采用了两个运行队列#xff0c;一个活动队列和一个过期队列。活动队列中的进程是有资格获取CPU时间片的进程#x…概念
在Linux中O(1)调度算法是一种进程调度算法。O(1)表示算法的时间复杂度是常数级别的与系统中的进程数量无关。 运行队列结构
他采用了两个运行队列一个活动队列和一个过期队列。活动队列中的进程是有资格获取CPU时间片的进程过期队列中的进程是已经用完时间片的进程。而操作系统始终只会调度活动队列的进程。多个队列又被分为多个优先级数组例如从0~139。优先级不同Linux下版本可能有差异数值越小优先级越高。利用哈系统指针数组140个元素类型为struct task_struct*前100个下标不用考虑是为实时进程进行使用的。剩下的40个元素是对于分时进程进行考虑。对于剩下的40个元素利用哈系统将进程优先级相同的。串在一起。通过优先级挂队里相同优先级的进程会被链接在一起。也可以理解为在一个CPU里面有一个运行队列一个运行队列里面有两张表一个是活动队列和一个过期队列。
活动队列
时间片还没有结束的所有进程都按照优先级放在该队列。nr_active总共有多少运行状态的进程queue[140]一个元素就是一个进程队列相同优先级的进程按照fifo规则进行排队调度所以数组下标就是优先级。在该结构中选择一个最合适的进程过程是如何从0号下标开始遍历queue[140]找到第一个非空队列该队列必定为优先级最高的队列。拿到选中队列的第一个进程开始运行调度完成。遍历queue[140]时间复杂度是常数但还是太低效了。bitmap[5]一共是140个优先级一共140个进程队列。为了提高查找非空队列的效率就可以用五个。32个比特位表示队列是否为空这样便可以大大提高查找效率。
过期队列
过期队列和活动队列结构一模一样。过期队列上放置的进程都是时间片耗尽的进程。当活动队列上的进程都被处理完毕之后对过期队列的进程进行时间片重新计算。
active指针和expired指针
active永远指向活动队列。expired永远指向国旗队列。活动队列上的进程越来越少过期队列上的进程越来越多因为进程时间片到期时一直都存在的。在最终只要能够交换活动队列指针和过期队列指针的内容就相当于又具有一批新的活动进程。进程有三种情况运行退出。不退出但时间偏到了。有新的进程产生了。
调度过程 初始状态
系统中有活动队列和过期队列活动队列包含有资格获取CPU时间片的进程这些进程按照优先级分布在不同的优先级数组中。优先级从0~139。
选择进程运行
当进行进程调度时调度器首先查看活动队列中优先级最高数组在这个优先级最高的数组中选择一个进程来运行。这个选择过程比较简单快速因为它不需要遍历整个系统的所有行程只需在特定的优先级数组里选择。
时间片用完
当活动队列中的进程用完自己的时间片之后他不会立刻回到活动队列的头部重新竞争CPU。因为操作系统采用分时操作系统。分时操作系统是要保持绝对的公平进程调度绝对公平。而是被移动到过期队列中相应的优先级数组里。
队列交换
当活动队列中所有的进程都玩都用完时间片也就是活动队列中没有可运行的进程时活动队列和过期队列进行交换。此时原来的过期队列变为活动队列而原来的活动队列变为过期队列新的活动队列中的进程又可以开始竞争CPU资源。这个交换操作的时间复杂度也是o1。
优点
由于采用这种结构查到下一个要运行的进程的时间复杂度为o一无论系统中有多少个进程都能快速的做出调度决策提高了系统的响应速度和整体的性能。并且保证了分时操作系统调度进程绝对的公平。
应用场景
多用户交互环境
在桌面Linux系统中当多个用户同时登录并且运行多个程序时如打开多个办公软件浏览器标签等oe1调度算法能够快速的在这些进程中进行切换保证每个用户操作都能得到及时响应提供流畅的交互体验。
服务器环境
由于外部服务器就像运行或ngnx服务器可能同时处理多个客户端请求oe调度算法可以高效的调度处理这些请求的进程。不管同时存在的请求数量多少都能快速的分配cpu响应性能。
多任务处理
在Linux系统执行多任务时例如一边进行文件下载一边编译程序一边运行后台服务等情况。O1调度算法能够合理分配CPU时间片给各个任务。对应的进程使这些任务都能有条不紊的进行。
