Processos do Inferno

O Sistema inferno possui uma variedade de tipos de processos. O primeiro é o tipo de processo que executa um código Dis interpretado. Para esses processos, a máquina virtual tem controle total sobre o processo até mesmo sobre a execução de instruções individuais. Isso torna as operações, como a troca de contexto e a determinação do final de uma fatia de tempo, muito simples.

Em muitas plataformas, o Inferno inclui um compilador just-in-time, que traduz o código Dis para o conjunto de instruções nativas da máquina. Essa facilidade cria uma variação nos processos de usuário, a qual executa o código nativo da máquina. Como o interpretador da máquina virtual não tem controle total sobre esses módulos compilados para o código nativo, os detalhes de seu gerenciamento de processos são necessariamente diferentes.

Por fim, existe os processos do kernel. Estes são denominados kprocs por causa da função utilizada para cria-los e são threads de controle independentes dentro do kernel. No inferno hospedado, eles são threads gerenciadas pelo SO hospedeiro. Enquanto o sistema funciona, outros são criados, conforme necessário.

Todos os processos no inferno são considerados mais threads e são executados compartilhando um espaço comum de memória. Em consequencia. O conjunto de todos os processos do kernel compõe um único programa multithread. Isso só é possível graças a natureza da linguagem limbo e do projeto da máquina virtual Dis que evitam que programas tenham acesso irrestrito entre si. Um processo pode em alguns casos fazer parte de mais de uma fila nas estruturas de processos.

Estados de Processos

Como existem duas classes gerais de processos no Inferno (de kernel e de usuário), temos dois diferentes conjuntos de estados de processos. Se tratando de processos de kernel o inferno hospedado direciona os seus assuntos principais para serem tratados pelo SO hospedeiro, já o inferno nativo mantém seu próprio conjunto de estados de processos para os processos do kernel, porque é responsável pelo gerenciamento destes.

Processos do Kernel

Para os kprocs que executam o interpretador de máquina virtual, além do gerenciamento de processos usual há um nível de escalonamento adicional onde cada um deles é capaz de executar processos de usuário. Para executar os processos de usuário, um código em libinterp trabalha similar a uma CPU. Existe um único conjunto de registradores que apenas um processo pode utilizar por vez. Processos que não utilizam interpretador, quando estão prestes a fazer uma operação que pode gerar um bloqueio, chama a função release() para sinalizar que outro kproc pode utilizar o interpretador e quando necessitar novamente do interpretador chama a função acquire() para pedir controle dele.

Caso o interpretador bloqueie em nome de algum processo de usuário, então é necessário executar outro interpretador. Após o processo bloqueado despertar, precisa ser executado novamente de onde parou. Dessa maneira, os kprocs de interpretador pode estar nos seguintes estados:

Figura 1 Máquina de Estados de Processos do kernel no Inferno Hospedado

Em execução: Há apenas um kproc interpretador por vez que possui controle sobre o interpretador. Ele é identificado como no estado Em Execução por uma variável global, que aponta para sua entrada na tabela de processos.
Bloqueado: Um kproc bloqueado é o que está esperando por algum evento.
Pronto: Esse estado representa o caso em que um kproc interpretador foi despertado de um estado bloqueado e, assim, tem um processo do usuário ligado a ele por estar esperando para obter o interpretador.
Ocioso: É o estado que identifica um kproc interpretador que não possui processo do usuário associado e, portanto, esta disponível se a corrente bloquear.

Processos de Usuário

No inferno, o conjunto de estados dos processos de usuário é definido em include/interp.h. A máquina de estados principal para esses processos está ilustrada na figura a baixo. Dois estados foram omitidos afim de simplificação, Depura e Interrompido.

Figura 2 Máquina de Estados Dos Processos de Usuário

Alterna: É utilizado quando o processo executa uma instrução alt da linguagem Limbo. Ele permite a um processo esperar por diversos descritores de arquivos de entrada ou saída simultaneamente.
Envia e Recebe: Os estados Envia e Recebe são utilizados com canais de comunicação. A função é a de enviar ou receber canais únicos. Esses três (Envia, Alterna, Recebe) são tipos de estados bloqueado.
Depura: Um processo é enviado para esse estado quando está sob o controle de um depurador.
Pronto: Processos elegíveis para serem interpretados estão no estado Pronto. Se um processo estiver nessa lista, estará também numa lista encadeada de processos prontos.
Libera: Quando a função release() é chamada, um processo é posicionado em Libera. Nesse estado um processo está liberando seu pedido de CPU virtual.
Saída: Após o termino de um processo, ele é posicionado no estado de Saída, onde será realizada o processo de limpeza.
Interrompido: Utilizamos este estado para marcar um processo que saiu enquanto estava sob o controle de um depurador ou quando um processo termina como resultado da maioria das condições de erro. O processo é posicionado para que o depurador possa analisar a causa de sua saída.

Estruturas de Dados de Processos

Por existirem diversos tipos de processos dentro do inferno e por suas otimizações, a tabela de processos acaba por se tornar mais complexa do que o comum encontrados em sistemas UNIX.

Estrutura e tabela de processos do kernel

A estrutura de dados dos processos de kernel é a estrutura Procs definida em emu/port/dat.h:

struct Procs
{
	Lock    l;
	Proc*   head;
	Proc*   tail;
};

Esta estrutura define uma lista duplamente encadeada de todos os processos do kernel. Existe apenas uma única instância dessa estrutura definida como variavel global procs. O membro l da estrutura é uma variável para garantir exclusão mútua quando diversas threads tentam acessar a lista simultaneamente. Os ponteiros head e tail apontam para o início e fim da fila, quando ela não está vazia. Cada uma de suas instâncias são descritas por uma estrutura Proc também definida em emu/port/dat.h. A fila duplamente encadeada com os kprocs é ilustrada abaixo.

Figura 3 Lista de Processos do Kernel

A estrutura Proc é a entrada da tabela de processos para processos do kernel e é definido como se segue. O membro type se o processo é um kproc interpretador ou não. O campo text pode ser usado para identificar o processo. A lista duplamente encadeada de todos os processo de kernel é definida pelos membros next e prev.

struct Proc{
	int type;       /* interpreter or not */
	char    text[KNAMELEN];
	Proc*   qnext;      /* list of processes waiting on a Qlock */
	long    pid;
	Proc*   next;       /* list of created processes */
	Proc*   prev;
	Lock    rlock;  /* sync between sleep/swiproc for r */
	Rendez* r;      /* rendezvous point slept on */
	Rendez  sleep;      /* place to sleep */
	int     killed;     /* by swiproc */
	int swipend;    /* software interrupt pending for Prog */
	int syscall;    /* set true under sysio for interruptable syscalls */
	int intwait;    /* spin wait for note to turn up */
	int sigid;      /* handle used for signal/note/exception */
	Lock    sysio;      /* note handler lock */
	char    genbuf[128];    /* buffer used e.g. for last name element from namec */
	int nerr;       /* error stack SP */
	osjmpbuf    estack[NERR];   /* vector of error jump labels */
	char*   kstack;
	void    (*func)(void*); /* saved trampoline pointer for kproc */
	void*   arg;        /* arg for invoked kproc function */
	void*   iprog;      /* work for Prog after release */
	void*   prog;       /* fake prog for slaves eg. exportfs */
	Osenv*  env;        /* effective operating system environment */
	Osenv   defenv;     /* default env for slaves with no prog */
	osjmpbuf    privstack;  /* private stack for making new kids */
	osjmpbuf    sharestack;
	Proc    *kid;
	void    *kidsp;
	void    *os;        /* host os specific data */
};

Estrutura e Tabela de Processos de Usuário

A estrutura de processos de usuário é denominada Prog e está descrita em emu/port/dis.c da maneira como segue abaixo:

struct{
	Lock    l;
	Prog*   runhd;
	Prog*   runtl;
	Prog*   head;
	Prog*   tail;
	Rendez  irend;
	int idle;
	int nyield;
	int creating;
	Proc*   vmq;        /* queue of procs wanting vm */
	Proc*   vmqt;
	Proc*   idlevmq;    /* queue of procs wanting work */
	Atidle* idletasks;
} isched;

A variavel de lock é utilizada para fornecer a exclusão mútua aos acessos á estrutura de dados. A lista de processos prontos de usuário para escalonamento é identificada pelos ponteiros runhd e runtl. Os ponteiros head e tail têm a função de apontar para as extremidades da lista duplamente encadeada que contém o conjunto de processos. Quando o escalonador está ocioso (no processo de usuário a ser escalonado), a flag ilde deve ser setada. Os ponteiros vmq e vmqt estão no começo e no final de uma lista encadeada dos kprocs de interpretador no estado de Pronto. Esses são os que têm entrada na tabela de processos de usuário ligada ao membro da estrutura iprog. Os kprocs de interpretador que estão ociosos (ou seja, não têm um processo do usuário associado) estão em uma lista encadeada apontada por idlevmq.

Uma representação da estrutura e filas de processos de usuário é mostrada abaixo. Nela os itens a,b,c e d são kprocs, enquanto que os itens numerados são os IDs de processos de usuário.

A estrutura Prog da tabela de processos de usuário é definida em include/interp.h como segue abaixo:

struct Prog{
	REG     R;      /* Register set */
	Prog*       link;       /* Run queue */
	Channel*        chan;   /* Channel pointer */
	void*       ptr;        /* Channel data pointer */
	enum ProgState  state;      /* Scheduler state */
	char*       kill;       /* Set if prog should error */
	char*       killstr;    /* kill string buffer when needed */
	int     pid;        /* unique Prog id */
	int     quanta;     /* time slice */
	ulong   ticks;      /* time used */
	int     flags;      /* error recovery flags */
	Prog*       prev;
	Prog*       next;
	Prog*   pidlink;    /* next in pid hash chain */
	Progs*  group;  /* process group */
	Prog*   grpprev;    /* previous group member */
	Prog*   grpnext;    /* next group member */
	void*   exval;  /* current exception */
	char*   exstr;  /* last exception */
	void        (*addrun)(Prog*);
	void        (*xec)(Prog*);
	void*       osenv;
};

O membro R é um registro para manter uma cópia dos registradores do processo quando este não está no estado Em Execução. O ponteiro link é utilizado para apontar para o próximo processo da lista encadeada do estado Prontos. Para processos bloqueados este ponteiro é ignorado. Os membros chan e ptr são ponteiros utilizados para um recurso oferecido pela linguagem Limbo denominada canais, enquanto chan registra um canal quando o processo está bloqueado, ptr registra o endereço do buffer de envio e recebimento de dados. O estado corrente do processo é registrado em state e pode assumir os estados apresentados na Figura 2.

No caso de uma falha do processo durante sua execução, o ponteiro kill é apontado para uma mensagem de erro descrevendo a falha, ou em certos casos killstr apontar para um buffer contendo a string de erro.

OsIDs de cada processo são armazenados no campo pid. O inferno numera cada ID exclusivamente com um um numero sequencial até o limite do numero inteiro. Como não existe reutilização de IDs, quando esse numero estoura, o inferno é desligado, contudo, uma máquina 32bits pode suportar mais de 2bilhões de processos antes de desligar, assim, mesmo que um processo seja criado por segundo, ainda demoraria aproximadamente 68 anos para que houvesse o estouro dos IDs.

Dentro do Inferno, os processo podem fazer parte de grupos, indicados pelo ponteiro group. Geralmente processos filhos fazem parte do mesmo grupo do processo pai. O membro quanta é utilizado para controlar o tempo que o processo tem para ser executado antes de sofrer preempção. Quando existe necessidade de tratamento de exceções o membro flag pode ser setado.

Como todos os processos fazem parte de uma fila duplamente encadeada, existem dois ponteiros next e prev para esta estrutura. Como a busca em lista tem tempo linear proporcional ao número de processos, o que pode se tornar demorado a depender da quantidade de processos rodando, o sistema operacional mantém também uma tabela hash com todos os processos. Processos que se dispersam sobre o mesmo bucket são encadeados em outra lista utilizando o membro pidlink. Para cada grupo de processos existe também uma lista duplamente encadeada que se servem dos ponteiros prgprev e prgnext para apontar para os processos adjacentes.

Ponteiros exval e exstr assim como flag são usados no tratamentos de exceções e por fim addrun e xec são ponteiros para funções usados na inicialização e no processamento enquanto que osenv aponta para uma estrutura Osenv que contém informações adicionais sobre o processo.

Escalonamento de Processos

Os processos de kernel e usuário são escalonados de maneira distintas. Processos de kernel sobre tudo são escalonados de maneira diferente em um Inferno hospedado ou nativo. Quando hospedado os processos de kernel são escalonados pelo sistema hospedeiro, e apenas os processos de usuário ficam a cargo do Inferno, enquanto que, nativo o próprio inferno precisa escalonar os kprocs. Isto é feito por uma estrutura de FIFO (First In First Out), pois já que existe apenas um kproc de interpretador por vez, o escalonador equivale simplesmente a selecionar um dos kprocs ociosos e deixar que ele execute até bloquear.

Os processos de usuário, por sua vez, são escalonados pelo interpretador Dis, que utiliza uma seleção por fila circular (Round Robin) onde cada processo é selecionado, executado por uma fatia de tempo e quando sofre preempção, é colocado no final da lista de Prontos, sem qualquer noção de prioridade envolvida. Todos os processos são tratados igualmente a todo tempo. Ao contrário do comum, em que o quantum de execução para cada processo é quantificado em tempo, no Inferno, o quantum equivale a um número de instruções (2048) que o processo poderá executar antes de sofrer preempção.