用户调度问题算法

❶ 调度算法有哪些

先来先服务(FCFS, First Come First Serve)
时间片轮转法
多级反馈队列算法(Round Robin with Multiple Feedback)
最短进程优先
最短剩余时间优先
最高响应比优先
常用的应该就这么几种吧 具体实现算法原理其实不是很难

❷ 哪些调度算法需要不考虑用户信道质量

无线资源管理主要包括切换控制、功率控制、接入控制、负荷控制以及分组调度等方面的内容。
无线资源管理是3G系统无线网络控制器（RNC）的重要组成部分，其主要作用是负责空中接口资源的分配和使用，确保用户业务的服务质量、系统规划的覆盖区域以及提高系统容量。在3G的演进过程中，标准化组织3GPP和 3GPP2也在不断完善和增强相关技术。对于分组调度算法，一方面要考虑到算法实现的复杂度，另一方面需要注意对系统性能指标的影响，如公平性、时延、业务的服务质量（QoS）等。目前采用比较多的调度算法主要有轮循调度、最大载干比调度、比例公平调度三种类型。
在分组通信中，为了获得统计复用增益，需要多个业务流共享带宽。因此，当多个用户争用资源时，就需要有一种机制来确定服务次序，有效地分配无线资源，这就是分组调度。由于无线信道时变特性、带宽资源有限和移动台功率受限等因素的影响，无线网络中的分组调度算法有别于有线网络。
调度器首先根据信道状态监视/预测模块提供的信道信息和用户的队列状态，依据一定的调度算法，计算出每个用户的优先级，然后根据优先级对用户数据排队，并分配无线资源，最后送到发射机。
1．Round Robin 轮叫调度（Round-Robin Scheling） 狭义解释：
时间片轮转算法的基本思想是，系统将所有的就绪进程按先来先服务算法的原则，排成一个队列，每次调度时，系统把处理机分配给队列首进程，并让其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序根据这个请求停止该进程的运行，将它送到就绪队列的末尾，再把处理机分给就绪队列中新的队首进程，同时让它也执行一个时间片。
广义解释：
时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法是时间片调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，，当进程用完它的时间片后，它被移到队列的末尾

❸ 调度算法的调度算法

在操作系统中调度是指一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的段作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应当采用轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可以用于作业调度，也可以用于进程调度。
通常将作业或进程归入各种就绪或阻塞队列。
调度算法要求：高资源利用率、高吞吐量、用户满意等原则。
进程调度所采用的算法是与整个系统的设计目标相一致的：
1.批处理系统：增加系统吞吐量和提高系统资源的利用率;
2.分时系统：保证每个分时用户能容忍的响应时间。
3.实时系统：保证对随机发生的外部事件做出实时响应。

❹ 关于操作系统中调度算法的问题

1. 这只是考题，而不是现实

2. 现实中可以通过多次运行一个程序的结果统计平均运行时间
   

❺ 什么算法能解决多对多调度问题

我们也纠结啊

❻ 为什么说多级反馈队列调度算法能较好的满足各方面用户需要

多级反馈队列调度算法是一种性能较好的作业低级调度策略，能够满足各类用户的需要。对于分时交互型短作业，系统通常可在第一队列（高优先级队列）规定的时间片内让其完成工作，使终端型用户都感到满意；对短的批处理作业，通常，只需在第一或第一、第二队列（中优先级队列）中各执行一个时间片就能完成工作，周转时间仍然很短；对长的批处理作业，它将依次在第一、第二、……，各个队列中获得时间片并运行，决不会出现得不到处理的情况。此系统模拟了多级反馈队列调度算法及其实现

❼ 贪心算法多机调度问题伪代码

void machineWork::Sort( int timeId[] )
{
for( int i = 0 ; i < works ; i++ )
timeId[i] = i;
for( i = 0 ; i < works - 1 ; i++ )
{
double min = timesUnsorted[ timeId[i] ];
int p = i;
for( int j = i + 1 ; j < works ; j++ )
{
if( this->timesUnsorted[ timeId[j] ] > min )
{
min = this->timesUnsorted[ timeId[j] ];
p = j;
}
}
int t = timeId[i];
timeId[i] = timeId[p];
timeId[p] = t;
}
}

❽ 作业的调度算法有几种各自的优缺点是什么

先来先服务
时间片轮转
最短作业优先
多级反馈队列
优先级
最高响应比

❾ 请教linux下用户态进程调度问题

在进行Linux系统操作的时候，有时候会遇到一次用户态进程死循环，即系统反应迟钝、进程挂死等问题，那么遇到这些问题又该如何解决呢？下面小编就给大家介绍下一次用户态进程死循环的问题该如何处理。
Linux下如何处理一次用户态进程死循环问题
1、问题现象
业务进程（用户态多线程程序）挂死，操作系统反应迟钝，系统日志没有任何异常。从进程的内核态堆栈看，看似所有线程都卡在了内核态的如下堆栈流程中：
［root@vmc116 ~］# cat /proc/27007/task/11825/stack
［《ffffffff8100baf6》］ retint_careful+0x14/0x32
［《ffffffffffffffff》］ 0xffffffffffffffff
2、问题分析
1）内核堆栈分析
从内核堆栈看，所有进程都阻塞在 retint_careful上，这个是中断返回过程中的流程，代码（汇编）如下：
entry_64.S
代码如下：
ret_from_intr：
DISABLE_INTERRUPTS（CLBR_NONE）
TRACE_IRQS_OFF
decl PER_CPU_VAR（irq_count）
/* Restore saved previous stack */
popq %rsi
CFI_DEF_CFA rsi，SS+8-RBP /* reg/off reset after def_cfa_expr */
leaq ARGOFFSET-RBP（%rsi）， %rsp
CFI_DEF_CFA_REGISTER rsp
CFI_ADJUST_CFA_OFFSET RBP-ARGOFFSET
。。。
retint_careful：
CFI_RESTORE_STATE
bt $TIF_NEED_RESCHED，%edx
jnc retint_signal
TRACE_IRQS_ON
ENABLE_INTERRUPTS（CLBR_NONE）
pushq_cfi %rdi
SCHEDULE_USER
popq_cfi %rdi
GET_THREAD_INFO（%rcx）
DISABLE_INTERRUPTS（CLBR_NONE）
TRACE_IRQS_OFF
jmp retint_check
这其实是用户态进程在用户态被中断打断后，从中断返回的流程，结合retint_careful+0x14/0x32，进行反汇编，可以确认阻塞的点其实就在
SCHEDULE_USER
这其实就是调用schele（）进行调度，也就是说当进程走到中断返回的流程中时，发现需要调度（设置了TIF_NEED_RESCHED），于是在这里发生了调度。
有一个疑问：为什么在堆栈中看不到schele（）这一级的栈帧呢？
因为这里是汇编直接调用的，没有进行相关栈帧压栈和上下文保存操作。
2）进行状态信息分析
从top命令结果看，相关线程实际一直处于R状态，CPU几乎完全耗尽，而且绝大部分都消耗在用户态：
［root@vmc116 ~］# top
top - 09:42:23 up 16 days， 2:21， 23 users， load average： 84.08， 84.30， 83.62
Tasks： 1037 total， 85 running， 952 sleeping， 0 stopped， 0 zombie
Cpu（s）： 97.6%us， 2.2%sy， 0.2%ni， 0.0%id， 0.0%wa， 0.0%hi， 0.0%si， 0.0%st
Mem： 32878852k total， 32315464k used， 563388k free， 374152k buffers
Swap： 35110904k total， 38644k used， 35072260k free， 28852536k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
27074 root 20 0 5316m 163m 14m R 10.2 0.5 321:06.17 z_itask_templat
27084 root 20 0 5316m 163m 14m R 10.2 0.5 296:23.37 z_itask_templat
27085 root 20 0 5316m 163m 14m R 10.2 0.5 337:57.26 z_itask_templat
27095 root 20 0 5316m 163m 14m R 10.2 0.5 327:31.93 z_itask_templat
27102 root 20 0 5316m 163m 14m R 10.2 0.5 306:49.44 z_itask_templat
27113 root 20 0 5316m 163m 14m R 10.2 0.5 310:47.41 z_itask_templat
25730 root 20 0 5316m 163m 14m R 10.2 0.5 283:03.37 z_itask_templat
30069 root 20 0 5316m 163m 14m R 10.2 0.5 283:49.67 z_itask_templat
13938 root 20 0 5316m 163m 14m R 10.2 0.5 261:24.46 z_itask_templat
16326 root 20 0 5316m 163m 14m R 10.2 0.5 150:24.53 z_itask_templat
6795 root 20 0 5316m 163m 14m R 10.2 0.5 100:26.77 z_itask_templat
27063 root 20 0 5316m 163m 14m R 9.9 0.5 337:18.77 z_itask_templat
27065 root 20 0 5316m 163m 14m R 9.9 0.5 314:24.17 z_itask_templat
27068 root 20 0 5316m 163m 14m R 9.9 0.5 336:32.78 z_itask_templat
27069 root 20 0 5316m 163m 14m R 9.9 0.5 338:55.08 z_itask_templat
27072 root 20 0 5316m 163m 14m R 9.9 0.5 306:46.08 z_itask_templat
27075 root 20 0 5316m 163m 14m R 9.9 0.5 316:49.51 z_itask_templat
。。。
3）进程调度信息
从相关线程的调度信息看：
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
15681811525768 129628804592612 3557465
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
15682016493013 129630684625241 3557509
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
15682843570331 129638127548315 3557686
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
15683323640217 129642447477861 3557793
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
15683698477621 129645817640726 3557875
发现相关线程的调度统计一直在增加，说明相关线程一直是在被调度运行的，结合其状态也一直是R，推测很可能在用户态发生了死循环（或者非睡眠死锁）。
这里又有问题：为什么从top看每个线程的CPU占用率只有10%左右，而不是通常看到的死循环进程导致的100%的占用率？
因为线程数很多，而且优先级都一样，根据CFS调度算法，会平均分配时间片，不会让其中一个线程独占CPU。结果为多个线程间轮流调度，消耗掉了所有的cpu。。
另一个问题：为什么这种情况下，内核没有检测到softlockup？
因为业务进程的优先级不高，不会影响watchdog内核线程（最高优先级的实时线程）的调度，所以不会产生softlockup的情况。
再一个问题：为什么每次查看线程堆栈时，总是阻塞在retint_careful，而不是其它地方？
因为这里（中断返回的时候）正是调度的时机点，在其它时间点不能发生调度（不考虑其它情况~），而我们查看线程堆栈的行为，也必须依赖于进程调度，所以我们每次查看堆栈时，正是查看堆栈的进程（cat命令）得到调度的时候，这时正是中断返回的时候，所以正好看到的阻塞点为retint_careful。
4）用户态分析
从上面的分析看，推测应该是用户态发生了死锁。
用户态确认方法：
部署debug信息，然后gdb attach相关进程，确认堆栈，并结合代码逻辑分析。
最终确认该问题确为用户态进程中产生了死循环。