Process Scheduling
Renato de Castro Dutra
COPPE/UFRJ
Jul/2006
Baseado no capítulo 4 do livro Linux Kernel Development 2 nd Edition de Robert Love
Agenda
1.
2.
3.
4.
5.
6.
Linux kernel
Escalonador
Runqueue
Vetores de Prioridade
Sleeping e Wakeup
Balanceamento de
Carga
7. Chaveamento de
Contexto
8. System Calls
9. Discussão
10. Futuro do Escalonador
11. Referências
1.1. Linux Kernel
• Linux Kernel 2.6.17.4 (estável)
– Kernel tornou-se preemptivo no Kernel 2.5
– Robert Love foi o principal articulador
• Linux Kernel 2.4 (estável)
– Kernel não-preemptivo
• O que é kernel preemptivo ?
1.2. Kernel Preemptivo
• Os processos são preemptivos (podem ser interrompidos)
– se um processo A entra no estado TASK_RUNNING (processo
runnable), o kernel checa se a prioridade dinâmica do processo A é
maior que a prioridade do processo que está rodando
– Se é, a execução do processo corrente é interrompida e o
escalonador é chamado para selecionar um outro processo para
rodar (normalmente, o processo A)
– Um processo também pode entrar em preempção se o timeslice
expira (este valor é pré-determinado, calculado dinamicamente)
» Se isto ocorre, o campo need_resched do processo corrente fica
ativo, e o escalonador é chamado quando o tempo do interrupt
handler termina ( ou seja, kernel libera o interrupt)
• Processo preemptivo não é suspenso, desde que ele fica no
estado TASK_RUNNING, apenas não usa CPU.
1.3. Escalonador
– Função – componente do Kernel que seleciona o
processo que vai rodar primeiro
– Pode ser visto como o elemento que divide os
recursos finitos do tempo do processador entre os
processos com estado TASK_RUNNING
– É a base da multi-tarefa, dando a impressão de que
vários processos estão rodando simultaneamente
– Três formas de escalonamento:
– FIFO
– RoundRobin
– Prioridade (calculada dinamicamente)
1.4. Escalonamento Baseado em
Prioridade Dinâmica
•
Inicia com uma prioridade default e permite ao escalonador aumentar ou diminuir,
dinamicamente, a prioridade de acordo com seus objetivos.
– Duas faixas de Prioridade:
• Nice Range (default = 0)
-20
0
+19
Mínimo Timeslice
Máximo Timeslice
Prioridade baixa
• Real-Time Range
0
+99
Prioridade baixa
• Um processo Real-Time tem sempre maior prioridade do que um
processo normal!
1.5. Timeslice*
• Valor numérico que representa quanto tempo uma tarefa
pode rodar até ser interrompida na preempção.
• Este valor de Timeslice é difícil de estimar, nem deve ser
curto demais, nem longo demais…
– Curto – muito do tempo será perdido na troca de processos
– Longo – processos interativos vão se tornar tediosos
Mínimo
5 ms
baixa prioridade
alta prioridade
menos interativo
mais interativo
Default
100 ms
Máximo
800 ms
•
Processos não precisam gastar todo seu Timeslice em uma rodada somente. Pode rodar em pedaços separados.
•
Ao fim do Timeslice o processo é considerado expirado e só poderá rodar após todos os Timeslices
dos outros processos terem terminado. Então o escalonador fará uma nova atribuição de
Timeslices.
*Em alguns sistemas operacionais também chamado de quantum ou processor slice
1.6. Equação de Timeslice
164 #define SCALE_PRIO(x, prio) \
165 max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)
•
Por pior que seja a prioridade do processo, o menor valor de Timeslice será
MIN_TIMESLICE = 5ms
•
O processo pode quebrar seu Timeslice utilizando a função
TIMESLICE_GRANULARITY:
135 #define TIMESLICE_GRANULARITY(p) (GRANULARITY * \
136 (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)))
1.7. Objetivos para o Kernel 2.5
•
•
•
•
•
•
•
O(1) scheduler
preemptive kernel
latency improvements
redesigned block layer
improved VM subsystem
improved threading support
new sound layer
1.8. Objetivos para o Escalonador O(1)
• Prover complexidade O(1) !
• Escalabilidade SMP perfeita – Quando
aumenta o número de processadores o
escalonamento é escalável.
• Afinidade SMP melhorada – a troca de
processos entre processadores apenas para fim
de balanceamento da runqueue, evitando efeito
“ping-pong”.
2. Escalonador O(1)
• Escalonador O(1) – Decidir qual processo vai rodar em
tempo constante, independente do número de processos.
– Antigamente O(N):
– Lista única de processos N:
Para cada processo N runnable{
Acha a dignidade deste processo;
Se (este é o processo mais digno ainda) {
Lembra isto;
}
}
Roda o processo mais digno;
– Mesma prioridade -> Round Robin
Escala linearmente com o número de processos !
2.1. Escalonador O(1) (cont.)
• O(1) – utiliza Listas de Prioridade
•
•
•
•
•
Pegue a Lista de Prioridade Mais Alta que tenha processos
Pegue o primeiro processo desta Lista de Prioridade Mais Alta
Rode este processo
Como fazer isto ?
Agradecimentos ao Ingo Molnar!
12 * 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar:
13 * hybrid priority-list and round-robin design with
14 * an array-switch method of distributing timeslices
15 * and per-CPU runqueues. Cleanups and useful suggestions
16 * by Davide Libenzi, preemptible kernel bits by Robert Love.
Fonte: Linux-kernel-sched_c.htm
2.2. Gráfico O(N) x O(1)
Fonte: Timo Hönig – Linux Magazin
http://www.linuxmagazin.de/Artikel/ausgabe/2004/02/038_
scheduler/scheduler.html
1 CPU: Pentium III 1 GHz, 512 MByte RAM
2 CPU: Pentium III 850 MHz, 1 GByte RAM
4 CPU: Pentium III 700 MHz, 4 GByte RAM
8 CPU: Pentium III 700 MHz, 8 GByte RAM
v.2.4
v.2.6
3. Runqueue
• Estrutura básica do Escalonador é a
runqueue
• É uma lista de processos runnable em um
dado processador
• Adicionalmente contém informação de
escalonamento por processador
3.1. Struct Runqueue
198 struct runqueue {
199 spinlock_t lock;
200
201 /*
202 * nr_running and cpu_load should be in the same cacheline because
203 * remote CPUs use both these fields when doing load calculation.
204 */
205 unsigned long nr_running;
206 #ifdef CONFIG_SMP
207 unsigned long cpu_load;
208 #endif
209 unsigned long long nr_switches;
210
211 /*
212 * This is part of a global counter where only the total sum
213 * over all CPUs matters. A task can increase this counter on
214 * one CPU and if it got migrated afterwards it may decrease
215 * it on another CPU. Always updated under the runqueue lock:
216 */
217 unsigned long nr_uninterruptible;
218
219 unsigned long expired_timestamp;
220 unsigned long long timestamp_last_tick;
221 task_t *curr, *idle;
222 struct mm_struct *prev_mm;
223 prio_array_t *active, *expired, arrays[2];
224 int best_expired_prio;
225 atomic_t nr_iowait;
226
227 #ifdef CONFIG_SMP
228 struct sched_domain *sd;
229
230 /* For active balancing */
231 int active_balance;
232 int push_cpu;
233
234 task_t *migration_thread;
270 unsigned long wunt_cnt;
235 struct list_head migration_queue;
271 unsigned long wunt_moved;
236 #endif
272
237
273 /* sched_migrate_task() stats */
238 #ifdef CONFIG_SCHEDSTATS
274 unsigned long smt_cnt;
239 /* latency stats */
275
240 struct sched_info rq_sched_info;
276 /* sched_balance_exec() stats */
241
277 unsigned long sbe_cnt;
242 /* sys_sched_yield() stats */
278 #endif
243 unsigned long yld_exp_empty;
279 };
244 unsigned long yld_act_empty;
245 unsigned long yld_both_empty;
246 unsigned long yld_cnt;
247
248 /* schedule() stats */
249 unsigned long sched_noswitch;
250 unsigned long sched_switch;
251 unsigned long sched_cnt;
252 unsigned long sched_goidle;
253
254 /* pull_task() stats */
255 unsigned long pt_gained[MAX_IDLE_TYPES];
256 unsigned long pt_lost[MAX_IDLE_TYPES];
257
258 /* active_load_balance() stats */
259 unsigned long alb_cnt;
260 unsigned long alb_lost;
261 unsigned long alb_gained;
262 unsigned long alb_failed;
263
264 /* try_to_wake_up() stats */
265 unsigned long ttwu_cnt;
266 unsigned long ttwu_attempts;
267 unsigned long ttwu_moved;
268
269 /* wake_up_new_task() stats */
3.2. Struct Runqueue Clean
struct runqueue{
spinlock_t
unsigned long
unsigned long
unsigned long
unsigned long
unsigned long long
struct task_struct
struct tasl_struct
struct mm_struct
struct prio_array
struct prio_array
struct prio_array
struct tasl_strucut
struct list_head
atomic_t
};
lock;
nr_running;
nr_switches;
expired_timestamp;
nr_uninterruptible;;
timestamp_last_tick;
*curr;
*idel;
*prev_mm;
*active;
*expired;
arrays[2];
*migration_thread;
migration_queue;
nr_iowait;
/* spin lock that protects this runqueue */
/* number of runnable tasks */
/* context switch count */
/* time of last array swap */
/* uninterruptible tasks */
/* last scheduler tick */
/* currently running task */
/* this processor´s idle task */
/* mm_struct of last ran task */
/* active priority array */
/* the expired priority array */
/* the actual priority arrays */
/* migration thread */
/* migration queue */
/* number of tasks waiting in I/O */
• Antes de um runqueue ser manipulado deve ser protegido por um lock
3.3. Parênteses
Escalabilidade SMP
• Em máquinas uniprocessadas o escalonador O(1)
de Ingor Molnat é muito bom, porém como
resolver os problemas inerentes a escalonamento
em SMP/NUMA ?
– Escalonamento Multiqueue
– SpinLock
– Balanceamento de Carga
3.4. Parênteses
SMP, MPP, NUMA
Symmetric Multi-Processor
Non-Uniform Memory Access
Massively Parallel Processor
3.5. Parênteses
Problemas
• Deadlock
• Condições necessárias e suficientes para ocorrer:
–
–
–
–
Exclusão Mútua – somente um processo pode usar um recurso por vez
Hold-and-wait – processo pode bloquear um recurso enquanto aguarda
Não preemptivo – recurso não pode ser removido de um processo rodando
Ciclo no grafo – A -> B -> C -> A
• Formas de evitar:
– Prevention - Prevenir
– Avoidance - Evitar
– Detection - Detetar
• Starvation
3.6. Solução
• Multiqueue Scheduler
3.7. Afinidade entre SMP
• Versão 2.4 tinha um problema indesejável:
• Um processo podia ficar pingando de um processador para
outro (efeito “Ping-Pong”)
time 1 time 2 time 3 time 4 time 5
Process A CPU 0 CPU 1 CPU 0 CPU 1 CPU 0
Process B CPU 1 CPU 0 CPU 1 CPU 0 CPU 1
CPU
• Este problema foi solucionado também pelas runqueues por
processador e garante a afinidade entre multi-processadores
3.8. Lock
• Para garantir que somente um processador possa manipular concorrentemente a
runqueue, esta é protegida por um lock. Assim, somente um processador pode
executar o escalonador concorrentemente.
• É raro um processador diferente da origem da runqueue manipulá-lo, porém é
possível.
• Funções de lock e unlock:
task_rq_lock()
task_rq_unlock()
• Para evitar deadlock o código deve sempre obter o lock na mesma ordem: pelo
endereço de runqueues ascendente (cap. 8)
v.2.4
v.2.6
4. Vetores de Prioridade
• Cada runqueue possui dois vetores de prioridade:
• Vetor de Prioridade Ativo
• Vetor de Prioridade Expirado
• São estes vetores que permitem que a complexidade do
algoritmo seja O(1).
4.1. Vetores de Prioridade
• Cada vetor de prioridade contém uma fila de processos runnable
por nível de prioridade.
• As filas contém listas de processos runnable em cada nível de
prioridade
• O vetor de prioridade também contém um bitmap de prioridade
usado para eficientemente descobrir a tarefa de mais alta
prioridade no sistema.
185 struct prio_array {
186
unsigned int nr_active;
187
unsigned long bitmap[BITMAP_SIZE];
188
struct list_head queue[MAX_PRIO];
189 };
4.2. Vetores de Prioridade
• Cada vetor de prioridade contém um campo bitmap que tem ao
menos um bit para toda prioridade no sistema. Inicialmente todos
os bits são 0.
• Quando uma tarefa torna-se runnable, o bit correspondente à
prioridade da tarefa no bitmap torna-se 1. O problema, então é
achar, na tabela, o processo mais prioritário dos que tiverem bit 1.
Como a tabela é estática porque o número de prioridades é fixo
(140), esta busca tem complexidade constante e não depende do
número de processos N.
• Cada vetor de prioridade também contém um vetor queue da struct
list_head, uma fila para cada prioridade e contém todos os
processos que têm o mesmo valor de prioridade (representado pela
variável nr_active).
4.3. Recálculo de Timeslice
• Sistemas antigos faziam esta tarefa em O(N).
• Devido aos vetores Ativo e Expirado, este recálculo não precisa
ser feito em O(N).
• Vetor de Prioridade Ativo – contém todas as tarefas na runqueue
associada em que o Timeslice não expirou.
• Vetor de Prioridade Expirado – contém todas as tarefas na
runqueue associada em que o Timeslice expirou
• Quando o Timeslice da tarefa expira, este é movido para o vetor
Expirado, porém, antes, seu Timeslice é recalculado.
4.4. Troca de Vetores Ativo / Expirado
2765 array = rq->active;
2766 if (unlikely(!array->nr_active)) {
2767 /*
2768 * Switch the active and expired arrays.
2769 */
2770 schedstat_inc(rq, sched_switch);
2771 rq->active = rq->expired;
2772 rq->expired = array;
2773 array = rq->active;
2774 rq->expired_timestamp = 0;
2775 rq->best_expired_prio = MAX_PRIO;
4.5. Cálculo de Prioridade e Timeslice
• Prioridade Dinâmica – leva em conta uma heurística porque não sabe se
o processo é interativo ou não. Se o processo tem muito tempo inativo, é
interativo. Se não, não é. Implementação -> guarda em sleep_avg (uma
tabela) a razão entre o tempo dormindo e o tempo acordado para cada
processo.
• Sleep_avg é incrementado quando o processo se torna runnable (até
MAX_SLEEP_AVG) e decrementado a cada tick de tempo que o processo
roda (até 0)
MAX_SLEEP_AVG
0
Bonus/penalty
-5
0
Default = 10 ms
+5
4.6. Cálculo de Prioridade e Timeslice
105 * Here are a few examples of different nice levels:
106 *
107 * TASK_INTERACTIVE(-20): [1, 1, 1, 1, 1, 1,1,1,1,0,0]
108 * TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
109 * TASK_INTERACTIVE( 0):
[1,1,1,1,0,0,0,0,0,0,0]
110 * TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
111 * TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
112 *
113 * (the X axis represents the possible -5 ... 0 ... +5 dynamic
114 * priority range a task can explore, a value of '1' means the
115 * task is rated interactive.)
4.7. Cálculo de Prioridade e Timeslice
• Timeslice é recalculado baseado na prioridade
estática.
• Quando um novo filho é criado o pai e o filho
dividem o Timeslice remanescente (como?)
• Quando o Timeslice expira, o escalonador inclui a
tarefa no vetor Expirado, recalculando antes o
Timeslice.
5. Sleeping e Wakeup
6. Balanceamento de Carga
• load_balance() no Escalonador. Dois métodos de chamada:
• Quando a runqueue está vazia
• Pelo timer
• A cada 1ms quando o sistema está parado
• A cada 200ms quando não
• Em sistema uniprocessados não é compilado.
7. Chaveamento de Contexto
– Manipulado pelo context_switch. Ocorre sempre que um novo
processo é chamado para run.
– Executa dois trabalhos:
» Chama switch_mm() – troca o mapeamento de memória virtual
do processo antigo para o novo
» Chama switch_to() – troca o estado do processador do
processo novo para o antigo, envolvendo atualização de pilhas
e registradores
– Utiliza uma flag need_resched para que o kernel chame o
escalonador pis existe um processo novo para substituir o antigo
– Duas formas para ativar a flag
» Quando o timeslice de um processo expira o scheduler_tick()
ativa a flag
» Quando um processo de maior prioridade acorda o
try_to_wake_up() ativa a flag
8. SystemCalls Relacionadas com
Escalonamento
• Splice () e Tee() system calls (fonte: Abril/2006 – Linus Torvalds)
• Splice() é um read/write para um buffer do kernel diretamente.
• Tee() é um memcpy() de um buffer do Kernel para outro, sem copiar realmente,
apenas incrementando ponteiros de referência.
• Existe um buffer do kernel aleatório no espaço do usuário e que o usuário tem
controle (como é buffer do kernel, é mais eficiente).
• Pode fazer movimento de dado zero-copy.
– Exemplo: Direcionar dado de um socket para outro sem copiar isto no espaço do
usuário. Assim, é possível direcionar dado que venha de um Encoder MPEG-4 e fazer
um Tee() para duplicar o stream e escrever um dos streams para disco e outro para
socket para um broadcast em tempo real, sem copiar fisicamente na memória.
• Aumentam a performance, porque agiliza os processos que precisam
de leitura/escrita.
9. Discussão
–
A versao 2.6.17 é mais rápida em SMP (Symmetric MultiProcessor), porém em máquinas uniprocessadas rápidas
(2GHz) esta diferença não é perceptível.
9.1. Discussão
Comparação entre Linux 2.6.4 e 2.4.25
Test System and Benchmarks
CPU
Motherboard
Chipset
Memory
Storage
OS
Dual Xeon Test Box
2x 3.2GHz Xeons w/ 1MB L3 Cache
MSI Master LS2
Intel E7505
1GB Crucial Registered/ECC PC2700
Western Digital 400JB
Gentoo Linux 1.4
What benchmarks will we run?
picColor Image
software compiling (MySQL source code compiled with make -j 4)
mp3 encoding (BladeEnc)
Apache Static HTML
Apache PHP/MySQL
MySQL Super Smack(SELECT and UPDATE)
dbench v. 2.0 (file server performance)
9.2. Discussão
9.3. Discussão
File Server
10. Futuro do Escalonador
• Scheduler Modes – classificar workloads em categorias e
permitir que usuários root ajustem o comportamento do
escalonador dinamicamente.
• Swappable Scheduler (http://www.gnu.org/software/hurd) usuário especifica qual escalonador deve ser usado
dependendo da aplicação.
11. Referências
•
•
•
•
•
•
•
Love, R., Linux Kernel Development – 2nd edition, Novell Press, June
2005.
Bovet, D. P., Cesati, M. Understanding The Linux Kernel – 1st edition,
O´Reilly, October 2000.
Aas, J., Understanding the Linux kernel 2.6.8.1 CPU Scheduler –
Silicon Graphics Inc., February 2005.
Cross Reference Linux – Linux/kernel/sched.c http://lxr.linux.no/source/kernel/sched.c
Love, R., Introducing the 2.6 kernel – Linux Journal, may 2003
Heursch, A.C., Grambow, D., Roedel, D., Rzehak, H., Time-critical
tasks in Linux 2.6 Concepts to increase the preemptability of the Linux
kernel – Linux Automation Konferenz 2004
Ge, l. – Kernel Comparison: Web Serving on 2.4 and 2.6 – Linux
Technology Center IBM – February 2004
12. Questão _______
•
Suponha que 5 processos, de P1 a P5, sejam sucessivamente submetidos para execução em
intervalos de 1ut (unidade de tempo). O tempo estimado de serviço para os processos é
respectivamente de: 5, 3, 4, 5 e 2ut, uma política de time slice de 2ut é igualmente usada para todos
os processos, o critério de escalonamento adotado é o Round Robin e a estratégia para deadlock é a
da detecção.
•
a) Defina e compare as estratégias para:
–
–
–
prevenir (prevention)
evitar (avoidance)
e detectar (detecion) deadlocks.
•
b) Monte o gráfico e determine o turnaround dos processos.
•
c) Determine o fator de eficiência do método (Ts/Tq).