Informazioni su Linux Scheduler

Question

Sono nuovo nel kernel di Linux e nella programmazione di basso livello. Volevo sapere come si suppone che linux scheduler sia O (1) in termini di complessità temporale.

mi sono imbattuto nel seguente articolo, che è molto informativo, ma ho un problema capire il pargraph ho riprodotto qui di seguito http://www.ibm.com/developerworks/linux/library/l-scheduler/

Il lavoro dello scheduler è semplice: scegliere l'attività sul più alto priorità lista da eseguire. Per rendere questo processo più efficiente, viene utilizzata una bitmap per definire quando le attività si trovano in un determinato elenco di priorità. Pertanto, sulla maggior parte delle architetture, un'istruzione find-first-bit-set è utilizzata per trovare il bit con priorità più alta impostato in una delle cinque parole a 32 bit (per le 140 priorità). Il tempo necessario per trovare un'attività da eseguire dipende non dal numero di attività attive ma dal numero di priorità . Ciò rende lo scheduler 2.6 un processo O (1) poiché il tempo di pianificazione è fisso e deterministico indipendentemente dal numero di attività attive .

Perché 5 parole di 32 bit per 140 code? Chi l'istruzione find-first-bit-set aiuta a selezionare una delle 140 code?

Answer 1

un campo di bit utilizza un singolo valore per rappresentare un numero di stati booleani, ad esempio se stessimo usando un po 'intero 8 allora potremmo dire che:

17 (decimal) = 00010001 (binary) 

il che indica che il 4 ° e 8 ° i valori booleani sono veri, in cui tutti gli altri valori booleani sono falsi. In totale 8 stati booleani possono essere tracciati in quanto ci sono 8 bit.

Come si desidera tenere traccia di 140 stati (1 per ogni coda, true che indica che la coda contiene un'attività), sono necessari 140 bit e, pertanto, come 140/32 = 4.375, sono necessari almeno 5 numeri interi da 32 bit per l'archiviazione tutti gli stati booleani.

Answer 2

Qualcosa di simile a questo:

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 

viene utilizzato per raggiungere il particolare processo con serie di priorità e questo è come bitmap sono utilizzati in scheduler che a sua volta dipende dalla struct prio_array

L'articolo è stato sottolineato è superato controllare questo uno http://www.informit.com/articles/article.aspx?p=101760&seqNum=2