Baixe conceitos e mecanismo e outras Manuais, Projetos, Pesquisas em PDF para Informática, somente na Docsity! Sistemas Operacionais: Conceitos e Mecanismos II - Gerência de Tarefas Prof. Carlos Alberto Maziero DAInf UTFPR http://dainf.ct.utfpr.edu.br/∼maziero 2 de junho de 2013 Este texto está licenciado sob a Licença Attribution-NonCommercial-ShareAlike 3.0 Unported da Creative Commons (CC). Em resumo, você deve creditar a obra da forma especificada pelo autor ou licenciante (mas não de maneira que sugira que estes concedem qualquer aval a você ou ao seu uso da obra). Você não pode usar esta obra para fins comerciais. Se você alterar, transformar ou criar com base nesta obra, você poderá distribuir a obra resultante apenas sob a mesma licença, ou sob uma licença similar à presente. Para ver uma cópia desta licença, visite http://creativecommons.org/licenses/by-nc-sa/3.0/. Este texto foi produzido usando exclusivamente software livre: Sistema Operacional GNU/Linux (distri- buições Fedora e Ubuntu), compilador de texto LATEX 2ε, gerenciador de referências BibTeX, editor gráfico Inkscape, criadores de gráficos GNUPlot e GraphViz e processador PS/PDF GhostScript, entre outros. c© Carlos Maziero : SUMÁRIO Sumário 1 Objetivos 3 2 O conceito de tarefa 4 3 A gerência de tarefas 6 3.1 Sistemas mono-tarefa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Sistemas multi-tarefa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Sistemas de tempo compartilhado . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Ciclo de vida das tarefas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4 Implementação de tarefas 11 4.1 Contextos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Trocas de contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Processos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3.1 Criação de processos . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.4 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 Escalonamento de tarefas 23 5.1 Objetivos e métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 Escalonamento preemptivo e cooperativo . . . . . . . . . . . . . . . . . . 25 5.3 Escalonamento FCFS (First-Come, First Served) . . . . . . . . . . . . . . . 26 5.4 Escalonamento SJF (Shortest Job First) . . . . . . . . . . . . . . . . . . . . . 29 5.5 Escalonamento por prioridades . . . . . . . . . . . . . . . . . . . . . . . . 30 5.5.1 Definição de prioridades . . . . . . . . . . . . . . . . . . . . . . . . 32 5.5.2 Inanição e envelhecimento de tarefas . . . . . . . . . . . . . . . . 33 5.5.3 Inversão e herança de prioridades . . . . . . . . . . . . . . . . . . 35 5.6 Outros algoritmos de escalonamento . . . . . . . . . . . . . . . . . . . . . 38 5.7 Um escalonador real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 A O Task Control Block do Linux 41 2 c© Carlos Maziero : O conceito de tarefa 1 2 3 4 Figura 1: Tarefas de um navegador Internet Dessa forma, as tarefas definem as atividades a serem realizadas dentro do sistema de computação. Como geralmente há muito mais tarefas a realizar que processadores disponíveis, e as tarefas não têm todas a mesma importância, a gerência de tarefas tem uma grande importância dentro de um sistema operacional. 5 c© Carlos Maziero : A gerência de tarefas 3 A gerência de tarefas Em um computador, o processador tem de executar todas as tarefas submetidas pelos usuários. Essas tarefas geralmente têm comportamento, duração e importância distintas. Cabe ao sistema operacional organizar as tarefas para executá-las e decidir em que ordem fazê-lo. Nesta seção será estudada a organização básica do sistema de gerência de tarefas e sua evolução histórica. 3.1 Sistemas mono-tarefa Os primeiros sistemas de computação, nos anos 40, executavam apenas uma tarefa de cada vez. Nestes sistemas, cada programa binário era carregado do disco para a memória e executado até sua conclusão. Os dados de entrada da tarefa eram carregados na memória juntamente com a mesma e os resultados obtidos no processamento eram descarregados de volta no disco após a conclusão da tarefa. Todas as operações de transferência de código e dados entre o disco e a memória eram coordenados por um operador humano. Esses sistemas primitivos eram usados sobretudo para aplicações de cálculo numérico, muitas vezes com fins militares (problemas de trigonometria, balística, mecânica dos fluidos, etc.). A Figura 2 a seguir ilustra um sistema desse tipo. processador Memória barramentos control. de disco 1 2 3 4 dados resultados tarefa disco Figura 2: Sistema mono-tarefa: 1) carga do código na memória, 2) carga dos dados na memória, 3) processamento, consumindo dados e produzindo resultados, 4) ao término da execução, a descarga dos resultados no disco. Nesse método de processamento de tarefas é possível delinear um diagrama de estados para cada tarefa executada pelo sistema, que está representado na Figura 3. nova executando terminada inicia a execução termina a execução Figura 3: Diagrama de estados de uma tarefa em um sistema mono-tarefa. Com a evolução do hardware, as tarefas de carga e descarga de código entre memória e disco, coordenadas por um operador humano, passaram a se tornar críticas: mais 6 c© Carlos Maziero : Sistemas multi-tarefa tempo era perdido nesses procedimentos manuais que no processamento da tarefa em si. Para resolver esse problema foi construído um programa monitor, que era carregado na memória no início da operação do sistema com a função de coordenar a execução dos demais programas. O programa monitor executava continuamente os seguintes passos sobre uma fila de programas a executar, armazenada no disco: 1. carregar um programa do disco para a memória; 2. carregar os dados de entrada do disco para a memória; 3. transferir a execução para o programa recém-carregado; 4. aguardar o término da execução do programa; 5. escrever os resultados gerados pelo programa no disco. Percebe-se claramente que a função do monitor é gerenciar uma fila de programas a executar, mantida no disco. Na medida em que os programas são executados pelo processador, novos programas podem ser inseridos na fila pelo operador do sistema. Além de coordenar a execução dos demais programas, o monitor também colocava à disposição destes uma biblioteca de funções para simplificar o acesso aos dispositivos de hardware (teclado, leitora de cartões, disco, etc.). Assim, o monitor de sistema constitui o precursor dos sistemas operacionais. 3.2 Sistemas multi-tarefa O uso do programa monitor agilizou o uso do processador, mas outros problemas persistiam. Como a velocidade de processamento era muito maior que a velocidade de comunicação com os dispositivos de entrada e saída1, o processador ficava ocioso durante os períodos de transferência de informação entre disco e memória. Se a operação de entrada/saída envolvia fitas magnéticas, o processador podia ficar vários minutos parado, esperando. O custo dos computadores era elevado demais (e sua capacidade de processamento muito baixa) para permitir deixá-los ociosos por tanto tempo. A solução encontrada para resolver esse problema foi permitir ao processador suspender a execução da tarefa que espera dados externos e passar a executar outra tarefa. Mais tarde, quando os dados de que necessita estiverem disponíveis, a tarefa suspensa pode ser retomada no ponto onde parou. Para tal, é necessário ter mais memória (para poder carregar mais de um programa ao mesmo tempo) e definir procedimentos para suspender uma tarefa e retomá-la mais tarde. O ato de retirar um recurso de uma tarefa (neste caso o recurso é o processador) é denominado preempção. Sistemas que implementam esse conceito são chamados sistemas preemptivos. A adoção da preempção levou a sistemas mais produtivos (e complexos), nos quais várias tarefas podiam estar em andamento simultaneamente: uma estava ativa 1Essa diferença de velocidades permanece imensa nos sistemas atuais. Por exemplo, em um computa- dor atual a velocidade de acesso à memória é de cerca de 10 nanossegundos (10 × 10−9s), enquanto a velocidade de acesso a dados em um disco rígido IDE é de cerca de 10 milissegundos (10 × 10−3s), ou seja, um milhão de vezes mais lento! 7 c© Carlos Maziero : Ciclo de vida das tarefas pronta executando terminada recebe o processador termina a execução nova terminou de ser carregada em memória suspensa aguarda um dado externo ou outro evento dado disponível ou evento ocorreu fim do quantum Figura 6: Diagrama de estados de uma tarefa em um sistema de tempo compartilhado. Pronta : A tarefa está em memória, pronta para executar (ou para continuar sua execução), apenas aguardando a disponibilidade do processador. Todas as tarefas prontas são organizadas em uma fila cuja ordem é determinada por algoritmos de escalonamento, que serão estudados na Seção 5. Executando : O processador está dedicado à tarefa, executando suas instruções e fazendo avançar seu estado. Suspensa : A tarefa não pode executar porque depende de dados externos ainda não disponíveis (do disco ou da rede, por exemplo), aguarda algum tipo de sincronização (o fim de outra tarefa ou a liberação de algum recurso compartilhado) ou simplesmente espera o tempo passar (em uma operação sleeping, por exemplo). Terminada : O processamento da tarefa foi encerrado e ela pode ser removida da memória do sistema. Tão importantes quanto os estados das tarefas apresentados na Figura 6 são as transições entre esses estados, que são explicadas a seguir: · · · → Nova : Esta transição ocorre quando uma nova tarefa é admitida no sistema e começa a ser preparada para executar. Nova→ Pronta : ocorre quando a nova tarefa termina de ser carregada em memória, juntamente com suas bibliotecas e dados, estando pronta para executar. Pronta→ Executando : esta transição ocorre quando a tarefa é escolhida pelo escalona- dor para ser executada, dentre as demais tarefas prontas. Executando→ Pronta : esta transição ocorre quando se esgota a fatia de tempo desti- nada à tarefa (ou seja, o fim do quantum); como nesse momento a tarefa não precisa de outros recursos além do processador, ela volta à fila de tarefas prontas, para esperar novamente o processador. Executando→ Terminada : ocorre quando a tarefa encerra sua execução ou é abortada em consequência de algum erro (acesso inválido à memória, instrução ilegal, 10 c© Carlos Maziero : Implementação de tarefas divisão por zero, etc.). Na maioria dos sistemas a tarefa que deseja encerrar avisa o sistema operacional através de uma chamada de sistema (no Linux é usada a chamada exit). Terminada→ · · · : Uma tarefa terminada é removida da memória e seus registros e estruturas de controle no núcleo são apagadas. Executando→ Suspensa : caso a tarefa em execução solicite acesso a um recurso não disponível, como dados externos ou alguma sincronização, ela abandona o processador e fica suspensa até o recurso ficar disponível. Suspensa→ Pronta : quando o recurso solicitado pela tarefa se torna disponível, ela pode voltar a executar, portanto volta ao estado de pronta. A estrutura do diagrama de ciclo de vida das tarefas pode variar de acordo com a interpretação dos autores. Por exemplo, a forma apresentada neste texto condiz com a apresentada em [Silberschatz et al., 2001] e outros autores. Por outro lado, o diagrama apresentado em [Tanenbaum, 2003] divide o estado “suspenso” em dois subestados separados: “bloqueado”, quando a tarefa aguarda a ocorrência de algum evento (tempo, entrada/saída, etc.) e “suspenso”, para tarefas bloqueadas que foram movidas da memória RAM para a área de troca pelo mecanismo de memória virtual (vide Seção ??). Todavia, tal distinção de estados não faz mais sentido nos sistemas operacionais atuais baseados em memória paginada, pois neles os processos podem executar mesmo estando somente parcialmente carregados na memória. 4 Implementação de tarefas Conforme apresentado, uma tarefa é uma unidade básica de atividade dentro de um sistema. Tarefas podem ser implementadas de várias formas, como processos, threads, jobs e transações. Nesta seção são descritos os problemas relacionados à implementação do conceito de tarefa em um sistema operacional típico. São descritas as estruturas de dados necessárias para representar uma tarefa e as operações necessárias para que o processador possa comutar de uma tarefa para outra de forma eficiente e transparente. 4.1 Contextos Na Seção 2 vimos que uma tarefa possui um estado interno bem definido, que representa sua situação atual: a posição de código que ela está executando, os valores de suas variáveis e os arquivos que ela utiliza, por exemplo. Esse estado se modifica conforme a execução da tarefa evolui. O estado de uma tarefa em um determinado instante é denominado contexto. Uma parte importante do contexto de uma tarefa diz respeito ao estado interno do processador durante sua execução, como o valor do contador de programa (PC - Program Counter), do apontador de pilha (SP - Stack Pointer) e demais registradores. Além do estado interno do processador, o contexto de uma tarefa também inclui informações sobre os recursos usados por ela, como arquivos abertos, conexões de rede e semáforos. 11 c© Carlos Maziero : Trocas de contexto Cada tarefa presente no sistema possui um descritor associado, ou seja, uma estrutura de dados que a representa no núcleo. Nessa estrutura são armazenadas as informações relativas ao seu contexto e os demais dados necessários à sua gerência. Essa estrutura de dados é geralmente chamada de TCB (do inglês Task Control Block) ou PCB (Process Control Block). Um TCB tipicamente contém as seguintes informações: • Identificador da tarefa (pode ser um número inteiro, um apontador, uma referência de objeto ou um identificador opaco); • Estado da tarefa (nova, pronta, executando, suspensa, terminada, ...); • Informações de contexto do processador (valores contidos nos registradores); • Lista de áreas de memória usadas pela tarefa; • Listas de arquivos abertos, conexões de rede e outros recursos usados pela tarefa (exclusivos ou compartilhados com outras tarefas); • Informações de gerência e contabilização (prioridade, usuário proprietário, data de início, tempo de processamento já decorrido, volume de dados lidos/escritos, etc.). Dentro do núcleo, os descritores das tarefas são organizados em listas ou vetores de TCBs. Por exemplo, normalmente há uma lista de tarefas prontas para executar, uma lista de tarefas aguardando acesso ao disco rígido, etc. Para ilustrar o conceito de TCB, o Apêndice A apresenta o TCB do núcleo Linux (versão 2.6.12), representado pela estrutura task_struct definida no arquivo include/linux/sched.h. 4.2 Trocas de contexto Para que o processador possa interromper a execução de uma tarefa e retornar a ela mais tarde, sem corromper seu estado interno, é necessário definir operações para salvar e restaurar o contexto da tarefa. O ato de salvar os valores do contexto atual em seu TCB e possivelmente restaurar o contexto de outra tarefa, previamente salvo em outro TCB, é denominado troca de contexto. A implementação da troca de contexto é uma operação delicada, envolvendo a manipulação de registradores e flags específicos de cada processador, sendo por essa razão geralmente codificada em linguagem de máquina. No Linux as operações de troca de contexto para a plataforma Intel x86 estão definidas através de diretivas em Assembly no arquivo arch/i386/kernel/process.c dos fontes do núcleo. Durante uma troca de contexto, existem questões de ordem mecânica e de ordem estratégica a serem resolvidas, o que traz à tona a separação entre mecanismos e políticas já discutida anteriormente (vide Seção ??). Por exemplo, o armazenamento e recuperação do contexto e a atualização das informações contidas no TCB de cada tarefa são aspectos mecânicos, providos por um conjunto de rotinas denominado despachante ou executivo (do inglês dispatcher). Por outro lado, a escolha da próxima tarefa a receber o processador a cada troca de contexto é estratégica, podendo sofrer influências de diversos fatores, 12 c© Carlos Maziero : Criação de processos 4.3.1 Criação de processos Durante a vida do sistema, processos são criados e destruídos. Essas operações são disponibilizadas às aplicações através de chamadas de sistema; cada sistema operacional tem suas próprias chamadas para a criação e remoção de processos. No caso do UNIX, processos são criados através da chamada de sistema fork, que cria uma réplica do processo solicitante: todo o espaço de memória do processo é replicado, incluindo o código da(s) tarefa(s) associada(s) e os descritores dos arquivos e demais recursos associados ao mesmo. A Figura 9 ilustra o funcionamento dessa chamada. Processo pai memóriatarefas conexõesarqs abertos núcleo Processo pai memóriatarefas conexõesarqs abertos núcleo Processo filho memóriatarefas conexõesarqs abertos fork return return Figura 9: A chamada de sistema fork: antes (esq) e depois (dir) de sua execução pelo núcleo do sistema UNIX. A chamada de sistema fork é invocada por um processo (o pai), mas dois processos recebem seu retorno: o processo pai, que a invocou, e o processo filho, recém-criado, que possui o mesmo estado interno que o pai (ele também está aguardando o retorno da chamada de sistema). Ambos os processos têm os mesmos recursos associados, embora em áreas de memória distintas. Caso o processo filho deseje abandonar o fluxo de execução herdado do processo pai e executar outro código, poderá fazê-lo através da chamada de sistema execve. Essa chamada substitui o código do processo que a invoca pelo código executável contido em um arquivo informado como parâmetro. A listagem a seguir apresenta um exemplo de uso dessas duas chamadas de sistema: 15 c© Carlos Maziero : Criação de processos 1 #include <unistd.h> 2 #include <sys/types.h> 3 #include <sys/wait.h> 4 #include <stdio.h> 5 #include <stdlib.h> 6 7 int main (int argc, char *argv[], char *envp[]) 8 { 9 int pid ; /* identificador de processo */ 10 11 pid = fork () ; /* replicação do processo */ 12 13 if ( pid < 0 ) /* fork não funcionou */ 14 { 15 perror ("Erro: ") ; 16 exit (-1) ; /* encerra o processo */ 17 } 18 else if ( pid > 0 ) /* sou o processo pai */ 19 { 20 wait (0) ; /* vou esperar meu filho concluir */ 21 } 22 else /* sou o processo filho*/ 23 { 24 /* carrega outro código binário para executar */ 25 execve ("/bin/date", argv, envp) ; 26 perror ("Erro: ") ; /* execve não funcionou */ 27 } 28 printf ("Tchau !\n") ; 29 exit(0) ; /* encerra o processo */ 30 } A chamada de sistema exit usada no exemplo acima serve para informar ao núcleo do sistema operacional que o processo em questão não é mais necessário e pode ser destruído, liberando todos os recursos a ele associados (arquivos abertos, conexões de rede, áreas de memória, etc.). Processos podem solicitar ao núcleo o encerramento de outros processos, mas essa operação só é aplicável a processos do mesmo usuário, ou se o processo solicitante pertencer ao administrador do sistema. Na operação de criação de processos do UNIX aparece de maneira bastante clara a noção de hierarquia entre processos. À medida em que processos são criados, forma-se uma árvore de processos no sistema, que pode ser usada para gerenciar de forma coletiva os processos ligados à mesma aplicação ou à mesma sessão de trabalho de um usuário, pois irão constituir uma sub-árvore de processos. Por exemplo, quando um processo encerra, seus filhos são informados sobre isso, e podem decidir se também encerram ou se continuam a executar. Por outro, nos sistemas Windows, todos os processos têm o mesmo nível hierárquico, não havendo distinção entre pais e filhos. O comando pstree do Linux permite visualizar a árvore de processos do sistema, como mostra a listagem a seguir. 16 c© Carlos Maziero : Criação de processos 1 init-+-aacraid 2 |-ahc_dv_0 3 |-atd 4 |-avaliacao_horac 5 |-bdflush 6 |-crond 7 |-gpm 8 |-kdm-+-X 9 | ‘-kdm---kdm_greet 10 |-keventd 11 |-khubd 12 |-2*[kjournald] 13 |-klogd 14 |-ksoftirqd_CPU0 15 |-ksoftirqd_CPU1 16 |-kswapd 17 |-kupdated 18 |-lockd 19 |-login---bash 20 |-lpd---lpd---lpd 21 |-5*[mingetty] 22 |-8*[nfsd] 23 |-nmbd 24 |-nrpe 25 |-oafd 26 |-portmap 27 |-rhnsd 28 |-rpc.mountd 29 |-rpc.statd 30 |-rpciod 31 |-scsi_eh_0 32 |-scsi_eh_1 33 |-smbd 34 |-sshd-+-sshd---tcsh---top 35 | |-sshd---bash 36 | ‘-sshd---tcsh---pstree 37 |-syslogd 38 |-xfs 39 |-xinetd 40 ‘-ypbind---ypbind---2*[ypbind] Outro aspecto importante a ser considerado em relação a processos diz respeito à comunicação. Tarefas associadas ao mesmo processo podem trocar informações facilmente, pois compartilham as mesmas áreas de memória. Todavia, isso não é possível entre tarefas associadas a processos distintos. Para resolver esse problema, o núcleo deve prover às aplicações chamadas de sistema que permitam a comunicação inter-processos (IPC – Inter-Process Communication). Esse tema será estudado em profundidade no Capítulo ??. 17 c© Carlos Maziero : Threads Processo pa threads memória núcleo Processo pb threads memória threads de núcleo Figura 11: O modelo de threads 1:1. é denominada Modelo de Threads N:M, onde N threads de usuário são mapeados em M ≤ N threads de núcleo. A Figura 12 apresenta esse modelo. Processo pa threads memória núcleo biblioteca Processo pb threads memória biblioteca thread de núcleo threads de núcleo Figura 12: O modelo de threads N:M. O modelo N:M é implementado pelo Solaris e também pelo projeto KSE (Kernel- Scheduled Entities) do FreeBSD [Evans and Elischer, 2003] baseado nas idéias apresenta- das em [Anderson et al., 1992]. Ele alia as vantagens de maior interatividade do modelo 1:1 à maior escalabilidade do modelo N:1. Como desvantagens desta abordagem podem ser citadas sua complexidade de implementação e maior custo de gerência dos threads de núcleo, quando comparado ao modelo 1:1. A Tabela 1 resume os principais aspectos dos três modelos de implementação de threads e faz um comparativo entre eles. 20 c© Carlos Maziero : Threads Modelo N:1 1:1 N:M Resumo Todos os N threads do pro- cesso são mapeados em um único thread de nú- cleo Cada thread do processo tem um thread correspon- dente no núcleo Os N threads do processo são mapeados em um conjunto de M threads de núcleo Local da imple- mentação bibliotecas no nível usuá- rio dentro do núcleo em ambos Complexidade baixa média alta Custo de gerên- cia para o núcleo nulo médio alto Escalabilidade alta baixa alta Suporte a vários processadores não sim sim Velocidade das trocas de con- texto entre thre- ads rápida lenta rápida entre threads no mesmo processo, lenta entre threads de processos distintos Divisão de recur- sos entre tarefas injusta justa variável, pois o mapea- mento thread→ processa- dor é dinâmico Exemplos GNU Portable Threads Windows XP, Linux Solaris, FreeBSD KSE Tabela 1: Quadro comparativo dos modelos de threads. 21 c© Carlos Maziero : Threads No passado, cada sistema operacional definia sua própria interface para a criação de threads, o que levou a problemas de portabilidade das aplicações. Em 1995 foi definido o padrão IEEE POSIX 1003.1c, mais conhecido como PThreads [Nichols et al., 1996], que busca definir uma interface padronizada para a criação e manipulação de threads na linguagem C. Esse padrão é amplamente difundido e suportado hoje em dia. A listagem a seguir, extraída de [Barney, 2005], exemplifica o uso do padrão PThreads (para compilar deve ser usada a opção de ligação -lpthread). 1 #include <pthread.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 #define NUM_THREADS 5 6 7 /* cada thread vai executar esta função */ 8 void *PrintHello (void *threadid) 9 { 10 printf ("%d: Hello World!\n", (int) threadid); 11 pthread_exit (NULL); 12 } 13 14 /* thread "main" (vai criar as demais threads) */ 15 int main (int argc, char *argv[]) 16 { 17 pthread_t thread[NUM_THREADS]; 18 int status, i; 19 20 /* cria as demais threads */ 21 for(i = 0; i < NUM_THREADS; i++) 22 { 23 printf ("Creating thread %d\n", i); 24 status = pthread_create (&thread[i], NULL, PrintHello, (void *) i); 25 26 if (status) /* ocorreu um erro */ 27 { 28 perror ("pthread_create"); 29 exit (-1); 30 } 31 } 32 33 /* encerra a thread "main" */ 34 pthread_exit (NULL); 35 } O conceito de threads também pode ser utilizado em outras linguagens de programa- ção, como Java, Python, Perl, C++ e C#. O código a seguir traz um exemplo simples de criação de threads em Java (extraído da documentação oficial da linguagem): 22 c© Carlos Maziero : Escalonamento preemptivo e cooperativo Tempo de resposta (response time, tr): é o tempo decorrido entre a chegada de um evento ao sistema e o resultado imediato de seu processamento. Por exemplo, o tempo decorrido entre apertar uma tecla e o caractere correspondente aparecer na tela, em um editor de textos. Essa medida de desempenho é típica de sistemas interativos, como sistemas desktop e de tempo-real; ela depende sobretudo da rapidez no tratamento das interrupções de hardware pelo núcleo e do valor do quantum de tempo, para permitir que as tarefas cheguem mais rápido ao processador quando saem do estado suspenso. Justiça : este critério diz respeito à distribuição do processador entre as tarefas prontas: duas tarefas de comportamento similar devem receber tempos de processamento similares e ter durações de execução similares. Eficiência : a eficiência E, conforme definido na Seção 4.2, indica o grau de utilização do processador na execução das tarefas do usuário. Ela depende sobretudo da rapidez da troca de contexto e da quantidade de tarefas orientadas a entrada/saída no sistema (tarefas desse tipo geralmente abandonam o processador antes do fim do quantum, gerando assim mais trocas de contexto que as tarefas orientadas a processamento). 5.2 Escalonamento preemptivo e cooperativo O escalonador de um sistema operacional pode ser preemptivo ou cooperativo (não-cooperativo): Sistemas preemptivos : nestes sistemas uma tarefa pode perder o processador caso termine seu quantum de tempo, execute uma chamada de sistema ou caso ocorra uma interrupção que acorde uma tarefa mais prioritária (que estava suspensa aguardando um evento). A cada interrupção, exceção ou chamada de sistema, o escalonador pode reavaliar todas as tarefas da fila de prontas e decidir se mantém ou substitui a tarefa atualmente em execução. Sistemas cooperativos : a tarefa em execução permanece no processador tanto quanto possível, só abandonando o mesmo caso termine de executar, solicite uma ope- ração de entrada/saída ou libere explicitamente o processador, voltando à fila de tarefas prontas (isso normalmente é feito através de uma chamada de sistema sched_yield() ou similar). Esses sistemas são chamados de cooperativos por exigir a cooperação das tarefas entre si na gestão do processador, para que todas possam executar. A maioria dos sistemas operacionais de uso geral atuais é preemptiva. Sistemas mais antigos, como o Windows 3.*, PalmOS 3 e MacOS 8 e 9 operavam de forma cooperativa. Em um sistema preemptivo, normalmente as tarefas só são interrompidas quando o processador está no modo usuário; a thread de núcleo correspondente a cada tarefa não sofre interrupções. Entretanto, os sistemas mais sofisticados implementam a preempção de tarefas também no modo núcleo. Essa funcionalidade é importante para sistemas de tempo real, pois permite que uma tarefa de alta prioridade chegue mais rapidamente ao 25 c© Carlos Maziero : Escalonamento FCFS (First-Come, First Served) processador quando for reativada. Núcleos de sistema que oferecem essa possibilidade são denominados núcleos preemptivos; Solaris, Linux 2.6 e Windows NT são exemplos de núcleos preemptivos. 5.3 Escalonamento FCFS (First-Come, First Served) A forma de escalonamento mais elementar consiste em simplesmente atender as tarefas em sequência, à medida em que elas se tornam prontas (ou seja, conforme sua ordem de chegada na fila de tarefas prontas). Esse algoritmo é conhecido como FCFS – First Come - First Served – e tem como principal vantagem sua simplicidade. Para dar um exemplo do funcionamento do algoritmo FCFS, consideremos as tarefas na fila de tarefas prontas, com suas durações previstas de processamento e datas de ingresso no sistema, descritas na tabela a seguir: tarefa t1 t2 t3 t4 ingresso 0 0 1 3 duração 5 2 4 3 O diagrama da Figura 13 mostra o escalonamento do processador usando o algoritmo FCFS cooperativo (ou seja, sem quantum ou outras interrupções). Os quadros sombreados representam o uso do processador (observe que em cada instante apenas uma tarefa ocupa o processador). Os quadros brancos representam as tarefas que já ingressaram no sistema e estão aguardando o processador (tarefas prontas). 1 3 5 70 14 t1 t2 t3 t4 t 11 Figura 13: Escalonamento FCFS. Calculando o tempo médio de execução (Tt, a média de tt(ti)) e o tempo médio de espera (Tw, a média de tw(ti)) para o algoritmo FCFS, temos: Tt = tt(t1) + tt(t2) + tt(t3) + tt(t4) 4 = (5 − 0) + (7 − 0) + (11 − 1) + (14 − 3) 4 = 5 + 7 + 10 + 11 4 = 33 4 = 8.25s Tw = tw(t1) + tw(t2) + tw(t3) + tw(t4) 4 = (0 − 0) + (5 − 0) + (7 − 1) + (11 − 3) 4 = 0 + 5 + 6 + 8 4 = 19 4 = 4.75s 26 c© Carlos Maziero : Escalonamento FCFS (First-Come, First Served) A adição da preempção por tempo ao escalonamento FCFS dá origem a outro algoritmo de escalonamento bastante popular, conhecido como escalonamento por revezamento, ou Round-Robin. Considerando as tarefas definidas na tabela anterior e um quantum tq = 2s, seria obtida a sequência de escalonamento apresentada na Figura 14. 1 3 70 14 t1 t2 t3 t4 t 112 4 6 10 12 135 8 9 Figura 14: Escalonamento Round-Robin. Na Figura 14, é importante observar que a execução das tarefas não obedece uma sequência óbvia como t1 → t2 → t3 → t4 → t1 → t2 → . . ., mas uma sequência bem mais complexa: t1 → t2 → t3 → t1 → t4 → t3 → . . .. Isso ocorre por causa da ordem das tarefas na fila de tarefas prontas. Por exemplo, a tarefa t1 para de executar e volta à fila de tarefas prontas no instante t = 2, antes de t4 ter entrado no sistema (em t = 3). Por isso, t1 retorna ao processador antes de t4 (em t = 6). A Figura 15 detalha a evolução da fila de tarefas prontas ao longo do tempo, para esse exemplo. Calculando o tempo médio de execução Tt e o tempo médio de espera Tw para o algoritmo round-robin, temos: Tt = tt(t1) + tt(t2) + tt(t3) + tt(t4) 4 = (13 − 0) + (4 − 0) + (12 − 1) + (14 − 3) 4 = 13 + 4 + 11 + 11 4 = 39 4 = 9.75s Tw = tw(t1) + tw(t2) + tw(t3) + tw(t4) 4 = 8 + 2 + 7 + 8 4 = 25 4 = 6.25s Observa-se o aumento nos tempos Tt e Tw em relação ao algoritmo FCFS simples, o que mostra que o algoritmo round-robin é menos eficiente para a execução de tarefas em lote. Entretanto, por distribuir melhor o uso do processador entre as tarefas ao longo do tempo, ele pode proporcionar tempos de resposta bem melhores às aplicações interativas. O aumento da quantidade de trocas de contexto também tem um impacto negativo na eficiência do sistema operacional. Quanto menor o número de trocas de contexto e menor a duração de cada troca, mais tempo sobrará para a execução das tarefas em si. Assim, é possível definir uma medida de eficiência E do uso do processador, em função das durações médias do quantum de tempo tq e da troca de contexto ttc: 27 c© Carlos Maziero : Escalonamento por prioridades tempo, esse algoritmo pode ser de grande valia, sobretudo para tarefas orientadas a entrada/saída. Suponha uma tarefa orientada a entrada/saída em um sistema preemptivo com tq = 10ms. Nas últimas 3 vezes em que recebeu o processador, essa tarefa utilizou 3ms, 4ms e 4.5ms de cada quantum recebido. Com base nesses dados históricos, é possível estimar qual a duração da execução da tarefa na próxima vez em que receber o processador. Essa estimativa pode ser feita por média simples (cálculo mais rápido) ou por extrapolação (cálculo mais complexo, podendo influenciar o tempo de troca de contexto ttc). A estimativa de uso do próximo quantum assim obtida pode ser usada como base para a aplicação do algoritmo SJF, o que irá priorizar as tarefas orientadas a entrada/saída, que usam menos o processador. Obviamente, uma tarefa pode mudar de comportamento repentinamente, passando de uma fase de entrada/saída para uma fase de processamento, ou vice-versa. Nesse caso, a estimativa de uso do próximo quantum será incorreta durante alguns ciclos, mas logo voltará a refletir o comportamento atual da tarefa. Por essa razão, apenas a história recente da tarefa deve ser considerada (3 a 5 últimas ativações). Outro problema associado ao escalonamento SJF é a possibilidade de inanição (starvation) das tarefas mais longas. Caso o fluxo de tarefas curtas chegando ao sistema seja elevado, as tarefas mais longas nunca serão escolhidas para receber o processador e vão literalmente “morrer de fome”, esperando na fila sem poder executar. Esse problema pode ser resolvido através de técnicas de envelhecimento de tarefas, como a apresentada na Seção 5.5.2. 5.5 Escalonamento por prioridades Vários critérios podem ser usados para ordenar a fila de tarefas prontas e escolher a próxima tarefa a executar; a data de ingresso da tarefa (usada no FCFS) e sua duração prevista (usada no SJF) são apenas dois deles. Inúmeros outros critérios podem ser especificados, como o comportamento da tarefa (em lote, interativa ou de tempo-real), seu proprietário (administrador, gerente, estagiário), seu grau de interatividade, etc. No escalonamento por prioridades, a cada tarefa é associada uma prioridade, geral- mente na forma de um número inteiro. Os valores de prioridade são então usados para escolher a próxima tarefa a receber o processador, a cada troca de contexto. O algoritmo de escalonamento por prioridades define um modelo genérico de escalonamento, que permite modelar várias abordagens, entre as quais o FCFS e o SJF. Para ilustrar o funcionamento do escalonamento por prioridades, serão usadas as tarefas descritas na tabela a seguir, que usam uma escala de prioridades positiva (ou seja, onde valores maiores indicam uma prioridade maior): tarefa t1 t2 t3 t4 ingresso 0 0 1 3 duração 5 2 4 3 prioridade 2 3 1 4 30 c© Carlos Maziero : Escalonamento por prioridades O diagrama da Figura 17 mostra o escalonamento do processador usando o algoritmo por prioridades em modo cooperativo (ou seja, sem quantum ou outras interrupções). 1 3 5 70 1410 t1 t2 t3 t4 t Figura 17: Escalonamento por prioridades (cooperativo). Calculando o tempo médio de execução Tt e o tempo médio de espera Tw para esse algoritmo, temos: Tt = tt(t1) + tt(t2) + tt(t3) + tt(t4) 4 = (7 − 0) + (2 − 0) + (14 − 1) + (10 − 3) 4 = 7 + 2 + 13 + 7 4 = 29 4 = 7.25s Tw = tw(t1) + tw(t2) + tw(t3) + tw(t4) 4 = (2 − 0) + (0 − 0) + (10 − 1) + (7 − 3) 4 = 2 + 0 + 9 + 4 4 = 15 4 = 3.75s Quando uma tarefa de maior prioridade se torna disponível para execução, o escalonador pode decidir entregar o processador a ela, trazendo a tarefa atual de volta para a fila de prontas. Nesse caso, temos um escalonamento por prioridades preemptivo, cujo comportamento é apresentado na Figura 18 (observe que, quando t4 ingressa no sistema, ela recebe o processador e t1 volta a esperar na fila de prontas). 1 3 5 70 1410 t1 t2 t3 t4 t Figura 18: Escalonamento por prioridades (preemptivo). 31 c© Carlos Maziero : Definição de prioridades Calculando o tempo médio de execução Tt e o tempo médio de espera Tw para esse algoritmo, temos: Tt = tt(t1) + tt(t2) + tt(t3) + tt(t4) 4 = (10 − 0) + (2 − 0) + (14 − 1) + (6 − 3) 4 = 10 + 2 + 13 + 3 4 = 28 4 = 7s Tw = tw(t1) + tw(t2) + tw(t3) + tw(t4) 4 = 5 + 0 + 9 + 0 4 = 14 4 = 3.5s 5.5.1 Definição de prioridades A definição da prioridade de uma tarefa é influenciada por diversos fatores, que podem ser classificados em dois grandes grupos: Fatores externos : são informações providas pelo usuário ou o administrador do sistema, que o escalonador não conseguiria estimar sozinho. Os fatores externos mais comuns são a classe do usuário (administrador, diretor, estagiário) o valor pago pelo uso do sistema (serviço básico, serviço premium) e a importância da tarefa em si (um detector de intrusão, um script de reconfiguração emergencial, etc.). Fatores internos : são informações que podem ser obtidas ou estimadas pelo escalona- dor, com base em dados disponíveis no sistema local. Os fatores internos mais utilizados são a idade da tarefa, sua duração estimada, sua interatividade, seu uso de memória ou de outros recursos, etc. Todos esses fatores devem ser combinados para produzir um valor de prioridade para cada tarefa. Todos os fatores externos são expressos por valor inteiro denominado prioridade estática (ou prioridade de base), que resume a “opinião” do usuário ou administrador sobre aquela tarefa. Os fatores internos mudam continuamente e devem ser recalculados periodicamente pelo escalonador. A combinação da prioridade estática com os fatores internos resulta na prioridade dinâmica ou final, que é usada pelo escalonador para ordenar as tarefas prontas. A Figura 19 resume esse procedimento. Em geral, cada família de sistemas operacionais define sua própria escala de prioridades estáticas. Alguns exemplos de escalas comuns são: Windows 2000 e sucessores : processos e threads são associados a classes de prioridade (6 classes para processos e 7 classes para threads); a prioridade final de uma thread depende de sua prioridade de sua própria classe de prioridade e da classe de prioridade do processo ao qual está associada, assumindo valores entre 0 e 31. As prioridades do processos, apresentadas aos usuários no Gerenciador de Tarefas, apresentam os seguintes valores default: • 4: baixa ou ociosa 32 c© Carlos Maziero : Inversão e herança de prioridades e no próximo turno terão mais chances de ser escolhidas. A constante α é conhecida como fator de envelhecimento. Usando o algoritmo de envelhecimento, a divisão do processador entre as tarefas se torna proporcional às suas prioridades. A Figura 21 ilustra essa proporcionalidade na execução das três tarefas t1, t2 e t3 com p(t1) < p(t2) < p(t3), usando a estratégia de envelhecimento. Nessa figura, percebe-se que todas as três tarefas recebem o processador periodicamente, mas que t3 recebe mais tempo de processador que t2, e que t2 recebe mais que t1. 0 t1 t2 t3 t Figura 21: Escalonamento por prioridades com envelhecimento. 5.5.3 Inversão e herança de prioridades Outro problema relevante que pode ocorrer em sistemas baseados em prioridades é a inversão de prioridades [Sha et al., 1990]. Este tipo de problema é mais complexo que o anterior, pois envolve o conceito de exclusão mútua: alguns recursos do sistema devem ser usados por um processo de cada vez, para evitar problemas de consistência de seu estado interno. Isso pode ocorrer com arquivos, portas de entrada saída e conexões de rede, por exemplo. Quando um processo obtém acesso a um recurso com exclusão mútua, os demais processos que desejam usá-lo ficam esperando no estado suspenso, até que o recurso esteja novamente livre. As técnicas usadas para implementar a exclusão mútua são descritas no Capítulo ??. A inversão de prioridades consiste em processos de alta prioridade serem impedidos de executar por causa de um processo de baixa prioridade. Para ilustrar esse problema, pode ser considerada a seguinte situação: um determinado sistema possui um processo de alta prioridade pa, um processo de baixa prioridade pb e alguns processos de prioridade média pm. Além disso, há um recurso R que deve ser acessado em exclusão mútua; para simplificar, somente pa e pb estão interessados em usar esse recurso. A seguinte sequência de eventos, ilustrada na Figura 22, é um exemplo de como pode ocorrer uma inversão de prioridades: 1. Em um dado momento, o processador está livre e é alocado a um processo de baixa prioridade pb; 2. durante seu processamento, pb obtém o acesso exclusivo a um recurso R e começa a usá-lo; 35 c© Carlos Maziero : Inversão e herança de prioridades 3. pb perde o processador, pois um processo com prioridade maior que a dele (pm) foi acordado devido a uma interrupção; 4. pb volta ao final da fila de tarefas prontas, aguardando o processador; enquanto ele não voltar a executar, o recurso R permanecerá alocado a ele e ninguém poderá usá-lo; 5. Um processo de alta prioridade pa recebe o processador e solicita acesso ao recurso R; como o recurso está alocado ao processo pb, pa é suspenso até que o processo de baixa prioridade pb libere o recurso. Neste momento, o processo de alta prioridade pa não pode continuar sua execução, porque o recurso de que necessita está nas mãos do processo de baixa prioridade pb. Dessa forma, pa deve esperar que pb execute e libere R, o que justifica o nome inversão de prioridades. A espera de pa pode ser longa, pois pb tem baixa prioridade e pode demorar a receber o processador novamente, caso existam outros processos em execução no sistema (como pm). Como tarefas de alta prioridade são geralmente críticas para o funcionamento de um sistema, a inversão de prioridades pode ter efeitos graves. 0 Pb Pm Pa t Pa acorda, solicita o recurso e fica bloqueado esperando Pm recebe o processador Pb aloca um recurso para si Pm libera o processador Pb libera o recurso bloqueado e perde o processador inversão de prioridades! R R Pa recebe o recurso e o processador Figura 22: Cenário de uma inversão de prioridades. Uma solução elegante para o problema da inversão de prioridades é obtida através de um protocolo de herança de prioridade [Sha et al., 1990]. O protocolo de herança de prioridade mais simples consiste em aumentar temporariamente a prioridade do processo pb que detém o recurso de uso exclusivo R. Caso esse recurso seja requisitado por um processo de maior prioridade pa, o processo pb “herda” temporariamente a prioridade de pa, para que possa voltar a executar e liberar o recurso R mais rapidamente. Assim que liberar o recurso, pb retorna à sua prioridade anterior. Essa estratégia está ilustrada na Figura 23. Provavelmente o melhor exemplo real de inversão de prioridades tenha ocorrido na sonda espacial Mars Pathfinder, enviada pela NASA em 1996 para explorar o solo marciano (Figura 24) [Jones, 1997]. O software da sonda executava sobre o sistema operacional de tempo real VxWorks e consistia de 97 threads com vários níveis de prioridades. Essas tarefas se comunicavam através de uma área de trasferência em memória compartilhada, com acesso mutuamente exclusivo controlado por semáforos (semáforos são estruturas de sincronização discutidas na Seção ??). 36 c© Carlos Maziero : Inversão e herança de prioridades 0 Pb Pm Pa t Pa acorda, solicita o recurso e fica bloqueado esperando Pm recebe o processador Pb aloca um recurso para si Pb libera o recurso bloqueado e perde o processador R R Figura 23: Um protocolo de herança de prioridade. Figura 24: Sonda Mars Pathfinder com o robô Sojourner (NASA). A gerência da área de transferência estava a cargo de uma tarefa tg, rápida mas de alta prioridade, que era ativada frequentemente para mover blocos de informação para dentro e fora dessa área. A coleta de dados meteorológicos era feita por uma tarefa tm de baixa prioridade, que executava esporadicamente e escrevia seus dados na área de transferência, para uso por outras tarefas. Por fim, a comunicação com a Terra estava sob a responsabilidade de uma tarefa tc de prioridade média e potencialmente demorada (Tabela 2 e Figura 25). Como o sistema VxWorks define prioridades preemptivas, as tarefas eram atendidas conforme suas necessidades na maior parte do tempo. Todavia, a exclusão mútua no acesso à área de transferência escondia uma inversão de prioridades: caso a tarefa de coleta de dados meteorológicos tm perdesse o processador sem liberar a área de transferência, a tarefa de gerência tg teria de ficar esperando até que tm voltasse a 37 c© Carlos Maziero : REFERÊNCIAS Referências [Anderson et al., 2002] Anderson, D., Cobb, J., Korpela, E., Lebofsky, M., and Werthimer, D. (2002). SETI@home: An experiment in public-resource computing. Communications of the ACM, 45(11):56–61. [Anderson et al., 1992] Anderson, T., Bershad, B., Lazowska, E., and Levy, H. (1992). Scheduler activations: effective kernel support for the user-level management of parallelism. ACM Transactions on Computer Systems, 10(1):53–79. [Barney, 2005] Barney, B. (2005). POSIX threads programming. http://www.llnl.gov/computing/tutorials/pthreads. [Black, 1990] Black, D. L. (1990). Scheduling and resource management techniques for multiprocessors. Technical Report CMU-CS-90-152, Carnegie-Mellon University, Computer Science Dept. [Boyd-Wickizer et al., 2009] Boyd-Wickizer, S., Morris, R., and Kaashoek, M. (2009). Reinventing scheduling for multicore systems. In 12th conference on Hot topics in operating systems, page 21. USENIX Association. [Burns and Wellings, 1997] Burns, A. and Wellings, A. (1997). Real-Time Systems and Programming Languages, 2nd edition. Addison-Wesley. [Corbató, 1963] Corbató, F. (1963). The Compatible Time-Sharing System: A Programmer’s Guide. MIT Press. [Engeschall, 2005] Engeschall, R. (2005). The GNU Portable Threads. http://www.gnu.org/software/pth. [Evans and Elischer, 2003] Evans, J. and Elischer, J. (2003). Kernel-scheduled entities for FreeBSD. http://www.aims.net.au/chris/kse. [Farines et al., 2000] Farines, J.-M., da Silva Fraga, J., and de Oliveira, R. S. (2000). Sistemas de Tempo Real – 12a Escola de Computação da SBC. Sociedade Brasileira de Computação. [Ford and Susarla, 1996] Ford, B. and Susarla, S. (1996). CPU Inheritance Scheduling. In Usenix Association Second Symposium on Operating Systems Design and Implementation (OSDI), pages 91–105. [Jones, 1997] Jones, M. (1997). What really happened on Mars Rover Pathfinder. ACM Risks-Forum Digest, 19(49). [Kay and Lauder, 1988] Kay, J. and Lauder, P. (1988). A fair share scheduler. Communi- cations of the ACM, 31(1):44–55. [Love, 2004] Love, R. (2004). Linux Kernel Development. Sams Publishing Developer’s Library. 40 c© Carlos Maziero : O Task Control Block do Linux [Nichols et al., 1996] Nichols, B., Buttlar, D., and Farrell, J. (1996). PThreads Programming. O’Reilly Media, Inc. [Nieh and Lam, 1997] Nieh, J. and Lam, M. (1997). The design, implementation and evaluation of SMART: a scheduler for multimedia applications. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 184–197. [Sha et al., 1990] Sha, L., Rajkumar, R., and Lehoczky, J. (1990). Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, 39(9):1175–1185. [Silberschatz et al., 2001] Silberschatz, A., Galvin, P., and Gagne, G. (2001). Sistemas Operacionais – Conceitos e Aplicações. Campus. [Tanenbaum, 2003] Tanenbaum, A. (2003). Sistemas Operacionais Modernos, 2a edição. Pearson – Prentice-Hall. A O Task Control Block do Linux A estrutura em linguagem C apresentada a seguir constitui o descritor de tarefas (Task Control Block) do Linux (estudado na Seção 4.1). Ela foi extraída do arquivo include/linux/sched.h do código-fonte do núcleo Linux 2.6.12 (o arquivo inteiro contém mais de 1.200 linhas de código em C). 1 struct task_struct { 2 volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ 3 struct thread_info *thread_info; 4 atomic_t usage; 5 unsigned long flags; /* per process flags, defined below */ 6 unsigned long ptrace; 7 8 int lock_depth; /* BKL lock depth */ 9 10 int prio, static_prio; 11 struct list_head run_list; 12 prio_array_t *array; 13 14 unsigned long sleep_avg; 15 unsigned long long timestamp, last_ran; 16 unsigned long long sched_time; /* sched_clock time spent running */ 17 int activated; 18 19 unsigned long policy; 20 cpumask_t cpus_allowed; 21 unsigned int time_slice, first_time_slice; 22 23 #ifdef CONFIG_SCHEDSTATS 24 struct sched_info sched_info; 25 #endif 26 27 struct list_head tasks; 41 c© Carlos Maziero : O Task Control Block do Linux 28 /* 29 * ptrace_list/ptrace_children forms the list of my children 30 * that were stolen by a ptracer. 31 */ 32 struct list_head ptrace_children; 33 struct list_head ptrace_list; 34 35 struct mm_struct *mm, *active_mm; 36 37 /* task state */ 38 struct linux_binfmt *binfmt; 39 long exit_state; 40 int exit_code, exit_signal; 41 int pdeath_signal; /* The signal sent when the parent dies */ 42 /* ??? */ 43 unsigned long personality; 44 unsigned did_exec:1; 45 pid_t pid; 46 pid_t tgid; 47 /* 48 * pointers to (original) parent process, youngest child, younger sibling, 49 * older sibling, respectively. (p->father can be replaced with 50 * p->parent->pid) 51 */ 52 struct task_struct *real_parent; /* real parent process (when being debugged) */ 53 struct task_struct *parent; /* parent process */ 54 /* 55 * children/sibling forms the list of my children plus the 56 * tasks I’m ptracing. 57 */ 58 struct list_head children; /* list of my children */ 59 struct list_head sibling; /* linkage in my parent’s children list */ 60 struct task_struct *group_leader; /* threadgroup leader */ 61 62 /* PID/PID hash table linkage. */ 63 struct pid pids[PIDTYPE_MAX]; 64 65 struct completion *vfork_done; /* for vfork() */ 66 int __user *set_child_tid; /* CLONE_CHILD_SETTID */ 67 int __user *clear_child_tid; /* CLONE_CHILD_CLEARTID */ 68 69 unsigned long rt_priority; 70 cputime_t utime, stime; 71 unsigned long nvcsw, nivcsw; /* context switch counts */ 72 struct timespec start_time; 73 /* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */ 74 unsigned long min_flt, maj_flt; 75 76 cputime_t it_prof_expires, it_virt_expires; 77 unsigned long long it_sched_expires; 78 struct list_head cpu_timers[3]; 79 80 /* process credentials */ 81 uid_t uid,euid,suid,fsuid; 82 gid_t gid,egid,sgid,fsgid; 42