Comprensión del programador de Linux

Question

Soy nuevo en el kernel de Linux y en la programación de bajo nivel. Quería saber cómo se supone que el programador de Linux es O (1) en complejidad de tiempo.

me encontré con el siguiente artículo que es muy informativo, pero tengo un problema en la comprensión de la pargraph He reproducido a continuación http://www.ibm.com/developerworks/linux/library/l-scheduler/

La tarea del programador es simple: seleccione la tarea en la más alta prioridad lista para ejecutar Para que este proceso sea más eficiente, se usa un mapa de bits para definir cuándo las tareas están en una lista de prioridades dada. Por lo tanto, en la mayoría de las arquitecturas, una instrucción find-first-bit-set es utilizada para encontrar el bit de prioridad más alta establecido en una de cinco palabras de 32 bits (para las 140 prioridades). El tiempo que lleva encontrar una tarea para ejecutar no depende del número de tareas activas, sino del número de prioridades . Esto hace que el programador 2.6 sea un proceso O (1) porque el tiempo de programación es fijo y determinista independientemente del número de tareas activas .

¿Por qué 5 palabras de 32 bits para 140 colas? ¿Quién la instrucción find-first-bit-set ayuda a seleccionar una de las 140 colas?

Answer 1

Un campo de bits utiliza un único valor para representar un número de estados booleanos, por ejemplo, si estábamos usando un entero de 8 bits, entonces podríamos decir que:

17 (decimal) = 00010001 (binary) 

lo que indica que la cuarta y la octava Los valores booleanos son verdaderos, donde todos los demás valores booleanos son falsos. En total, se pueden rastrear 8 estados booleanos ya que hay 8 bits.

Como deseamos rastrear 140 estados (1 por cada cola, verdadero que indica que la cola contiene una tarea), se requieren 140 bits, y así como 140/32 = 4.375, necesitamos al menos 5 enteros de 32 bits para almacenar todos los estados booleanos.

Answer 2

Algo como esto:

int bitmap_idx = priority/BITS_PER_WORD; 
int bitmap_bit = priority%BITS_PER_WORD; 

isSet = (bitmap[bitmap_idx]&(1<<bitmap_bit)); //test 
bitmap[bitmap_idx] |= 1<<bitmap_bit;    //set 

se utiliza para llegar al proceso en particular con arreglo prioridad y esto es cómo se utilizan los mapas de bits en el planificador que a su vez depende de la estructura prio_array

El artículo que ha señalado está desactualizado verifique este http://www.informit.com/articles/article.aspx?p=101760&seqNum=2