Notes On Operating Systems: Three Easy Pieces
Um programa executa instruções. Milhões de vezes por segundo o processador busca (fetch) uma instrução da memória, a decodifica (decode) e a executa (execute). E assim ocorre até que o programa seja finalizado. O Sistema Operacional (OS) facilita a execução de programas, permitindo o compartilhamento de memória, a interação com dispositivos, entre outros.
Para isso, o OS utiliza a virtualização, uma técnica que transforma um recurso físico do computador em um virtual. Logo, OSs são chamados ocasionalmente de Máquinas Virtuais. Para que o usuário possa ter acesso à esses recursos, o OS também fornece APIs para comunicação. São as system calls, que o OS exporta. Esse conjunto de funções é chamado de standard library.
O OS também é conhecido por resource manager, visto que a virtualização acarreta o compartilhamento de recursos, cabe ao sistema operacional fazer a organização dos mesmos.
O código abaixo imprime na tela a string passada pelo usuário a cada segundo.
int main(int argc, char *argv[]){
if(argc != 2){
fprintf(stderr, "usage: cpu <string>\n");
exit(1);
}
while(1){
Spin(1);
printf("%s\n", argv[1]);
}
return 0;
}Para isso, chama a função Spin, definida na biblioteca 'common.h', definida abaixo.
#ifndef __common_h__
#define __common_h__
#include <sys/time.h>
#include <sys/stat.h>
#include <assert.h>
double GetTime(){
struct timeval t;
int rc = gettimeofday(&t, NULL);
assert(rc == 0);
return (double) t.tv_sec + (double) t.tv_usec/1e6;
}
void Spin(int howlong) {
double t = GetTime();
while((GetTime() - t) < (double) howlong);
}
#endifAo executar o programa, o seguinte resultado é obtido:
gcc -o cpu cpu.c
./cpu "A"A A A A A A ^C
Para finalizar a execução, é necessário pressionar C-c. A execução do programa é simples e direta. A seguir,
são invocadas quatro instâncias do programa. O resultado mostra que os processos, de certa forma, executaram
simultaneamente.
./cpu "A" & ./cpu "B" & ./cpu "C" & ./cpu "D"[1] 22 [2] 23 [3] 24 [4] 25 A B C D A B C D A B C D ...
Entretanto, este comportamento é uma ilusão orquestrada pelo Sistema Operacional, em conjunto com o hardware da máquina, que consegue transformar uma única CPU em várias CPUs virtuais. Este processo é chamado de virtualização da CPU.
A memória física é um array de bytes. Para que a memória seja lida, deve-se especificar o endereço para recuperação dos dados armazenados. Para escrita, os dados a serem gravados também devem ser fornecidos. A memória é acessada diversas vezes quando um programa é executado. Não só os dados utilizados pelo programa são armazenados em memória, como também as instruções do próprio programa. A seguir, está definido um programa que faz acessos à memória.
int main(){
int *p = malloc(sizeof(int));
assert(p != NULL);
printf("(%d) address pointed to by p: %p\n", getpid(), p);
*p = 0;
while (1){
Spin(1);
*p = *p + 1;
printf("(%d) p: %d\n", getpid(), *p);
}
return 0;
}Executando-o:
gcc -o mem mem.c
./mem(104) address pointed to by p: 0x80052a0 (104) p: 1 (104) p: 2 (104) p: 3 (104) p: 4 ^C
Este programa realiza uma alocação de memória, depois imprime o endereço da memória alocada, em seguida coloca 0 como conteúdo daquele endereço e por fim entra em um loop que incrementa esse valor a cada segundo. Nas impressões, o identificador de processo (PID) do programa em execução também é informado. Quando mais de uma instância desse programa executa, o seguinte resultado é obtido.
./mem & ./mem &[2] 105 [3] 106 (105) address pointed to by p: 0x80052a0 (106) address pointed to by p: 0x80052a0 (105) p: 1 (106) p: 1 (105) p: 2 (106) p: 2 (105) p: 3 (106) p: 3 (105) p: 4 (106) p: 4 (105) p: 5 (106) p: 5 ...
Observa-se que ambos os programas alocaram memória do mesmo endereço, entretanto, as alterações que cada um faz é independente. Isto se deve à virtualização da memória, na qual cada processo acessa seu próprio espaço virtual de endereços (virtual address space, ou address space, somente), cabendo ao SO mapear essa memória particular na física.
Termo que se refere a uma gama de problemas que surgem quando tarefas são executadas simultaneamente. Estes problemas não se limitam ao SO, como também aparecem em programas modernos multi-threaded, como o seguinte:
volatile int counter = 0;
int loops;
void *worker(void *arg){
int i;
for(i = 0; i < loops; i++){
counter++;
}
return NULL;
}
int main(int argc, char *argv[]){
if(argc != 2){
fprintf(stderr, "usage: threads <value>\n");
exit(1);
}
loops = atoi(argv[1]);
pthread_t p1, p2;
printf("Initial value : %d\n", counter);
Pthread_create(&p1, NULL, worker, NULL);
Pthread_create(&p2, NULL, worker, NULL);
Pthread_join(p1, NULL);
Pthread_join(p2, NULL);
printf("Final value : %d\n", counter);
return 0;
}Tal programa utiliza a biblioteca 'common_threads.h', definida abaixo:
#ifndef __common_threads_h__
#define __common_threads_h__
#include <pthread.h>
#include <assert.h>
#include <sched.h>
#ifdef __linux__
#include <semaphore.h>
#endif
#define Pthread_create(thread, attr, start_routine, arg) assert(pthread_create(thread, attr, start_routine, arg) == 0);
#define Pthread_join(thread, value_ptr) assert(pthread_join(thread, value_ptr) == 0);
#define Pthread_mutex_lock(m) assert(pthread_mutex_lock(m) == 0);
#define Pthread_mutex_unlock(m) assert(pthread_mutex_unlock(m) == 0);
#define Pthread_cond_signal(cond) assert(pthread_cond_signal(cond) == 0);
#define Pthread_cond_wait(cond, mutex) assert(pthread_cond_wait(cond, mutex) == 0);
#define Mutex_init(m) assert(pthread_mutex_init(m, NULL) == 0);
#define Mutex_lock(m) assert(pthread_mutex_lock(m) == 0);
#define Mutex_unlock(m) assert(pthread_mutex_unlock(m) == 0);
#define Cond_init(cond) assert(pthread_cond_init(cond, NULL) == 0);
#define Cond_signal(cond) assert(pthread_cond_signal(cond) == 0);
#define Cond_wait(cond, mutex) assert(pthread_cond_wait(cond, mutex) == 0);
#ifdef __linux__
#define Sem_init(sem, value) assert(sem_init(sem, 0, value) == 0);
#define Sem_wait(sem) assert(sem_wait(sem) == 0);
#define Sem_post(sem) assert(sem_post(sem) == 0);
#endif
#endifEste programa cria duas threads usando o Pthread_create(). Um thread pode ser imaginada como uma função
que roda no mesmo espaço de memória de outras funções, com mais de uma delas sendo executada ao mesmo tempo.
No exemplo acima, cada thread começa executando a rotina worker(), na qual um contador é incrementado
dentro de um loop. Executando o código para loops = 1000, temos:
gcc -o thread thread.c -Wall -pthread
./thread 1000| Initial | value | : | 0 |
| Final | value | : | 2000 |
Como esperado, cada thread incrementa o contador 1000 vezes, resultando em um valor final de 2000.
./thread 100000| Initial | value | : | 0 |
| Final | value | : | 124234 |
./thread 100000| Initial | value | : | 0 |
| Final | value | : | 123549 |
Para valores maiores de loops, algo inesperado acontece, como observado acima. Não só o resultado apresentado
foi incorreto, como também inconsistente, como mostra a segunda execução com loops = 100000. Este comportamento
ocorre por causa da natureza de execução do código. A instrução que incrementa o contador compartilhado se
transforma em três comandos: um para carregar o valor do contador da memória para o registrador, outro para
incrementá-lo e um último para registrá-lo novamente na memória. O erro aparece pois estas instruções não são
executadas atomicamente (todas de uma vez).
Memórias DRAM armazenam valores de forma volátil, sendo sucetíveis a perda em caso de falha do sistema ou uma reinicialização. Portanto, memórias persistentes são fundamentais para armazenamento de longo prazo. O OS fornece um file system, responsável por armazenar os arquivos (files), que o usuário cria. O programa a seguir cria um arquivo que contém a string “hello world”.
int fd = open("/tmp/file", O_WRONLY|O_CREAT|O_TRUNC, S_IRWXU);
assert(fd > -1);
int rc = write(fd, "hello world\n", 13);
assert(rc == 13);
close(fd);
return 0;gcc -o io io.c -Wall
./io
echo "$(cat /tmp/file)"hello world
Para isto, o programa abre o arquivo e o cria (open()), escreve dados (write()) e por fim o fecha
(close()). Esses system calls são direcionados ao file system. O OS deve encontrar no disco onde este
arquivo residirá, alem de manter registros sobre isto ao longo da execução, enviando diversos comandos de I/O
para o dispositivo de armazenamento. Desta forma, o sistema operacional fornece uma forma simples e padronizada
de comunicação com tais dispositivos. Por isso ele é chamado (as vezes) de standard library.
Assim, um OS é encarregado de transformar recursos físicos, como CPU, memória, disco, e os virtualizar. Além disso, cuida de problemas relacionados à simultaneidade e garante a persistência dos dados. Tal sistema é desenvolvido tendo em mente algumas metas, que ajudam no foco do design. Uma das principais é construir abstrações, tornando o sistema fácil de usar. Outra meta é a de garantir alta performance (minimize the overheads do OS). Não é possível alcançar a perfeição em termos de performance, logo otimizações em tempo (menos instruções) e espaço (na memória ou no disco) devem ser conciliadas. Proteção também deve ser uma das metas, sendo fundamental que o OS garanta a isolation entre os programas (e também o próprio OS). Confiabilidade também deve ser levada em conta, já que uma falha no OS corresponde à uma falha em todos os programas em execução. Dependo da aplicação, um OS pode ter diferentes metas, como eficiência energética, segurança, mobilidade.
O processo é uma das abstrações mais fundamentais fornecidas pelo OS. Informalmente, um processo é um programa em execução. Ao virtualizar a CPU, o OS cria a ilusão de que múltiplas CPUs estão disponíveis para os programas, sendo possível executar vários deles simultaneamente. Para isto, o OS divide o tempo de uso da CPU (time sharing) entre os processos que a requerem. Tal ilusão vem a custo de performance, já que o recurso está sendo compartilhado. A implementação da virtualização da CPU é composta de mecanismos (mechanisms), que são métodos/protocolos em baixo nível que implementa uma parte da funcionalidade, e políticas (policies), algoritmos para alguma tomada de decisão por parte do OS (qual processo deve rodar em seguida, por exemplo).
Um processo é um programa em execução. O mesmo pode ser resumido de acordo com as diferentes peças do sistema que ele acessa ou afeta durante execução. O machine state de um processo corresponde ao que um programa consegue ler ou atualizar. Durante a execução de um programa, algumas partes do computador são essenciais. São eles: Memória (instruções armazenadas em memória, além do espaço de memória que o processo tem acesso), registradores e dispositivos de armazenamento persistentes.
A API de um processo deve possibilitar: criação, destruição, espera, controles diversos, controle de estado,
Inicialmente o código do programa e os dados estáticos necessários (exemplo variáveis inicializadas) são carregados
do disco para o address space do processo, na memória.
Em seguida, memória é alocada para o run-time stack (stack), e os valores de argumentos do programa são
inicializados na pilha.
O OS também pode alocar espaço para o heap (memória alocada dinamicamente pelo usuário) e realizar tarefas
diversas envolvendo configuração de I/O. Então, o OS deve inicializar o programa em determinado ponto (main())
e passar o controle para o processo.
Um processo pode estar em um de três estados:
- Em execução (Running): O processo está sendo executado, o processador está executando as instruções do mesmo.
- Pronto (Ready): O processo está pronto para ser executado e esperando que o OS o selecione para execução.
- Bloqueado (Blocked): O processo está com alguma pendência, que impede sua execução até a finalização de um evento (exemplo: ao requisitar I/O).
Assim como qualquer programa, o OS também possui algumas estruturas de dados chave para rastrear as informações relevantes. Por exemplo, uma lista de processos, que indica quais deles estão prontos para execução, quais estão bloqueados, além de armazenar os registradores de contexto (register context) de um processo parado, para que possam ser restaurados para os registradores físicos, quando o mesmo entrar em execução. Algumas vezes, a estrutura que armazena as informações de um processo é chamada de Bloco de Controle de Processo (Process Control Block - PCB), também chamado de process descriptor.
100%, visto que todas as instruções são para a CPU.
./homework/cpu-intro/process-run.py -l 5:100,5:100 -c -p| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:cpu | READY | 1 | |||
| 2 | RUN:cpu | READY | 1 | |||
| 3 | RUN:cpu | READY | 1 | |||
| 4 | RUN:cpu | READY | 1 | |||
| 5 | RUN:cpu | READY | 1 | |||
| 6 | DONE | RUN:cpu | 1 | |||
| 7 | DONE | RUN:cpu | 1 | |||
| 8 | DONE | RUN:cpu | 1 | |||
| 9 | DONE | RUN:cpu | 1 | |||
| 10 | DONE | RUN:cpu | 1 | |||
| Stats: | Total | Time | 10 | |||
| Stats: | CPU | Busy | 10 | (100.00%) | ||
| Stats: | IO | Busy | 0 | (0.00%) | ||
./homework/cpu-intro/process-run.py -l 4:100,1:0 -c -p| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:cpu | READY | 1 | |||
| 2 | RUN:cpu | READY | 1 | |||
| 3 | RUN:cpu | READY | 1 | |||
| 4 | RUN:cpu | READY | 1 | |||
| 5 | DONE | RUN:io | 1 | |||
| 6 | DONE | WAITING | 1 | |||
| 7 | DONE | WAITING | 1 | |||
| 8 | DONE | WAITING | 1 | |||
| 9 | DONE | WAITING | 1 | |||
| 10* | DONE | DONE | ||||
| Stats: | Total | Time | 10 | |||
| Stats: | CPU | Busy | 5 | (50.00%) | ||
| Stats: | IO | Busy | 4 | (40.00%) | ||
./homework/cpu-intro/process-run.py -l 1:0,4:100 -c -p| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:io | READY | 1 | |||
| 2 | WAITING | RUN:cpu | 1 | 1 | ||
| 3 | WAITING | RUN:cpu | 1 | 1 | ||
| 4 | WAITING | RUN:cpu | 1 | 1 | ||
| 5 | WAITING | RUN:cpu | 1 | 1 | ||
| 6* | DONE | DONE | ||||
| Stats: | Total | Time | 6 | |||
| Stats: | CPU | Busy | 5 | (83.33%) | ||
| Stats: | IO | Busy | 4 | (66.67%) | ||
./homework/cpu-intro/process-run.py -l 1:0,4:100 -c -p -S SWITCH_ON_END| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:io | READY | 1 | |||
| 2 | WAITING | READY | 1 | |||
| 3 | WAITING | READY | 1 | |||
| 4 | WAITING | READY | 1 | |||
| 5 | WAITING | READY | 1 | |||
| 6* | DONE | RUN:cpu | 1 | |||
| 7 | DONE | RUN:cpu | 1 | |||
| 8 | DONE | RUN:cpu | 1 | |||
| 9 | DONE | RUN:cpu | 1 | |||
| Stats: | Total | Time | 9 | |||
| Stats: | CPU | Busy | 5 | (55.56%) | ||
| Stats: | IO | Busy | 4 | (44.44%) | ||
./homework/cpu-intro/process-run.py -l 1:0,4:100 -c -p -S SWITCH_ON_IO| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:io | READY | 1 | |||
| 2 | WAITING | RUN:cpu | 1 | 1 | ||
| 3 | WAITING | RUN:cpu | 1 | 1 | ||
| 4 | WAITING | RUN:cpu | 1 | 1 | ||
| 5 | WAITING | RUN:cpu | 1 | 1 | ||
| 6* | DONE | DONE | ||||
| Stats: | Total | Time | 6 | |||
| Stats: | CPU | Busy | 5 | (83.33%) | ||
| Stats: | IO | Busy | 4 | (66.67%) | ||
./homework/cpu-intro/process-run.py -l 3:0,5:100,5:100,5:100 -c -p -S SWITCH_ON_IO -I IO_RUN_LATER| Time | PID: | 0 | PID: | 1 | PID: | 2 | PID: | 3 | CPU | IOs |
| 1 | RUN:io | READY | READY | READY | 1 | |||||
| 2 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 3 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 4 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 5 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 6* | READY | RUN:cpu | READY | READY | 1 | |||||
| 7 | READY | DONE | RUN:cpu | READY | 1 | |||||
| 8 | READY | DONE | RUN:cpu | READY | 1 | |||||
| 9 | READY | DONE | RUN:cpu | READY | 1 | |||||
| 10 | READY | DONE | RUN:cpu | READY | 1 | |||||
| 11 | READY | DONE | RUN:cpu | READY | 1 | |||||
| 12 | READY | DONE | DONE | RUN:cpu | 1 | |||||
| 13 | READY | DONE | DONE | RUN:cpu | 1 | |||||
| 14 | READY | DONE | DONE | RUN:cpu | 1 | |||||
| 15 | READY | DONE | DONE | RUN:cpu | 1 | |||||
| 16 | READY | DONE | DONE | RUN:cpu | 1 | |||||
| 17 | RUN:io | DONE | DONE | DONE | 1 | |||||
| 18 | WAITING | DONE | DONE | DONE | 1 | |||||
| 19 | WAITING | DONE | DONE | DONE | 1 | |||||
| 20 | WAITING | DONE | DONE | DONE | 1 | |||||
| 21 | WAITING | DONE | DONE | DONE | 1 | |||||
| 22* | RUN:io | DONE | DONE | DONE | 1 | |||||
| 23 | WAITING | DONE | DONE | DONE | 1 | |||||
| 24 | WAITING | DONE | DONE | DONE | 1 | |||||
| 25 | WAITING | DONE | DONE | DONE | 1 | |||||
| 26 | WAITING | DONE | DONE | DONE | 1 | |||||
| 27* | DONE | DONE | DONE | DONE | ||||||
| Stats: | Total | Time | 27 | |||||||
| Stats: | CPU | Busy | 18 | (66.67%) | ||||||
| Stats: | IO | Busy | 12 | (44.44%) | ||||||
./homework/cpu-intro/process-run.py -l 3:0,5:100,5:100,5:100 -c -p -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE| Time | PID: | 0 | PID: | 1 | PID: | 2 | PID: | 3 | CPU | IOs |
| 1 | RUN:io | READY | READY | READY | 1 | |||||
| 2 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 3 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 4 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 5 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 6* | RUN:io | READY | READY | READY | 1 | |||||
| 7 | WAITING | RUN:cpu | READY | READY | 1 | 1 | ||||
| 8 | WAITING | DONE | RUN:cpu | READY | 1 | 1 | ||||
| 9 | WAITING | DONE | RUN:cpu | READY | 1 | 1 | ||||
| 10 | WAITING | DONE | RUN:cpu | READY | 1 | 1 | ||||
| 11* | RUN:io | DONE | READY | READY | 1 | |||||
| 12 | WAITING | DONE | RUN:cpu | READY | 1 | 1 | ||||
| 13 | WAITING | DONE | RUN:cpu | READY | 1 | 1 | ||||
| 14 | WAITING | DONE | DONE | RUN:cpu | 1 | 1 | ||||
| 15 | WAITING | DONE | DONE | RUN:cpu | 1 | 1 | ||||
| 16* | DONE | DONE | DONE | RUN:cpu | 1 | |||||
| 17 | DONE | DONE | DONE | RUN:cpu | 1 | |||||
| 18 | DONE | DONE | DONE | RUN:cpu | 1 | |||||
| Stats: | Total | Time | 18 | |||||||
| Stats: | CPU | Busy | 18 | (100.00%) | ||||||
| Stats: | IO | Busy | 12 | (66.67%) | ||||||
./homework/cpu-intro/process-run.py -s 1 -l 3:50,3:50 -c -p| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:cpu | READY | 1 | |||
| 2 | RUN:io | READY | 1 | |||
| 3 | WAITING | RUN:cpu | 1 | 1 | ||
| 4 | WAITING | RUN:cpu | 1 | 1 | ||
| 5 | WAITING | RUN:cpu | 1 | 1 | ||
| 6 | WAITING | DONE | 1 | |||
| 7* | RUN:io | DONE | 1 | |||
| 8 | WAITING | DONE | 1 | |||
| 9 | WAITING | DONE | 1 | |||
| 10 | WAITING | DONE | 1 | |||
| 11 | WAITING | DONE | 1 | |||
| 12* | DONE | DONE | ||||
| Stats: | Total | Time | 12 | |||
| Stats: | CPU | Busy | 6 | (50.00%) | ||
| Stats: | IO | Busy | 8 | (66.67%) | ||
./homework/cpu-intro/process-run.py -s 1 -l 3:50,3:50 -c -p -I IO_RUN_IMMEDIATE -S SWITCH_ON_IO| Time | PID: | 0 | PID: | 1 | CPU | IOs |
| 1 | RUN:cpu | READY | 1 | |||
| 2 | RUN:io | READY | 1 | |||
| 3 | WAITING | RUN:cpu | 1 | 1 | ||
| 4 | WAITING | RUN:cpu | 1 | 1 | ||
| 5 | WAITING | RUN:cpu | 1 | 1 | ||
| 6 | WAITING | DONE | 1 | |||
| 7* | RUN:io | DONE | 1 | |||
| 8 | WAITING | DONE | 1 | |||
| 9 | WAITING | DONE | 1 | |||
| 10 | WAITING | DONE | 1 | |||
| 11 | WAITING | DONE | 1 | |||
| 12* | DONE | DONE | ||||
| Stats: | Total | Time | 12 | |||
| Stats: | CPU | Busy | 6 | (50.00%) | ||
| Stats: | IO | Busy | 8 | (66.67%) | ||
A chamada de sistema fork() é usada para criar um novo processo. Considerando o seguinte código:
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if(rc < 0) {
//fork failed
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
//child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else {
//parent goes down this path (main)
printf("hello, I am parent of %d (pid:%d)\n", rc, (int) getpid());
}gcc -o p1 p1.c -Wall
./p1hello world (pid:2524) hello, I am parent of 2525 (pid:2524) hello, I am child (pid:2525)
Quando este executa, imprime na tela o PID (Process Identifier). Em seguida, chama fork(), criando um
novo processo, quase idêntico ao primeiro, se iniciando a partir da instrução do fork(), mas com sua própria
cópia do address space, seus próprios registradores, seu próprio PC, etc. A diferença é que o processo que invocou
o fork() recebe o PID do processo filho, enquanto o processo filho recebe 0 como retorno do fork(). Além disso,
a saída desse programa é não determinística, pois quando um novo processo é invocado, qualquer um dos dois processos
pode passar a ser executado.
Geralmente, um processo pai deseja que um processo filho termine sua execução, antes de prosseguir com as outras
instruções. Para isso, deve-se utilizar o system call wait(), como demonstra o código a seguir:
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if(rc < 0) {
//fork failed
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
//child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else {
//parent goes down this path (main)
int rc_wait = wait(NULL);
printf("hello, I am parent of %d (rc_wait:%d) (pid:%d)\n", rc, rc_wait, (int) getpid());
}gcc -o p2 p2.c -Wall
./p2hello world (pid:2541) hello, I am child (pid:2542) hello, I am parent of 2542 (rc_wait:2542) (pid:2541)
Desta forma, a saida do programa passa a ser determinística, já que a ordem de execução será sempre igual.
A chamada de sistema exec() serve para executar um novo programa, diferente do que o invocou.
O código abaixo demonstra tal comportamento.
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if(rc < 0) {
//fork failed
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
//child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
char *myargs[3];
myargs[0] = strdup("wc");
myargs[1] = strdup("p3.c");
myargs[2] = NULL;
execvp(myargs[0], myargs);
printf("this shouldn't print out");
} else {
//parent goes down this path (main)
int rc_wait = wait(NULL);
printf("hello, I am parent of %d (rc_wait:%d) (pid:%d)\n", rc, rc_wait, (int) getpid());
}gcc -o p3 p3.c -Wall
./p3hello world (pid:2551) hello, I am child (pid:2552) 36 95 716 p3.c hello, I am parent of 2552 (rc_wait:2552) (pid:2551)
Dado um nome de um executável (e alguns argumentos), exec() carrega o código (e dados estáticos)
daquele executável e sobrescreve o segmento atual de código, bem como de dados estáticos, com os carregados.
O heap, o stack e outras partes do espaço de memória de um programa são reiniciados. Então, o OS executa aquele programa.
Logo, não cria um novo processo, mas transforma o programa corrente em um outro. Uma chamada bem sucedida de exec()
nunca retorna.
A separação de fork() e exec() é fundamental na construção de um UNIX shell, pois permite a execução de código
depois da criação de um processo e antes da execução do código do mesmo. Um comando do tipo:
prompt> wc p3.c > newfile.txt
Redireciona a saída de wc p3.c para o arquivo newfile.txt. Isto é possível pois o shell fecha o standard output
e abre o arquivo antes da chamada de exec(), e após a criação do processo com o fork(). O programa a seguir
segue o mesmo princípio.
int rc = fork();
if (rc < 0) {
fprintf(stderr, "fork failed\n"); exit(1);
} else if (rc == 0) {
close(STDOUT_FILENO);
open("./p4.output", O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU);
char *myargs[3];
myargs[0] = strdup("wc");
myargs[1] = strdup("p4.c");
myargs[2] = NULL;
execvp(myargs[0], myargs);
} else {
int rc_wait = wait(NULL);
}gcc -o p4 p4.c -Wall
./p4
cat p4.output31 63 501 p4.c
Os pipes do UNIX são implementados de forma semelhante, utilizando a chamada de sistema pipe().
Nela, a saída de um processo é conectado a um in-kernel pipe, e a entrada de outro processo é conectada
a esse mesmo pipe. Logo, a saída de um processo serve como entrada para outro.
Além dos comandos citados acima, existem diversas interfaces para comunicação com processos em sistemas UNIX.
Algumas chamadas, como kill() enviam sinais ao processo. Para que o processo reaja a tais sinais, deve-se
utilizar a chamada signal(), que suspende a execução normal na presença de determinado sinal. Para controlar
quem pode enviar sinais a um processo, os sistemas modernos utilizam o conceito de usuários. O usuário, após
fazer seu login com as devidas credenciais, ganha acesso aos recursos do sistema. Usuários geralmente podem controlar
apenas seus próprios processos.
int x = 100;
int rc = fork();
if(rc < 0) {
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
//child
printf("Old value in child: %d\n", x);
x = 10;
printf("New value in child: %d\n", x);
} else {
//parent
printf("Old value in parent: %d\n", x);
x = 20;
printf("New value in parent: %d\n", x);
}| Old | x | value | in | parent: | 100 |
| New | x | value | in | parent: | 20 |
| Old | x | value | in | child: | 100 |
| New | x | value | in | child: | 10 |
int file = open("./cpu-api-02.output", O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU);
assert(file > -1);
int rc = fork();
int counter = 0;
if(rc < 0) {
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
//child
counter = write(file, "print from child\n", 17);
assert(counter == 17);
close(file);
} else {
//parent
counter = write(file, "print from parent\n", 18);
assert(counter == 18);
close(file);
}cat ./cpu-api-02.output| from | parent | |
| from | child |
int rc = fork();
if (rc < 0) {
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
//execl("/bin/ls", "ls", NULL);
//execle("/bin/ls", "ls", NULL, NULL);
//execlp("/bin/ls", "ls", NULL);
char *args[] = {"ls", NULL};
//execv("/bin/ls", args);
//execvp("/bin/ls", args);
execvpe("/bin/ls", args, NULL);
} else {
wait(NULL);
}| README.org |
| common.h |
| common_threads.h |
| cpu |
| cpu-api-01.c |
| cpu-api-02.c |
| cpu-api-02.output |
| cpu-api-03 |
| cpu-api-03.c |
| cpu.c |
| homework |
| io |
| io.c |
| mem |
| mem.c |
| newfile.txt |
| p1 |
| p1.c |
| p2 |
| p2.c |
| p3 |
| p3.c |
| p4 |
| p4.c |
| p4.output |
| thread |
| thread.c |
int rc = fork();
int fpid = -1;
if (rc < 0) {
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
fpid = wait(NULL);
printf("This first. By the way, wait (in child) returned this: %d\n", fpid);
} else {
//fpid = wait(NULL);
printf("Then this. In parent, wait returned this: %d\n", fpid);
}| Then this. In parent | wait returned this: -1 |
| This first. By the way | wait (in child) returned this: -1 |
int rc = fork();
if (rc < 0) {
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
printf("Child\n");
} else {
waitpid(rc, NULL, NULL);
printf("Parent");
}| Child |
| Parent |
int rc = fork();
if (rc < 0) {
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) {
close(STDOUT_FILENO);
open();
printf("Wow, how this even worked?");
} else {
int pid = wait(NULL);
printf("Wait: %d\n", pid);
}Wait: 3350
int rc1, rc2, pipefd[2];
char buffer[2];
if(pipe(pipefd) == -1) {
fprintf(stderr, "pipe failed\n");
exit(1);
}
rc1 = fork();
if (rc1 < 0) {
fprintf(stderr, "fork 1 failed\n");
exit(1);
} else if (rc1 == 0) {
close(pipefd[0]);
write(pipefd[1], "42", 2);
} else {
wait(NULL);
rc2 = fork();
if (rc2 < 0) {
fprintf(stderr, "fork 2 failed\n");
exit(1);
} else if (rc2 == 0) {
close(pipefd[1]);
read(pipefd[0], buffer, 2);
close(pipefd[0]);
printf("Hey %d, what is the answer to life the universe and everything?\n%s", (int) getpid(), buffer);
} else {
wait(NULL);
}
}| Hey | 160, | what | is | the | answer | to | life | the | universe | and | everything? |
| 42 |
Para virtualizar a CPU, o OS deve gerenciar o compartilhamento da CPU com os vários processos em execução. Logo, cada processo roda por uma fração de tempo. Este processo é conhecido por time sharing. Entretanto, algumas dificuldades surgem, pois é necessário garantir uma alta performance enquanto se mantém o controle do acesso.
Inicialmente, a execução direta significa que um programa roda diretamente na CPU. Quando o OS deseja executar algum programa, ele cria a entrada do processo na process list, aloca a memória necessária, carrega o programa para a memória, identifica o ponto de entrada do programa e o o inicia a partir dali. Com isso, vários probemas são originados, levando à parte do “limitada” no nome.
Algumas operações devem ser restritas aos processos. Um exemplo é a requisição de I/O, que se fosse liberada, poderia levar a um processo lendo ou escrevendo em todo o disco, podendo sobrescrever inclusive o sistema operacional, danificando a máquina. Assim, um novo modo de processador é introduzido, o user mode. Nesse modo, o código executado possui limitações no que pode fazer. No caso da tentativa de requisição de I/O, o processador levantaria uma exceção, retornando o controle ao OS, que provavelmente eliminaria o processo. Em contrapartida, existe o kernel mode, no qual o OS roda. Nesse modo, o código executado pode fazer o que desejar. Então, como um processo de usuário poderia realizar operações privilegiadas? A técnica desenvolvida para solucionar esse problema foi a criação das system calls.
Para executar uma system call, o programa deve executar uma instrução trap especial. Esta instrução simultaneamente pula para o kernel e levanta o nível de privilégio para kernel mode. Assim, o sistema consegue realizar as operações requisitadas e após finalização, retornar o controle para o programa, ao mesmo tempo em que abaixa o nível de privilégio para user mode, através de uma instrução especial return-from-trap.
Desta forma, o OS deve manter controle de algumas informações do processo atual, para que possa retornar a ele uma vez finalizadas as operações. No x86, o processador irá empilhar o program counter, flags e alguns outros registradores em um kernel stack por processo. O return-from-trap irá desempilhar esses valores do stack e continuar a execução da aplicação do usuário.
O kernel deve tomar cuidado com o código executado dentro de uma trap, evitando que o processo que a invocou obtenha controle sobre o sistema, por exemplo. Para isso, o kernel configura uma trap table em tempo de boot. Quando a máquina se inicia (em kernel mode), o OS define qual código executar para cada evento excepcional. O OS informa o hardware a localização desses trap handlers, os executando automaticamente na presença das devidas interrupções.
Cada system call possui um system-call number, que deve ser apresentada pelo processo requisitor, evitando que o mesmo forneça um endereço do trecho de código a ser executado.
O OS não deixa de ser um programa como qualquer outro, logo também deve compartilhar o tempo de uso da CPU. Como fazer então, para que o OS execute algo se o mesmo não está rodando na CPU? Como retomar o controle da CPU?
Uma das estratégias adotadas é a cooperativa. Nela, o sistema confia que o processo irá se comportar da forma devida, passando o controle para o OS periodicamente caso esteja demorando demais em sua execução. Esta transferência ocorre quando uma system call é invocada, ou alguma operação ilegal é executada. Existe uma syscall que apenas transfere o controle. É a chamada yield. Obviamente, esta estratégia não é a ideal, pois um loop infinito acarretaria no bloqueio do sistema.
Para solucionar isto, uma interrupção por tempo é introduzida, a qual retorna o controle ao OS (ao interrupt handler, no caso) a cada alguns milisegundos, permitindo que o sistema rode o que desejar. Assim como na chamada de uma trap, tal interrupção deve armazenar as informações de contexto do programa, para que se retome a execução posteriormente.
Recuperado o controle, o OS deve decidir qual processo rodar em seguida. Isto é decidido pelo scheduler. Caso decida trocar de processo, um pedaço de código em baixo-nível chamado context switch é executado. Nele, o OS deve salvar alguns valores de registradores do processo atualmente em execução (em um kernel stack, por exemplo) e restaurar os do processo a ser executado.
Para salvar o contexto do processo corrente, o OS irá salvar os registradores de propósito geral, o PC, e o kernel stack pointer do processo corrente. Tendo salvo tais informações, o kernel stack do novo processo é carregado para essas posições, mudando o contexto. Assim, o sistema executa uma instrução return-from-trap, fazendo que o outro processo passe a executar.
O sistema deve se preocupar com interrupções (e trap handlers) durante interrupções. Acionada uma interrupção, o OS irá realizar algum processamento. Durante esse tempo, novas interrupções podem surgir. Uma estratégia para evitar esse cenário é desabilitar as interrupções nesse período. Deve-se tomar cuidado para que interrupções também não sejam perdidas.
#define N 1000
struct timeval start_time, end_time;
int i;
long elapsed_time;
gettimeofday(&start_time, NULL);
for(i = 1; i <= N; i++){
read(0, NULL, 0);
}
gettimeofday(&end_time, NULL);
elapsed_time = end_time.tv_usec - start_time.tv_usec;
printf("Start: %ldms | End: %ldms | Elapsed: %ldms | N: %d | Average Cost %ldms",
start_time.tv_usec, end_time.tv_usec, elapsed_time, N,
(elapsed_time/N));| Start: 654766ms | End: 656164ms | Elapsed: 1398ms | N: 1000 | Average Cost 1ms |
#define N 1000
struct timeval start_time, end_time;
long elapsed_time;
int i, fd1[2], fd2[2], rc1, rc2;
rc1 = fork();
if ((pipe(fd1) == -1) || (pipe(fd2) == -1)) {
fprintf(stderr, "pipe failed\n");
exit(1);
}
if (rc1 < 0) {
fprintf(stderr, "fork 1 failed\n");
exit(1);
} else if (rc1 == 0) {
for(i = 1; i <= N; i++){
close(fd2[0]);
close(fd1[1]);
read(fd1[0], NULL, 0);
write(fd2[1], NULL, 0);
}
} else {
rc2 = fork();
if (rc2 < 0) {
fprintf(stderr, "fork 2 failed\n");
exit(1);
} else if (rc2 == 0) {
for(i = 1; i <= N; i++){
close(fd2[1]);
close(fd1[0]);
read(fd2[0], NULL, 0);
write(fd1[1], NULL, 0);
}
} else {
gettimeofday(&start_time, NULL);
wait(NULL);
gettimeofday(&end_time, NULL);
elapsed_time = end_time.tv_usec - start_time.tv_usec;
close(fd1);
close(fd2);
printf("Start: %ldms | End: %ldms | Elapsed: %ldms | N: %d | Average Cost %ldms",
start_time.tv_usec, end_time.tv_usec, elapsed_time, N,
(elapsed_time/N));
}
}| Start: 478966ms | End: 482957ms | Elapsed: 3991ms | N: 1000 | Average Cost 3ms |
Os mecanismos de execução de um processo foram estudados nas seções anteriores. Resta agora compreender como o sistema determina em alto nível quais processos executarão, ou seja as políticas adotadas por ele. Logo, serão estudadas uma série de políticas de agendamento (scheduling policies) desenvolvidas ao longo dos anos.
Para simplificar a política apresentada, algumas premissas sobre o processo em execução são feitas. São elas:
- Cada tarefa é executada pela mesma quantidade de tempo
- Todas as tarefas são requisitadas ao mesmo tempo
- Após iniciados, cada tarefa executa até que esteja completa
- Todos as tarefas utilizam apenas a CPU
- O tempo de execução de cada tarefa é conhecido
Ao longo do capítulo, essas premissas são desfeitas, permitindo a aproximação de uma situação real.
Além das premissas sobre a carga de trabalho, é necessário estabelecer scheduling metrics. Inicialmente, será utilizado apenas o turnaround time, definido pelo tempo em que cada job termina sua execução menos o tempo em que chegou no sistema. Pela premissa 2, este tempo se iguala ao tempo de conclusão (em um primeiro momento). Vale notar que tal métrica busca medir a performance do scheduler.
Algoritmo simples, em que cada processo executa até que seja finalizado, por ordem de chegada. Caso um processo demore bastante tempo a finalizar, outros que chegaram logo após ficarão em espera. Assim, o turnaround time aumentará consideravelmente. Este problema é conhecido como efeito convoy.
Por executar os menores trabalhos primeiro, o turnaround time diminui consideravelmente (em situações na qual a premissa 2 ainda seja seguida). Caso os processos cheguem ao sistema em tempos diferentes, é possível que uma tarefa longa esteja em execução, colocando os outros em espera, aumentando o turnaround.
Retirando a premissa 3, é possível solucionar o problema acima, ao interromper a execução de um processo longo para que outros mais rápidos executem. O algoritmo STCF adiciona preempção ao SJF. Assim, quando um job chega ao sistema, o mesmo determina qual dos trabalhos possuem menos tempo de execução restante. Possui ótimo turnaround time. Não muito boa em tempo de resposta.
Sabendo o tempo de finalização dos trabalhos, e considerando que apenas a CPU seja utilizada e a única métrica disponível seja a turnaround, STCF aparece como uma ótima política. Entretanto, em sistemas interativos, é necessária a criação de uma nova métrica, o tempo de resposta (response time). O tempo de resposta corresponde ao período entre a chegada de um processo ao sistema e a primeira execução do mesmo.
Ao invés de rodar os processos até a conclusão, o algoritmo RR executa o trabalho por uma fatia de tempo (time slice, também chamada de scheduling quantum), trocando em seguida para a próxima tarefa na fila, e assim repetidamente. Assim, RR por vezes é chamado de time-slicing. Vale notar que uma fatia do tempo deve ser um múltiplo do período de interrupção por timer, sendo o tempo de resposta diretamente proporcional à fatia escolhida para cada processo. Deve-se levar em conta que valores muito pequenos para a fatia de tempo podem fazer com que a troca de contexto demore mais que a execução do processo em si, diminuindo a responsividade do sistema.
Apesar de apresentar bons resultados em tempo de resposta, acaba ficando para trás em turnaround time. Isto porque cada processo é alongado ao máximo, executando vários de uma única vez. Qualquer política que seja justa (fair), dividindo recursos ao longo do tempo com vários processos tende a apresentar resultados ruins em turnaround time. O oposto também é verdadeiro, já que monopolizar recursos tende a melhorar o turnaround time.
Na presença de requisições de I/O, o sistema deve ajustar a escala dos processos de acordo com a conclusão da requisição. Supondo um escalonador STCF nessas condições, não é vantajoso que um processo seja executado por completo, antes que outro entre em execução, visto que durante as requisições, o mesmo se encontrará bloqueado, e consequentemente, não estará utilizando da CPU. Então, cada sub-tarefa do processo (entre as requisições) é tradada separadamente, no que diz respeito à alocação do processo na fila. Assim, o sistema operacional considera finalizado o trabalho durante a requisição de I/O, executando outro enquanto isso.
./homework/cpu-sched/scheduler.py -p SJF -j 3 -l 200,200,200 -c
./homework/cpu-sched/scheduler.py -p FIFO -j 3 -l 200,200,200 -c
./homework/cpu-sched/scheduler.py -p SJF -j 3 -l 100,200,300 -c
./homework/cpu-sched/scheduler.py -p FIFO -j 3 -l 100,200,300 -c
./homework/cpu-sched/scheduler.py -p RR -j 3 -l 10,20,30 -q 1 -c
Quando as tarefas estão em ordem crescente de tamanho
./homework/cpu-sched/scheduler.py -p RR -j 3 -l 10,10,10 -q 10 -c
./homework/cpu-sched/scheduler.py -p SJF -j 3 -l 10,10,10 -c
./homework/cpu-sched/scheduler.py -p SJF -j 3 -l 10,10,10 -c
./homework/cpu-sched/scheduler.py -p SJF -j 3 -l 400,400,400 -c
Tempo de resposta aumenta. Para o último, (n - 1) quantas serão executadas antes que a enésima comece.
Logo, o tempo de resposta do último será
Nesta seção, é apresentado o scheduler MLFQ (Multi-Level Feedback Queue), descrito por Corbato em 1962. Tal algoritmo rendeu a ele o Prêmio Turing. Tal scheduler visa otimizar o turnaround time. Como visto anteriormente, isto é geralmente alcançado ao rodar primeiro programas que terminem primeiro. Entretanto, não se sabe a duração de execução desses processos. Em segundo lugar, busca deixar o sistema responsivo a interação dos usuários, minimizando, assim, o tempo de resposta.
Existem várias implementações do MLFQ. A maioria delas compartilham similaridades. A MLFQ descrita a seguir possui queues (filas) distintas, cada uma com um nível de prioridade. Em qualquer momento, um job que está pronto (ready) está localizado em uma única fila. Processos com prioridades maiores vão rodar, em detrimento dos com prioridades menores. Caso tenham a mesma prioridade, rodam em Round Robin. Logo, cabe ao MLFQ designar as prioridades para cada trabalho. Esta prioridade é variável, de acordo com o comportamento observado pelo OS.
Levando em conta que o workload (carga de trabalho) consiste em uma mistura de jobs interativos (e de execução curta) e jobs longos (com grande demanda de CPU), algumas regras são adicionadas numa tentativa de melhorar o desempenho:
- Ao entrar no sistema, um processo é colocado na fila de maior prioridade.
- Caso um processo utilize toda a fatia de tempo enquanto roda, sua prioridade é reduzida.
- Caso um processo entregue o controle da CPU antes que sua fatia de tempo se esgote, ele continua na mesma fila.
Assim, mesmo que o sistema não saiba se o processo é demorado ou não, ele assume que seja curto, colocando todos na maior prioridade no início. Se estiver certo, o processo continuará nas filas de alta prioridade, sendo assim executado mais rapidamente. Em caso de palpite incorreto, o processo acabará caindo nas filas de baixa prioridade, sendo executado depois. Nesse sentido, o MLFQ se aproxima do SJF. Em jobs com requisição de I/O, o processo entrega o controle da CPU antes do tempo, assim não pode ser penalizado, logo continuando na mesma fila.
Entretanto, tal estratégia apresenta problemas. O primeiro, starvation, descreve a situação em que existem vários processos interativos no sistema, que combinados ocupam todo o tempo de CPU. Dessa forma, os processos de baixa prioridade não são executados. O segundo envolve um processo que game the schedule, ou seja, que monopoliza o tempo de CPU ao fazer uma requisição de I/O logo antes do fim da fatia de tempo. Por último, um programa pode mudar de comportamento ao longo do tempo, visto que da forma como está, não é possível que um processo aumente sua prioridade.
Buscando resolver o problema de starvation (e o da mudança de comportamentos ao longo do tempo), decide-se periodicamente impulsionar todos os processos, os colocando na fila de maior prioridade a cada período S. Esse tempo S é algo arbitrário, não sendo possível determinar um valor que atenda perfeitamente a todas as situações.
Para prevenir o gaming of the scheduler, altera-se a regra que mantém um processo na mesma fila caso sua execução devolva o controle antes que acabe a fatia de tempo para uma que contabiliza o tempo de execução do processo. Caso a tarefa demore mais que a quota permitida para cada fila, sua prioridade é diminuida, não levando em consideração quantas vezes o controle foi devolvido para o OS.
Um outro problema desse scheduler é pertinente às configurações de cada parâmetro. Número de filas, fatia de tempo por fila, periodicidade do impulso de prioridade, etc. Em algumas implementações, cada fila possui fatias de tempo diferentes. É possível também que outras formas de priorização sejam utilizadas, como formulação matemática, de acordo o uso da CPU, por exemplo.
1- Se prioridade de A for maior que a de B, A roda e B não 2- Se prioridade de A for igual a de B, rodam em RR, utilizando a fatia de tempo (quanta) da fila 3- Quando um processo entra no sistema, é colocado na fila de maior prioridade 4- Quando um processo usa uma fração de tempo definida (independente de quantas vezes ele devolveu o controle), o mesmo tem sua prioridade reduzida 5- Após um período de tempo S, todos os processos são movidos para a fila superior
Nesta seção é abordado um scheduler conhecido como proportional-share (ou fair-share). Ao invés de se otimizar turnaround time ou response time, este scheduler visa garantir que cada job recebe uma certa porcentagem de uso da CPU. Um exemplo de scheduler por proportional-share é criado por Waldspurger e Weihl, conhecido como lottery scheduling. Nele, periodicamente é feito um sorteio para determinar qual processo será executado a seguir. Processos que deveriam rodar mais frequentemente possuem mais chances de ganhar o sorteio.
Cada processo recebe um número de tickets de acordo com o uso de CPU a ser destinado a ele. Então, um número aleatório é sorteado (entre todos os valores de tickets disponíveis). O processo com o ticket sorteado executa até o próximo sorteio.
Scheduling por loteria fornecem mecanismos para manipular tickets de várias formas. Um desses mecanismos é o de ticket currency. Nele, um usuário pode alocar quantos tickets quiser para cada processo, mesmo que este valor não seja o determinado pelo sistema. Supondo que dois usuários recebam 100 tickets, por exemplo, O primeiro usuário pode rodar dois processos alocando 500 tickets para cada, enquanto o segundo pode rodar 1 processo com 10 tickets. Cabe ao OS converter os tickets utilizados por cada processo em uma moeda global.
Outro mecanismo é o de transferência de tickets, que corresponde a um processo entregar temporariamente seus tickets para outro (server e client, por exemplo). Por fim, existe a inflação de ticket, útil em alguns cenários. Nesse caso, um processo consegue aumentar ou diminuir seu próprio número de tickets (utilizado em ambientes onde haja um grupo de processos com confiança mútua).
Para implementação, é necessário um gerador de números aleatórios, uma estrutura de dados para registrar os processos (uma lista) e o número total de tickets. Um valor aleatório é escolhido, e a lista é percorrida. Em cada elemento, o número de tickets do mesmo é somado a um contador (inicialmente 0). Depois da soma, faz-se a comparação entre o valor do contador com o gerado. Caso o contador tenha ultrapassado, o processo em questão é escolhido. Caso não, passa-se para o outro elemento da lista.
int global_tickets = 0;
struct node_t {
int car;
struct node_t *cdr;
};
struct node_t *list = NULL;
void cons(int car) {
struct node_t *tmp = malloc(sizeof(struct node_t));
assert(tmp != NULL);
tmp->car = car;
tmp->cdr = list;
list = tmp;
global_tickets += car;
}
void print_list() {
struct node_t *curr = list;
printf("'List: ");
while (curr) {
printf("[%d]", curr->car);
curr = curr->cdr;
}
printf("\n");
}
int main(int argc, char* argv[]) {
if (argc != 3) {
fprintf(stderr, "usage: lottery <seed> <loops>\n");
exit(1);
}
int seed = atoi(argv[1]);
int loops = atoi(argv[2]);
srandom(seed);
cons(50); cons(100); cons(25);
int i, counter, winner;
struct node_t *current;
for (i = 0; i < loops; i++) {
counter = 0;
winner = random() % global_tickets;
current = list;
while (current) {
counter = counter + current->car;
if (counter > winner) break;
current = current->cdr;
}
print_list();
printf("winner: %d %d\n\n", winner, current->car);
}
return 0;
}'List: [25][100][50] winner: 15 25 'List: [25][100][50] winner: 1 25 'List: [25][100][50] winner: 154 50 'List: [25][100][50] winner: 59 100 'List: [25][100][50] winner: 156 50
Supondo dois jobs, com o mesmo tempo de execução, e com o mesmo número de tickets. Nesse cenário, deseja-se que ambos concluam quase ao mesmo tempo. Para medir isto, uma métrica chamada unfairness metric U é criada. Nela, o tempo em que o primeiro trabalho se encerra é dividido pelo tempo do segundo. Quanto mais próximo de um, melhor. Nessas condições, observa-se que o U dos processos se aproxima de um a medida que o tamanho dos processos aumenta.
Um problema ainda não abordado é a da alocação dos tickets por processo. Como o sistema deve distribuir os tickets entre os processos existentes? É possível que ele apenas deixe para o usuário a alocação dos tickets, distribuindo para este um número determinado. Mas isto ainda não é a solução desejada.
Apesar de apresentar um scheduler simples e aproximadamente correto, a aleatoriedade pode atrapalhar nas proporções corretas, principalmente em jobs curtos. Visando solucionar este problema, Waldspurger inventou o stride scheduling, um scheduler fair-share determinístico. Nele, cada processo possui um stride e um pass. Para determinar o stride de cada processo, divide-se um número grande pelo número de tickets de cada um. Já o pass corresponde a um counter, inicialmente em zero, e que é incrementado toda vez que um processo roda. O valor adicionado é o do stride do processo. O algoritmo sempre seleciona o processo com menor pass para execução. Ao final do ciclo de scheduling, as proporções exatas de execução serão atingidas. Entretanto, caso um novo processo entre no meio do ciclo, ele monopolizará a CPU, visto que o valor de pass dele será bem inferior ao dos outros.
No CFS, o scheduler não se baseia em uma fração fixa do tempo, e sim por uma técnica de contagem conhecida como virtual runtime (vruntime). A medida que um processo executa, ele acumula vruntime. No caso mais simples, o vruntime de todos os processos incrementam em valores iguais, relativos ao tempo físico. Quando uma decisão de schedule acontece, o processo com menor vruntime acumulado executa a seguir.
Assim, é necessário balancear o tempo de troca entre os processos. Se este valor for pequeno, fairness é atingido, a um custo de performance (troca de contexto frequente), e vice-versa. Para resolver tal problema, o CFS utiliza alguns parâmetros de controle. O primeiro, sched_latency determina quanto tempo um processo executa até uma troca. Nesse período, o CFS garante a fairness ao dividir esse tempo pelo número de processos. Assim, todos executam. Para evitar que o time slice seja reduzido a ponto de causar um overhead de scheduling por context switch, o CFS utiliza o parâmetro min_granularity, que limita o time slice mínimo possível.
Também é possível que processos recebam prioridades. Utiliza, para isso, de um mecanismo UNIX chamado nível nice, que vai de -20 a +19. O CFS utiliza do valor nice para mapear o processo a um peso, por uma tabela. Assim, a fatia de tempo de um processo será definida pela multiplicação do sched_latency pela fração do peso do processo sobre a somatória dos pesos de todos os processos. O total de vruntime acumulado por um processo também deve ser proporcional a esse peso, senão um processo com prioridade, que executou durante um periodo maior, ficará esperando por um bom tempo.
Um dos maiores focos do CFS é a eficiência. Um dos elementos que deve ser otimizado é a busca pelo próximo processo a rodar. Sistemas modernos são compostos de centenas de processos, e estruturas como listas não escalonam bem o suficiente. Então, o CFS utiliza-se de uma red-black tree para armazenar os processos. Apenas processos em execução ou prontos para são armazenados. Na árvore, os processos são ordenados por vruntime, e as operações são logarítmicas.
Caso um processo entre em espera, quando voltar, seu vruntime será bem inferior ao dos outros processos, assim monopolizando o uso da CPU. Pra evitar que isso ocorra, o CFS altera o vruntime de uma tarefa quando volta para a árvore. Ela recebe um vruntime equivalente ao menor valor encontrado na árvore.
./homework/cpu-sched-lottery/lottery.py -s 1 -j 3 -c
./homework/cpu-sched-lottery/lottery.py -l 10:1,10:100 -c
Com a chegada dos sistemas com multiprocessadores, o problema de scheduling fica mais complicado.
Em cada CPU, existem hierarquias de caches de hardware, responsáveis por armazenar cópias de dados populares coletados da memória principal, para serem reutilizados futuramente. Caches são baseados no conceito de localidade. Existindo dois tipos: localidade temporal e localidade espacial. A localidade temporal assume que quando uma parte de informação é acessada, é provavel que seja acessada de novo em um futuro próximo (variáveis e instruções em um loop, por exemplo). A localidade espacial assume que quando uma parte de informação é acessada no endereço x, é provavel que acesse, também, os endereços próximos de x (percorrendo um array, por exemplo).
Quando múltiplos processadores são envolvidos, aparece um problema chamado de coerência de cache. Como cada processador possui seu próprio sistema de cache, é possível que uma informação que tenha sido atualizada por algum processo e ainda não tenha sido escrita na memória principal apresente incongruência se outro processador tentar acessá-la. Para solucionar, o hardware deve monitorar os acessos a memória. Uma forma é através do barramento, pelo qual cada cache presta atenção às atualizações na memória, modificando o valor lido ou escrito caso tenha uma versão mais atualizada ou se atualiza.
Além disso, quando processos são feitos para executar em múltiplos processadores, deve-se garantir que o acesso a estruturas entre as CPU não seja compartilhado, evitando que dois processadores escrevam ou leiam valores incorretos. Como solução, algumas rotinas devem ser corrigidas via locking.
É vantajoso rodar um processo na mesma CPU, visto que durante a execução, várias informações de estado ficam salvas no cache daquela CPU.
Fila única, na qual todos os processos se encontram. Cada processador utiliza algum algoritmo para decidir o proximo processo. Entretanto possui alguns problemas. O primeiro é a falta de escalabilidade, já que o usuário deve ter programado vários locks nos códigos, restringindo o processo disponível para cada processador. Outro problema é o de afinidade de cache. Já que cada processador apenas escolhe o próximo processo da fila, é possível que a tarefa em questão fique indo de CPU a CPU, contrariando a afinidade de cache. Assim, a maioria dos schedulers SQMS incluem alguma forma de mecanismo de afinidade, garantindo que um processo continue a executar na mesma CPU, se possível. Assim, SQMS possui suas vantagens e desvantagens: simples de implementar, a partir de um single-CPU scheduler, mas não escalona bem (por causa das overheads de sincronização), e não preserva afinidade de cache.
E MQMS, existem várias filas. Cada fila seguirá sua disciplina de scheduling, organizando os processos de forma independente. Assim, evita problemas de compartilhamento de informações e sincronização encontrados no SQMS. Alguns problemas surgem: O primeiro referente ao desbalanceamento da carga, visto que os processos em uma CPU podem encerrar antes dos processos de uma outra, desbalanceando a carga e a fatia de tempo das tarefas. Assim, é necessário migrar processos de uma CPU para outra. Uma estratégia comum é a de work stealing. Nela, uma fila que está com poucos processos irá verificar as outras filas. Caso tenha menos carga que ela, o processo é migrado. Claro que pode existir um overhead se essa verificação for constante, ou um desbalanceamento de carga, se demorada demais.
Não há senso comum em relação a um scheduler multiprocessador. Com o tempo, três alternativas surgiram: o O(1), o CFS e o BFS. O(1) e CFS usam múltiplas filas, enquanto o BFS utiliza apenas uma. O O(1) é um scheduler baseado em prioridade (semelhante ao MLFQ), enquanto o CFS adota uma abordagem de compartilhamento proporcional determinístico.
./homework/cpu-sched-multi/multi.py -n 1 -L a:30:200 -c -t
./homework/cpu-sched-multi/multi.py -n 1 -L a:30:200 -M 300 -c -t
./homework/cpu-sched-multi/multi.py -n 1 -L a:30:200 -M 300 -c -t -T
./homework/cpu-sched-multi/multi.py -n 1 -L a:30:200 -M 300 -c -t -T -C
./homework/cpu-sched-multi/multi.py -n 2 -L a:100:100,b:100:50,c:100:50 -c