USF_EAD_U2_Ambientes_computacionais

Prévia do material em texto

SÍLVIO PETROLI NETO
AMBIENTES COMPUTACIONAIS
30
Processos Computacionais
2
UNIDADE 2
PROCESSOS COMPUTACIONAIS
INTRODUÇÃO
Esse componente trabalha os conceitos de gerenciamento de hardware via software, ou 
seja, como o hardware desenvolvido a partir de circuitos digitais lógicos é gerenciado 
para ofertar ao usuário final toda sua capacidade de forma fácil e transparente.
Para isso, são trabalhados os seguintes assuntos:
01. Funcionamento de um Sistema Operacional, que é o principal software responsável 
pela gestão do hardware;
02. O funcionamento da Unidade Central de Processamento e dos processos computacio-
nais, por meio dos quais todas as tarefas são executadas com a utilização dos circuitos lógicos;
03. Sincronização e comunicação entre processos, em que será estudada a relação entre 
os processos e como eles compartilham e/ou disputam o uso dos recursos para realizar tarefas;
04. Gerenciamento e escalonamento da Unidade Central de Processamento, em que 
se estuda como é feita a divisão dos recursos de hardware com cada tarefa em execução.
Utilizando-se desses conceitos, pretende-se que sejam desenvolvidas as 
seguintes habilidades:
01. Compreender a função dos Sistemas Operacionais;
02. Entender o processamento e como o Sistema Operacional o gerencia;
03. Analisar os possíveis problemas gerados pela comunicação entre processos;
04. Entender o escalonamento da unidade central de processamento como forma de com-
partilhamento da Unidade Central de Processamento.
31
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
A unidade a seguir apresenta, portanto, de forma sucinta, como o computador gerencia 
seu próprio hardware através do uso de um software gerenciador de sistema (Sistema 
Operacional), quais são os desafios para esse gerenciamento e como são solucionados 
os principais problemas.
1. SISTEMAS OPERACIONAIS
Desde que foram criados, os computadores sempre foram máquinas que estiveram à 
frente de seu tempo no que tange a complexidade e o uso de alta tecnologia. A conjun-
ção de circuitos lógicos programáveis faz dos computadores máquinas genéricas, ca-
pazes de executar as mais diversas tarefas, sejam elas aritméticas ou lógicas. Porém, 
a utilização dessas máquinas requer um conhecimento muito amplo de eletrônica e da 
própria concepção dos sistemas que as compõem, tonando-se sua utilização para pou-
cos e, portanto, não escalável. A fim de tentar resolver esse problema, ou, ao menos, 
de minimizá-lo, surgem os softwares de sistema, capazes de entregar ao usuário final 
uma experiência mais simples de utilização do hardware. 
Sendo o computador uma máquina de níveis, em que o nível mais baixo representa o quão 
perto se está dos circuitos físicos e o nível mais alto representa a proximidade com o usu-
ário, pode-se definir os níveis de um computador como sendo (TANENBAUM, 2013, p. 3):
Nível 5 – Nível das linguagens orientadas para solução de problemas (Tradução);
Nível 4 – Nível da linguagem do montador (Assembly);
Nível 3 – Nível do Sistema Operacional (Interpretação parcial);
Nível 2 – Nível da arquitetura do conjunto de instruções (Micro programas);
Nível 1 – Nível da microarquitetura (Hardware);
Nível 0 – Nível da lógica digital.
32
Processos Computacionais
2
Pode-se perceber que, desde sua concepção enquanto circuitos lógicos combinados 
(nível 0) até a sua completa utilização pelo ser humano (nível 5), existe uma série de 
etapas a serem cumpridas. A cada etapa, existe um software associado, destinado a 
deixar mais simples o processo, desde softwares escritos em micro programação, até 
os mais complexos, escritos em linguagens modernas de alto nível. 
A Figura 1 mostra uma relação de softwares responsáveis pelo controle do computador, 
desde o hardware, até a entrega final ao usuário da máquina.
Figura 01. Relação hardware e software
Jogos
Editores Compiladores
Sistema Operacional
Firmware
Micro programação
Sistemas
Shell
Fonte: elaborada pelo autor.
Percebe-se que, para que uma máquina possa ser programada utilizando-se alto nível, 
existem várias camadas de software que ficam ocultas e cujo trabalho é disponibilizar, 
de forma transparente, toda capacidade computacional do hardware ao programador.
O foco de nossos estudos, aqui nesse capítulo, é o Sistema Operacional. Segundo 
Machado e Maia (2013, p. 3):
Um sistema operacional, por mais complexo que possa parecer, é apenas 
um conjunto de rotinas executado pelo processador, de forma semelhante 
aos programas dos usuários. Sua principal função é controlar o funciona-
mento de um computador, gerenciando a utilização e o compartilhamento 
dos seus diversos recursos, como processadores, memórias e dispositivos 
de entrada e saída. 
Ele é, portanto, um software como outro qualquer, que também concorre por recursos 
de máquina, mas que tem uma função primordial de fazer com que os usuários não pre-
cisem lidar com a complexidade do hardware, mas sim com funcionalidades disponíveis 
nesse hardware através de interfaces programadas para ofertar a operação de cada um 
dos componentes do hardware.
Stallings (2010, p. 241), ao definir os objetivos de um Sistema Operacional o define 
como uma interface entre o usuário final e o hardware do computador, controlando a 
execução dos aplicativos e possuindo dois objetivos principais:
33
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
coAssim, qualquer Sistema Operacional deve partir dos seguintes princípios:
 ` Conveniência: um Sistema Operacional visa tornar o uso do computador mais conveniente;
 ` Eficiência: um Sistema Operacional permite uma utilização mais eficiente dos recursos 
do sistema. 
Por fim, para Tanenbaum, um sistema computacional moderno consiste em algo bem am-
plo, contemplando desde o hardware, com um ou mais processadores, memória, discos, 
dispositivos de entrada e saída e interfaces de rede e que os Sistemas Operacionais são 
os sistemas cujo trabalho é gerenciar isso tudo, fornecendo aos programas de usuário um 
hardware com interface bem mais simples (TANENBAUM; BOS, 2016, p. 1).
Para entender como se dá esse processo de gerenciamento de hardware e fornecimento 
de uma interface simples ao usuário, iniciaremos com o estudo dos processos computacio-
nais (tarefas em execução em um sistema), como esses processos interagem entre si e dis-
putam recursos, e como o controle desses recursos é controlado pelo Sistema Operacional.
2. PROCESSOS
Existem muitas formas de se definir processo computacional. A maioria dos autores 
trata processo como um programa em execução (TANENBAUM; BOS, 2016, p. 27; 
SILBERSCHATZ; GALVIN; GAGNE, 2015, p. 61). Porém, também há um consenso 
entre todos os autores que essa definição é simplista demais. Um processo é, além da 
representação de um programa em execução, com todo o código envolvido na execu-
ção de uma determinada tarefa, o conjunto de todos os recursos necessários para a 
execução, o que envolve todos os registradores e o próprio processador, endereços de 
memória, dispositivos de entrada e saída, enfim, tudo o que uma tarefa necessitar para 
ser executada em um meio computacional é o que define um processo computacional.
Além da definição de processos computacionais, faz-se necessária aqui, a definição de 
alguns termos que serão utilizados ao logo da explicação de como os processos com-
putacionais funcionam.
O primeiro conceito importante é a definição de thread. Em tradução livre, thread pode ser 
traduzida como linha, corda, enfim, algo sequencial. A ideia de uma thread como conceito 
de Sistemas Operacionais é de uma linha de execução, ou seja, o processo, passo 
 ` Oferecer, de forma simples e transparente, todos os recursos do computador;
 ` Buscar a eficiência na utilização do computador, gerenciando a utilização de todos os 
seus recursos;
 ` Garantir a segurança e a integridade dos dados armazenados e/ou processados pelo computador.
34
Processos Computacionais
2
a passo, desde o início da execução deuma tarefa, até sua finalização, é chamado de 
thread. Assim, é possível pensar que um processo é composto por uma ou mais threads. 
Antes de entender melhor o conceito de thread, vamos definir o conceito de multipro-
gramação, ou multitarefa. Hoje, praticamente todos os sistemas operacionais são mul-
titarefa, o que significa que eles podem executar várias tarefas simultaneamente. Mas 
como seria possível executar duas ou mais tarefas ao mesmo tempo, se não temos, na 
maioria das vezes, mais do que um processador? Nesse sentido, é necessário entender 
que existe um conceito de pseudoparalelismo, ou seja, mesmo o computador possuindo 
apenas um único processador, devido à sua velocidade, é possível, dentro de um tempo 
bem curso, executar diversos comandos.
Suponha que você está sendo atendido por alguém enquanto faz compras, por exemplo. 
Imagine que você chegou à loja, o vendedor se apresentou, você fez o pedido a ele do tipo 
de roupa que desejaria ver. Ele te entregou algumas peças e pediu para que as você prove, 
enquanto isso, ele foi pegar mais algumas peças que achou que poderiam ser de seu gosto. 
Enquanto você provava as roupas, o mesmo vendedor iniciou a conversa com outro cliente, 
de forma que você nem percebe que ele está atendendo mais alguém além de você. Devido 
à versatilidade e agilidade do vendedor, toda vez que você necessita dele para alguma coi-
sa ele está sempre presente e te atende de forma que você fique muito satisfeito e, por sua 
vez, o outro cliente que está sendo atendido por ele tem a mesma impressão. Nem você 
sabe da existência do outro cliente nem o outro cliente sabe da sua existência.
Esse exemplo representa uma analogia do que acontece em sistemas multitarefas. A 
velocidade de um hardware computacional é tão grande que, em um tempo bem razo-
ável (tempo de resposta), vários processos são atendidos e recebem seus resultados 
parciais ou finais. Assim, um único processador é capaz de executar, de forma simul-
tânea, mas não paralela, um conjunto bem grande de tarefas e, a essa capacidade, 
daremos o nome de multitarefa ou multiprogramação. 
Nesse ponto é preciso deixar claro que multiprogramação ou multitarefa é diferente de mul-
tiprocessamento. O multiprocessamento requer a existência de vários processadores, exe-
cutando vários processos de forma absolutamente paralela. Já, na multiprogramação, um 
único processador, usando de sua velocidade, mesmo atendendo a um processo de cada 
vez, consegue atender a vários dentro de um tempo de resposta considerado razoável.
Sabendo disso, é possível perceber que podem existir, ao mesmo tempo, vários processos em 
execução, cada um com sua thread específica; mas também é possível imaginar que um mes-
mo processo possa executar, de forma concorrente ou simultânea, várias threads. Como exem-
plos, pense primeiramente em um processo que executa uma planilha na qual você esteja tra-
balhando e outro processo que execute uma música que você ouve enquanto trabalha. Nesse 
caso, temos dois processos, que aparentemente estão ocorrendo simultaneamente, mas que 
estão sendo executados separadamente. O processador atende parte do processo que executa 
a planilha, em seguida executa parte do processo que executa a música e volta a atender parte 
do processo que executa a planilha, repetindo isso sucessivamente e de forma bem rápida.
Isso vai fazer com que o usuário não tenha a percepção dessa ruptura (processo 1 dei-
xa de ser atendido para que o processo 2 seja atendido). Ao mesmo tempo, fica claro 
que cada processo executa sua tarefa específica, ou seja, uma única thread.
35
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Agora, suponha um mesmo processo que permita a você ouvir música enquanto trabalha 
na sua planilha. Esse processo pode lançar mão de duas threads, duas linhas de execu-
ção independentes, que concorrem pelo recurso computacional. Uma vez que essas duas 
threads fazem parte de uma mesma tarefa, elas serão trabalhadas em um único processo.
A vantagem da utilização de multithreadem em vez de utilizar dois ou mais processos é 
que a criação de um processo requer tempo de execução e uso extra de recursos, como 
memória, por exemplo. Segundo Berenger e Paulo (2011, p. 46):
O conceito de thread foi introduzido na tentativa de reduzir o tempo gasto em 
criação, eliminação e troca de contexto de processos nas aplicações concor-
rentes, bem como economizar recursos do sistema como um todo. Em um am-
biente multithread, um único processo pode suportar múltiplos threads, cada 
qual associado a uma parte do código da aplicação [...]. Nesse caso, não é 
necessário haver diversos processos para a implementação da concorrência. 
Existem, portanto, uma relação entre esses conceitos: todo sistema multiprocessado 
é, obrigatoriamente, um sistema multiprogramado (também chamado de multitarefa ou 
multiusuário). Porém, nem todo sistema multiprogramado precisa ser, necessariamen-
te, multiprocessado. É possível usar do conceito de pseudoparalelismo para implemen-
tação de multiprogramação mesmo em sistemas com um único processador, seja esse 
sistema multiprogramado multithread ou não.
Como dito anteriormente, a criação de um processo requer a execução, por parte do 
Sistema Operacional, de um conjunto de procedimentos, que executam todas as tare-
fas necessárias para alocar esse processo na memória e colocá-lo na fila de execução. 
Conceitualmente, um processo pode criar outros processos, o que remete à ideia de um 
processo pai (aquele que cria o subprocesso) e um processo filho (que é criado a partir do 
processo pai). Esse processo gera uma árvore de processos, como mostrado na Figura 2. 
Figura 02. Árvore de processos
P1
P2 P3
P4 P5 P6
Fonte: elaborada pelo autor.
36
Processos Computacionais
2
Nesse caso, é possível perceber que, ao eliminar o processo pai (P1), todos os proces-
sos filhos serão eliminados automaticamente.
O estudo dos processos computacionais é muito importante, uma vez que a razão de 
ser de um computador é a execução de tarefas e que a eficiência com que essas tarefas 
utilizam os recursos ditará quantas tarefas poderão ser executadas simultaneamente e 
a velocidade com que apresentarão as respostas (seus resultados).
Uma vez que os sistemas podem executar, de forma simultânea, mais de um processo, 
teremos duas categorias de processo:
Processos sequenciais, nunca existindo dois processos em execução em um mesmo 
período. Eles ocorrem um de cada vez no tempo, como mostrado na Figura 3.
Figura 03. Processos sequenciais
P1 P2 P3
Fonte: elaborada pelo autor.
Embora pareça viável que todos os processos aconteçam dessa forma, evitando-se 
problemas de concorrência por recursos, por exemplo, sistemas desse tipo apresentam 
uma ociosidade muito grande de recursos computacionais, diminuindo a produtividade 
do sistema como um todo.
37
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Processos paralelos, que ocorrem simultaneamente em um mesmo período. A Figura 
4 representa a ocorrência desse tipo de processo.
Figura 04. Processos paralelos
P1 P2
P4 P5
P6
P3
Fonte: elaborada pelo autor.
Como não se consegue prever como os processos ocorrerão, o Sistema Operacional 
deve ser capaz de lidar com a ocorrência de processos paralelos que, embora mais 
complexos, permitem a utilização mais eficiente dos recursos computacionais, diminuin-
do a ociosidade e aumentando a produtividade.
Além disso, a forma como esses processos são executados acarretam que eles aca-
bem, em algum momento, disputando os recursos finitos da máquina entre si. Assim, os 
processos paralelos podem ser de três tipos:
 ` Independentes, quando não disputam recursos entre si;
 ` Cooperantes, quando dois ou mais processos utilizam um determinado conjunto de re-
cursos para completarem uma dada tarefa;
 ` Concorrentes, quando pretendem utilizar os mesmos recursos. Nesses casos, há neces-
sidade de existirem ações do Sistema Operacional para determinarqual dos processos 
terá o privilégio de utilizar o recurso e qual deverá aguardar pela liberação do mesmo.
38
Processos Computacionais
2
Sabendo que podem existir vários processos em execução simultaneamente 
mesmo em sistemas com um único processador, percebe-se que nem todos os 
processos podem estar utilizando o processador ao mesmo tempo, apesar de 
estarem todos em processo de execução. Então, para que isso ocorra, os proces-
sos em execução precisam estar em estados distintos, em que apenas um utilize, 
de fato, o processador (SILBERSCHATZ; GALVIN; GAGNE, 2015, p. 62). Os es-
tados possíveis são:
 ` Execução: se o processo se encontra nesse estado, ele está utilizando o processador 
nesse momento. Em sistemas monoprocessados e multiprogramados, apenas um único 
processo pode estar nesse estado em um período;
 ` Pronto: se o processo está pronto para execução (não existe nada que o impeça), mas 
ele não pode utilizar o processador, porque outro processo está fazendo essa utilização, 
dizemos que o processo está nesse estado. Vários processos podem estar nesse estado, 
havendo um controle que organiza quem será o próximo a ir para execução;
 ` Bloqueado: se o processo necessita de um recurso que não está presente no momento, 
ele é colocado no estado bloqueado. Isso ocorre para que o processo não fique ocupando 
lugar de outro no processamento, uma vez que ele não conseguirá executar sua tarefa 
por falta de algum recurso.
A Figura 5 mostra um diagrama indicando os estados possíveis para os processos 
e as formas de transição que existem entre eles. Nela, é possível perceber que, 
quando o processo é criado, ele entra automaticamente em execução. Não há 
como um processo ser criado sem que ele utilize o processador para isso. Então, 
em sistemas multiprogramados, existem duas possibilidades a partir daí, ou o pro-
cesso executa até o fim e é finalizado ou ele executa por um período pré-definido 
de tempo (chamamos essa forma de execução de tempo compartilhado) e, ao 
finalizar esse tempo, o processo é transferido para o estado pronto, em que entra 
em uma fila de espera, aguardando sua vez de entrar em execução novamente. A 
cada período de tempo, um processo que está no estado pronto passa ao estado 
de execução e outro que estava em execução, ou termina ou volta para o estado 
de pronto, formando um ciclo de execução.
39
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Figura 05. Estados do processo
EXECUÇÃO 
BLOQUEADOPRONTO
Processo 
criado 
Tempo 
esgotado
Processo 
Finalizado
Recurso 
disponível
Despacho do 
escalonador
Recurso disponível 
novamente 
Fonte: elaborada pelo autor.
O ciclo de execução só será diferente se o processo necessitar de um recurso que não 
esteja disponível. Nesse caso, em vez de ir para o estado pronto, aguardar pela próxima 
oportunidade de utilizar o processador, o processo passa para o estado bloqueado e fica 
nele até que o recurso que ele necessita para continuar a execução volte a estar dispo-
nível. Para exemplificar esse caso, suponha que um determinado processo necessite 
utilizar a internet, por exemplo. Se não há internet no momento da execução, o processo 
é bloqueado por falta de recurso e aguarda lá até que a internet volte a estar disponível.
Não há, portanto, como existir uma transição do estado pronto para o estado bloquea-
do, uma vez que, para saber se o recurso está ou não disponível, o processo precisa 
estar em execução. Só assim ele requisitará o recurso e descobrirá que, naquele mo-
mento, o recurso não se encontra disponível.
A transição do estado bloqueado diretamente para o estado de execução é possível, porém, 
não é muito usual e, por isso, não foi representado na Figura 5. O mais comum é que, ao re-
ceber a notificação de que o recurso que necessitava voltou a estar disponível, o processo 
vá para a fila de processos prontos, aguardar a sua vez de entrar em execução.
40
Processos Computacionais
2
A única transição que é controlada pelo próprio processo é a transição do estado execu-
ção para o estado pronto. Todas as demais são controladas por agentes externos (agen-
tes do próprio Sistema Operacional). O mais conhecido agente é o escalonador de pro-
cessos, que determina quando e de que forma, os processos que estão no estado pronto 
serão selecionados para a execução e falaremos melhor desse recurso no capítulo 4.
3. SINCRONIZAÇÃO E COMUNICAÇÃO ENTRE PROCESSOS
Uma vez que os processos podem executar de forma simultânea e que os recursos que 
eles necessitam para essa execução são limitados, a própria existência desses vários 
processos vai causar concorrência entre eles. Portanto, a multiprogramação, apesar de 
trazer benefícios já citados, como o uso mais adequado dos recursos e a maior produti-
vidade, também traz inúmeros desafios e é exatamente sobre esses desafios que esse 
capítulo sobre a sincronização e a comunicação entre os processos trata.
3.1 SITUAÇÃO DE CORRIDA
Para entender o primeiro desses desafios, precisamos entender o que é região crítica. 
Sempre que existir algum recurso que não pode, não importa por qual motivo, ser aces-
sado por dois processos simultaneamente, esse recurso será chamado de região críti-
ca. Então, a região crítica pode ser, por exemplo, uma porção de memória, um trecho 
de código ou até mesmo um recurso físico.
Toda vez que dois ou mais processos tentarem fazer acesso a essa região crítica, cha-
maremos de situação de corrida e toda vez que, dada uma região crítica, sempre que um 
processo fizer acesso a ela, os demais processos fiquem impedidos de acessá-la teremos 
um processo de exclusão mútua. Assim, o que queremos em um sistema multitarefa é evi-
tar situações de corrida e promover a exclusão mútua em regiões ou seções de corrida.
Por outro lado, se um dado recurso pode ser acessado sem problemas por mais de um 
processo, esse recurso é chamado de código reentrante. 
Não há necessidade de se preocupar com esses nomes todos, mas é importante que se 
conheça o processo para poder entender os desafios ao se utilizar um sistema multitarefa.
Suponha, por exemplo, que exista duas esteiras, cada uma transportando pacotes em 
uma empresa de logística. O que se deseja é contar o número de pacotes que passam 
em cada uma das esteiras, somando-os, para obter um valor final de pacotes que foram 
embalados. Para isso, existe um sensor em cada esteira, que identifica a passagem 
de pacotes por ela. Suponha, ainda, que cada vez que um pacote passa por cada um 
desses sensores, eles atualizem a mesma variável contador, responsável por acumular 
a contagem desses pacotes.
Sabemos que o processo de atualização de uma variável segue os seguintes passos 
distintos, conforme mostra o Código 1:
41
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Código 1 - Etapas (microinstruções) para atualizar um valor
1. Ler o valor atual da variável;
2. Atualizar o valor lido;
3. Atualizar o valor da variável com o valor atualizado.
Fonte: elaborado pelo autor.
É preciso entender que mesmo o incremento do valor de uma variável não ocorre de 
forma indivisível. Se baixarmos o nível e formos de um alto nível (nível 5) para um baixo 
nível (nível 1), por exemplo, veremos que uma simples expressão matemática A = A+1 
será representada no nível mais baixo por um conjunto de microinstruções.
Antes de continuarmos com o nosso exemplo, precisamos definir preempção. Apesar 
do nome complicado, dizemos que um sistema é preemptivo se for possível retirar um 
recurso de um processo e não preemptivo se não pudermos, em hipótese alguma, re-
mover um recurso de um processo. 
Em um exemplo de sistema preemptivo, mesmo um processo possuindo um tempo de 
execução de vários segundos, ele pode usar o processador em tempos de um segundo 
e, ao final desse segundo, o processador é retirado dele para que outro processo possa 
utilizá-lo e esse primeiro processo volta a disputar o uso do processador para executar 
o tempo que ainda ficou faltando.Então, se o processador é um recurso e estamos 
trabalhando com um sistema multitarefa em que esse processador precisa ser compar-
tilhado, a única forma de garantir que todos os processos executem simultaneamente é 
impedindo que um determinado processo monopolize o uso do processador, retirando 
esse recurso do processo a cada período estimado, conforme foi explicado na Figura 5.
Voltando ao nosso exemplo, vamos supor agora que o valor inicial da variável contador 
seja 0 (zero) e que a esteira um faça a primeira leitura de um pacote passando pelo seu 
sensor. Ela executará as etapas apresentadas no Código 1. Lerá o valor 0 (zero), atuali-
zará o valor para 1 (um) e atualizará a variável contador com o novo valor. Então, a partir 
daqui contador que antes valia 0 (zero) agora vale 1 (um). O mesmo pode ocorrer com a 
segunda esteira, que, ao receber um novo pacote, lerá o valor 1 (um) no contador, incre-
mentará para 2 (dois) e atualizará o valor do contador, que agora passa a valer 2 (dois).
Porém, suponha que um novo pacote passe pela primeira esteira novamente e que ela 
leia o novo valor do contador, que agora é 2 (dois), incremente esse valor para 3 (três), 
mas antes de atualizar o valor da variável contador, o processo que controla a primeira 
esteira sofra preempção. O processo que controla a primeira esteira guarda todos os 
valores de seu estado atual, em um processo que chamamos de armazenamento de 
contexto e passa para o estado pronto. Lembrem-se de que, nesse momento, o pro-
cesso precisa apenas pegar o novo valor que ele já tem (que é o valor 3) e atualizar 
o contador. Mas ele foi impedido de atualizar o contador, já que seu tempo de uso do 
processador terminou. Então, enquanto o processo da primeira esteira encontra-se no 
42
Processos Computacionais
2
estado pronto, um novo pacote passa pela segunda esteira e ela entra em execução. A 
segunda esteira consegue fazer todo o processo, lê o valor do contador, que continua 
sendo 2 (dois) já que a primeira esteira não conseguiu atualizá-lo, incrementa para 3 
(três) e a atualiza o valor. 
Nesse ponto, o valor do contador é 3 (três) e o processo que controla a primeira esteira 
volta para a execução com a missão de apenas atualizar o contador para que finalize a 
tarefa. O processo já havia calculado o novo valor (que era 3) e faz a atuação do conta-
dor para 3 (três). É possível perceber que dois objetos passaram pela esteira, portanto 
o contador deveria estar marcando o valor 4 (quatro), porém, como houve preempção 
do processo da primeira esteira, perdeu-se a contagem de um pacote.
Esse exemplo exemplifica bem o problema de concorrência entre processos. Nesse 
caso, a variável contadora é uma região crítica e não poderia ser acessada simultane-
amente pelos dois processos.
Conforme afirmam Tanenbaum e Bos (2016, p. 83):
[...] às vezes um processo tem de acessar uma memória compartilhada ou 
arquivos, ou realizar outras tarefas críticas que podem levar a corridas. Essa 
parte do programa onde a memória compartilhada é acessada é chamada 
de região crítica ou seção crítica. Se conseguíssemos arranjar as coisas de 
maneira que jamais dois processos estivessem em suas regiões críticas ao 
mesmo tempo, poderíamos evitar as corridas. 
Existem duas dessas maneiras indicadas por Tanenbaum e Bos (2016) para evitar situações 
de corrida. Uma delas é realizada por hardware, com a criação de uma operação capaz de 
incrementar e atualizar o valor de uma variável de forma indivisível. Assim, o procedimento 
não pode ficar pela metade. Isso chegou a ser implementado, com a criação das instruções 
TST (Test and Set) e TSL (Test and Set Lock). Porém, em 1981, G. L. Peterson descobriu 
uma maneira muito mais simples de realizar exclusão mútua (TANENBAUM; BOS, 2016, p. 
85). Peterson desenvolveu um algoritmo (Código 2), chamado de protocolo de acesso, que 
define basicamente que, se existe uma região crítica e um processo já está fazendo uso 
dessa região, os demais processos são impedidos de acessá-la (exclusão mútua).
Código 2 | Exemplo de Solução de Peterson para 2 processos
#define FALSE 0
#define TRUE 1
#define N 2
intturn;
intinterested[N];
43
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Fonte: adaptado de Tanenbaum e Bos (2016, p. 86).
voidenterregion(intprocess) {
intother = 1 - process;
interested[process] = TRUE;
turn = process;
while (turn==process&&interested[other]==TRUE);
}
voidleaveregion(intprocess) {
interested[process] = FALSE;
}
3.2 DEADLOCK
O segundo desafio causado pela concorrência entre os processos está também rela-
cionado ao fato de dois processos serem impedidos de acessarem o mesmo recurso. O 
computador está cheio de recursos que só podem ser acessados por um processo de 
cada vez e, por isso, é tão importante que os problemas causados por esses acessos 
simultâneos sejam conhecidos e tratados.
O problema que trataremos agora é um desses, mas, diferente da situação de corrida, 
em que existe um recurso que não pode ser acessado por dois processos simultane-
amente, o problema que chamaremos de deadlock é causado quando um processo é 
impedido de fazer acesso a um recurso que seja de uso exclusivo porque outro proces-
so já faz uso dele.
Até esse momento tudo bem, pois podemos imaginar em criar uma fila e, após o primei-
ro processo fazer acesso ao recurso, ele o liberará e esse será utilizado pelo segundo 
processo. Porém, existem casos em que o primeiro processo nunca liberará o recurso. 
Como exemplo, suponha que um determinado primeiro processo, que chamaremos 
de processo A precisa usar o Scanner para copiar uma determinada imagem e depois 
gravá-la em uma fita de backup. E que um outro processo, que chamaremos de proces-
so B precisa fazer exatamente o mesmo processo. Suponha, ainda, que o processo A 
requisita o Scanner primeiro e começa a cópia da imagem e que o processo B, uma vez 
que o Scanner está ocupado, requisita a fita de backup para garantir seu uso assim que 
o Scanner estiver liberado. Para finalizar o uso do Scanner, o processo A vai precisar da 
fita de backup, para poder armazená-la, mas o processo B, para liberar a 
44
Processos Computacionais
2
fita de backup precisa da liberação do Scanner. Percebe-se, aqui, um impasse criado 
entre o processo A e o processo B. Esses processos entram em um estado crítico em 
que um depende do recurso que o outro detém e, por sua vez, não libera o recurso de 
que o outro precisa. Essa situação não tem solução fácil e chamamos esse impasse de 
deadlock (TANENBAUM; BOS, 2016, p. 302).
O deadlock não deve ser confundido com um problema de adiamento infinito, embora 
ele possa causar adiamento infinito. O problema do adiamento infinito ocorre quan-
do um processo é sistematicamente impedido de utilizar um determinado recurso. Por 
exemplo, suponha um cruzamento de duas vias de trânsito em que não haja semáforo. 
Pelas regras de trânsito, se dois carros chegarem ao mesmo tempo, a preferência será 
dada ao veículo que se encontra à direita. Agora, suponha o caso mostrado na Figura 6:
Figura 06. Analogia para adiamento infinito
V1
V3
V2
V4
Fonte: elaborada pelo autor.
Se os quatro veículos chegarem exatamente ao mesmo tempo e, seguido a lei de trân-
sito, quem tem o direito de seguir, uma vez que, para cada veículo, sempre existe outro 
à sua direita, que terá preferência? Esse caso ilustra bem o problema de adiamento 
infinito. Todos estão prontos para passar, mas, ao mesmo tempo, ninguém passa. Em 
termos computacionais, todos podem usar o recurso, mas todos estão, ao mesmo tem-
po, impedidos de utilizá-lo, mesmo o recurso continuando livre. A solução do problema 
de adiamento infinito é mais simples, porque um processo não depende de um recurso 
45
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
que está com outro processo e que dependerá de uma ação do primeiro processo para 
liberá-lo. Essa cadeia circular que se forma, de um processo dependendo de umaação 
do outro, enquanto o outro depende de uma ação do primeiro é o que caracteriza dea-
dlock e o diferencia de adiamento infinito.
Para ilustrar, criaremos um diagrama em que o processo é representado por um círculo 
e o recurso por um quadrado. Uma seta saindo do recurso em direção ao processo, sig-
nifica que o processo detém a utilização do recurso e uma seta saindo do processo em 
direção ao recurso significa que o processo requisita acesso ao recurso. Chamaremos 
esse diagrama de diagrama de processos (TANENBAUM; BOS, 2016, p. 304). A Figura 
7 ilustra um caso em que temos vários processos alocando vários recursos. Porém, 
esse diagrama mostra que não há ocorrência de deadlock.
Figura 07. Exemplo diagrama de processos
P1
R1 R5
R4
R3
R2
P3
P2
P4
Fonte: elaborada pelo autor.
Embora fique clara a disputa, quando o processo P4 utilizar o recurso R4, ele o liberará 
e o recurso R4 será então utilizado pelo P3 que, ao terminar, liberará tanto R4 quanto 
R3. Nesse momento, o processo P1 utilizará os recursos R1, R2 e R3 e os liberará em 
seguida, quando o recurso R1 poderá ser utilizando em conjunto com o recurso R5 pelo 
processo P2, finalizando a execução de todos os processos sem nenhum problema.
46
Processos Computacionais
2
Agora, observe o diagrama apresentado na Figura 8. É possível perceber a formação 
de uma cadeia, um ciclo, que indica que o processo P1 requer o recurso R1 sendo 
detentor do recurso R2 e só liberará o recurso R2 quando obtiver o recurso R1. O pro-
blema é que o recurso R1 pertence ao processo P2, que só o liberará quando obtiver 
acesso ao recurso R2. Isso forma um ciclo que não será quebrado a não ser por inter-
ferência externa.
Figura 08. Exemplo formação de deadlock
R1
R2
P1 P2
Fonte: elaborada pelo autor.
Existem, basicamente, quatro condições para que os deadlocks ocorram e essas con-
dições devem surgir simultaneamente para que isso ocorra (SILBERSCHARTZ, 2015, 
p. 170). São elas:
 ` Exclusão mútua: ao menos um dos recursos deve apresentar a necessidade de ser 
acessado por um único processo de cada vez;
 ` Retenção e espera: um processo deve possuir um recurso e estar aguardando por outro 
recurso enquanto mantém a posse do primeiro;
47
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Vemos, portanto, que a formação de deadlocks depende de todas as quatro condições 
ocorrendo em conjunto, ou seja, não é algo que acontece com frequência. Porém, é um 
problema que pode causar a queda total de um sistema computacional.
Para prevenir a formação de deadlocks, deve-se basicamente evitar que as condições 
apresentadas acima ocorram. Analisaremos cada uma das condições para verificar a 
possibilidade de preveni-las (SILBERSCHARTZ, 2015, p. 173):
 ` Inexistência de preempção: um recurso não pode ser retirado de um processo antes do 
seu término;
 ` Espera circular: existe uma fila de processos em que um está esperando o recurso que 
o seguinte detém, formando um círculo fechado, parecido com o mostrado na Figura 8.
 ` A prevenção da exclusão mútua é praticamente impossível em um sistema computacio-
nal. Isso implicaria na inexistência de recursos que requerem acesso exclusivo e existem 
recursos que são intrinsicamente não compartilháveis.
 ` Para evitar retenção e espera existem dois casos possíveis: o primeiro é obrigar os pro-
cessos a indicarem quais recursos eles utilizarão já na sua criação e, dessa forma, permi-
tindo ao Sistema Operacional fazer uma previsão se esses recursos estarão disponíveis. 
Essa alternativa é complexa, porque obriga os programadores a indicar quais recursos 
serão utilizados a priori e isso nem sempre é possível, sem contar que eles podem mentir, 
apenas para garantir a execução do seu processo, superestimando o uso de recursos e 
causando problemas; a segunda maneira é fazer com que os processos apenas possam 
solicitar novos recursos ao liberarem os recursos que já possuem, o que também não é 
fácil de implementar, uma vez que, muitas vezes, dois ou mais recursos precisam ser 
utilizados simultaneamente para a execução de uma determinada tarefa;
 ` Para evitar a inexistência de preempção, o que pode ser feito é uma cópia do estado 
atual do recurso em uso por um processo e sua retirada, caso seja requisitado por outro 
processo, devolvendo-o ao processo original e usando a cópia para que seja retomado 
seu uso de onde parou. Porém, só é possível em casos nos quais os recursos permitam 
essa cópia;
 ` Para evitar a espera circular, pode-se criar uma ordem absoluta de uso dos recursos. Nu-
meramos, por exemplo, os recursos de 1 a n, onde n é o número de recursos disponíveis. 
A partir daí, cada recurso tem um número absoluto, que o representa, existindo o R1, o 
R2, o R3 e assim sucessivamente. Se obrigarmos que qualquer processo requisite recur-
sos sempre respeitando essa ordem, evitamos a existência de espera circular. 
Como visto, prevenir o aparecimento de deadlock depende de várias condições, nem 
sempre fáceis. Então, uma das maneiras de se tratar deadlock é deixar que eles acon-
teçam, apostando que a chance de ocorrerem é pequena, desde que haja número de 
48
Processos Computacionais
2
recursos suficientes para a execução das tarefas principais de um sistema computacio-
nal, e utilizar mecanismos de recuperação, caso ocorram.
Existem algumas possibilidades de recuperação de deadlocks, lembrando que, nem 
sempre, são operações simples e, quase sempre, causam algum tipo de trauma e perda 
a algum processo ou até mesmo ao sistema como um todo (TANENBAUM; BOS, 2016, 
p. 310). São elas:
 ` Recuperação mediante preempção: nada mais é que a retirada de um determinado re-
curso de um processo para quebrar a fila circular formada. Analogamente, é como retirar 
o brinquedo que está causando a briga entre duas crianças até que elas voltem a brincar 
normalmente e deixem de brigar e, aí sim, devolver o brinquedo. Retirar um recurso pode 
causar uma demora na finalização de um ou mais dos processos envolvidos, mas certa-
mente essa demora é menos traumática do que deixar o deadlock acontecer;
 ` Recuperação mediante retrocesso: como a chance de ocorrência de deadlock é peque-
na, pode-se guardar pontos em que o sistema pode regredir, ou seja, definir momentos 
em que o sistema todo pode regredir antes da ocorrência do deadlock e imaginar que uma 
nova execução a partir desse ponto tem uma chance grande de não levar novamente ao 
deadlock. Aqui, existe a dificuldade de guardar esses pontos de recuperação e o atraso 
causado por esse retrocesso;
 ` Recuperação mediante eliminação de processos: como a existência de um deadlock 
pode causar uma fila circular em que mais e mais processos possam se envolver, até cau-
sar a parada total do sistema, uma das formas de recuperação de deadlock é eliminar um 
dos processos envolvidos no problema, obrigando-o a reiniciar. Nesse caso, sacrifica-se 
um dos processos em prol do sistema.
Analisaremos, por fim, um método que pode ser utilizado para impedir a existência 
de deadlock, fazendo uma gestão eficiente dos recursos. O algoritmo que implementa 
esse método trabalha com a ideia de que, se os recursos forem distribuídos de forma 
inteligente, existirá recursos para todos. Conhecido como algoritmo do banqueiro, 
consiste em manter o sistema em estados seguros, em que haja garantia da existência 
de recursos para que todos os processos terminem (TANENBAUM; BOS, 2016, p. 312). 
Suponha os seguintes casos:
 ` Existem 3 processos (P1, P2 e P3);
 ` Existem 10 recursos disponíveis;
 ` O processo P1 necessita 9 desses recursos para terminar, o processo P2, por sua vez, 
necessita 4 desses recursos e, por fim, o processo P3 necessita 7 recursos. 
49
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
 ` Em um tempo t1, a seguinte configuração se apresenta:
 � P1 tem 3 recursos;
 � P2 tem 2 recursos;
 � P3 tem 2 recursos;
 � Estão disponíveis 3 recursos.
 ` Seguindo a ideia de estado seguro (garantindoque não faltará recurso para ninguém, o 
algoritmo distribui dois dos recursos disponíveis para o processo P2 (que tem a garantia 
de terminar e devolver os recursos).
 ` Em um tempo t2, a seguinte configuração se apresenta:
 � P1 continua com 3 recursos;
 � P2 agora tem 4 recursos (lembre-se que ele necessita de 4 recursos);
 � P3 continua com 2 recursos;
 ` Está disponível apenas 1 recurso agora.
 ` Como o processo P2 termina (ele tem tudo o que precisa), ele devolve os 4 recursos que 
estavam com ele e o algoritmo entrega esses 4 recursos ao P3. 
 ` Em um tempo t3, a seguinte configuração se apresenta:
 � P1 continua com 3 recursos;
 � P2 terminou;
 � P3 agora tem 7 recursos (lembre-se de que ele precisa de exatamente 7 recursos);
 � Não há recurso disponível.
 ` Como o processo P3 termina (ele tem os 7 recursos que precisa), ele devolve os 7 re-
cursos e pode-se entregar 6 desses ao processo P1, que ficará com os 9 recursos que 
necessita e terminará.
Como vimos, a boa gestão do uso de recursos pode garantir que todos os processos 
terminem, mesmo esses recursos sendo escassos. Por outro lado, se esses recursos 
forem mal distribuídos, dizemos que entramos em um estado inseguro, em que os pro-
cessos detêm quantidades de recursos que são insuficientes para terminarem, por-
tanto, não os devolvem, e o sistema fica sem recurso para distribuir, causando uma 
estagnação do sistema.
50
Processos Computacionais
2
4. ESCALONAMENTO DA UNIDADE CENTRAL DE 
PROCESSAMENTO
Em sistemas multiprogramados, vários processos concorrem por recursos o tempo 
todo. Lembrando-se de que existe um número limitado de processadores (geralmente 
apenas um), a definição clara de quais processos terão o privilégio de utilizar o proces-
sador e como se dará o controle para que todos consigam utilizá-lo de forma eficiente 
e justa é uma das tarefas primordiais do Sistema Operacional. A entidade do sistema 
responsável por esse controle é o escalonador (scheduller, em inglês) e existem várias 
formas de se fazer esse controle, cada uma dessas formas apresentando um algoritmo, 
que chamaremos de algoritmo de escalonamento.
Antes de falarmos de cada algoritmo, precisamos entender algumas regras e medidas 
para verificarmos a eficiência desses algoritmos. Observe a Figura 9, nela podemos ver 
cinco processos. Cada um desses processos chegou para execução em um determina-
do momento e chamaremos esse momento em que o processo foi criado de tempo de 
chegada do processo, representado na figura por tc1 a tc5. É possível perceber que o 
processo P1 chegou para processamento no tempo 0 (zero) e o processo P4 chegou para 
o processamento no tempo 3 (três) e assim sucessivamente com os demais processos.
Figura 09. Processos escalonamento
P1
P5
P6
P3
P2
0 51 62 73 84 9 10
tc1 tc3tc2 tc4 tc5
ts2
ts1
Fonte: elaborada pelo autor.
51
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Além disso, observa-se na Figura 9 que cada processo ficará um determinado tempo 
em processamento. Assim, o processo P1 tem um tempo de serviço marcado por ts1 
que é igual a 2 e o processo P2, por sua vez, tem um tempo ts2 de 3. Analogamente, 
o processo P3 tem tempo de serviço de serviço igual a 9, o processo P4 tem tempo de 
serviço de 5 e o processo P5 tem tempo de serviço igual a 1. Perceba que a unidade 
de medida de tempo aqui não é importante, pode-se imaginar que sejam segundos, 
milissegundos ou até nanosegundos. O que importa é que cada processo chega para 
o processamento (é criado) em um determinado tempo e que ele tem um tempo de 
serviço (tempo que ele demorará para terminar o processamento).
Colocando essas informações em uma tabela para facilitar o entendimento 
teremos o seguinte:
Tabela 01. Tempos de chegada e serviço
PROCESSO TEMPO DE CHEGADA (TC) TEMPO DE SERVIÇO (TS)
P1 0 2
P2 1 3
P3 2 7
P4 3 5
P5 4 1
Fonte: elaborada pelo autor.
Agora sabemos quando cada processo foi criado e quanto tempo cada um necessitará 
de uso do processador. Porém, como apenas um processo poderá utilizar o proces-
sador em um dado momento, isso causará uma espera nos demais processos, o que 
chamaremos de tempo de espera (te). Utilizando o exemplo apresentado na Tabela 1 
e supondo que o processo P1 entre em execução imediatamente após sua criação, ele 
terá tempo de espera 0 (zero). Como seu tempo de serviço é 2, ele sairá do processador 
apenas no tempo 2 e isso fará com que o processo P2, que chegou no tempo 1, só con-
siga utilizar o processador após a saída do processo P1, ou seja, no tempo 2 também. 
Isso implica que o processo P2 terá um tempo de espera 1. 
Aplicando esse mesmo conceito aos demais processos, teremos que todos os proces-
sos, a partir do processo P1 podem apresentar um tempo de espera, que poderá ser 
maior ou menor, dependendo da eficiência do algoritmo e, com essas informações será 
possível demonstrar a eficiência de cada algoritmo. A eficiência será dada pelo tempo 
de permanência de cada processo na execução. Assim, quanto menor for o tempo de 
permanência, melhor será a eficiência do algoritmo. O tempo de permanência será 
descrito pela Equação 1:
52
Processos Computacionais
2
Equação 1 - Tempo de permanência
A fim de podermos comparar o tempo de permanência entre processos com tempos 
de serviços distintos, utiliza-se a Equação 2, que apresenta o tempo de permanência 
normalizado. Assim, no melhor dos casos (tempo de espera for zero), o tempo de per-
manência normalizado será 1 (um).
Equação 2 - Tempo de permanência normalizado
A Figura 10 ilustra o processo de medida do tempo de permanência de um processo. 
Utilizamos, como exemplo, o processo P2, que tem tempo de serviço 3 e tempo de che-
gada 1, mas que terá que esperar pelo término do processo P1, causando um tempo de 
espera de 1. Isso altera seu tempo de permanência, que passa de 3 (igual ao seu tempo 
de serviço, o que seria ideal) para 4.
Por fim, para conseguirmos entender os algoritmos de escalonamento, é preciso divi-
di-los, ao menos, em dois grupos: o grupo dos algoritmos preemptivos, aqueles que 
utilizarão o processador em um período pré-estabelecido e depois sofrerão preempção, 
mesmo que ainda não tenham terminado a tarefa, voltando ao estado pronto e aguar-
dando sua vez na fila de execução; o grupo dos algoritmos não preemptivo, que não 
poderão sofrer preempção durante a execução. Nesses casos, uma vez que o processo 
entrou para processamento, ele só sairá da execução ao terminar sua tarefa (passado 
seu tempo de serviço).
Existem vários algoritmos de escalonamento, mas, para fins didáticos, utilizaremos dois 
representantes do grupo de algoritmos preemptivos, o ShortestRemainingFirst (SRF) 
e o Multilevel Feedback Queues (MFQ); e dois representantes do grupo de algoritmos 
não preemptivos, o First In First Out (FIFO) e o ShortestJobFirst (SJF).
53
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
Figura 10. Tempo de permanência
Tempo de 
chegada (tc)
P2
Tempo de 
espera (te) Tempo de serviço (ts)
Tempo de permanência (tp)
0 51 62 73 84 9 10
Fonte: elaborada pelo autor.
4.1 ALGORITMO FIRST IN FIRST OUT
O algoritmo FIFO é uma forma bem simples de controle de entrada de processos para 
execução. Ele implementa uma fila simples em que o primeiro a chegar é, também, o 
primeiro a entrar em execução e os demais processos vão sendo enfileirados de acordo 
com seu tempo de chegada. Utilizando o nosso exemplo da Tabela 1, podemos obter o 
tempo de permanência normalizado de cada um dos processos, obtendo como resulta-
do apresentado na Tabela 2.
É possível perceber que o principal problema desse algoritmo é que ele não atende sa-
tisfatoriamente processos cujo tempo de serviço sejam pequenos em relação aos demais 
se esses processos entrarem em produção depois da criação de processos cujos tempos 
de serviços são grandes. Em média, esse algoritmo é bem ineficiente e não favorece a 
produtividade do sistema, mas seu mérito é ser bem simples e de fácilimplementação.
Tabela 02. Algoritmo FIFO
PROCESSO tc ts te tp tpn
P1 0 2 0 2 1,00
P2 1 3 1 4 1,33
P3 2 7 3 10 1,43
P4 3 5 9 14 2,80
54
Processos Computacionais
2
Fonte: elaborada pelo autor.
PROCESSO tc ts te tp tpn
P5 4 1 13 14 14,0
Média 14,11
Para minimizar os problemas causados pelo algoritmo FIFO, atendendo aos sistemas 
não preemptivos, foi desenvolvido o algoritmo SJF.
4.2 ALGORITMO SHORTESTJOBFIRST
O algoritmo SJF é uma alternativa para minimizar a penalidade causada pelo algoritmo 
FIFO aos processos menores. Ele também coloca os processos em uma fila, mas antes 
de seguirem para a fila, eles são ordenados em ordem crescente do tempo de serviço. 
Assim, o menor processo acaba sendo favorecido e a média do tempo de permanência 
tende a diminuir, aumentando a eficiência do sistema como um todo.
Tabela 03. Algoritmo SJF
PROCESSO tc ts te tp tpn
P1 0 2 0 2 1,00
P2 1 3 1 4 1,33
P5 4 1 1 2 2,00
P4 3 5 3 8 1,60
P3 2 7 9 16 2,28
Média
Fonte: elaborada pelo autor.
Analisando os dados apresentados na Tabela 3, percebe-se que o algoritmo é muito 
mais eficiente que o FIFO, ficando a média do tempo de permanência normalizada em 
1,64 contra 14,11 do FIFO. Isso se dá ao fato da ordenação dos processos em ordem 
do tempo de serviço. É preciso notar, porém, que o processo P2, apesar de ter um tem-
po de serviço maior que o tempo de serviço do processo P5 foi executado primeiro e o 
mesmo aconteceu com o processo P1, que foi o primeiro a entrar em execução. Acon-
tece que no momento 0 só havia o processo P1, ou seja, não havia outros processos 
criados para serem ordenados pelo tempo de serviço e, então, o processo P1 entrou 
em execução. Quando o processo P1 finalizou sua execução, no tempo 2, havia dois 
processos na disputa, o P2 com tempo de serviço 3 e o P3 com tempo de serviço 7 e, 
então, o processo P2 entrou para execução, terminando no tempo 5. A partir daí, como 
todos os demais processos já haviam chegado, o algoritmo ordenou-os do menor para 
o maior tempo de serviço.
Os algoritmos exibidos até aqui são variantes não preemptivas, ou seja, não preveem 
que o processo execute em etapas, voltando à fila a cada ciclo. Para sistemas preemp-
tivos, alguns algoritmos são mostrados a seguir.
55
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
4.3 ALGORITMO SHORTESTREMAININGFIRST
Essa é uma variante preemptiva do SJF. Nesse algoritmo, os processos são alocados 
de acordo com o seu tempo de serviço, sendo que os menores têm prioridade sobre os 
maiores. O menor processo entra em execução. Se chegar um novo processo, ele é or-
ganizado na fila de acordo com o seu tempo de serviço e, se chegar um processo menor 
que o processo que já está em execução, o processo em execução sofre preempção e 
é reorganizado na fila de acordo com o seu tempo de serviço restante. Assim, existe um 
privilégio dos processos menores em relação aos maiores, favorecendo a produtividade.
Figura 11. Algoritmo SRF
P3 P2 P1 CPU
Preempção. Volta para fila de 
acordo com tamanho restante
Finalização
Fonte: elaborada pelo autor.
4.4 ALGORITMO MULTILEVEL FEEDBACK QUEUES
O algoritmo MFQ, ou algoritmo de filas com feedbacks multinível são mais complexos e 
mais eficientes que os algoritmos mostrados até o momento. 
Figura 12. Algoritmo MFQ
CPU
Finalização
Finalização
Finalização
Finalização
CPU
CPU
CPU
Preempção
Preempção
Preempção
Fila nível 1
Fila nível 2
Fila nível 3
Fila nível n
Fonte: elaborada pelo autor.
56
Processos Computacionais
2
A Figura 12 mostra o funcionamento de um algoritmo desse tipo. Ele também é um al-
goritmo preemptivo, como o SRF, mas, nele, os processos são colocados em uma fila 
inicial (Fila de nível 1) e vão para o processamento de acordo com a ordem de chegada. 
Porém, existe um tempo para que os processos fiquem utilizando a CPU. Esse tempo 
é chamado de quanta, e representa o quanto cada processo fará de utilização da CPU 
antes de ser preemptado. Se, dentro desse tempo for maior que o tempo de serviço do 
processo, ele é finalizado. Caso contrário, ele é preemptado. Porém, não volta para a 
fila de nível 1 e sim para a fila de nível 2. A fila de nível 2 funciona da mesma forma 
que a fila de nível 1, com a diferença que os processos só entram em execução caso 
não haja processo na fila de nível 1. Isso ocorre sucessivamente e o número de níveis 
depende de sua implementação. No último nível, os processos preemptados circulam 
dentro da mesma fila até terminarem.
Existem vários outros algoritmos de escalonamento. Alguns são variantes dos algorit-
mos apresentados e todos têm a finalidade de escolher quais são os processos que en-
trarão de fato em execução, dada uma concorrência entre eles. A ideia aqui foi mostrar 
o que são e dar exemplos de como esses algoritmos podem estar definidos. Podemos 
fazer um comparativo entre eles a fim de resumir o seu funcionamento e propósito, 
como mostrado na Tabela 4.
Tabela 04. Comparativo Algoritmos de Escalonamento
FIFO SJF SRF MFQ
Seleção Tempo de 
chegada Tempo de serviço Tempo de serviço 
restante Complexa
Preempção Não Não Sim Sim
Produtividade Baixa Média Alta Média
Tempo de resposta Alto Pequeno Pequeno Pequeno
Sobrecarga Mínima Alta Alta Alta
Adiamento infinito Não Possível Possível Possível
Fonte: elaborada pelo autor.
Analisando cada algoritmo apresentado, é possível verificar que o FIFO, apesar de ter 
uma produtividade baixa, é o único que garante que não haverá adiamento infinito. Isso 
se deve ao fato de que todos os processos que são criados entrarão, mais cedo ou mais 
tarde, para a execução. Os demais, devido à natureza de favorecimento dos processos 
menores, podem causar adiamento infinito nos processos maiores. Além disso, devido 
à sua facilidade de implementação, o FIFO também apresenta a menor sobrecarga de 
execução (tempo que o algoritmo gasta para organizar os processos). Porém, devido ao 
fato de não ser preemptivo e a produtividade de sistemas que implementam esse tipo 
de algoritmo ser impraticável, sua utilização é inviável. Para sistemas não preemptivos, 
o SJF se apresenta como uma boa solução, enquanto o MFQ se apresenta como uma 
boa solução para sistemas preemptivos.
57
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co
CONCLUSÃO
Os Sistemas Operacionais são os sistemas responsáveis pela gestão do hardware de 
um computador. Sendo o computador uma máquina complexa, apresentar esse har-
dware ao usuário final prejudicaria a produtividade, uma vez que a curva de aprendiza-
do desse hardware seria muito complexa.
Para facilitar a gestão, o hardware do computador é dividido seguindo a arquitetura em 
hardware de processamento, cujo controle se dá através de como os processos são 
criados e quais são as possibilidades de uso de recurso desses processos. Porém, com 
a multiprogramação (possibilidade de sistemas multitarefa), os processos concorrem 
por recursos que são sempre finitos e, às vezes, escassos.
A concorrência entre os processos gera alguns problemas, como o controle de acesso a 
recursos que só podem ser acessados por um único processo de cada vez e até mesmo 
adiamentos infinitos e deadlocks. Cada um desses problemas deve ser tratado pelo Sistema 
Operacional, responsável por manter o sistema funcionando e favorecendo a produtividade.
Uma vez que existe a possibilidade de se trabalhar de forma multiprogramada mesmo 
em sistemas monoprocessados, existem diversos algoritmos que fazem o escalona-
mento dos processos para definição de qual, dentre todos, poderá utilizar de fato o 
processador, existindo um algoritmo ideal para cada tipo de sistema.
58
Processos Computacionais
2
REFERÊNCIAS BIBLIOGRÁFICAS
MACHADO, F. B.; MAIA, L. P. Arquitetura de Sistemas Operacionais. 5. ed. São Paulo: Grupo GEN, 2013. 
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2288-8/. Acesso em: 13 fev. 2022.
BERENGER, M. F.; PAULO, M. L. Fundamentos de Sistemas Operacionais. São Paulo: Grupo GEN,2011. 
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2081-5/. Acesso em: 2 fev. 2022.
SILBERSCHATZ, A; GALVIN, P. B.; GAGNE, G. Fundamentos de Sistemas Operacionais. São Paulo: Gru-
po GEN, 2015. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-3001-2/. Acesso 
em: 2 fev. 2022.
STALLINGS, W. Arquitetura e Organização de Computadores. 8. ed. São Paulo: Pearson, 2010.
TANENBAUM, A. S. Organização Estruturada de Computadores. 6. ed. São Paulo: Pearson, 2013.
TANENBAUM, A.; BOS, H. Sistemas Operacionais Modernos. 4. ed. São Paulo: Pearson Education do 
Brasil, 2016.
59
2
Ambientes computacionais
U
ni
ve
rs
id
ad
e 
S
ão
 F
ra
nc
is
co