Sistemas

Operacionais
 Sistemas
Operacionais

1ª edição
2019
 Autoria Paulo Sérgio Pádua de Lacerda
Parecerista Validador Augusto Mendes Gomes Jr.

*Todos os gráficos, tabelas e esquemas são creditados à autoria, salvo quando indicada a referência.

Informamos que é de inteira responsabilidade da autoria a emissão de conceitos. Nenhuma parte

desta publicação poderá ser reproduzida por qualquer meio ou forma sem autorização. A violação dos
direitos autorais é crime estabelecido pela Lei n.º 9.610/98 e punido pelo artigo 184 do Código Penal.
Unidade 2
2. Gerência de Processos

Para iniciar seus estudos

2
Olá! Nesta unidade, você entenderá a definição de processos e thread. Em
sistema multitarefa a função agendamento das tarefas que são executadas
na CPU é atribuída ao sistema operacional. Analisar os princípios desse
agendamento ajuda no esclarecimento de problemas de starvation e
deadlock. Algoritmos são usados na aplicação desses agendamentos.
Sistema de jogos é interativo e faz uso de todos esses conceitos. Vamos
começar?

Objetivos de Aprendizagem
• Definir os conceitos de processo e thread.

• Identificar as diferenças entre processos e threads.

• Registrar a importância do escalonamento de processos.

• Identificar os tipos de algoritmos de escalonamento.

27
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Introdução da unidade
Os sistemas operacionais têm uma função muito importante em sistemas interativos. Esses sistemas criam
diversos processos que disputam concorrentemente um tempo de execução pelo processador. A gerência do
procedimento que decide qual o processo e quanto ele será processado pela unidade central de processamento
(CPU) é responsabilidade dos sistemas operacionais.

Esta unidade tem como objetivo dialogar e estudar os conceitos fundamentais da gerência de processos
começando pela definição de processos e thread, identificando suas diferenças e descrevendo o funcionamento
da sua estrutura, e por fim, apresentando os algoritmos que são utilizados pelos diversos tipos de sistemas
operacionais nesse gerenciamento.

Algoritmo que são usados, por exemplo, num pool de impressão. Esse sistema é uma fila de impressão criada a
partir do envio de vários arquivos para uma impressora compartilhada por vários usuários. O primeiro processo
a chegar na fila de impressão é executado. Em suma, você será capaz de analisar e comparar os conceitos sobre
gerenciamento de processos e, por exemplo, julgar qual algoritmo pode ser aplicado em diversos tipos de sistemas
como exemplo pool de impressão.

2.1 Conceitos
Um sistema operacional possui o objetivo de controlar ou gerenciar tanto o hardware quanto o software, ou seja,
um recurso do computador. Esse recurso pode ser um dado armazenado na memória ou controlar um fluxo de um
dispositivo de entrada e saída (Figura 14). Um sistema multiprogramável simula um ambiente monoprogramável
para cada usuário. Esse usuário tem a percepção do uso exclusivo do recurso. Nesses sistemas, várias tarefas
são executadas quase que ao mesmo tempo na CPU e diversos algoritmos determinam quando e como serão
executadas. Processo é a estrutura que mantém as informações necessárias a respeito de uma tarefa como por
exemplo endereço de alocação na memória. (MACHADO; MAIA, 2013)

Figura 14 – Sistema Operacional

Sistema Operacional

Fonte: Shutterstock, 2018.

28
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

2.2 Processos
Processo é um programa ou parte dele sendo executado na CPU. Também pode ser definido como uma abstração
de um programa em execução (MACHADO; MAIA, 2013). Toda a estrutura que gira em torno desse conceito
(registradores, endereço de memória, etc) é muito importante para o entendimento do processo em sistemas
operacionais.

2.2.1 Modelo de processos

A estrutura de dados que armazena as informações necessárias para tratar um processo é chamada de bloco de
controle de processo (Process Block Control -PCB, em inglês) (Figura 15). Essa estrutura fica no núcleo do sistema
operacional, e a partir do PCB, informações a respeito do processo como identificação, prioridade, estado corrente,
recursos alocados e informações sobre o programa em execução são mantidas pelo Sistema Operacional –SO
(MACHADO; MAIA, 2013).

Figura 15 – Bloco de controle de processo

Ponteiros
Estado do processo
Nome do processo
....
....
Limite de memória
Limite de arquivos abertos

Fonte: Elaborada pelo autor.

A chamada de sistema faz a gerência dos processos e permite realizar operações como criação, eliminação e
sincronização. Toda essa estrutura pode ser dividida em três partes: contexto de hardware, contexto de software e
espaço de endereçamento, e juntas, mantém todas as informações de um programa em execução na CPU.

2.2.1.1 Contexto de hardware

O contexto de hardware basicamente é formado pelo registrador, Program Counter (PC), Stack Pointer (SP). Um
registrador é uma memória RAM (Random Access Memory) que fica no processador e armazena os dados de um
programa em execução. Quando um programa está em execução, as informações em memória do processo são
deslocadas para os registradores, e ao término do processamento, são deslocadas novamente para memória.
Para que essa mudança ocorra sem problemas é preciso armazenar as informações do processo interrompido por
outro processo para que, retorne a execução de onde parou. (TANENBAUM, 2016)

Nesse contexto, um registrador mantém o endereço do processo atual numa pilha, o program counter contém o
endereço (posição) da próxima instrução a ser executada na sequência do programa e o stack pointer (Ponteiro da
Pilha) armazena informações sobre as sub-rotinas ativas num programa de computador.

29
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Essa troca de processos na CPU é chamada de troca ou mudança de contexto (MACHADO; MAIA, 2013) (Figura
16). Essa mudança consiste em gravar as informações do registrador e carregá-lo com os valores do novo processo
que esteja ganhando a CPU.

Figura 16 – Contexto de hardware

Processo A Processo B

executando

Salva os
registradores de A

Carrega os
registradores de B

executando

Salva os
registradores de B

Carrega os
registradores de A

executando

Fonte: Elaborada pelo autor.

2.2.1.2 Contexto de software

Contexto de software contém as características e limites de recursos que podem ser alocados por um processo,
ou seja, que irão influenciar na execução de um programa como tamanho do buffer de entrada e saída, nome
do processo, proprietário, data da criação etc. Esse contexto é dividido em três partes: identificação, quotas e
privilégio.

Cada processo ao ser criado recebe um número de identificação do usuário ou processo que o criou, data da
criação e hora da criação. Esse processo criado recebe também quotas de alocação para cada recurso do sistema
como número máximo de arquivos abertos, número máximo de operações de entrada e saída (E/S) e número
máximo de subprocesso que pode criar, e por último, privilégios que são as ações que um processo pode fazer
com relação a ele mesmo, a outros processos e ao sistema operacional como prioridade de execução e limites
alocados de memória.

No Linux, existem dois tipos de prioridade: estática e dinâmica. A prioridade estática é definida pelo usuário e
utilizada para sistemas em tempo real, e a dinâmica para os demais sistemas. Na prioridade estática o escalonador
não tem interferência, ou seja, definida a prioridade pelo usuário, somente este poderá redefini-la. Na dinâmica,
a prioridade é determinada pela quantidade de processos que ainda resta para ser processado.

30
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Já no Windows, sistema gráfico e interativo, todo processo ganha prioridade normal e o escalonador determina
a ordem de execução na CPU pelo nível de prioridade. São 32 níveis de prioridade, sendo que 16 - 31 são os
níveis de prioridade mais alta, e 0 a 15, os níveis de prioridade variáveis. A prioridade é determinada pela classe
de prioridade dentro de cada processo (Tempo Real, Alta, Acima do Normal, Normal, Abaixo do Normal, Baixo)
podendo ser alteradas pelo usuário.

2.2.1.3 Espaço de Endereçamento

O processo ao ser executado ocupa uma área de memória. Essa área é denominada espaço de memória.
Este espaço de memória que determina uma área (espaço) para onde os processos serão endereçados.

Cada processo possui o seu espaço de memória que deve ser protegido do acesso de outros processos.

2.2.2 Estados de um processo

Num sistema multitarefa, um processo possui vários estados (Figura 17), pois nem sempre todo o processo está
sendo processado na CPU (SILBERSCHATZ, 2015). Muitos desses estados são devido aos diversos processos que
estão sendo executados pelo sistema operacional. Um processo pode ter os seguintes estados:

• Running (execução) – quando o processo está sendo executado na CPU.

• Ready (pronto) – quando o processo está em memória esperando para ser executado pela CPU.

• WAIT (espera) – quando o processo está aguardando por um evento externo ou recurso para ser executado
na CPU, por exemplo, um evento de entrada e saída.

• BLOCKED (bloqueado) – quando um processo é interrompido por outro processo na CPU e aguarda por um
recurso do sistema que ainda não está disponível, por exemplo, um dispositivo de entrada e saída.

• FINISHED (finalizado) – quando um processo é finalizado.

• New (novo) – quando o arquivo é criado.

Figura 17 – Estado de um processo

1 3 6
Finalizado
Novo Executando

4 5
Espera
Bloqueado

2
Pronto

Fonte: Elaborada pelo autor.

31
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Estado Evento

1 – Novo O momento que o processo é criado no sistema operacional.

2- Pronto O processo está armazenado em memória RAM, foi atribuído um determinado recurso e
o seu para ser executado na CPU.

3 – Executando Nesse momento o processo está sendo executado no processador num determinado
tempo ou totalmente.

4 – Espera O processo está armazenado em memória secundária, disco, e espera por um evento
externo ou algum recurso para voltar a ser processado. Por exemplo, uma determinada
data e/ou hora para poder voltar a ser processado ou por um término de uma operação
de entrada/saída.

5 – Finalizado O processo é finalizado quando sua tarefa for concluída.

Um processo em estado de espera já garantiu o recurso, mas somente espera o momento para a sua execução.
Já no estado bloqueado, o processo não garantiu o recurso e aguarda uma autorização para utilizar determinado
recurso e ser processado.
Devido a uma técnica chamada swapping (troca), processos em estado de pronto ou espera/bloqueado podem
momentaneamente estar em memória secundária, e não em memória principal.
Quando o processo está sendo executado no estado de executando, pode sofrer uma interferência externa e
passar para o estado de espera. Essa interferência pode ser um evento externo de entrada e saída.
Quando o processo for interrompido por fatia de tempo ou por prioridade e ainda precisar de mais tempo na
CPU para terminar sua execução, ele passa do estado de executando para o estado de pronto, e outro processo
na fila de pronto poderá ser executado na CPU. Após seu tempo, ele aloca uma nova fatia de tempo e retorna o
processamento na CPU. Esse procedimento será realizado até o fim de todo o processamento desse processo.
Quando o processo em estado de execução termina sua tarefa, ele é finalizado e, assim, pode ser removido da
memória.

2.2.3 Mudanças de estados de um processo

Em um sistema multitarefa, um processo muda de estado várias vezes devido a eventos provocados pelo próprio
processo ou pelo SO. São mudanças de estado permitidas:

• Pronto → Execução;

• Execução → Espera:

• Espera → Pronto;

• Execução → Pronto;

• Execução → Bloqueado;

• Bloqueado → Pronto.

32
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

2.2.4 Subprocesso e Thread

Um processo (processo-pai) pode criar outros processos (processo-filho). Esse processo-filho, agora processo-
pai, pode criar outros processo-filho e assim sucessivamente. Esse procedimento de criar subprocessos pelos
processos existentes é denominado hierarquia de processos (SILBERSCHATZ, 2015).

Esse procedimento de criação de vários processos pode gerar um super processamento de processos na CPU
(overhead), pois os processos são estruturas independentes e possuem seus próprios contextos.

Threads são linhas de comando (programação) existentes dentro de um processo que podem executar tarefas
concorrentes. Possuem o mesmo contexto de software, compartilham o mesmo endereçamento de memória,
porém seu contexto de hardware é diferente do contexto do processo.

Threads são divididas em dois níveis: usuário e kernel. O sistema operacional fornece o suporte à nível de kernel,
e a nível de usuário são implementadas por meio de bibliotecas de determinada linguagem de programação.
Como características as threads (Figura) possuem um contexto mais simplificado, mais fáceis de criar/destruir e
melhoram o desempenho em sistema de muita E/S.

Figura 18 – Processos x Thread

Thread Processo
Thread

Tabela
Tabela
de
thread de
thread

usuário usuário

kernel kernel

Tabela de
processo

Fonte: Elaborada pelo autor.

Um sistema que possui um único processo com uma única thread, é chamada monothread, mas o sistema que
opera com vários processos, ou seja, cada processo com diversas threads é chamado multithread. Em sistema com
dois processadores, as threads podem ser executadas em paralelo. Um jogo é um excelente exemplo de sistema
multithread, pois permite que uma thread fique responsável pelo desenho e outra pelo áudio.

33
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

As threads são subdivisões de um processos. São criadas por linhas de comando, utilizam os mesmo recursos de
um processo, morre se o processo que a contém morrer, pode compartilhar os recursos do processo com outras
threads independentes e possui seu próprio fluxo de controle.

Imagine um usuário utilizando o Word, ele pode fazer a ortografia, fazer a gravação, fazer a formatação e continuar
escrevendo sem necessariamente fechar o processo do Word, pois por linha de comando, o desenvolvedor criou
rotinas que são habilitadas dentro do processo do Word e executadas dentro do contexto desse processo.

As threads possuem vantagens em relação a um processo:

• Na programação, um modelo mais simples de programação.

• Maior velocidade.

• Melhor desempenho.

As threads são utilizadas por programadores para a divisão de trabalho. Imagine um computador com dois núcleos
de processamento; nesse caso, uma thread poderia ser processada para exibição de vídeo num núcleo, enquanto
a outra trataria o som no outro núcleo. Caso não houvesse divisão de trabalho, tudo seria realizado num único
núcleo, utilizando, consequentemente, 50% do total do processamento. As threads consomem menos memória,
compartilham as informações do processo ao qual que estão associadas e possuem um tempo de troca de contexto
mais curto. Paralelismo, eficiência na comunicação e tempo de criação são características que fazem com que a
thread seja muito utilizada.

Se não houvesse o recurso de thread, poderia acontecer uma sobrecarga de processos na CPU, causando
paralização/congelamento do sistema. Um processo poderia, em sistema multitarefa, ocupar 100% da CPU até que
fosse terminado, o que poderia ocasionar uma inanição do sistema. Não haveria implementação de paralelismo
e concorrência. Os processos possuem contexto de software e hardware e endereçamento de memória diferentes.
Por esse motivo, o compartilhamento de estado de objetos de uma aplicação e as comunicações em geral entre
processos são operações muito custosas e que devem ser evitadas.

Fique atento!

Sistemas operacionais Android fazem uso de thread para envio de emails.

2.2.5 Tipos de processos

Os processos podem ser classificados em dois tipos: CPU-BOUND e I/O-BOUND (Figura 19).

• CPU-BOUND: esse tipo de processo depende mais da CPU do que entradas e saídas. Como exemplo,
tem-se os processos focados em processamento de alto desempenho.

• I/O-BOUND: esse tipo de processo realiza um número elevado de operações de entrada e saída, ficando
um tempo maior no estado de Espera do que no estado de Execução ou Pronto.

34
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Figura 19 – Tipos de processo

CPU
BOUND

I/O
BOUND

CPU
BOUND

Tempo

I/O
BOUND

I/O
BOUND

CPU
BOUND

Tempo

Fonte: Elaborada pelo autor.

2.3 Escalonamento de processos

Os sistemas operacionais multiprogramáveis foram implementados a partir do momento que o conceito de
compartilhamento foi aplicado à CPU. Vários processos podem ser executados concorrentemente na CPU. O
sistema operacional através de uma regra determina quem é o processo que terá a vez de ser processado pela
CPU (Figura 20). Esse mecanismo é chamado de escalonamento (STUART, 2011).

Existem diversas técnicas e critérios para escalonamento. Muitos dos problemas existentes no escalonamento de
processos são válidos para thread. O escalonador de processos utiliza diversos tipos de algoritmos para aplicação
do escalonamento. Esse procedimento é chamado de algoritmo de escalonamento.

35
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Figura 20 – Processos a escalonar

P2 P1
Qual processo
para execução?

CPU
P4 P3

Fonte: Elaborada pelo autor.

2.3.1 Critérios de escalonamento

A principal função do algoritmo de escalonamento é definir qual processo tem a prioridade de execução na CPU.
Cada sistema operacional precisa de um algoritmo adequado ao seu tipo de processamento. Um sistema em
jogo, por exemplo, precisa de um algoritmo que tenha como característica um tempo de resposta alto. Já um
sistema de impressão precisa que um algoritmo controle bem as filas de impressão.

Alguns critérios são determinantes para escolha de um algoritmo de escalonamento, tais como:

• Utilização da CPU: em quase todos os sistemas, a CPU deve estar ocupada na sua carga máxima, 100%.
Porém, critérios podem ser adotados para garantir uma melhor eficiência da CPU. Um sistema com 40%
de utilização do processador pode ser considerado um sistema de baixa utilização, mas um valor de 80%
pode ser considerado um nível ideal de utilização (STUART, 2011).

A utilização da CPU é dada pela fórmula: (a soma total dos tempos de processamento de cada processo)
/ (tempo total). Um sistema com três processos (A, B, C) com tempos de CPU 10, 20, 30 sendo processados
sequencialmente, tem como valor de utilização: (10+20+30) / (10+20+30) = 1 = 100%, ou seja, nesse sistema a
CPU terá 100% de utilização. Para explicitar a utilização da CPU, um servidor com um núcleo de processamento
utiliza 10 minutos de processamento de um tempo total de 20 minutos. Nesse caso, 10/20 = 0,5, ou seja, a CPU
tem 50% de utilização. Em outro exemplo, os mesmos tempos de processamento, porém um processador com 4
núcleos, então, teria 0,5/4 = 0,125, ou seja, 12,5% ocupada.

• Throughput: é a quantidade de processos que é processado num determinado intervalo de tempo. A

relação é direta, quanto maior o throughput melhor será o desempenho do sistema. Essas características
são desejadas em todos os sistemas. Um sistema que contém 3 processos e leva 20 segundos para
processá-los possui um throughput de (3/20) = 0,15, mas um outro sistema que processe esses mesmos 3
processos num intervalo de 40 segundos, (3/40), terá o throughput com valor igual a 0,075. Sendo assim,
o primeiro sistema seria mais desejável a um melhor desempenho.
• Tempo de retorno (turnaround): tempo total medido desde a admissão do processo na CPU até o seu término.
O tempo de retorno leva em consideração o tempo perdido na alocação de memória, fila de espera de
processos de pronto, processamento na CPU e nas trocas de contextos. Um sistema que possui um tempo
de processamento na CPU de 10s, tempo de chegada de 0s, leva exatos 10 segundos para ser executado
por completo, porém um segundo processo que chegue logo em seguida com tempo de chegada de 0s e
um tempo de processamento de 20s, terá o tempo de retorno em 30 segundos (10+0+20) = 30.

36
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

• Tempo de resposta: muito utilizado em sistemas interativos. O tempo de resposta é o tempo medido
entre a admissão e a primeira resposta do sistema. Um dispositivo de entrada ou saída pode limitar esse
tempo de resposta.

2.3.2 Algoritmos de escalonamento

Também conhecido como agendador de processos (sheduler), o escalonador de processos faz uso de algoritmos
(Figura 21) em sistemas operacionais para possibilitar que processos concorrentes sejam executados na CPU,
tanto os processos CPU-BOUND quanto os processos I/O-BOUND (TANENBAUM, 2016).

Figura 21 – Algoritmo de escalonamento

executando

Processo D

Processo D é escolhido

Escalonador

wait

Processo D
pronto
Processo C
Processo A
Processo B

Fonte: Elaborada pelo autor.

Diversos algoritmos são implementados de acordo com o sistema em uso. O escalonador tem que levar uma série
de condições em questão, ou seja, para projetar um Scheduler deve-se levar em consideração:

• Justiça: todos os processos devem ser processados em igualdade de condições, sem adiamento indefinido.

• Produtividade (100%): a maximização das tarefas por tempo tem que ser a maior possível, de preferência
em 100%.

• Previsibilidade: sempre usar o mesmo tempo e os recursos computacionais na execução da mesma tarefa.

• Tempo de resposta: minimizar ao máximo em sistemas interativos.

• Usuários: maximizar ao máximo em sistemas interativos.

• Sobrecarga (overhead): minimizar o desperdício de recursos.

37
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

• Balanceamento: balancear os recursos; devem ser balanceados no uso de recursos.

• Cumprimento dos prazos: sistema tem que atender no tempo correto as requisições.

• Proporcionalidade: Satisfazer as perspectivas dos usuários.

Sempre que um processo for bloqueado ou esperar um dispositivo de entrada e saída, o escalonador de processos
deve usar os algoritmos para definir qual processo deverá ter prioridade de execução.

Os algoritmos de escalonamento podem ser divididos em três categorias: lote, interativo, e de tempo real. Para
cada categoria há características determinantes, ilustradas no Quadro 5.

Quadro 5 – Categorias x Características

Categoria Características

Todos os sistemas Justiça

Aplicação da política

Equilíbrio
Sistema em Batch Throughput
Tempo de retorno

Utilização
Sistemas interativos Tempo de resposta

Proporcionalidade

Sistema de tempo real Cumprimento dos prazos

Previsibilidade

Fonte: Elaborado pelo autor.

2.3.3 Escalonamento não preemptivo

Os sistemas operacionais das primeiras gerações eram predominantemente por processamento em batch, ou
seja, não preemptivo. Cada processo que ganhava a CPU, tinha o direito de ser totalmente processado para
depois liberar a CPU para o próximo processo.

O sistema de processamento não preemptivo (batch) também pode ser exemplificado no processo de impressão.
Cada processo de impressão entra em uma fila de impressão (pool de impressão), e somente um por vez é atendido
e totalmente processado pelo sistema (TANENBAUM, 2016).

Existem alguns algoritmos que satisfazem um sistema em lote: primeiro a chegar, primeiro a sair (First IN First OUT),
o menor trabalho primeiro (Short Job First), próximo de menor tempo (Short Remaing Time Next) e Três níveis.

Um exemplo clássico de um sistema em batch é um backup de dados, pois é executado em lote sem a necessidade
de interação com o usuário.

38
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

2.3.3.1 Escalonamento FIFO (First IN First OUT)

Esse algoritmo satisfaz a condição de quem chega primeiro é atendido. Quando o processo está com a permissão
de ser executado pela CPU, ele é totalmente processado até o seu término, e só então, libera a CPU para o próximo
processo na fila, muito utilizado em um pool de impressão. Ou seja, numa fila de impressão, o processo que chega
primeiro na impressora é impresso (Figura 22). Outro exemplo são os circuitos eletrônicos de buffer e controle de
fluxo que usam o algoritmo FIFO para ler e escrever os dados.

Figura 22 – Escalonamento FIFO

CPU
P3 P2 P1

Chegada

Fonte: Elaborada pelo autor.

Imagine que cheguem na CPU três processos – A, B, C – com tempo de chegada 0, 2, 1 e tempos de processamento
24, 3, 4. A ordem de chegada é A-B-C, respectivamente.

Cada processo é executado por vez na CPU, mas seus tempos de espera são diferentes. O tempo de espera de A é
0s, ou seja, imediatamente é processado; o tempo de espera de B é de 22 segundos, ou seja, leva os 24 segundos
de processamento de A menos os 2 segundos de chegada. O tempo de espera do processo C é de 23 segundos,
pois leva os 24 segundos de A menos 1 segundo de C.

Nesse cenário, com a ordem de chegada (A, B, C), o tempo médio de espera total seria de 15 segundos (0 + 22 +
23/3 = 15).

No caso do tempo médio de execução, leva-se em consideração o tempo de cada processo de execução menos
o tempo de espera para ser executado. Nesse mesmo cenário, com ordem de chegada A, B, C, os tempos de
execução de cada processo seriam:

• Processo A: tempo total de execução - tempo de chegada: 24 - 0 = 24.

• Processo B: tempo total de execução - tempo de chegada: (24 + 3) - 2 = 25.

• Processo C: tempo total de execução - tempo de chegada: (24 + 3 + 4) - 1 = 30.

Então, o tempo médio de processamento seria (24 + 25 + 1)/3 = 16,66 segundos.

No modelo FIFO, o tempo de processamento leva em consideração o tempo do próprio processo + o tempo do
processo que estão à frente na fila de processamento.

2.3.4 Escalonamento SJF (Short Job First)

O tempo de execução do processo na CPU é determinante, pois é previamente conhecido pelo sistema operacional
(Figura 23). Esse tempo de processamento determina a ordem de chegada dos processos na CPU. Rotinas

39
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

diárias previamente conhecidas pelo tempo gasto em sua execução podem ser organizadas usando conceito do
algoritmo: trabalho mais curto primeiro. Esse algoritmo pode ser aplicado em sistemas que são orientados por
tarefas de entrada e saída como servidores de rede e compiladores.

Agora, imagine o mesmo cenário do exemplo FIFO. Nesse caso, o sistema tem que conhecer o tempo de
processamento previamente, pois esse tempo definirá a ordem de processamento. Então, a ordem seria B (3), C
(4), A (24), pois é determinada pelo tempo de execução de cada processo.

O tempo médio de espera seria (3 + 2 + 24 / 3 ) = 9,66s, e o tempo de execução de cada processo seria:
• Processo B: tempo total de execução - tempo de chegada: 3 - 0 = 3.
• Processo C: tempo total de execução - tempo de chegada: (3 + 4) - 1 = 6.
• Processo A: tempo total de execução - tempo de chegada: (3 + 4 + 24) - 0 = 31.
• Então, o tempo médio de processamento seria (3 + 6 + 31) /3 = 13,33 segundos.

Figura 23 – Escalonamento SJF

CPU
A C B

Chegada

Fonte: Elaborada pelo autor.

2.4 Escalonamento preemptivo

Os sistemas interativos, como o jogo, por exemplo, possuem diversos tipos de algoritmos que satisfazem o seu
objetivo. Todo algoritmo de sistema interativo pode ser usado em sistema em batch, com exceção do sistema em
três níveis, pois não é adequado.

Os algoritmos de interatividade são: Round-Robin, por prioridade, múltiplas filas, garantido, sorteio. Esses
algoritmos trabalham com alternância de processos na CPU.

2.4.1 Circular (Round-Robin)

No algoritmo de alternância circular (Figura 25), a cada processo é atribuído um tempo chamado de quantum.
Esse quantum é o tempo que esse processo tem de CPU a cada ciclo de processamento. Um processo que tem 10
segundos e um quantum de 2 segundos, irá ser processado em 5 vezes, alterando com outros processos na fila.
Após o seu processamento, ele é colocado no final da fila.

No filme Minority Report (2002), o ator principal interage com um sistema operacional multitarefa.
Diversas tarefas estão sendo escalonadas pelo sistema operacional. Vale a pena assistir ao filme e
avaliar as características do sistema operacional.

40
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Figura 24 – Round Robin

Quantum = 2

CPU
P3 P2 P3 P2 P1
4 2 6 4 2

Chegada
Tempo de processamento

Fonte: Elaborada pelo autor.

Nesse algoritmo o importante é o tamanho do quantum. A cada preempção, o sistema tem que registrar o tempo
gasto para a administração dessa troca de contexto (salvar, carregar registradores, mapas de memória, listas de
tabelas, etc.). A ideia é minimizar o tempo gasto pela troca de contexto. Um sistema que tem um quantum de 4ms
e um tempo de troca de contexto de 1ms, tem 20% do tempo gasto pela CPU só para fazer a troca de processos,
mas um sistema com um quantum de 99ms, tem, nesse mesmo cenário, 1% de perda na troca de contexto.

Agora, suponha que 10 usuários apertem a tecla Enter ao mesmo tempo, quanto tempo o último usuário levaria
para receber uma resposta? O conceito é estabelecer um balanceamento entre o tamanho do quantum e tempo
de troca de contexto, pois quantum pequeno gera muitas trocas e reduz a eficiência da CPU, e quantum longo,
gera demora nas requisições curtas em sistemas interativos A duração da fatia de tempo depende do sistema
operacional e do processador. Como cada fatia de tempo é pequena (aproximadamente 20 milissegundos),
vários segmentos parecem estar sendo executados ao mesmo tempo. No Linux Kernel 2.6, a fatia é de 20 ms; no
Windows, por sua vez, é de aproximadamente 15 ms:(STUART, 2011). O algoritmo Round_Robin é utilizado em
sistemas destinados à otimização de áudio e vídeo na internet.

Imagine agora (Figura 25), os processos A, B, C com os respectivos tempos de chegada (0, 2, 1), de processamento
(6, 3, 4) e quantum (tempo de processo na CPU) (2). Considere a ordem de chegada A, B, C. No algoritmo RR, cada
processo tem somente 2 (unidade de tempo) para serem executados na CPU; após esse tempo, o processo sofre
preempção e retorna para o fim da fila. Outro processo receberá os mesmos 2 ut para serem executados na CPU.
Então, o tempo de espera de cada processo será:

• Processo A: tempo de chegada = 0, pois, ao chegar à CPU, o processo começa.

• Processo B: tempo de chegada = 2, pois ele chega no tempo 2.

• Processo C: tempo de chegada = 1. Há dois outros processos sendo processados pela ordem de chegada
(A, B); nesse caso, será descontado o tempo de processamento dos processos: 4 - 1 = 3.

O tempo médio de espera será (0 + 2 + 3) /3 = 1,66.

O tempo de processamento de cada processo tem que levar em consideração a preempção, ou seja, a cada 2 ut,
o processo sofre uma preempção. Nesse caso, o tempo de processamento de cada processo seria:

• Processo A: tempo de processamento total - tempo de chegada - tempo de CPU = ( 13 - 0 - 6) = 7.

• Processo B: (9 - 2 - 3) = 4.

• Processo C: (11 - 1 - 4) = 6.

O tempo médio de processamento será (7 + 4 + 6) /3 = 5,66.

41
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Figura 25 – Aplicação do algoritmo RR

CPU

Processo C

Processo B

Processo A

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Tempo de chegada

Fonte: Elaborada pelo autor.

2.4.2 Por prioridade

No algoritmo por prioridade (Figura 26), a cada processo é atribuída uma prioridade, estaticamente ou
dinamicamente, e a política de prioridade (a mais alta primeiro ou a mais baixa primeiro) determina quem é
executado na CPU. Quando dois processos concorrentes chegam a CPU, o de maior prioridade ganha a CPU, mas
a cada interrupção do relógio, decrementa o valor da prioridade. Quando a prioridade do processo fica menor
que a prioridade do próximo processo, há uma alternância de processo, e o próximo passa ter a vez na CPU.
Entre dois processos, um envia em background e o outro exibe informações no vídeo, o segundo processo tem
prioridade sobre o primeiro, como gravar tem prioridade sobre impressão. O sistema por prioridade é utilizado
pelo Windows para determinar qual processo será processado ou tem a prioridade de execução. Outro exemplo,
é o sistema de retirada de fila bancária que determina prioridade para pessoas especiais (idosos, gestantes,
deficientes).
Figura 26 – Escalonamento por prioridade

Executando

Processo B

Escalonador, prioridade
mais alta em primeiro

Espera

Processo A
Prioridade = 3
pronto

Processo B Processo B
Prioridade = 4 Prioridade = 4

Fonte: Elaborada pelo autor.

Imagine agora (Figura 27) o seguinte cenário. Processos A, B, C com tempo de chegada 0, 0, 0 e tempo de
processamento na CPU 6, 4, 6, respectivamente. A ordem de chegada na CPU é A, B, C, porém com prioridades

42
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

diferentes (2, 3, 4, respectivamente). A permissão de execução na CPU é determinada pelo valor mais alto de
prioridade. A preempção será realizada a cada duas unidades de tempo na CPU, ou seja, quantum igual a 2.

O tempo de espera para início do processamento de cada processo será:

• Processo C: 0 s.

• Processo B: 2 s.

• Processo A: 4 s.

O tempo médio de espera será (0 + 2 + 4) /3 = 2.

O tempo de processamento de cada processo será:

• Processo C: (14 - 0 - 6) = 8.

• Processo B: (10 - 0 - 4) = 4.

• Processo A: (16 - 0 - 6) = 10.

O tempo médio de processamento será (8 + 10 + 4) /3 = 8.

Figura 27 – Aplicação do algoritmo por prioridade

CPU

Processo C

Processo B

Processo A

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Tempo de chegada
Quantum = 2

Processo Tempo de CPU Tempo de Chegada Prioridade

A 6 0 2
B 4 0 3
C 6 0 4

Fonte: Elaborada pelo autor.

2.4.3 Múltiplas filas

Como os sistemas possuem características diferentes de processamento, torna-se difícil que um único mecanismo
de escalonamento seja adequado a todos os tipos de processo.

43
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

O algoritmo por múltiplas filas (Figura 28) subdivide os processos em grupos de duas ou mais filas. Depois, prioriza
cada fila por meio de um algoritmo (qualquer algoritmo). Cada fila, individualmente, tem seu próprio escalonador
e um critério de prioridade.

Esse algoritmo é utilizado no agendamento de diferentes tipos de pacote – como pacotes de dados em tempo
real e não em tempo real –, em nós de sensores com restrições de recursos em redes de sensores sem fio (WSN) a
fim de reduzir o consumo de energia dos sensores e os atrasos na transmissão dos dados de ponta a ponta.
Figura 28 – Algoritmo de múltiplas filas

Executando
Proc D

Escalonador

Espera
Algoritmo entre filas

pronto

Fila 1 Fila 2
Algoritmo
Proc A Proc D por fila

Proc B Proc E

Fonte: Elaborada pelo autor.

2.4.4 Sorteio (loteria)

O algoritmo é semelhante a um sorteio de loteria. Porém, os prêmios são recursos do sistema. Esses recursos
podem ser, por exemplo, o tempo de execução na CPU atribuído a determinado processo (Figura 29). Na hora
da decisão, um sorteio aleatório é realizado e o processo ganhador tem um tempo x para executar todos os seus
recursos.

Nesse algoritmo, processos podem trocar bilhetes entre si, dando mais prioridade na execução das tarefas. Esse
algoritmo é altamente responsivo. Um servidor de vídeo pode ter taxa de alimentação com valores diferentes 10,
20, 25. Supondo que ele ganhe 10, 20, 25 bilhetes respectivamente, a CPU será dividida na mesma proporção do
tempo de execução 10:20:25.

Servidores consolidados com virtualização, os acessos a dispositivos de rede física de máquinas virtuais convidadas
precisam ser coordenados. Os dispositivos de rede virtualizados são necessário para atender às cargas de trabalho
executadas simultaneamente a partir de várias VMs, visto que é importante alocar largura de banda de E/S de rede
de forma justa e estável entre várias máquinas virtuais. O algoritmo de agendamento de loteria com base pode
ser usado para implementar o ajuste de largura de banda e atender ao agendamento proporcional dos requisitos
de entrega de dados de rede. Imagine dois processos (A e B): o processo A com 40 bilhtetes (1 a 40), e o processo B

44
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

com 20 bilhetes (41 a 60). O escalonador escolhe um número aleatório de 1 a 60. Então, se o escalonador sortear
um número de 1 a 40, o processo A é executado; entre 41 a 60, o processo B é sorteado.

Imagine que o escalonador tenha sorteado oito bilhetes nesse formato (10, 20, 40, 44, 55, 60, 3, 10). Nesse
cenário, os processamentos respectivamente seriam de A, A, A, B, B, B, A, A, ou seja, o processo A seria executado
cinco vezes, e o processo B, três vezes.

Figura 29 – Algoritmo por loteria

Executando O processo A ganha um tempo X

devido ao bilhete premiado 10
Processo A(10)

Escalonador sorteia 8 bilhetes

10(A), 20(A), 40(A), 44(B), 55(B),
60(B), 3(A), 10(A)
Espera

pronto

Processo A: bilhetes (1 a 40)

Processo B: bilhetes (41 a 60)

Fonte: Elaborada pelo autor.

2.4.5 Escalonamento SJRF (Short Job Remain First)

Nesse algoritmo, o tempo restante para processamento determina a ordem de execução dos processos na CPU
(Figura 30). Quando um processo chega a CPU, o sistema operacional verifica se o tempo total desse processo é
menor do que o tempo que falta para processar o processo (job) em execução. Caso seja menor, o job em execução
é suspenso e um novo é inicializado na CPU.

Esse sistema faz uma preempção (alternância) na escolha dos processos, porém todo o processo é executado.
Jobs curtos tem melhor desempenho e o tempo de processo tem que ser previamente conhecido (TANENBAUM,
2016). Esse algoritmo é uma versão preemptiva do algoritmo SJF onde trabalha com sistema que são orientados
a tarefas de entrada e saída como servidores de rede.

45
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Figura 30 – Algoritmo SJRT

Executando

Escalonador
Espera

pronto Processo B = 4s

Processo C = 7s

Processo A = 6s
Fonte: Elaborada pelo autor.

Esse algoritmo inicialmente utiliza o JOB; nesse caso (Figura 30), os processos seriam executados na ordem B, A e
C, porém com quantum no valor de 2 ut. Na segunda rodada de execução, o processo A teria 4 segundos restantes
de processamento; o processo B teria 4; e o processo C, 5 segundos. Considerando o menor tempo restante
em primeiro, o processo B seria executado em primeiro plano; depois, o A; por fim, o C. Agora, o processo B foi
finalizado. O escalonador definirá entre B e C para ser executado e escolherá o menor tempo ainda restante de
CPU. Nesse caso, restam 2 s para A e 3 s para C. O processo A será executado em primeiro e, por fim, o processo C.

2.5 Escalonamento de tempo real

Um sistema de tempo real não precisa ser ultrarrápido, mas precisa ter previsibilidade (ou seja, seu tempo de
resposta deve ser conhecido no melhor e pior caso de operação). Tempos de acesso a disco e sincronizações
excessivas são essenciais para minimizar esperas e latência.

Existem dois tipos de sistema de tempo real: softreal time e hardreal time. O Softreal time pode ser demonstrado no
som ou vídeo online, quando há atrasos é sentido pelo usuário na qualidade do som ou imagem, e o Hardreal time,
em que aperda de prazos pelo sistema pode perturbar o objeto controlado, com graves consequências humanas
ou ao ambiente, como sistemas de aviação (Figura 31) e sistemas hospitalares (UTI). São exemplos de sistema de
tempo real QNX, RT-Linux e VxWorks.

46
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Figura 31 – Exemplos de sistema de tempo de real

Fonte: SHUTTERSTOCK, 2018.

Algoritmos de sistemas de tempo real podem ser estáticos ou dinâmicos. O algoritmo estático toma a decisão de
escalonamento antes do início da execução das tarefas, o dinâmico em tempo de execução.

Um sistema de detecção de gás pode usar um algoritmo de tempo real para evitar incidentes, ou um sistema
de monitoração de conversas em tempo real para contagem de fonemas em tempo real e aplicativo para
monitoramento da taxa de fala.

Threads possuem escalonamento?

2.6 Políticas x Mecanismo

Mecanismo é o processo pelo qual o sistema operacional aplica os algoritmos de escalonamento. Políticas são
as estratégias de acordo com as premissas do usuário. Como premissas considera-se a atribuição, em nível mais
alto, de quantidade de memória a ser usada a cada processo. Como mecanismo considere as atribuições de nível
mais baixo, enviar ou receber um pacote de rede, alocar ou não memória para um determinado processo.

47
 Sistemas Operacionais | Unidade 2 - Gerência de Processos

Síntese da unidade
Nessa unidade, você aprendeu sobre os funcionamentos das tarefas que são executadas na CPU. No início da
unidade, conceitos sobre processos threads foram apresentados e suas características definidas.

Ainda nesta unidade, os contextos de processo foram definidos. Cada processo criado no sistema operacional
apresenta um estado. Entender o estado do processo determina a compreensão de como funciona a relação
entre processador e memória. Um processo em estado de execução está sendo executado na CPU, mas um
processo em estado de pronto permanece em memória.

Processos podem criar novos processos, esses processos criados são chamados processos-pai e suas crias
processo-filho. Um processo-filho pode criar um novo processo, e assim sucessivamente criando uma hierarquia.
Você compreendeu que thread são rotinas de programa utilizadas para melhorar o desempenho de sistemas
multitarefas. Threads contém o mesmo contexto de software, mas contextos de hardware diferentes. Os tipos de
arquivos CPU-BOUND e I/O-BOUND foram especificados.

Você ainda conheceu a importância de escalonador e dos algoritmos de escalonamento. Entendeu que existem
três categorias de sistemas: batch, interativo e tempo real. Características de cada categoria foram apresentadas
e definidas.

Por fim, o entendimento sobre a diferença entre mecanismo e política.

48
 Considerações finais
A cada geração os sistemas aumentam o volume de tarefas concorrentes
executadas ou controladas pelo sistema operacional. Esses sistemas ficam
mais sofisticados e os processadores são mais exigidos. Porém, os conceitos
primordiais de funcionamento são os mesmos. Entender o mecanismo de
agendamento dos processos pelo sistema operacional permite também
o entendimento da aplicação em outras áreas de conhecimento. Como
por exemplo, o algoritmo Round Robin que pode ser aplicado em sistemas
destinados à otimização de áudio e vídeo na internet.

49