Projeto Final

Comprovando o lab de Dave Probert, modificando o algoritmo do escalonador

 

Solução

O WRK implementa uma fila geral de vários níveis (multi-level feedback queue – MLFQ) que consiste em 32 níveis de prioridade. As prioridades real-time são as maiores que 15, e são atribuídas estaticamente às threads. Assim como qualquer SO que utiliza MLFQ, as prioridades são ajustadas dinamicamente a fim de minimizar o tempo de resposta, maximizar a utilização da CPU, maximizar a preempção e geralmente minimizar o tempo para executar as threads.

O WRK trata todas as threads igualmente sem considerar a qual processo a thread pertence. Por exemplo, se um processo cria 99 threads e outro cria 1 thread, o escalonador se comporta como se 1 processo tivesse criado 100 threads, ou como se 100 processos tivessem criado 1 thread cada. Ou seja, os processos vão ganhar mais tempo se tiverem mais threads, o que não parece tão justo.
Implementamos então uma variação do fair-share scheduling, onde todos os processos que forem designados como “justos” terão aproximadamente o mesmo percentual da CPU, independente do número de threads.
A idéia é simples, escolher aleatoriamente um processo e escolher aleatoriamente uma thread desse processo.
Nossa abordagem foi tomar uma ação sempre que a thread para de executar na CPU.

  1. Re-inserir a thread que acabou de acabar (just-end) em sua posição no MLFQ.
  2. Manualmente selecionar a thread real-time que queremos que seja a próxima a executar, se existir. (via random –process-then-random-thread).
  3. Manualmente colocar a thread real-time selecionada no início da fila apropriada.

Para o segundo passo acima:

  1. Achar todas as threads real-time na MLFQ. Lembrando que as prioridades real-time são maiores que 15.
  2. Dividir as threads de acordo com os processos as quais pertencem. Cada thread tem um ponteiro para o seu processo, esse passo ajuda a determinar um conjunto de processos real-time que possam ser selecionados aleatoriamente.
  3. Imprimir o processo e a thread. Esse passo ajuda a visualizar quando o mecanismo está funcionando.

 

Mudanças no código

ps.h:

typedef struct _EPROCESS {
...
  ULONG ThreadCount : 16;
  ULONG ProcessFlag : 1;
...
} EPROCESS, *PEPROCESS;

dpcsup.c:

VOID
KiQuantumEnd (
  VOID
)
{
...
  if (Prcb->NextThread == NULL) {
  
    // Tenta selecionar thread pelo fair-share
    
    NewThread = KiSelectRandomThread(Prcb);
    
    // Se nao conseguiu seleciona pelo modo normal
    if (NewThread == NULL) {
      NewThread = KiSelectReadyThread(Thread->Priority, Prcb);
    }
    
    if (NewThread != NULL) {
      NewThread->State = Standby;
      Prcb->NextThread = NewThread;
    }
    
  }
...
}

ki.h:

// Prototipo da funcao

PKTHREAD
FASTCALL
KiSelectRandomThread (
  IN PKPRCB Prcb
);

threadsup.c:

ULONG RandomMinPriority = 16;
ULONG RandomSeed = 0xdeadf00d;

PKTHREAD
FASTCALL
KiSelectRandomThread (
  IN PKPRCB Prcb
)
{
   ULONG HighPriority;
   PRLIST_ENTRY ListHead;
   PRLIST_ENTRY NextEntry;
   ULONG PrioritySet;
   PKTHREAD Thread;
   PEPROCESS eProcess;
   ULONG ProcessCount;
   ULONG WhichProcess;
   ULONG WhichThread;
   PEPROCESS SelectedProcess;
   PKTHREAD SelectedThread;
  
  // Pega o numero da maior prioridade da ReadyList  
  
  PrioritySet = Prcb->ReadySummary;
  KeFindFirstSetLeftMember(PrioritySet, &HighPriority);  
  
  // Retorna NULL se for 0 ou prioridade real-time   
  
  if (HighPriority < RandomMinPriority || HighPriority > RandomMaxPriority) {
    return NULL;
  }   
  
  ListHead = &Prcb->DispatcherReadyListHead[HighPriority];   
  
  ProcessCount = 0;   
  
  NextEntry = ListHead->Flink;
  while (NextEntry != ListHead) {     
  
    Thread = CONTAINING_RECORD(NextEntry, KTHREAD, WaitListEntry);
    eProcess = CONTAINING_RECORD(Thread->Process, EPROCESS, Pcb);     
    
    // Conta a quantidade de processos diferentes
    // e a quantidade de threads em cada processo
    if (eProcess->ProcessFlag == 0) {
      ProcessCount++;
      eProcess->ThreadCount = 0;
      eProcess->ProcessFlag = 1;
    }     
    
    eProcess->ThreadCount++;     
    
    NextEntry = NextEntry->Flink;

  }   
  
  // Pega um processo aleatorio   
  
  WhichProcess = RtlRandomEx(&RandomSeed) % ProcessCount;   
  
  SelectedProcess = NULL;
  SelectedThread = NULL;   
  
  // Pega uma thread aleatoria do processo e zera a flag   
  
  NextEntry = ListHead->Flink;
  while (NextEntry != ListHead) {     
    
    Thread = CONTAINING_RECORD(NextEntry, KTHREAD, WaitListEntry);
    eProcess = CONTAINING_RECORD(Thread->Process, EPROCESS, Pcb);     
    
    // Procura o processo     
  
    if (SelectedProcess == NULL) {
      if (eProcess->ProcessFlag == 1) {
        if (WhichProcess == 0) {
          SelectedProcess = eProcess;
          WhichThread = RtlRandomEx(&RandomSeed) % SelectedProcess->ThreadCount;
          continue;
        }
        WhichProcess--;
      }
    }     
  
    // Procura a thread   
    else if (SelectedThread == NULL) {
      if (eProcess == SelectedProcess) {
        if (WhichThread == 0) {
          SelectedThread = Thread;
        } else {
          WhichThread--;
        }
      }
    }     
  
    eProcess->ProcessFlag = 0;   
    NextEntry = NextEntry->Flink;

  }   

  // Remove a thread da lista   
  if (RemoveEntryList(&SelectedThread->WaitListEntry) != FALSE) {
    Prcb->ReadySummary ^= PRIORITY_MASK(HighPriority);
  }   

  return SelectedThread;
}