ads:
M´arcio Roberto Starke
Controle Dinˆamico de Recursos
em Sistemas Operacionais
Disserta¸c˜ao submetida ao Programa de P´os-
Gradua¸c˜ao em Inform´atica Aplicada da Pon-
tif´ıcia Universidade Cat´olica do Paran´a como
requisito final `a obten¸c˜ao do t´ıtulo de Mestre
em Inform´atica Aplicada.
Curitiba
2005
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
M´arcio Roberto Starke
Controle Dinˆamico de Recursos
em Sistemas Operacionais
Disserta¸c˜ao submetida ao Programa de
P´os-Gradua¸c˜ao em Inform´atica Aplicada da
Pontif´ıcia Universidade Cat´olica do Paran´a
como requisito final `a obten¸c˜ao do t´ıtulo de
Mestre em Inform´atica Aplicada.
´
Area de Concentra¸c˜ao: Metodologia e
T´ecnicas de Computa¸c˜ao
Orientador: Prof. Dr. Carlos A. Maziero
Curitiba
2005
ads:
Starke, M´arcio Roberto
S795c Controle dinˆamico de recursos em sistemas operacionais / M´arcio Roberto
2005 Starke ; orientador, Carlos Alberto Maziero. 2005.
97 f. : il. ; 30 cm
Disserta¸c˜ao (mestrado) - Pontif´ıcia Universidade Cat´olica do Paran´a,
Curitiba, 2005
Inclui bibliografia
1. Sistemas operacionais (Computadores). 2. Interfaces (Computadores).
4. Programa¸c˜ao (Computadores). I. Maziero, Carlos Alberto.
II. Pontif´ıcia Universidade Cat´olica do Paran´a. Programa de P´os-Gradua¸c˜ao em
Inform´atica Aplicada. III. T´ıtulo.
CDD 20. ed. 005.42
004.616
005.26
A minha amada esposa e aos meus queridos pais.
O tempo ´e o mestre de tudo.
(S´ofocles)
Agradecimentos
Primeiramente a Deus, autor da vida e que sempre me guia por caminhos
seguros.
Aos meus pais Paulo e Elizete que me zelaram, educaram-me e fizeram de
mim o que sou hoje.
A minha esposa S´ılvia que sempre me apoiou para que juntos sempre es-
tiv´essemos a subir.
Ao meu orientador Carlos Maziero pela orienta¸c˜ao, oportunidades e com-
preens˜ao.
Aos amigos Emerson e Fabiano pela convivˆenvia e pela eterna amizade.
E a CAPES pelo apoio financeiro t˜ao necess´ario para realiza¸c˜ao desse tra-
balho.
Resumo
Uma das principais fun¸c˜oes dos sistemas operacionais ´e a de ser gerente
dos recursos do computador. Em um sistema operacional de rede n˜ao ´e dife-
rente, por´em, a quantidade de recursos que devem ser gerenciados ´e maior.
Mesmo assim, os sistemas operacionais de mercado fornecem somente me-
canismos limitados de gerenciamento de recursos, onde n˜ao ´e poss´ıvel impor
restri¸c˜oes ou privil´egios de acesso aos recursos de um processo durante a sua
execu¸c˜ao. Tamb´em ´e not´orio que a gest˜ao dos recursos nestes sistemas opera-
cionais ´e feita sobre parˆametros de processos, n˜ao permitindo o ajuste do uso
dos recursos por usu´arios, grupo de usu´arios ou conjunto de processos.
Esta disserta¸c˜ao objetiva a descri¸c˜ao de um modelo flex´ıvel de gest˜ao dos
recursos computacionais, que permita definir e alterar a quantidade alocada
de recursos para um processo espec´ıfico ou um grupo de processos relacionados
por algum parˆametro, como usu´arios, grupo de usu´arios ou processos de uma
aplica¸c˜ao, sendo que essas defini¸c˜oes s˜ao aplicadas instantaneamente a partir
do momento de sua cria¸c˜ao.
Os recursos que este modelo prop˜oe a gerenciar s˜ao o uso do processador,
de mem´oria, espa¸co em disco, banda de rede e de disco e recursos internos do
sistema operacional. Para validar esta proposta foi implementado um prot´otipo
de gerenciamento dinˆamico de utiliza¸c˜ao do processador, capaz de privilegiar
ou restringir seu uso de acordo com especifica¸c˜oes feitas pelo administrador
do sistema.
Este modelo pode prover uma melhor distribui¸c˜ao dos recursos entre os pro-
cessos em execu¸c˜ao, bem como, pode melhor adequar o sistema computacional
`as necessidades da organiza¸c˜ao que o mant´em.
Esta proposta visa prover uma interface de programa¸c˜ao (API) que pode ser
utilizada por outros desenvolvedores que necessitem implementar um sistema
operacional com suporte a qualidade de servi¸co (QoS); por administradores que
desejam uma alternativa mais sofisticada no controle dos recursos do sistema;
por aplicativos desenvolvidos com garantia de acesso aos recursos para sua
execu¸c˜ao apropriada; e por sistemas protegidos contra invas˜ao e contra falhas
como m´etodo de resposta aos ataques.
Palavras-Chave: Controle Dinˆamico, Gest˜ao de Recursos, Sistemas Ope-
racionais.
Abstract
One of the main functions of the operating systems is to manage the com-
puter resources. A network operating system has the same duty, however, the
quantity of resources that should be manage is bigger. Even so, COTS opera-
ting systems supply only limited mechanisms of resources management, where
is not possible impose contraints or privileges of access to the resources used
by a process in execution. Also it is notorious that the management of the
resources in these operating systems is done by parameters of one process, not
permitting adjust the use of the resources by users, users groups or processes
groups.
This dissertation objective is the description of a flexible model of manage-
ment of the computer resources, that permit to define and alter the quantity of
allocated resources for a specific process or a processes group related by some
parameter, as users, users group or process of an application. That definitions
are applied instantly from the moment of its creation.
The resources that this model proposes to manage are the use of the pro-
cessor, of memory, disk space, network and disk band and internal resources
of the operating system. For the validation of this proposal was implemented
a prototype of dynamic management of processor utilization, capable of privi-
lege or restrain the CPU use in agreement with the specifications made by the
system administrator.
This model can supply a better distribution of the resources among the
processes in execution, and it can better adapt the computer system to the
needs of the organization that maintain it, as well.
This proposal is going to supply a programming interface (API) that can be
utilized by others developers that are going to implement an operating system
with quality of service (QoS); by administrators that desire a more sophisti-
cated alternative in the control of the resources of the system; by applications
developed with guarantee of access to the resources for their appropriate execu-
tion; and by systems protected against invasion and fail as a method of attack
response.
Keywords: Dynamic Control, Resource Management, Operational Sys-
tems.
Sum´ario
1 Introdu¸c˜ao 1
1.1 Contexto geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Objetivo geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Objetivos espec´ıficos . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Estrutura do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Gest˜ao de recursos 6
2.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Recursos de um sistema de computa¸c˜ao . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Gest˜ao do processador . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Gerˆencia de mem´oria . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Gest˜ao de disco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.4 Gest˜ao de rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.5 Recursos internos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.6 Classifica¸c˜ao dos recursos . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Mecanismos avan¸cados de gest˜ao de recursos 25
3.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Escalonamento baseado em prioridades . . . . . . . . . . . . . . . . . . . . 25
3.3 Mecanismos avan¸cados de gest˜ao de recursos . . . . . . . . . . . . . . . . . 30
3.3.1 Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.2 Class-Based Kernel Resource Management — CKRM . . . . . . . . 32
3.3.3 Linux-SRT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.4 Dynamic Soft Real-Time CPU Scheduler . . . . . . . . . . . . . . . 34
3.3.5 Cap Processor Usage . . . . . . . . . . . . . . . . . . . . . . . . . . 35
ix
3.4 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Um modelo de gest˜ao de recursos 37
4.1 Hierarquia do uso dos recursos . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 O controle dinˆamico do uso dos recursos . . . . . . . . . . . . . . . . . . . 38
4.2.1 Processador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.2 Mem´oria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.3 Disco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.4 Rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.5 Recursos internos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Implementa¸c˜ao do modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Controle dinˆamico de processador 57
5.1 Descri¸c˜ao do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 O escalonador de processos no Linux . . . . . . . . . . . . . . . . . . . . . 58
5.3 O algoritmo de escalonamento proposto . . . . . . . . . . . . . . . . . . . . 61
5.4 Descri¸c˜ao da implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.5 Avalia¸c˜ao do prot´otipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.5.1 O desempenho e custo da implementa¸c˜ao . . . . . . . . . . . . . . . 72
5.6 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Considera¸c˜oes finais 74
6.1 Resumo do trabalho realizado . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2 Principais contribui¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.3 Limita¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.4 Trabalhos correlatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.5 Perspectivas e trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . 79
A C´odigo fonte do prot´otipo 85
B C´odigo fonte do monitor de uso da CPU 94
C C´odigo fonte do manipulador do prot´otipo 96
C.1 resourcelimits.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
C.2 chlimits.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Lista de Figuras
2.1 Diagrama de estado dos processos. . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Ordem de execu¸c˜ao de processos pelo algoritmo SJF. . . . . . . . . . . . . 11
2.3 Rela¸c˜ao entre endere¸cos virtuais e endere¸cos f´ısicos. . . . . . . . . . . . . . 16
3.1 Uso do processador por N processos no sistema operacional Windows XP . 28
3.2 Projeto de implementa¸c˜ao do CKRM. . . . . . . . . . . . . . . . . . . . . . 33
4.1 Aplica¸c˜ao de limite inferior (esquerda) e superior (direita) no uso do pro-
cessador. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 A granularidade do acesso aos recursos. . . . . . . . . . . . . . . . . . . . . 40
4.3 Utiliza¸c˜ao do processador por P1 durante N ciclos. . . . . . . . . . . . . . 42
4.4 Compartilhamento da banda de rede atrav´es de regras. . . . . . . . . . . . 51
5.1 Fluxograma do controle dinˆamico de recursos. . . . . . . . . . . . . . . . . 67
5.2 Uso da CPU por P1, com N processos disputando a CPU. . . . . . . . . . 69
5.3 Uso da CPU por P1 e P2 pertencentes a uma regra limite superior. . . . . 70
5.4 Uso da CPU por P1, com N processos disputando a CPU. . . . . . . . . . 70
5.5 Uso da CPU por P1 e P2 pertencentes a uma regra limite inferior. . . . . . 71
5.6 Acr´escimo de tempo de execu¸c˜ao imposto pelo mecanismo de aplica¸c˜ao das
regras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
xi
Lista de Tabelas
3.1 Uso do processador por N processos com diferentes prioridades durante a
inser¸c˜ao de um novo processo. . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Diferen¸cas entre os modelos alternativos de gest˜ao de recursos. . . . . . . . 36
4.1 Diferen¸cas entre os modelos alternativos de gest˜ao de recursos e o modelo
proposto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
xii
Cap´ıtulo 1
Introdu¸c˜ao
1.1 Contexto geral
Atualmente as necessidades dos usu´arios de computador s˜ao as mais variadas.
´
E
comum um usu´ario querer ouvir um arquivo de m´usica, redigir um texto, fazer uma
apresenta¸c˜ao ou editar uma imagem. Para que ele possa realizar essas tarefas ´e necess´ario
que o computador utilizado possua os programas que as executam. Um programa ´e um
conjunto finito de instru¸c˜oes com o prop´osito de resolver um problema espec´ıfico.
Para fazer uma melhor utiliza¸c˜ao do computador, os usu´arios costumam executar mais
de um programa ao mesmo tempo. Por exemplo, eles mantˆem o programa leitor de e-
mails aberto, enquanto ouvem m´usicas e digitam textos. Para que a execu¸c˜ao de um
processo n˜ao interfira na execu¸c˜ao de outro, o sistema operacional controla a ordem e o
tempo de execu¸c˜ao de todos os pro cessos, bem como o acesso aos recursos do sistema
computacional.
Com o aumento da capacidade de processamento dos computadores, os usu´arios
habituaram-se a abrir mais programas ao mesmo tempo. Os sistemas operacionais devem
estar aptos para tratarem essa grande quantidade de processos disputando os recursos
computacionais para que todos possam ser executados de forma justa e adequada.
Ao se tratar de sistemas multi-usu´arios a situa¸c˜ao ´e ainda mais cr´ıtica, pois v´arios
usu´arios podem estar executando v´arios processos, sendo que cada processo vai concorrer
pelo acesso aos recursos. Como um n´umero muito elevado de processos podem estar
em execu¸c˜ao em um determinado instante, sistema operacionais multi-usu´arios devem se
1. Introdu¸c˜ao 2
preocupar mais ainda com a gest˜ao dos recursos com a finalidade de tornar a execu¸c˜ao de
todos os processos a mais apropriada.
1.2 Motiva¸c˜ao
Os computadores modernos consistem em processadores, mem´orias, temporizadores,
discos, mouses, interfaces de rede, impressoras e uma ampla variedade de outros disp osi-
tivos. A fun¸c˜ao do sistema operacional, enquanto gerenciador de recursos, ´e oferecer uma
aloca¸c˜ao ordenada e controlada dos processadores, mem´orias e dos dispositivos de entrada
e sa´ıda entre os v´arios programas que competem por eles. Quando um computador tem
m´ultiplos usu´arios, a necessidade de gerenciar e proteger os recursos computacionais ´e
maior ainda [TW97].
O objetivo principal do gerenciamento de recursos ´e prover oportunidade e garantia
de acesso aos recursos, ao mesmo tempo que os protege. Os recursos em geral n˜ao s˜ao
completamente independentes uns dos outros, assim, existem situa¸c˜oes onde o acesso a
certos recursos compromete os novos acessos a ele mesmo ou a outros [GR02].
Uma situa¸c˜ao onde a interdependˆencia dos recursos pode ser notada ´e no tratamento
dos pacotes de rede. Quando a interface de rede recebe um pacote, ela faz uma requisi¸c˜ao
para o sistema operacional executar as a¸c˜oes necess´arias para transferˆencia do pacote
para o seu destino. Por´em, quando o processador est´a saturado, essa requisi¸c˜ao pode
demorar para ser atendida, e o pacote pode ser descartado. Isso ocorre principalmente
em interfaces de rede muito r´apidas, como as gigabit ethernets, em computadores com
processadores lentos.
Nos sistemas operacionais de mercado existem algumas ferramentas para monitorar e
controlar os recursos do sistema, mas funcionam de uma forma primitiva [MR95]. Esses
sistemas operacionais geralmente fornecem somente um mecanismo de prioridades para
ordenar o acesso aos recursos. E ainda assim, por muitas vezes, os ajustes de utiliza¸c˜ao
dos recursos podem ser aplicados somente estaticamente, ou seja, somente na pr´oxima
execu¸c˜ao do processo, ou no pr´oximo login do usu´ario ´e que esses ajustes ter˜ao efeito.
Este trabalho visa definir um modelo dinˆamico de controle de recursos. Por dinˆamico,
entende-se um modelo de controle de recursos em que n˜ao ´e necess´ario reiniciar o processo
ou a sess˜ao do usu´ario para que os ajustes de acesso aos recursos sejam efetuados. O
1. Introdu¸c˜ao 3
sistema aplicar´a as altera¸c˜oes assim que seja poss´ıvel, sem que seja necess´ario realizar
nenhuma outra a¸c˜ao. Tamb´em consiste de um modelo mais flex´ıvel de controle onde o
administrador pode fixar valores de limite m´aximo e m´ınimo de utiliza¸c˜ao dos recursos
pelos processos.
Com o controle dinˆamico dos recursos muitas novas caracter´ısticas podem ser incor-
poradas ao sistema operacional. Por exemplo, ao se fazer uma transmiss˜ao de dados na
internet, pode-se garantir uma largura de banda de rede m´ınima `a aplica¸c˜ao, e garantir
tamb´em recursos m´ınimos para que a banda alocada n˜ao fique vazia por falta de oportu-
nidade de se enviar dados sobre ela. Esse tipo de controle tamb´em poderia fornecer as
primitivas para implementar um sistema operacional com suporte `a qualidade de servi¸co
(QoS). Construindo-se um escalonador de QoS que seja capaz de analisar as requisi¸c˜oes
de aloca¸c˜ao de recursos das aplica¸c˜oes, o controle dinˆamico poderia ser utilizado para
garantir os recursos m´ınimos para a execu¸c˜ao adequada dos processos.
Da mesma forma, interagindo com programas que detectam anomalias no sistema
computacional, como sistemas de detec¸c˜ao de intrus˜ao ou falhas, o controle dinˆamico
de recursos poderia ser utilizado para restringir a execu¸c˜ao de processos comprometidos.
Assim, se for detectado algum tipo de ataque a processos, podem ser lan¸cadas medidas
de conten¸c˜ao, n˜ao permitindo que os processos afetados sejam executados ou que sejam
executados muito lentamente, evitando que ataques efetuados contra o sistema computa-
cional tenham sucesso, inclusive bloqueando ataques de Denial of Service [dAMF03]. Isso
garantiria ao sistema operacional mais confiabilidade e seguran¸ca.
Tamb´em pode-se privilegiar outros processos para que eles possam ter uma execu¸c˜ao
adequada. Essas s˜ao caracter´ısticas desejadas em um sistema operacional de rede, pois
muitos usu´arios comp etem por recursos compartilhados, e, dessa forma, o sistema ope-
racional, por muitas vezes, deve ceder mais recursos a um e negar a outros, para que
todos possam ser justamente executados. Podendo privilegiar determinados processos, o
administrador do sistema tem uma maior flexibilidade para definir quais s˜ao as aplica¸c˜oes
que devem ser mais prontamente executadas, focando mais diretamente no objetivo do
sistema.
1. Introdu¸c˜ao 4
1.2.1 Objetivo geral
O objetivo desse trabalho ´e apresentar um novo modelo para controle dos recursos do
sistema computacional. Esses recursos constituem-se do processador, mem´oria, espa¸co em
disco, banda de disco, banda de rede e recursos internos do sistema operacional. Nesse
modelo os processos podem ter aumentadas ou diminuidas suas chances de acesso aos
recursos a qualquer momento sem que haja a necessidade de reiniciar o processo ou a
sess˜ao. Tamb´em ´e poss´ıvel fixar um limite m´aximo ou m´ınimo de utiliza¸c˜ao de um ou
mais recursos por um processo, por um grupo de processos, por um usu´ario ou por um
grupo de usu´arios.
1.2.2 Objetivos espec´ıficos
• Definir um modelo de controle que seja capaz de ser ajustado dinamicamente de
acordo com as especifica¸c˜oes do administrador para limitar ou privilegiar o acesso
aos principais recursos de um sistema computacional
1
;
• Especificar uma API oferecendo a possibilidade de controlar dinamicamente:
1. o tempo de utiliza¸c˜ao dos processadores, diminuindo ou aumentando o per-
centual de utiliza¸c˜ao do processador, dentro de um determinado per´ıodo ou
durante toda a execu¸c˜ao do processo;
2. a mem´oria, definindo a quantidade de p´aginas residentes em mem´oria f´ısica, o
n´umero de faltas de p´agina que ocorre e a quantidade de p´aginas em mem´oria
virtual;
3. espa¸co em disco, definindo cotas de tamanho de arquivos e quantidade de
arquivos abertos;
4. banda de disco, especificando a quantidade de informa¸c˜ao que pode ser trans-
ferida para o disco por segundo;
5. banda de rede, especificando a quantidade de bits que podem ser enviados pela
rede por segundo;
1
Note-se que foram escolhidos os recursos mais relevantes para compor o conjunto de elementos que
esse modelo aborda com base em conhecimento t´acito.
1. Introdu¸c˜ao 5
6. recursos internos (descritores, sockets, sem´aforos e mem´oria compartilhada),
definindo a quantidade de cada recurso interno que podem ser mantidos abertos
por um ou mais processos.
• Como prot´otipo, implementar uma API para controlar dinamicamente o processador
no sistema operacional Linux.
O produto final desse trabalho consiste de altera¸c˜oes no n´ucleo do Linux para que ele
possa atuar como um gerente de recursos que libere e negue acesso aos recursos e que
ajuste os recursos previamente alocados, privilegiando o acesso a partir de um ou mais
processos ou restringindo-os.
1.3 Estrutura do texto
Esse texto est´a estruturado da seguinte forma: neste primeiro cap´ıtulo foi visto a
necessidade de um sistema operacional que possa controlar dinamicamente os recursos
computacionais, que ´e a proposta desse trabalho. No segundo cap´ıtulo ser´a visto quais
s˜ao os principais recursos do computador e os m´etodos atuais de controle de recursos.
Seguindo, o cap´ıtulo trˆes apresentar´a os problemas encontrados na gest˜ao dos recursos
nos sistema operacionais atuais e ser´a descrito alguns modelos alternativos de gerˆencia
de recursos. O cap´ıtulo quatro desmonstrar´a o modelo de controle de recursos proposto
neste trabalho e o cap´ıtulo quinto a implementa¸c˜ao desse modelo para o processador, com
avalia¸c˜ao de seu funcionamento. Finalmente ser˜ao apresentadas as considera¸c˜oes finais e
trabalhos futuros.
Cap´ıtulo 2
Gest˜ao de recursos
2.1 Introdu¸c˜ao
Neste cap´ıtulo ser˜ao apresentados os principais recursos que comp˜oe um sistema com-
putacional e como um sistema operacional convencional coordena e realiza a aloca¸c˜ao
desses recursos de forma que os processos possam em algum momento utiliz´a-los.
Em termos gerais, um sistema computacional ´e composto de diversos componentes
f´ısicos e l´ogicos que s˜ao utilizados por programas para serem executados. Esses compo-
nentes s˜ao conhecidos como recursos computacionais e incluem o processador, a mem´oria,
os discos r´ıgidos, os componentes de rede, as impressoras e outros dispositivos de entrada
e sa´ıda. Al´em destes, s˜ao tamb´em considerados recursos as estruturas l´ogicas providas
pelo sistema operacional `as aplica¸c˜oes, como descritores de arquivos, sockets, sem´aforos,
threads e outras coisas mais.
Nos sistemas modernos ´e normal que existam v´arios processos em execu¸c˜ao ao mesmo
tempo. Sendo os recursos limitados, os processos devem acessar um determinado recurso
a fim de realizar uma tarefa e, em seguida, liber´a-lo para que outros processos possam
tamb´em completar sua execu¸c˜ao. Para evitar excessos na utiliza¸c˜ao dos recursos por parte
de algum processo, o sistema operacional age como gerente dos recursos, prevenindo que
haja abuso na utiliza¸c˜ao dos mesmos.
A seguir ser˜ao descritos os principais recursos de um sistema computacional e como o
n´ucleo do sistema operacional gerencia o acesso a cada um deles.
2. Gest˜ao de recursos 7
2.2 Recursos de um sistema de computa¸c˜ao
Recurso ´e definido como sendo um meio utilizado para atingir um fim. Em computa¸c˜ao
s˜ao os componentes f´ısicos ou l´ogicos utilizados por processos para realizar alguma tarefa
espec´ıfica. Os recursos f´ısicos mais comuns s˜ao o processador, a mem´oria, discos e rede.
Entre os recursos l´ogicos os mais comuns s˜ao os descritores de arquivos, sem´aforos, sockets,
processos, threads e mem´oria compartilhada. Nos pr´oximos t´opicos, estar˜ao relacionados
os principais recursos f´ısicos e l´ogicos, bem como, ser´a mostrado os m´etodos mais comuns
utilizados pelos sistemas operacionais para fazer o seu controle.
2.2.1 Gest˜ao do processador
O processador ´e o componente crucial de um sistema computacional.
´
E nele que ocorre
a atividade fim de qualquer sistema inform´atico, ´e onde realmente ocorre o processamento
dos dados.
Na realidade, s˜ao duas as fun¸c˜oes b´asicas do processador [Mon02]:
• fun¸c˜ao de processamento;
• fun¸c˜ao de controle.
As tarefas mais comuns que s˜ao executadas pelo processador em sua fun¸c˜ao de proces-
samento s˜ao as opera¸c˜oes aritm´eticas, opera¸c˜oes l´ogicas, movimenta¸c˜ao de dados, desvios
e opera¸c˜oes de entrada e sa´ıda.
Na fun¸c˜ao de controle, as principais atividades desenvolvidas pelo processador s˜ao a
busca das instru¸c˜oes a serem executadas, interpreta¸c˜ao das a¸c˜oes a serem tomadas e o
controle dos componentes internos, como a unidade l´ogica e aritm´etica, e dos componentes
externos como mem´oria e dispositivos de entrada e sa´ıda.
Devido a seu papel fundamental na execu¸c˜ao das instru¸c˜oes, o processador ´e um dos re-
cursos mais requisitados no sistema computacional. Cada processo necessita obter acesso
ao processador para executar as suas instru¸c˜oes, seja para fazer algum c´alculo, imprimir
um documento ou simplesmente para encerrar sua execu¸c˜ao. Mesmo em sistemas compu-
tacionais de escrit´orio s˜ao v´arios os processos em execu¸c˜ao simultˆanea, sendo a disputa
pelo uso do processador intensa. Em sistemas operacionais de rede, que geralmente for-
nececem uma grande quantidade de servi¸cos e/ou uma grande quantidade de acessos, o
2. Gest˜ao de recursos 8
Espera por um evento
Dispatch
Aceito
exit()
Novo
Pronto
Rodando
Espera
Terminado
Preempção
Evento Ocorrido
Figura 2.1: Diagrama de estado dos processos.
n´umero de processos sendo executados ao mesmo tempo p ode ser ainda superior, tornando
a competi¸c˜ao pelo uso do processador ainda mais intensa.
O respons´avel por controlar quem dever´a obter o acesso a esse recurso ´e o sistema
operacional.
´
E ele que define quanto tempo cada processo tem para executar suas ins-
tru¸c˜oes no processador e quando dever´a voltar a recebˆe-lo ap´os terminado seu per´ıodo de
execu¸c˜ao.
Sendo o sistema monoprocessado, isto ´e, p ossuindo somente um processador, n˜ao ´e
poss´ıvel executar mais que um processo por vez. Assim ´e necess´ario que o sistema operaci-
onal implemente um mecanismo que permita uma pseudo execu¸c˜ao paralela dos processos.
S˜ao os chamados sistemas operacionais multitarefas. Os processos s˜ao armazenados em
mem´oria durante a carga do programa e, ent˜ao, o sistema operacional alterna os proces-
sos que est˜ao sendo executados de tempo em tempo, executando parcialmente cada um
em sua vez. A parte respons´avel por essa tarefa dentro de um sistema operacional ´e o
escalonador. Com isso tem-se v´arios programas sendo executados em tempos diferentes,
por´em com a sensa¸c˜ao de estarem sendo executados simultaneamente, devido `a r´apida
alternˆancia entre eles.
A seguir ser˜ao vistos os principais algoritmos utilizados pelos sistemas operacionais
para implementar o escalonador de processos.
Escalonadores Round Robin
O Round Robin ´e um dos algoritmos de escalonamento mais antigos e mais simples
e consiste na atribui¸c˜ao de uma fatia de tempo para execu¸c˜ao do processo, denominado
2. Gest˜ao de recursos 9
quantum, que na verdade ´e um valor que corresponde a quantos ticks
1
de rel´ogio aquele
processo tem dispon´ıvel para usar o processador. Cada vez que ocorre um tick do rel´ogio, o
processo que est´a sendo executado tem seu quantum decrementado. Quando esse valor for
igual a zero o processo ´e retirado de execu¸c˜ao, indo para uma fila de processos que est˜ao
prontos para serem executados, e est˜ao esperando a sua vez de obterem o processador,
enquanto outro processo ´e colocado em seu lugar. Isso ´e chamado de troca de contexto.
Se um processo que est´a de posse do processador faz uma requisi¸c˜ao de entrada ou
sa´ıda, sendo que o tempo de acesso aos dispositivos de entrada e sa´ıda ´e muito alto, ou
lan¸ca algum outro tipo de evento a qual ele deve esperar para ser atendido, como um
acesso a uma regi˜ao cr´ıtica ou um alarme, esse processo perde o processador e ´e colocado
em uma fila de processos bloqueados e que est˜ao esperando pelo evento que satisfar´a a sua
requisi¸c˜ao. Quando esse evento ocorrer ele ser´a colocado novamente na fila de processos
prontos para execu¸c˜ao, voltando a concorrer ao uso do processador.
Nesse tipo de escalonamento todos os processos recebem sempre o mesmo quantum,
sendo tratados como iguais. N˜ao h´a nenhuma prioridade de execu¸c˜ao de um processo
sobre outro. Assim sendo, um processo de pouca importˆancia, um desfragmentador de
disco por exemplo, obt´em o mesmo tempo de execu¸c˜ao que um processo relevante, como
um servidor web, ignorando toda e qualquer hierarquia entre os processos.
De fato, o escalonamento por esse algoritmo consiste de uma fila de processos prontos
para serem executados. O processo escolhido para utilizar a CPU ´e sempre o primeiro da
fila, e ao terminar o seu quantum, ele ´e colocado ao final da fila, e o processo que agora
ocupa a primeira posi¸c˜ao na fila ´e ent˜ao pego para ser executado, como pode ser visto na
figura 2.1.
A principal caracter´ıstica desse algoritmo ´e a utiliza¸c˜ao do quantum, que n˜ao deve
ser muito pequeno, pois geraria uma sobrecarga muito grande no uso do processador por
parte do escalonador devido as freq¨uentes trocas de contexto, e tamb´em n˜ao deve ser
muito grande, pois a demora em realizar a troca de contexto pode tornar o tempo de
resposta do sistema muito elevado.
1
Um tick ´e definido como sendo o intervalo de tempo entre duas interrup¸c˜oes consecutivas do rel´ogio
do hardware. Esse intervalo de tempo tamb´em ´e conhecido como ciclo de tempo.
2. Gest˜ao de recursos 10
Escalonamento por prioridade
Conforme descrito, o algoritmo Round Robin trata to dos os processos como se todos
tivessem a mesma importˆancia para o sistema. Isso, no entanto, n˜ao ´e sempre verdade
para os usu´arios, nem mesmo para o sistema computacional ou para a organiza¸c˜ao, pois
alguns processos por muitas vezes s˜ao muito mais relevantes do que outros.
Houve ent˜ao a necessidade de criar prioridades para a execu¸c˜ao de processos, de forma
que processos de maior importˆancia pudessem obter o processador antes de outros, sendo,
ent˜ao, executados mais rapidamente, de acordo como foi definida a sua relevˆancia.
A fim de evitar que processos de alta prioridade sejam executados indefinidamente,
n˜ao permitindo que nenhum outro possa tamb´em ser executado, pode-se diminuir a pri-
oridade dos processos de mais alta prioridade de acordo com o tempo que eles obtˆem o
processador. Assim, mesmo os processos com baixa prioridade continuar˜ao sendo execu-
tados, por´em menos freq¨uentemente que os processos de maior prioridade. Isso ´e chamado
de envelhecimento de processos. Obviamente, o processo tem sua prioridade restaurada
assim que uma determinada condi¸c˜ao seja atingida.
Outro mecanismo para implementar prioridades, e ainda assim permitir que todos
os processos sejam executados, ´e atribuir valores de quantum diferentes de acordo com
a prioridade dos processos. Processos com maior prioridade obtˆem um quantum maior,
utilizando a CPU por mais tempo.
As prioridades dos processos n˜ao precisam ser est´aticas, podendo, ent˜ao, ser altera-
das de acordo com as necessidades do usu´ario, do sistema computacional ou da pr´opria
institui¸c˜ao que o mant´em. Tamb´em ´e poss´ıvel que o sistema altere automaticamente a pri-
oridade de seus processos a fim de atingir uma determinada meta. Em sistema Unix, por
exemplo, processos orientados a entrada e sa´ıda s˜ao priorizados em rela¸c˜ao aos processos
orientados a CPU.
Escalonamento job mais curto primeiro — SJF
Esse ´e um mecanismo especialmente utilizado em sistemas em que processos s˜ao exe-
cutados em lote, onde previamente se conhece o tempo de execu¸c˜ao do processo. A id´eia
de sistemas em lote ´e que todos os processos que precisam ser executados sejam colocados
juntos em uma unidade de entrada e, assim, o primeiro processo ´e executado at´e a sua
2. Gest˜ao de recursos 11
P4 − 2 minutos
P3 − 2 minutos
P2 − 6 minutos
P1 − 4 minutos
Tempo em minutos
2 4 6 8 10 12 14
FIFO
SJF
Figura 2.2: Ordem de execu¸c˜ao de processos pelo algoritmo SJF.
finaliza¸c˜ao, seguido de outro e assim por diante. Como esses processos s˜ao constantemente
executados pode-se predizer o tempo de execu¸c˜ao de cada um deles.
Nesse algoritmo, o processo que deve primeiramente ser escolhido para execu¸c˜ao ´e o
processo mais curto, isso porque sendo executado primeiro o tempo m´edio de resposta
total do sistema diminui. Um exemplo desse algoritmo ´e dado a seguir, conforme a figura
2.2: sejam os processos P1, P2, P3 e P4 com tempo de execu¸c˜ao em minutos de 4, 6, 2, 2
respectivamente, o tempo de resposta do sistema se os processos forem executados nessa
ordem, ´e de 4 minutos para P1, 10 para P2, 12 para P3 e 14 para P4, sendo que o tempo
m´edio ´e ent˜ao de (4 + 10 + 12 + 14) /4, ou seja de 10 minutos.
Se for utilizado o escalonador SJF, os processos P1, P2, P3 e P4 ser˜ao executados na
seguinte ordem: P3, P4, P1, P2, sendo que o tempo de resposta para P3 ´e de 2 minutos,
P4, 4, P1, 8 e P2, 14. O tempo de resposta m´edio ent˜ao ´e (2 + 4 + 8 + 14)/4, ou seja de
7 minutos.
Como SJF produz sempre o menor tempo m´edio de resposta, seria bom se ele pudesse
tamb´em ser utilizado em sistemas interativos, no entanto, para isso precisa-se prever o
tempo de execu¸c˜ao de cada processo e descobrir qual entre eles ´e o mais curto, o que ´e
dif´ıcil de se conseguir, no entanto podendo ser feito no n´ıvel de quantum.
2. Gest˜ao de recursos 12
Escalonamento de tempo-real
Sistemas operacionais de tempo-real s˜ao aqueles onde os resultados dos processos para
serem considerados corretos, devem, al´em de estarem logicamente adequados, ser produ-
zidos em um prazo previamente estipulado.
Esses sistemas s˜ao utilizados em ´areas espec´ıficas, onde o atraso na resposta dos proces-
sos do sistema pode provocar um impacto t˜ao ruim quanto n˜ao os executar. S˜ao os casos
dos sistemas de controle de seguran¸ca de ve´ıculos automotivos modernos, de espa¸conaves,
avi˜oes, sistemas de monitoramento em unidades de tratamento intensivo, etc.
Nos sistemas de tempo-real cr´ıticos (hard real-time), o n˜ao cumprimento do requisito
temporal pode ser catastr´ofico tanto no sentido econˆomico quanto em vidas humanas
[OCT02]. Um exemplo de utiliza¸c˜ao desse m´etodo seria os sistemas operacionais das
baterias anti m´ısseis que necessitam reagir no tempo exato para cumprir o seu papel.
Caso o sistema aceite um atraso toler´avel na execu¸c˜ao dos processos, o sistema ´e
conhecido como sistema de tempo-real flex´ıvel (soft real-time). Pode ser utilizado, por
exemplo, na execu¸c˜ao de aplica¸c˜oes multim´ıdia, onde o n˜ao cumprimento das metas esti-
puladas n˜ao causaria maiores danos, somente a diminui¸c˜ao da qualidade de apresenta¸c˜ao
do programa.
Os sistemas de tempo-real podem ser implementados de forma que as decis˜oes de
escalonamento s˜ao conchecidas antes mesmo que os processos estejam em execu¸c˜ao. Por
exemplo, o algoritmo de escalonamento sabe que deve executar o processo P1 antes de
todos em qualquer situa¸c˜ao, caso P1 n˜ao esteja presente ele escalonar´a os outros processos
de acordo com o mecanismo implementado. Essa t´ecnica ´e conhecida como escalonamento
est´atico, e geralmente ´e usada quando se possui um grupo de processos pequeno e bem
definido.
O escalonamento dinˆamico consiste em tomar as decis˜oes de escalonamento durante
a execu¸c˜ao dos processos de acordo com algum parˆametro, como prioridade entre os
processos, o prazo final ou o tempo que pode ser dispensado para execu¸c˜ao dos processos.
Para o Linux existem implementa¸c˜oes tanto de sistemas de tempo-real flex´ıveis, como
os [CI01, Jac02], quanto os cr´ıticos, como os [DNFW02, Yod99].
2. Gest˜ao de recursos 13
Processos e threads
Em computa¸c˜ao, um processo ´e uma instˆancia em execu¸c˜ao de um programa, incluindo
todas as suas vari´aveis e estados [FM02]. Em geral o processo ´e visto como container de
recursos como mem´oria — c´odigo e dados —, descritores de arquivos, sem´aforos, etc.
Na maioria dos sistemas operacionais de mercado a unidade b´asica de utiliza¸c˜ao do
processador n˜ao ´e processo, e sim thread. As threads pertencem aos processos e compar-
tilham com ele c´odigo, dados e outros recursos que pertencem ao processo, no entanto,
possuem seu pr´oprio contador de programa, conjunto de registradores e pilha, e podem ser
executadas separadamente. As threads s˜ao geralmente usadas em situa¸c˜oes onde tarefas
similares precisam ser realizadas ou quando tarefas necessitam ser executadas simultanea-
mente dentro do processo. Por exemplo, um servidor de e-mail que possa receber conex˜ao
de v´arios clientes. Essas conex˜oes p odem ser gerenciadas por threads, uma para cada
conex˜ao, para que o processo do servidor de e-mail possa atender a v´arias requisi¸c˜oes ao
mesmo tempo.
A utiliza¸c˜ao de threads melhora a interatividade de uma aplica¸c˜ao, j´a que uma thread do
processo pode ser, por exemplo, bloqueada, enquanto o processo continua as suas demais
opera¸c˜oes normalmente. Tamb´em pela economia de tempo na cria¸c˜ao dos processos e na
troca de contexto, visto que a thread utilizar´a os recursos j´a criados para o seu processo.
Em sistemas multiprocessados, cada thread pode estar rodando em paralelo, diminuindo
o tempo de execu¸c˜ao total.
As threads s˜ao recursos l´ogicos do sistema operacional e po dem ser implementadas
conforme os modelos abaixo:
Modelo Muitos-para-um : o gerenciamento das threads nesse modelo ´e feito no espa¸co
do usu´ario. Tamb´em s˜ao conhecidas como threads de usu´ario.
´
E imposs´ıvel execut´a-
las em paralelo em sistemas multiprocessados. Quando uma thread de usu´ario ´e
bloqueada todas as demais threads do mesmo processo s˜ao bloqueadas tamb´em;
Modelo Um-para-um : nesse modelo cada thread do usu´ario ´e mapeada em uma th-
read do n´ucleo. Cada thread ´e executada separadamente, podendo se beneficiar
do paralelismo em sistemas multiprocessados. O bloqueio de uma thread n˜ao im-
plica no bloqueio do processo como um todo. O Windows NT, o OS/2 e o Linux
implementam esse modelo;
2. Gest˜ao de recursos 14
Modelo Muito-para-muitos : nesse modelo as threads de um processo do usu´ario s˜ao
combinadas em um menor ou igual n´umero de threads no n´ucleo. Os escalonamento
´e feito tanto no n´ıvel do usu´ario quanto no n´ıvel do n´ucleo. Esse modelo ´e mais
flex´ıvel, no entanto muito mais complexo, exigindo que o programador defina quan-
tas threads o n´ucleo ter´a para o processo e como ser´a feita a sua execu¸c˜ao. Os
sistemas operacionais IRIX, o Solaris e o Digital Unix utilizam esse modelo.
2.2.2 Gerˆencia de mem´oria
Mem´oria ´e um comp onente computacional que permite armazenar dados e c´odigos
de programas temporariamente a fim de permitir a execu¸c˜ao dos processos na CPU.
´
E
tamb´em conhecida como RAM, ou mem´oria de acesso aleat´orio. Na arquitetura atual
dos computadores, um processo para ser executado necessita estar em mem´oria, pois ´e
nela que o processador busca as instru¸c˜oes para execu¸c˜ao. Cada processo obt´em uma
quantidade finita de mem´oria de acordo com sua pr´opria necessidade. Assim sendo,
quanto mais mem´oria o computador possui, mais processos podem ser armazenados nela
simultaneamente, tornando um sistema multiprogramado mais eficiente. Os dados e os
c´odigos s˜ao armazenados na mem´oria de forma vol´atil, isto ´e, eles s˜ao perdidos assim que
a mem´oria p´ara de receber energia.
Sendo a mem´oria um componente de tamanho finito (256MBs, 512MBs, etc.), n˜ao ´e
poss´ıvel armazenar nela infinitos processos, nem tampouco processos muito grandes que
n˜ao possam se ajustar `a mem´oria. Caso a mem´oria n˜ao seja suficientemente grande para
alocar todos os processos, o sistema pode utilizar o disco r´ıgido para armazenar o c´odigo
e os dados dos processos enquanto n˜ao est˜ao sendo executados. A utiliza¸c˜ao do espa¸co
em disco mais a mem´oria f´ısica como ´area de aloca¸c˜ao ´e conhecida como mem´oria virtual.
Como o acesso ao disco ´e muito mais lento do que o acesso `a mem´oria, computadores
com pouca quantidade de mem´oria tem a sua eficiˆencia comprometida devido ao grande
uso de disco. Assim, processos que se mantˆem o tempo todo em mem´oria f´ısica s˜ao mais
rapidamente executados em compara¸c˜ao aos que utilizam o disco. O espa¸co em disco
utilizado para armazenar informa¸c˜oes da mem´oria f´ısica ´e chamado de ´area de swap.
O m´etodo mais utilizado para implementa¸c˜ao da mem´oria virtual ´e o da pagina¸c˜ao,
que consiste no mapeamento dos endere¸cos de mem´oria internos do processo, os endere¸cos
2. Gest˜ao de recursos 15
virtuais, em outros endere¸cos, os reais ou f´ısicos. Ou seja, os endere¸cos de mem´oria que os
processos referenciam s˜ao posi¸c˜oes de mem´oria relativas a endere¸cos f´ısicos. O comp onente
computacional respons´avel pelo gerenciamento da mem´oria virtual ´e a MMU (Memory
Management Unit), Unidade de Gerenciamento de Mem´oria.
Os endere¸cos gerados pelos processos, os endere¸cos virtuais, formam o espa¸co de en-
dere¸co virtual que ´e dividido em p´aginas. As p´aginas s˜ao unidades de mem´oria onde os
processos s˜ao armazenados. A mem´oria f´ısica ´e dividida em quadros [TW97] que possuem
o mesmo tamanho das p´aginas e podem armazenar o conte´udo de uma p´agina.
Quando um programa ´e executado, seu c´odigo e seus dados s˜ao colocados nas p´aginas
de mem´oria, que podem estar tanto em swap quanto na mem´oria. A medida em que ´e
requerido o c´odigo ou os dados dos processos que est˜ao em p´aginas armazenadas em disco,
ocorre uma interrup¸c˜ao chamada de falta de p´agina que notificar´a o sistema operacional
que uma p´agina necess´aria para a continuidade de execu¸c˜ao do processo n˜ao est´a em
mem´oria. Caso n˜ao haja mais quadros vazios, ou seja, toda a mem´oria f´ısica est´a alocada,
um algoritmo escolhe uma das p´aginas em mem´oria para ser guardada em disco e o quadro
relativo a sua posi¸c˜ao ´e ent˜ao utilizado. Com isso, os processos podem at´e o cupar um
espa¸co maior que o tamanho da mem´oria f´ısica e eles ainda assim ser˜ao executados. A
figura 2.3 apresenta a rela¸c˜ao entre os endere¸cos internos aos processos com os endere¸cos
reais do computador.
Quando ocorre uma falta de p´agina, o sistema deve escolher uma p´agina que ir´a ser
removida da mem´oria para dar lugar `a p´agina que necessita ser carregada. Existem
v´arios algoritmos de escolha da p´agina que deve ser retirada de mem´oria. A seguir s˜ao
apresentados os algoritmos mais utilizados para esse fim.
Algoritmo ´otimo
O algoritmo ´otimo seria aquele que descarta a p´agina que levar´a mais tempo para
ser referenciada pelos processos entre todas as outras que est˜ao na mem´oria f´ısica. Este
algoritmo seria o ´otimo, pois n˜ao gastaria tempo computacional retirando uma p´agina
que vai ser utilizada logo em seguida. No entanto, este algoritmo ´e imposs´ıvel de se
implementar, pois os sistema op eracional n˜ao sabe quais p´aginas ser˜ao referenciadas nas
pr´oximas instru¸c˜oes.
2. Gest˜ao de recursos 16
4−8K
8−12K
12−16K
16−20K
20−24K
0−4K
24−28K
32−36K
28−32K
36−40K
40−44K
Memória Virtual
Página
0−4K
Memória Física
4−8K
8−12K
12−16K
16−20K
20−24K
0−4K
Quadro de Página
Figura 2.3: Rela¸c˜ao entre endere¸cos virtuais e endere¸cos f´ısicos.
First In, First Out — FIFO
Esse algoritmo consiste em descartar as p´aginas mais antigas que est˜ao em mem´oria.
Para isso, o sistema operacional guarda informa¸c˜oes da ordem de entrada da p´agina em
mem´oria atrav´es de uma lista, na qual o seu in´ıcio ´e a referˆencia para a p´agina mais
antiga. Quando ocorre uma falta de p´agina, a p´agina referenciada pelo in´ıcio da lista ´e
retirada da mem´oria e a p´agina que precisa ser carregada ´e inserida no final da lista.
Esse algoritmo, apesar de funcional, n˜ao ´e eficiente, pois estar em mem´oria a mais
tempo n˜ao ´e sinˆonimo de n˜ao ser utilizada. Assim sendo, se a p´agina que se encontra
no in´ıcio da lista for muito utilizada, logo dever´a ser carregada novamente em mem´oria,
disperdi¸cando tempo de execu¸c˜ao.
Segunda chance
Uma varia¸c˜ao da implementa¸c˜ao do FIFO ´e verificar se a p´agina referenciada pelo in´ıcio
da fila n˜ao foi utilitizada recentemente, ent˜ao ela pode ser imediatamente substitu´ıda. No
entanto, se ela foi utilizada, ela ´e colocada no final da fila. O sistema, ent˜ao, verificar´a se a
p´agina referenciada pelo n´o que agora se encontra no in´ıcio da fila foi tamb´em recentemente
utilizada e a substituir´a ou a colocar´a no final da fila de acordo com o resultado do teste,
2. Gest˜ao de recursos 17
e assim por diante.
Esse algoritmo possui uma leve vantagem sobre o FIFO em rela¸c˜ao a troca de p´aginas
que est˜ao sendo utilizadas, por´em, se todas as p´aginas estiverem sendo utilizadas, o algo-
ritmo se tornar´a um FIFO puro.
N˜ao recentemente utilizada
O hardware para controle de mem´oria virtual implementa um mecanismo para saber
o estado de cada p´agina, ou seja, ele guarda informa¸c˜oes sobre as p´aginas referenciadas
pelos processos. Para isso, cada p´agina possui um bit R que quando setado indica que
a p´agina foi utilizada. Quando ocorre um tick do rel´ogio o bit R ´e zerado. Isso permite
que o sistema saiba se a p´agina foi recentemente utilizada. O hardware tamb´em guarda
a informa¸c˜ao de modifica¸c˜ao da p´agina em um bit chamado M. Este bit ´e setado caso a
p´agina tenha sido modificada, para que no momento de sua substitui¸c˜ao o sistema saiba
se ela necessita ser gravada novamente em disco. O bit M n˜ao ´e zerado quando ocorre o
tick do rel´ogio, pois sen˜ao uma p´agina modificada poderia ser descartada.
Esse algoritmo divide as p´aginas que est˜ao em mem´oria em classes de acordo com as
informa¸c˜oes do estado de cada uma delas:
• classe 0: n˜ao-utilizada, n˜ao-modificada;
• classe 1: n˜ao-utilizada, modificada;
• classe 2: utilizada, n˜ao-modificada;
• classe 3: utilizada, modificada.
Assim, o algoritmo escolhe uma p´agina da classe de numera¸c˜ao mais baixa para dar
lugar `a nova p´agina que est´a sendo carregada. Caso nenhuma p´agina se encontre nessa
classe, uma p´agina da classe superior ´e escolhida.
Com isso, o algoritmo consegue escolher p´aginas que n˜ao foram recentemente utiliza-
das, antes de descartar uma que est´a sendo utilizada constantemente. N˜ao ´e um algoritmo
´otimo, mas ´e freq¨uentemente adequado.
2. Gest˜ao de recursos 18
Menos recentemente utilizada — LRU
Outro m´etodo que tem uma boa aproxima¸c˜ao do algoritmo ´otimo para troca de p´aginas
´e retirar de mem´oria a p´agina que foi menos recentemente utilizada, ou seja, a p´agina que
permaneceu mais tempo sem ser referenciada p or nenhuma instru¸c˜ao.
Para que seja poss´ıvel a implementa¸c˜ao desse algoritmo ´e necess´ario que o hardware
a cada instru¸c˜ao incremente um contador espec´ıfico para a p´agina em mem´oria que foi
utilizada naquela instru¸c˜ao.
Quando ocorrer uma falta de p´agina, o sistema operacional escolher´a para substitui¸c˜ao
a p´agina com o menor valor em seu contador. O mesmo mecanismo pode ser implemen-
tado utilizando-se matrizes. Um m´etodo semelhante pode ser implementado via software
utilizando os valores de R, que ´e o bit que armazena a informa¸c˜ao de utiliza¸c˜ao da p´agina.
Alguns sistemas operacionais de mercado permitem setar o n´umero m´aximo de p´aginas
em mem´oria que um processo pode ter, bem como setar o m´aximo de espa¸co de endere¸cos
de um processo.
Como manter o pro cesso em mem´oria f´ısica incrementa sua velocidade, visto que n˜ao
faz uso de disco, ´e importante ter um mecanismo que privilegie o uso da mem´oria por
processos espec´ıficos, conforme sua necessidade.
2.2.3 Gest˜ao de disco
O disco ´e um dispositivo para armazenamento de dados de forma n˜ao-vol´atil. Um
disco ´e na realidade um conjunto de superf´ıcies circulares magn´eticas que s˜ao rotaciona-
das juntas. Em ambos os lados de cada superf´ıcie existe uma cabe¸ca de leitura e grava¸c˜ao
respons´avel por ler e escrever dados. Essas cabe¸cas se movimentam juntas, isto ´e, se uma
cabe¸ca estiver sobre determinada posi¸c˜ao na superf´ıcie, todas outras tamb´em estar˜ao na
mesma posi¸c˜ao em suas respectivas superf´ıcies. Cada superf´ıcie ´e dividida em trilhas, que
s˜ao ´areas circulares concˆentricas. Elas s˜ao divididas em peda¸cos menores denominados
setores. S˜ao neles que as informa¸c˜oes s˜ao armazenadas. Os setores tamb´em s˜ao as uni-
dades de transferˆencia de dados entre o disco e o sistema computacional. O conjunto de
trilhas de mesma posi¸c˜ao nas diferentes superf´ıcies ´e chamado de cilindro.
Cada disco possui um tamanho que ´e a quantidade m´axima de bytes que podem
2. Gest˜ao de recursos 19
ser armazenados nele, geralmente medido em gigabytes (GBs). A banda de um disco
´e a quantidade m´axima de dados que p odem ser transferidos entre o disco e o sistema
computacional, sendo medido em megabytes por segundo (MBs/s).
Em sistemas operacionais Unix ´e poss´ıvel limitar o espa¸co em disco utilizado por um
usu´ario ou grupo de usu´arios, bem como limitar o n´umero de inodes
2
utilizado por eles
[Kar01]. Para tanto deve-se definir o limite desejado e habilitar o sistema de cotas atrav´es
do conjunto de utilit´arios quota.
Embora exista o sistema de cotas para limitar o uso do espa¸co em disco na maioria
dos sistemas operacionais de mercado, n˜ao h´a nenhuma maneira de controlar a utiliza¸c˜ao
da banda de disco [CI01]. Isso se deve ao fato de que o algoritmo de prioriza¸c˜ao de acesso
ao disco ´e feito com base na posi¸c˜ao em que se deseja acessar os dados no disco. A seguir
ser˜ao descritos os principais algoritmos para agendamento das requisi¸c˜oes de grava¸c˜ao e
leitura em disco.
First-Come, First-Served — FCFS
Nesse algoritmo o processo que vai primeiramente ter a sua requisi¸c˜ao de escrita ou
leitura em disco satisfeita ´e aquele que primeiro requisitou uma a¸c˜ao no disco. Esse
algoritmo n˜ao tem como objetivo otimizar o tempo de busca ou mesmo do deslocamento
da cabe¸ca do disco.
Shortest Seek First — SSF
Nessa t´ecnica os dados que est˜ao pr´oximos da cabe¸ca de leitura do disco s˜ao lidos ou
gravados antes, e o processo a quem eles pertencem ´e privilegiado. Com esse algoritmo
´e poss´ıvel diminuir muito o deslocamento da cabe¸ca do disco. No entanto, quando h´a
uma sobrecarga de requisi¸c˜oes a cabe¸ca tender´a a ficar sobre uma determinada ´area do
disco, pois tentar´a atender sempre as requisi¸c˜oes que est˜ao mais pr´oximas, gerando um
conflito entre o deslocamento da cabe¸ca do disco e o tempo de resposta m´ınimo para as
requisi¸c˜oes e a justi¸ca no acesso ao disco entre os processos.
2
Inode ´e uma estrutura de dados que armazena informa¸c˜oes sobre os arquivos em um sistema de
arquivo Unix. Existe um inode para cada arquivo. Um arquivo ´e identificado de forma ´unica pelo
sistema de arquivos que ele reside e p elo n´umero de seu inode nesse sistema [Fou01].
2. Gest˜ao de recursos 20
Algoritmo do elevador
Como o nome j´a diz, esse algoritmo possui a mesma pol´ıtica de decis˜ao de deslocamento
da cabe¸ca de grava¸c˜ao que os elevadores convencionais. Basicamente, a cabe¸ca do disco
permanece na mesma dire¸c˜ao que ela est´a se movimentando at´e que todas as requisi¸c˜oes
que se encontram `a sua frente naquela dire¸c˜ao sejam atendidas ou que o bra¸co atinja o
limite f´ısico do hardware. Quando isso acontece a dire¸c˜ao de movimenta¸c˜ao ´e invertida e
as requisi¸c˜oes v˜ao sendo atendidas at´e que n˜ao haja mais nenhuma requisi¸c˜ao pendente
naquela dire¸c˜ao. Esse algoritmo al´em de minimizar o deslocamento da cabe¸ca do disco,
n˜ao implica em diminui¸c˜ao do tempo de resposta mesmo quando h´a uma sobrecarga de
requisi¸c˜oes.
No Linux, por exemplo, o algoritmo utilizado para o agendamento das requisi¸c˜oes de
a¸c˜oes em disco ´e o algoritmo do Elevador, otimizando o tempo de busca e aumentando o
desempenho de entrada e sa´ıda. No entanto, como na maioria dos sistemas operacionais
modernos, n˜ao h´a como priorizar o atendimento das requisi¸c˜oes dos processos de maior
importˆancia para a organiza¸c˜ao ou para o usu´ario.
2.2.4 Gest˜ao de rede
A interface de rede ´e um dispositivo que conecta o computador com outros compu-
tadores ou perif´ericos usando algum tipo de meio de comunica¸c˜ao, como cabo coaxial,
par-tran¸cado, r´adio, fibra ´optica, etc. Existem v´arios padr˜oes de comunica¸c˜ao entre in-
terfaces de rede, sendo a mais comum a Ethernet. Com um dispositivo de rede um
computador ´e capaz de enviar e receber dados encapsulados em forma de pacotes.
Os processos que desejam utilizar a rede fazem requisi¸c˜oes de envio de pacotes ao n´ucleo
do sistema operacional. Se houver v´arias requisi¸c˜oes de envio no mesmo per´ıodo de tempo,
o n´ucleo deve decidir qual o pacote dever´a ser enviado primeiro, quais v˜ao esperar e quais
ser˜ao descartados. O mesmo pode ocorrer com os pacotes que s˜ao recebidos pela interface
de rede. A tarefa de sele¸c˜ao de pacotes ´e realizada por um escalonador de pacotes que
pode ser implementado de v´arias maneiras.
O escalonador mais utilizado nos sistemas operacionais de mercado ´e o First In First
Out, ou seja, ser´a atendida a requisi¸c˜ao que aconteceu primeiro. Nesse algoritmo n˜ao
existe uma pol´ıtica de atender antes processos com maior prioridade, nem existe controle
2. Gest˜ao de recursos 21
da banda utilizada por um processo ou usu´ario. O seu objetivo ´e simplesmente transmitir
os pacotes pela rede da forma mais simples.
Entende-se por banda a quantidade de dados que podem trafegar entre a interface
local de rede e outro ponto na rede. A banda de rede ´e geralmente medida em megabits
por segundo (Mbs/s).
Alguns sistemas operacionais modernos, como o Linux e o Windows XP, j´a implemen-
tam outros algoritmos de escalonamento de pacotes que possuem um controle do recurso
mais sofisticado, permitindo controlar a banda de rede.
No Windows, pode-se habilitar o QoS Packet Scheduler que implementa o algoritmo
Deficit Round Robin (DRR), que aloca v´arios canais de fluxos de dados e associa os
programas a estes canais.
´
E poss´ıvel fazer reserva de banda de rede utilizando a API de
QoS do Windows.
No Linux v´arios algoritmos s˜ao implementados para QoS. O algoritmo CBQ (Class-
Based Queueing) [FJ95] classifica os pacotes que est˜ao esperando em uma hierarquia
estilo ´arvore; as folhas dessa ´arvore s˜ao escalonadas p or diferentes algoritmos. A grande
vantagem do CBQ, ´e permitir o controle n˜ao s´o do tr´afego de entrada, bem como o trafego
de sa´ıda. J´a o algoritmo Traffic Shapper ´e ´util para reduzir a taxa do fluxo de sa´ıda de
dados pela rede. Ele faz isso criando dispositivos especiais virtuais e os associando aos
dipositivos de rede f´ısicos.
Para habilitar esses algoritmos ´e necess´ario configur´a-los atrav´es de ferramentas es-
pec´ıficas. No Linux, o administrador pode controlar esses algoritmos com os utilit´arios
iproute2+tc.
Atrav´es dessas ferramentas ´e poss´ıvel determinar a banda dispon´ıvel para uma deter-
minada porta
3
, que est´a sempre associada a um processo. Assim, se se quer aumentar ou
diminuir a banda destinada a um processo, cria-se uma regra para aquela porta.
Esses algoritmos s˜ao implementados tanto para fornecer qualidade de servi¸co — QoS
— em rede, como tamb´em para uma melhor configura¸c˜ao do sistema quando trabalhando
como roteador.
Esses algoritmos associados com outros protocolos podem ser uma grande ferra-
menta para controle dos recursos. Inclusive, eles podem ser utilizados juntos com RSVP
[ZDE
+
93] que ´e um protocolo de sinaliza¸c˜ao de reserva de recursos, para garantir que
3
Porta ´e o nome dado ao ponto final de uma conex˜ao l´ogica de rede.
2. Gest˜ao de recursos 22
processos ter˜ao a banda de rede necess´aria para executar adequadamente suas tarefas.
2.2.5 Recursos internos
Descritores de arquivos
Em sistema Unix, para obter acesso aos arquivos, o processo executa a chamada de
sistema open() que abre o arquivo e retorna um valor n˜ao negativo, conhecido como
descritor de arquivo. Esse valor ´e utilizado para escrever ou ler dados do arquivo.
Existem v´arios tipos de arquivo em sistemas Unix:
• arquivos comuns;
• diret´orios, que cont´em uma lista de arquivos comuns;
• dispositivos de blocos, como discos r´ıgidos;
• dispositivos de caracteres, como teclados e mouses;
• pipes e sockets, que permitem processos trocar informa¸c˜oes entre si;
• links simb´olicos, que permitem um arquivo ter mais de um nome.
A maioria dos recursos computacionais s˜ao acessados atrav´es dessas abstra¸c˜oes de
arquivos [Tro99]. Recursos como sockets, arquivos, dispositivos de som, unidades de fita,
disquetes, terminais e informa¸c˜oes do n´ucleo s˜ao tratados como se fossem arquivos.
O sistema Linux, por exemplo, provˆe uma maneira de limitar o m´aximo de descritores
abertos no sistema inteiro ou por um processo. No diret´orio /proc/sys/fs o arquivo
file-max mantˆem o n´umero m´aximo de descritores de arquivos que podem ser usados ao
mesmo tempo por todos os processos do sistema. Para setar o limite m´aximo de arquivos
abertos por um processo utiliza-se o comando ulimit -n MAX, onde MAX ´e o n´umero
m´aximo de descritores que podem ser ab ertos.
Sockets
Socket ´e uma API de comunica¸c˜ao com as camadas mais baixas da rede, ou seja, inde-
pendente de hardware. Sockets permitem a comunica¸c˜ao ponto-a-ponto entre processos e
´e geralmente usado em implementa¸c˜oes de servi¸cos de rede.
2. Gest˜ao de recursos 23
O limite do n ´umero de sockets que um processo pode criar pode ser definido pelas
chamada de sistema setsockopt em sistemas que seguem o modelo System V e o BSD.
Sem´aforos
Sem´aforos s˜ao contadores que permitem ou n˜ao acesso aos recursos compartilhados
pelas threads ou por processos concorrentes. Suas opera¸c˜oes b´asicas s˜ao de incrementar
e decrementar o contador atomicamente. Quanto o sem´aforo possui valor positivo, ´e
permitido o acesso ao recurso compartilhado. A contr´ario, quando o sem´aforo possui
valor 0 ou negativo, o acesso ao compartilhamento ´e negado.
O seu limite de utiliza¸c˜ao ´e o n´umero m´aximo de sem´aforos abertos no sistema ou o
n´umero de sem´aforos por identificador. Nenhum outro m´etodo de controle de utiliza¸c˜ao
´e poss´ıvel.
Mem´oria compartilhada
Mem´oria compartilhada ´e uma regi˜ao de mem´oria que pode ser compartilhada por pro-
cessos ou threads do sistema.
´
E utilizada para comunica¸c˜ao entre processos e transferˆencia
de dados entre eles. Sem´aforos s˜ao utilizados para impedir o acesso simultˆaneo `a mem´oria
compartilhada evitando que dados ali armazenados fiquem incorretos ou inconsistentes.
Assim como os sem´aforos, n˜ao existe uma forma de controlar a mem´oria comparti-
lhada. Um processo tem permiss˜ao para acessar ou criar um determinado n´umero de
peda¸cos de mem´oria compartilhada e cada peda¸co tem uma m´aximo de tamanho estipu-
lado.
2.2.6 Classifica¸c˜ao dos recursos
Quando se tratando de controle de recursos, pode-se classificar os recursos em:
• preempt´ıveis e n˜ao preempt´ıveis;
• com m´etricas absolutas e com m´etricas relativas.
2. Gest˜ao de recursos 24
Recursos preempt´ıveis e n˜ao preempt´ıveis
Os recursos preempt´ıveis s˜ao aqueles que podem ser alocados aos processos e retirados
sem que corrompa a continuidade de sua execu¸c˜ao. Um exemplo desse tipo de recurso ´e
o processador, que ´e entregue a um processo para execu¸c˜ao, e logo em seguida ´e retirado
do mesmo, para ser entregue a outro. Recursos que se encontram nessa categoria s˜ao a
quantidade de mem´oria f´ısica, banda de disco e banda de rede.
J´a os recursos n˜ao preempt´ıveis s˜ao aqueles que n˜ao po dem ser simplesmente retirados
do processo sem afetar a continuidade de sua execu¸c˜ao. Se enquadram nessa categoria
a quantidade de mem´oria total (f´ısica + swap) destinada a um processo e o n´umero de
descritores abertos. Limitar o uso desses recursos em n´ıveis muito baixos pode impedir
que os processos sejam executados ou lev´a-los a erros, caso sejam negados seus pedidos
de abertura de arquivos ou aloca¸c˜ao de mem´oria.
Recursos com m´etricas absolutas e com m´etricas relativas
Os recursos com m´etrica absoluta s˜ao aqueles que se pode contabilizar de maneira
efetiva a sua utiliza¸c˜ao. Um exemplo ´e o n´umero de descritores de arquivos abertos
destinados para um determinado processo que podem ser contados em valores inteiros.
Participam dessa categoria a utiliza¸c˜ao de mem´oria f´ısica, swap e total, descritores de
arquivos e utiliza¸c˜ao do espa¸co em disco.
J´a os recursos com m´etrica relativa s˜ao aqueles que se contabilizam de forma relativa,
ou seja, em fun¸c˜ao de um segundo parˆametro, geralmente o tempo. Como exemplo, tem-
se a banda de disco que ´e calculada em fun¸c˜ao do tempo. O uso do processador, da banda
de disco e banda de rede s˜ao encaixadas nessa categoria.
2.3 Conclus˜oes
Neste cap´ıtulo foram abordados os principais recursos computacionais e como um
sistema operacional p ode realizar a gest˜ao de cada um deles. No pr´oximo cap´ıtulo ser˜ao
apresentadas cr´ıticas aos mecanismos convencionais de aloca¸c˜ao de recursos e abordagens
avan¸cadas de controle do uso dos recursos.
Cap´ıtulo 3
Mecanismos avan¸cados de gest˜ao de
recursos
3.1 Introdu¸c˜ao
No cap´ıtulo anterior foram vistos os principais m´etodos utilizados pelos sistemas ope-
racionais modernos para gerenciar a distribui¸c˜ao dos recursos mais relevantes de um com-
putador. Esses m´etodos s˜ao geralmente desenvolvidos de forma a satisfazer a maioria
das necessidades comuns dos sistemas computacionais das organiza¸c˜oes ou dos usu´arios.
No entanto, esses m´etodos nem sempre s˜ao os mais adequados para serem utilizados em
situa¸c˜oes espec´ıficas onde se pode querer um controle mais refinado ou sofisticado do uso
dos recursos.
Nesse cap´ıtulo ser´a discutida a abordagem cl´assica de gest˜ao de uso do processador
em sistemas convencionais, conhecida como escalonamento baseado em prioridades. A
seguir, abordagens alternativas permitindo um controle mais sofisticado desse recurso
ser˜ao discutidas e comparadas.
3.2 Escalonamento baseado em prioridades
Um sistema operacional deve ser projetado de forma que, em situa¸c˜ao normal, todos
os processos possam obter acesso aos recursos computacionais e possam ser executados
de maneira satisfat´oria. Os processos devem conseguir acesso aos recursos mesmo quando
3. Mecanismos avan¸cados de gest˜ao de recursos 26
muitos destes disputam o acesso `aqueles, e quando n˜ao for poss´ıvel atender a todas as
requisi¸c˜oes de acesso a um recurso em um determinado instante, o sistema operacional tem
a responsabilidade de escolher quais processos obter˜ao acesso ao recurso e quais dever˜ao
esperar, de maneira que todos processos tenham a garantia que ser˜ao executados, mesmo
que isso comprometa o tempo de execu¸c˜ao de um ou mais deles.
No entanto, o sistema operacional pode n˜ao fazer a melhor escolha de quem ter´a acesso
priorit´ario aos recursos, pois n˜ao conhece a importˆancia de cada um dos processos para o
sistema como um todo ou para a organiza¸c˜ao que o mant´em. Os sistemas operacionais de
mercado implementam somente um mecanismo de prioridade determinado por um ´unico
crit´erio para estabelecer a ordem de importˆancia na obten¸c˜ao dos recursos computacionais,
ignorando que existem muitas outras vari´aveis que poderiam ser levadas em conta para
fazer tal escolha.
Isso pode ser notado no exemplo a seguir: se v´arios processos desejam escrever dados no
disco r´ıgido, sendo que limita¸c˜oes f´ısicas restringem a taxa de tranferˆencia de dados, alguns
desses processos devem esperar que outros processos utilizem esse recurso primeiro, para
que s´o ent˜ao eles possam guardar os seus pr´oprios dados. Em grande parte dos sistemas
operacionais a escolha dos processos que ser˜ao primeiramente atendidos ´e feita atrav´es de
um algoritmo, conhecido como elevador, como visto na se¸c˜ao 2.2.3, que visa distribuir o
acesso ao disco de forma homogˆenea entre os requisitantes ao mesmo tempo em que busca
otimizar os movimentos do bra¸co de leitura. A decis˜ao neste caso ´e feita somente com
base no deslocamento do bra¸co e na uniformidade de acesso ao dispositivo, sem mesmo
verificar a prioridade que o processo possui ou a sua importˆancia para o sistema. Com
isso, a escolha nem sempre ´e a mais adequada para a organiza¸c˜ao e nem mesmo para o
sistema computacional.
A tabela 3.1 apresenta os resultados de um experimento que visa demonstrar como
um sistema operacional t´ıpico distribui o processador entre v´arios processos requisitantes
usando o escalonamento baseado em prioridades. V´arios sistemas operacionais utilizam
a prioridade do processo — que ´e um valor definido no lan¸camento do processo, podendo
ser alterado durante a vida dele — como parˆametro de escolha de qual processo tem
prioridade no uso da CPU. O primeiro teste est´a representado na tabela na terceira
e quarta linha, e mostra a utiliza¸c˜ao do processador por v´arios processos (P1 a P5)
3. Mecanismos avan¸cados de gest˜ao de recursos 27
Tabela 3.1: Uso do processador por N processos com diferentes prioridades durante a
inser¸c˜ao de um novo processo.
P1 (-20) P2 (-10) P3 (0) P4 (10) P5 (20) P6
Inicial 37,9% 27,6% 20,7% 10,3% 3,4%
Inserindo P6 (-20) Nova fatia 27,3% 19,7% 14,8% 7,4% 2,5%
27,3%
Varia¸c˜ao 27,9% 28,6% 28,5% 28,1% 26,4%
Inserindo P6 (-10) Nova fatia 29,3% 21,3% 16,0% 8,0% 2,7%
21,3%
Varia¸c˜ao 22,9% 22,8% 22,7% 22,3% 20,0%
Inserindo P6 (0) Nova fatia 31,2% 22,8% 17,0% 8,5% 2,8%
17,0%
Varia¸c˜ao 17,6% 17,3% 17,8% 17,4% 17,6%
Inserindo P6 (10) Nova fatia 33,0% 24,0% 20,0% 9,0% 3,0%
9,0%
Varia¸c˜ao 12,9% 13,0% 13,38% 12,6% 11,7%
Inserindo P6 (20) Nova fatia 36,5% 22,8% 17,0% 8,5% 11,7%
3,3%
Varia¸c˜ao 3,7% 3,9% 3,8% 3,8% 2,9%
com diferentes prioridades de execu¸c˜ao
1
. Ent˜ao, em um determinado instante um novo
processo ´e inserido no sistema (P6), esse com prioridade (−20), que ´e a mais alta em
sistemas Unix. As linhas em preto mostram o impacto que a inclus˜ao desse novo processo
causou na utiliza¸c˜ao do processador pelos demais pro cessos. Outros testes tamb´em est˜ao
detalhados nas linhas subseq¨uentes.
Nas linhas entituladas varia¸c˜ao, pode-se verificar que a inser¸c˜ao de um novo processo
afeta os demais processos de forma semelhante, n˜ao importando a sua prioridade. No
entanto, seria de se esperar que os processos de maior prioridade sofressem um impacto
menor na utiliza¸c˜ao do processador quando o novo processo fosse inserido, ao mesmo
tempo que os de menor prioridade absorvessem mais o impacto da inser¸c˜ao. Embora
em valores relativos todos os processos tenham impacto similar, em valores absolutos o
processo mais afetado ´e o de maior prioridade, sendo ele o que mais cede tempo para que
o novo processo possa ser executado.
O mesmo experimento foi realizado no sistema operacional Windows XP com Service
Pack 2, com resultados que n˜ao puderam ser analisados adequadamente, pois este sistema
operacional trata as prioridades de uma forma um tanto quanto inusitada. Em qualquer
situa¸c˜ao em que se tinha um processo com maior prioridade, sendo que outros proces-
sos possu´ıam prioridades diversas, o resultado era sempre muito similar. O gr´afico 3.1
2
1
Os resultados nesse teste foram obtidos em uma esta¸c˜ao Athlon XP 2600+ com 256MBs de mem´oria
rodando o Slackware Linux 10, com a vers˜ao 2.4.26 kernel
2
Os testes foram realizados em um computador Athlon XP 2600 com 512MBs de mem´oria. Foi
utilizada a ferramenta top compilada para Windows [Noe98] para aferi¸c˜ao dos resultados.
3. Mecanismos avan¸cados de gest˜ao de recursos 28
0
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7
Uso do processador (%)
Tempo em segundos
P1 - Normal
P2 - Abaixo do normal
P3 - Baixa
P4 - Normal
Figura 3.1: Uso do pro cessador por N processos no sistema operacional Windows XP
apresenta o resultado obtido neste experimento, mostrando a inser¸c˜ao do processo P4, e
concorrendo pelo uso do processor com os processos P1, P2 e P3, sendo que estes possuem
diferentes prioridades.
Nota-se que o processo que mais transferiu tempo de uso da CPU para o novo processo
foi aquele que possu´ıa maior prioridade. Em outros testes, verificou-se que possuindo um
processo de alta prioridade e outros de menor prioridade, ao inserir um novo processo
com prioridade tamb´em menor, todos os processos continuavam com o mesmo tempo
de execu¸c˜ao no per´ıodo que obtinham a CPU, no entanto demoravam mais per´ıodos de
tempo para receber novamente o processador.
Mesmo assim, com os resultados obtidos nos testes aqui descritos, fica f´acil perceber
que a solu¸c˜ao adotada pelos sistemas operacionais de mercado n˜ao distribui justamente a
utiliza¸c˜ao dos recursos entre os processos, j´a que o impacto do uso do recurso em alguns
casos foi ainda maior nos processos de mais alta prioridade, sendo que o esperado fosse que
sempre os processos de maior prioridade sofressem menos impacto em valores percentuais
do que os de menor prioridade.
Al´em disso, os parˆametros usados para a decis˜ao de escalonamento por muitas vezes
n˜ao s˜ao os melhores para uma aplica¸c˜ao espec´ıfica, ou para o sistema como um todo, ou
ainda para a organiza¸c˜ao ou para os usu´arios.
3. Mecanismos avan¸cados de gest˜ao de recursos 29
Ademais, o administrador do sistema pode desejar que o processo de maior relevˆancia
para ele ou para a organiza¸c˜ao tenha acesso garantido a uma parcela significativa de um
determinado recurso, mesmo com uma grande quantidade de processos concorrendo com
ele, para satisfazer necessidades espec´ıficas de sua institui¸c˜ao.
No modelo atual de gerencimento de recursos adotado nos sistemas op eracionais de
mercado isso n˜ao ´e poss´ıvel. E essa restri¸c˜ao de controle n˜ao ocorre somente para o
processador, mas para a maioria dos recursos computacionais.
O problema do controle dos recursos ´e ainda mais complexo considerando que muitos
recursos s˜ao interdependentes, ou seja, para que um recurso funcione adequadamente ´e
necess´ario a utiliza¸c˜ao de outro recurso. Por exemplo, um gravador de CD, ao fazer uma
grava¸c˜ao, necessita que os dados a serem armazenados sejam enviados a ele rapidamente
para que a grava¸c˜ao n˜ao seja interrompida, o que faria o CD ser inutilizado. Para que
os dados cheguem suficientemente r´apido ao gravador ´e necess´ario que o meio que est´a
fornecendo os dados para a grava¸c˜ao possa transfer´ı-los de forma satisfat´oria. Caso o
sistema operacional n˜ao forne¸ca o acesso aos dois rapidamente, a grava¸c˜ao pode n˜ao ter
sucesso.
Por melhor que seja a implementa¸c˜ao do controle de recursos do sistema operacional,
´e imposs´ıvel para ele conhecer quais s˜ao os parˆametros externos que devem ser analisados
no agendamento dos processos. Por isso, ´e necess´ario que o administrador de sistema
possa definir regras que indicar˜ao ao sistema op eracional quais as melhores escolhas a
serem feitas no momento de fornecer o acesso aos recursos.
Essas regras podem tamb´em ser usadas quando se deseja que alguns processos obte-
nham mais freq¨uentemente um recurso, ou quando se quer restringir recursos para algumas
tarefas menos relevantes para a organiza¸c˜ao, liberando por mais tempo os recursos para
os processos mais importantes. O modelo de prioridades tenta realizar essa tarefa, mas
n˜ao a cumpre por completo, j´a que mesmo tendo prioridade baixa o processo pode obter
at´e 100% de uso de um recurso caso n˜ao haja nenhum outro processo concorrendo com
ele.
Essas restri¸c˜oes de acesso aos recursos tamb´em podem ser aplicadas a processos ma-
liciosos, processos sob ataques de nega¸c˜ao de servi¸co ou processos afetados p or intrus˜oes.
Para tanto, aplicativos de detec¸c˜ao de intrus˜ao, como o Snort [Roe99], podem ser usados
para detectar a invas˜ao e os processos comprometidos, e, assim, interagindo com o sis-
3. Mecanismos avan¸cados de gest˜ao de recursos 30
tema de controle dos recursos, lan¸car restri¸c˜oes sobre eles, a fim de manter a integridade
do sistema. Ao evitar simplesmente matar o processo comprometido, mant´em-se o valor
forense das informa¸c˜oes contidas no processo para que possam ser analisadas por peritos,
responsabilizando os culpados.
Tudo isso ´e poss´ıvel com um modelo de controle de recursos que permita que o ad-
ministrador do sistema, ou os pr´oprios usu´arios, interajam com o mecanismo de controle
de recursos. Assim, processos relevantes para a organiza¸c˜ao ou para o sistema podem ser
privilegiados na obten¸c˜ao de recursos devido `a sua importˆancia. Bem como, processos de
outras naturezas, como maliciosas ou n˜ao fundamentais, podem ser restritos.
Os problemas descritos aqui foram percebidos e por isso algumas tentativas de me-
lhoramento do controle dos recursos j´a foram propostas e s˜ao apresentadas na pr´oxima
se¸c˜ao.
3.3 Mecanismos avan¸cados de gest˜ao de recursos
Nessa se¸c˜ao ser˜ao descritos alguns m´etodos alternativos de gerˆencia dos recursos com-
putacionais que visam suplantar os m´etodos convencionais.
3.3.1 Limits
O padr˜ao System V e BSD definem um mecanismo para controlar os recursos do
sistema. A biblioteca libc implementa esse mecanismo e o disponibiliza para ser usado
em sistemas Unix.
As fun¸c˜oes setrlimit e getrlimit permitem respectivamente definir e obter os limites
dos recursos que esse mecanismo ´e capaz de controlar [Pro99a]. Com o setrlimit ´e
poss´ıvel definir dois tipos de limites: o soft e o hard. O primeiro ´e utilizado como um
alerta ao processo que o limite permitido foi atingido. E o ´ultimo funciona como limite
m´aximo permitido para utiliza¸c˜ao do recurso, sendo que a partir do momento que ´e
atingido, o sistema toma providˆencias para voltar a situa¸c˜ao de satisfa¸c˜ao do limites,
inclusive matando o pro cesso que utiliza os recursos indevidamente.
´
E bom salientar que
esses limites s˜ao aplicados exclusivamente por sess˜ao de usu´ario e n˜ao por processo.
Os recursos controlados por esse mecanismo s˜ao:
3. Mecanismos avan¸cados de gest˜ao de recursos 31
• RLIMIT_CPU (processador): especifica o limite m´aximo em segundos em que um
processo pode utilizar o processador. Quando o processo atinge o limite soft um
sinal de t´ermino ´e enviado ao processo. Se o processo ainda n˜ao estiver terminado
quando o limite hard for atingido o processo ser´a morto;
• RLIMIT_CORE (tamanho do arquivo de core)
3
: ajusta o tamanho m´aximo do arquivo
de core. Quando seu valor ´e 0 (zero), o arquivo de core n˜ao ´e criado;
• RLIMIT_DATA (segmento de dados): limita o tamanho m´aximo do segmento de dados
em mem´oria utilizados pelos processos;
• RLIMIT_LOCKS (n´umero de arquivos bloqueados): define o limite m´aximo de arquivos
que podem ser bloqueados ao mesmo tempo atrav´es das fun¸c˜oes flock() e fcntl();
• RLIMIT_MEMLOCK (bytes alocados pelo usu´ario em mem´oria f´ısica): permite especi-
ficar a quantidade de bytes que ficar˜ao em mem´oria f´ısica e n˜ao ser˜ao colocados na
mem´oria virtual;
• RLIMIT_FSIZE (tamanho dos arquivos): limita o tamanho m´aximo dos arquivos que
podem ser criados pelos pro cessos;
• RLIMIT_NOFILE (n´umero de arquivos): limita o m´aximo de descritores de arquivos
que podem ser abertos p elos processos;
• RLIMIT_NPROC (n´umero de processos): ajusta o n´umero m´aximo de processos si-
multˆaneos de um usu´ario;
• RLIMIT_RSS (p´aginas na mem´oria): limita o m´aximo de p´aginas que um processo
pode manter residente na mem´oria f´ısica;
• RLIMIT_STACK (tamanho da pilha): especifica o tamanho m´aximo da pilha de cada
processo.
Mais detalhes podem ser encontrados no Manual do Programador Linux [Pro99a].
Pode-se notar que esse mecanismo permite definir somente o limite m´aximo de utiliza¸c˜ao
3
Arquivo gerado pelo n´ucleo que cont´em a imagem da mem´oria de um processo abortado devido a
problemas (falha de segmenta¸c˜ao, etc.) Pode ser utilizado por desenvolvedores para depurar programas
problem´aticos.
3. Mecanismos avan¸cados de gest˜ao de recursos 32
dos recursos, n˜ao permitindo garantir limites m´ınimos de uso. Al´em disso, s˜ao definidas
por sess˜ao de usu´ario e n˜ao s˜ao alter´aveis durante a vida dos processos.
3.3.2 Class-Based Kernel Resource Management — CKRM
O CKRM ´e um gerenciador de recursos orientado a objetivos que visa fornecer
servi¸cos diferenciados a classes de tarefas para todos os recursos que ele pode gerenciar
[NvRF
+
04a].
Uma classe ´e definida como um grupo dinˆamico de objetos do sistema operacional
de um tipo esp ec´ıfico, como processos e threads. As classes possuem compartilhamentos
associados aos recursos do sistema [NvRF
+
04b], que s˜ao definidos pelo administrador do
sistema. Cada classe obt´em compartilhamentos separados para tempo de CPU, p´aginas
de mem´oria, banda de disco e banda de rede. O escalonador do recurso tenta da melhor
forma poss´ıvel respeitar os limites dos compartilhamentos da classe.
Por exemplo, uma classe A com um compartilhamento de 50% de tempo de CPU, co-
letivamente obt´em 50% do uso do processador [NFC
+
03], ou seja, para todos os processos
da classe.
O CKRM ´e dividido em v´arios componentes [NvRF
+
04a]:
• Core: define as entidades b´asicas usadas pelo CKRM, como as classes e os eventos,
e atua como elo de liga¸c˜ao entre todos os outros componentes;
• M´etodo de classifica¸c˜ao: ´e um componente opcional e ajuda na associa¸c˜ao au-
tom´atica dos objetos do n ´ucleo `as classes de seu tipo. Atualmente existem dois
tipos de classe: de tarefas e de sockets, para o agrupamento de processos e sockets
respectivamente.
• RCFS (sistema de arquivos de controle de recursos): provˆe uma interface de cria¸c˜ao
e manipula¸c˜ao das classes baseado em diret´orios e arquivos. A comunica¸c˜ao entre o
usu´ario e n´ucleo ´e feita atrav´es de leituras e escritas em arquivos nos diret´orios do
sistema de arquivos. Os diret´orios do RCFS corresponde `as classes.
• Controladores de recursos: s˜ao os reguladores de utiliza¸c˜ao dos recursos. S˜ao im-
plementa¸c˜oes independentes e est˜ao interessadas somente no controle de um recurso
espec´ıfico, ou seja, existe um controlador para cada recurso que se deseja gerenciar.
3. Mecanismos avan¸cados de gest˜ao de recursos 33
Método de
Classificação
nível de usuário
núcleo
rcfs
core
de tarefas
classe
de sockets
classe
CPU MEM I/O listenaq
Controladores de recursos
Tipo de Classes
Figura 3.2: Projeto de implementa¸c˜ao do CKRM.
O fato de ser dividido em m´odulos permite que pessoas interessadas em construir um
novo controlador para algum recurso possam utilizar a estrutura fornecida pelo CKRM,
diminuindo consideravelmente o tempo de desenvolvimento.
A figura 3.2 [SNK05] apresenta o modelo de implementa¸c˜ao do CKRM, os seus com-
ponentes e como est˜ao relacionados entre si.
O CKRM tamb´em permite um melhor mensuramento do uso do sistema. Atualmente
´e dif´ıcil atribuir os recursos consumidos em kernel mode a uma determinada tarefa. Com
uma medida mais acurada do consumo dos recursos, o administrador do sistema pode
decidir mais precisamente no controle de uma aplica¸c˜ao em particular ou conjunto de
tarefas no sistema.
3.3.3 Linux-SRT
O Linux-SRT ´e uma vers˜ao aprimorada do Linux padr˜ao que implementa uma pol´ıtica
de escalonamento de tempo-real flex´ıvel (sotf real-time). Esse sistema pode fazer a
aloca¸c˜ao de recursos, garantindo um limite m´ınimo de utiliza¸c˜ao. Esse limite pode n˜ao ser
alcan¸cado devido a algum fator, no entanto, a aloca¸c˜ao real obtida estar´a muito pr´oxima
da especificada.
Como a aloca¸c˜ao de tempo de processamento n˜ao ´e suficiente para garantir o compor-
3. Mecanismos avan¸cados de gest˜ao de recursos 34
tamento previsto para a aplica¸c˜ao, esse modelo provˆe, al´em de um novo escalonador de
uso do processador, uma nova pol´ıtica de agendamento de disco [CI01].
O Linux padr˜ao possui trˆes pol´ıticas de escalonamento de processos para utiliza¸c˜ao
da CPU: prioridades, FIFO e tempo-real. O Linux-SRT habilita mais trˆes pol´ıticas de
escalonamento. A primeira permite que as aplica¸c˜oes especifiquem uma quantidade fixa
de uso do processador em um determinado per´ıodo. A segunda ´e utilizada para manter
uma aplica¸c˜ao suspensa, enquanto a ´ultima define que uma aplica¸c˜ao s´o pode executar
quando o processador estiver ocioso.
As mesmas pol´ıticas foram implementadas para o agendamento do uso da banda de
disco. Foram criadas mais trˆes pol´ıticas, uma onde a aplica¸c˜ao define uma quantidade
fixa de uso da banda, outra que far´a com que as requisi¸c˜oes de acesso a disco sejam
postergadas e a ´ultima que permite o processo utilizar a banda de disco somente quando
ela estiver ociosa.
A contribui¸c˜ao do Linux-SRT ´e combinar escalonadores de v´arios dispositivos, resul-
tando em um sistema com gerenciamento de QoS realmente integrado.
A unidade de aloca¸c˜ao dos recursos ´e chamada de reserve, e ´e um conjunto de processos
definido pelo usu´ario. Somente um processo pode ser inclu´ıdo no reserve por vez.
´
E poss´ıvel definir tanto uma quantidade m´ınima quanto m´axima de utiliza¸c˜ao dos
recursos, no entanto, os ajustes s´o podem ser realizados em tempo espec´ıfico de confi-
gura¸c˜ao.
3.3.4 Dynamic Soft Real-Time CPU Scheduler
O sistema DSRT — Dynamic Soft Real-Time CPU Scheduler [Jac02] — implementa
um escalonador de uso do processador em n´ıvel de usu´ario (ou seja, fora do n´ucleo) capaz
de garantir tempo de processamento em aplica¸c˜oes de tempo-real que suportem pequenos
atrasos (flex´ıveis).
Por ser um escalonador de tempo-real flex´ıvel, esse modelo tenta cumprir os prazos
determinados em contratos de QoS, mas po de ser influenciado por interrup¸c˜oes ou faltas
de p´agina. O objetivo desse mo delo ´e prover um mecanismo para permitir que aplica¸c˜oes
multim´ıdia de tempo-real possam ser executadas adequadamente.
As requisi¸c˜oes de aloca¸c˜ao de CPU s˜ao feitas utilizando 3 (trˆes) argumentos: a quan-
3. Mecanismos avan¸cados de gest˜ao de recursos 35
tidade de reserva do recurso, a dura¸c˜ao da reserva e o momento do in´ıcio da reserva. N˜ao
sendo poss´ıvel garantir o uso do processador de acordo com o estipulado pela requisi¸c˜ao,
o sistema oferece a possibilidade de diminuir a reserva, ou diminuir a dura¸c˜ao da reserva
ou mesmo alterar o in´ıcio da reserva.
A arquitetura do DSRT mostra que ele se ajusta bem para aplica¸c˜oes multim´ıdia
que, geralmente, possuem tempo de dura¸c˜ao bem determinado, necessitam de acesso
privilegiado aos recursos e toleram o n˜ao cumprimento exato do contrato de QoS.
Por se tratar de um escalonador que executa em user mode, a sua portabilidade ´e
facilitada, tanto que existem vers˜oes do DSRT para Linux, SunOS, Windows NT e Irix.
N˜ao h´a necessidade de altera¸c˜oes no n´ucleo do sistema operacional para implement´a-lo.
Infelizmente esse sistema n˜ao ´e granular, ou seja, trata somente aplica¸c˜oes que ne-
cessitam ser modificadas para que possam utilizar o mecanismo de reserva de recursos
implementado pelo DSRT.
´
E importante salientar que esse sistema n˜ao ´e dinˆamico, pois
´e necess´ario informar os requisitos de execu¸c˜ao no lan¸camento do processo.
N˜ao h´a suporte para a defini¸c˜ao de limites m´aximos de uso do processador.
3.3.5 Cap Processor Usage
Tamb´em chamado de CPUCap, consiste de um patch para o n´ucleo do Linux que
permite limitar o quanto um processo pode utilizar o processador [Gol05].
Esse modelo de gerˆencia de recursos n˜ao cria uma nova pol´ıtica no n´ucleo do Linux,
somente altera a pol´ıtica dos processos comuns, adicionando uma verifica¸c˜ao que torna
poss´ıvel a aplica¸c˜ao de limites m´aximos de utiliza¸c˜ao da CPU para algum processo es-
pec´ıfico.
A tabela de controle de processos do Linux tamb´em ´e alterada, sendo adicionada a ela
informa¸c˜oes sobre os limites de uso do processador para aquele processo. A granularidade
desse sistema ´e o processo, n˜ao permitindo que limites sejam impostos sobre qualquer tipo
de agrupamento de processos. N˜ao ´e poss´ıvel definir limites inferiores para os processos.
H´a pouca documenta¸c˜ao dispon´ıvel, e no momento a vers˜ao mais atual ´e para o n´ucleo
do Linux 2.6.6.
3. Mecanismos avan¸cados de gest˜ao de recursos 36
Tabela 3.2: Diferen¸cas entre os mo delos alternativos de gest˜ao de recursos.
Limits CKRM Linux-SRT DSRT CPUCap
Dinˆamico N˜ao Sim N˜ao N˜ao Sim
Limite Superior Sim Sim Sim N˜ao Sim
Limite Inferior N˜ao Sim Sim Sim N˜ao
Granularidade Sess˜ao Classe Classe Aplica¸c˜ao Processo
Recursos CPU CPU CPU CPU CPU
Mem´oria Mem´oria Disco
Internos Disco
Rede
Outros
3.4 Conclus˜oes
Conforme pˆode ser visto, existem v´arios m´etodos para limitar o uso dos recursos. O
problema ´e que cada um implementa somente algumas das caracter´ısticas requeridas para
um modelo de gest˜ao de controle de recursos. Por exemplo, alguns deles s´o limitam o
m´aximo do uso, ou seja, pode-se restringir o acesso aos recursos, o que pode ser requerido
para diminuir a eficiˆencia de um programa sem, no entanto, priorizar outros.
A tabela 3.2 mostra as diferentes caracter´ısticas dos modelos apresentados na se¸c˜ao
anterior.
O CKRM ´e o modelo apresentado com mais funcionalidades. Como foi mostrado, ele
implementa as fun¸c˜oes mais desejadas em um m´etodo de gerˆencia de recursos.
Poucos ainda s˜ao os sistemas que garantem o uso m´ınimo dos recursos para os pro-
cessos, isto ´e, um sistema que priorize processos espec´ıficos independentemente se os
outros v˜ao ter o acesso aos recursos restringidos em conseq¨uˆencia disso. Os sistemas que
geralmente implementam essa caracter´ıstica s˜ao aqueles que visam garantir QoS. Esses
sistemas n˜ao tem como prioridade a implementa¸c˜ao do gerenciamento dos recursos, mas
o desempenho de uma aplica¸c˜ao espec´ıfica.
No pr´oximo cap´ıtulo ser´a proposto um modelo para gerenciar os recursos de forma que
tanto limites m´aximos e m´ınimos do uso dos recursos possam ser incorporados ao sistema
e ajustados de forma dinˆamica para atender necessidades espec´ıficas.
Cap´ıtulo 4
Um modelo de gest˜ao de recursos
Neste cap´ıtulo ser´a proposto um modelo dinˆamico de gest˜ao de recursos que, como ser´a
visto, se diferencia dos modelos convencionais atuais por sua melhor adaptabilidade `as
necessidades espec´ıficas dos usu´arios e pela capacidade de responder instantaneamente `as
modifica¸c˜oes feitas nos parˆametros utilizados para aloca¸c˜ao dos recursos para os processos.
4.1 Hierarquia do uso dos recursos
Em um sistema computacional, os processos em execu¸c˜ao obtˆem acesso aos recursos
f´ısicos e l´ogicos do computador atrav´es das designa¸c˜oes feitas pelo sistema operacional.
Para que haja uma justa distribui¸c˜ao da utiliza¸c˜ao dos recursos ´e necess´ario que o sistema
operacional gerencie o uso de cada um dos recursos. Assim, a responsabilidade de escolher
os processos que ter˜ao as suas requisi¸c˜oes de acesso aos recursos satisfeitas ´e do sistema
operacional. Essa escolha ´e feita por um algoritmo que avalia qual a melhor alterna-
tiva de aloca¸c˜ao dos recursos para um melhor desempenho do sistema ou para satisfazer
prioridades impostas pelos usu´arios.
Para cada recurso existem pol´ıticas de decis˜ao de aloca¸c˜ao e agendamento dos recur-
sos destinados aos processos [SGG02]. S˜ao essas pol´ıticas que determinam a ordem de
utiliza¸c˜ao dos recursos. Como exemplo tem-se a pol´ıtica de utiliza¸c˜ao dos processadores
em sistema Unix que priorizam processos que fazem maior uso dos recursos de entrada e
sa´ıda, ao inv´es de priorizar os processos orientados ao uso do processador. Esta pol´ıtica ´e
utilizada devido ao fato que, em geral, processos que utilizam mais freq¨uentemente os dis-
positivos de entrada e sa´ıda s˜ao interativos, ou seja, aqueles que o usu´ario est´a fornecendo
4. Um modelo de gest˜ao de recursos 38
dados e, na maioria das vezes, esperando a resposta no mesmo momento.
Para possibilitar as tomadas de decis˜oes feitas pelas pol´ıticas de escolha, existem
hierarquias `as quais os processos est˜ao submetidos. A hierarquia ´e definida por algum
parˆametro, tal como prioridade, proximidade f´ısica, uso dos recursos, ordem de requisi¸c˜ao
e outros fatores.
Para tentar melhorar o desempenho de uma aplica¸c˜ao espec´ıfica, o administrador
pode, por exemplo, aumentar a prioridade deste processo, fazendo que o mesmo obtenha
o processador com mais freq¨uˆencia. Mas, mesmo alterando a prioridade do processo, isso
n˜ao garante que a aplica¸c˜ao ter´a um aumento significante no seu desempenho, j´a que esse
processo pode ter que esp erar por outros recursos que ainda n˜ao est˜ao dispon´ıveis a ele,
visto que esses outros recursos podem p ossuir pol´ıticas de decis˜ao diferentes.
A debilidade de um sistema em aumentar o desempenho de uma aplica¸c˜ao consiste,
ent˜ao, na falta de pol´ıticas globais de priorizar ou restringir o acesso aos recursos.
´
E n´ıtido que por muitas vezes ´e necess´ario modificar as pol´ıticas n˜ao somente de um
processo, mas tamb´em de todos os processos de um usu´ario ou grupo de usu´arios. Isso
se deve ao fato de que determinados usu´arios realizam atividades de maior relevˆancia
que outros. Tamb´em pode-se modific´a-las de forma a afetar um grupo de processos
relacionados, como os processos de uma mesma aplica¸c˜ao, devido `a sua importˆancia para
a organiza¸c˜ao.
Melhor seria, ent˜ao, que as pol´ıticas de decis˜ao de aloca¸c˜ao e agendamento de recursos
fossem tomadas tamb´em com base nos recursos destinados a uma thread, a um processo,
a um grupo de processos, a um usu´ario ou um grupo de usu´arios. Como os sistemas Unix
j´a implementam essas unidades, ´e natural a possibilidade de definir que elas sejam usadas
tamb´em como forma de gerenciar os recursos.
Esse cap´ıtulo visa apresentar um modelo que fornece ao administrador pol´ıticas para
a aloca¸c˜ao de recursos de forma que as atividades realizadas no sistema possam ser privi-
legiadas ou restringidas na utiliza¸c˜ao dos mesmos.
4.2 O controle dinˆamico do uso dos recursos
A proposta deste modelo ´e definir um m´etodo de controle dinˆamico de recursos para
um sistema operacional multi-usu´ario. Por controle entende-se a possibilidade de definir
4. Um modelo de gest˜ao de recursos 39
5
10
15
20
25
30
35
40
45
50
55
60
65
70
0 1 2 3 4 5
Percentual de uso
Tempo em segundos
P1
P2 e P3
5
10
15
20
25
30
35
40
45
50
55
60
65
70
0 1 2 3 4 5
Percentual de uso
Tempo em segundos
P1
P2 e P3
Figura 4.1: Aplica¸c˜ao de limite inferior (esquerda) e superior (direita) no uso do proces-
sador.
limites inferiores e superiores na disponibilidade de recursos aos processos existentes no
sistema. Esses limites podem ser estabelecidos e reajustados dinamicamente, em qualquer
momento da vida das atividades que ser˜ao controladas, n˜ao necessitando suspendˆe-las ou
reinici´a-las para a aplica¸c˜ao dos limites.
O limite superior consiste da m´axima utiliza¸c˜ao permitida do recurso, enquanto que
o limite inferior garante o aproveitamento m´ınimo do recurso caso esse seja necess´ario.
Os diagramas da figura 4.1 exemplificam os conceitos de limite inferior e superior no uso
dos recursos. No diagrama `a esquerda, trˆes processos (P1, P2 e P3) com as mesmas
caracter´ısticas e mesma prioridade disputam o tempo de processador, ficando cada um
com 33% do mesmo. Ao ajustar o limite inferior de P1 para 60% em t = 2, este passa
a usar 60% do tempo de processador, enquanto os outros 40% do recurso s˜ao divididos
entre P2 e P3. No caso do diagrama `a direita ocorre o inverso: o limite superior de tempo
de processamento de P1 ´e ajustado para 10%; neste caso, P2 e P3 dividem entre si o
percentual restante (90%).
Nos diagramas da figura 4.1 observa-se que a mudan¸ca na distribui¸c˜ao do recurso entre
os processos n˜ao ocorre imediatamente. Devido `a natureza dos algoritmos de escalona-
mento dos recursos em jogo (processador, mem´oria f´ısica e outros recursos), existe um
per´ıodo de transi¸c˜ao durante o qual o sistema deve se adequar `as novas restri¸c˜oes. Um
dos objetivos da proposta ´e minimizar a dura¸c˜ao desse per´ıodo de transi¸c˜ao.
Nesse modelo, a pol´ıtica de decis˜ao ´e feita atrav´es de regras de aloca¸c˜ao de recursos
que s˜ao definidas p elo administrador do sistema. Essas regras definem quais os recursos
poder˜ao ser acessados por quais processos e dentro de quais limites.
4. Um modelo de gest˜ao de recursos 40
Grupo de Processos
Usuário
Grupo de Usuários
Processo
Sessão
Figura 4.2: A granularidade do acesso aos recursos.
Normalmente o controle do uso dos recursos ´e feito com base em processos, visto que
estes s˜ao a unidade b´asica de aloca¸c˜ao de recursos nos sistemas operacionais correntes
1
.
Algumas vezes, no entanto, pode ser necess´ario definir regras de aloca¸c˜ao de recursos para
grupos de processos relacionados. Assim, a defini¸c˜ao de regras de aloca¸c˜ao de recursos
deve considerar diferentes n´ıveis de agrupamento de processos. Os n´ıveis considerados na
presente proposta s˜ao apresentados na figura 4.2.
O grupo de processos indicado na figura 4.2 ´e uma cole¸c˜ao de processos que possuem
um identificador de grupo (group id) em comum. Esse identificador ´e fornecido pelo pro-
cesso chamado l´ıder do grupo. Qualquer processo pode tornar-se l´ıder, bastando executar
a chamada de sistema apropriada. Tal a¸c˜ao gerar´a um novo identificador de grupo e o
tornar´a l´ıder de seu pr´oprio grupo [Lib01].
Analogamente, uma sess˜ao de processos define um conjunto de grup os de processos que
compartilham um mesmo identificador de sess˜ao (session id), pertencente originalmente
ao l´ıder da sess˜ao. Para um processo tornar-se l´ıder de sess˜ao basta executar a chamada
de sistema apropriada, gerando um novo identificador de sess˜ao.
A pol´ıtica de acesso `as regras de defini¸c˜ao de limites ´e feita com base no usu´ario que
ativa a regra. Um usu´ario pode restringir o acesso aos recursos de seus pr´oprios processos,
ou seja, ele pode definir regras aplic´aveis sobre processos, sess˜oes ou grupos de processos
de sua propriedade, contanto que sejam regras estabelecendo limites superiores no uso dos
recursos. Somente o administrador do sistema poder´a criar ou alterar regras definindo
limites inferiores, ou regras sobre usu´arios ou grupos de usu´arios.
1
Isso pode variar dependendo da natureza do recurso em quest˜ao. Por exemplo, enquanto a unidade
b´asica de aloca¸c˜ao de mem´oria ´e o processo, em n´ucleos que implementam modelos de threading 1 − 1 ou
M − N a unidade b´asica de aloca¸c˜ao de processador ´e a thread, e n˜ao o processo.
4. Um modelo de gest˜ao de recursos 41
Deve-se ter em mente que, ao definir regras de limite inferior, somente a reserva de
recursos ´e feita. A sua utiliza¸c˜ao efetiva depender´a do processo (ou grupo) ao qual a regra
se aplica, pois o n´ucleo do sistema somente pode garantir que o recurso estar´a dispon´ıvel
caso seja necess´ario, e n˜ao pode for¸car o processo a efetivamente utilizar aquele recurso
caso n˜ao o necessite.
´
E de se esperar que, ao se tratar regras independentes, um processo possa ser afetado
por duas ou mais regras, que podem, inclusive, restringir e privilegiar ao mesmo tempo
para um mesmo recurso. Quando isso o correr, a regra mais restritiva ser´a a utilizada.
A seguir ser´a proposto o modelo de controle dinˆamico para os principais recursos
computacionais.
4.2.1 Processador
O processador ´e um dos recursos que possuem m´etricas relativas. A utiliza¸c˜ao do
processador ´e medida pelo tempo que o processo o utiliza. Para que seja poss´ıvel fazer
esse controle ´e necess´ario delimitar um espa¸co de tempo, conhecido como ciclo, onde ser˜ao
feitas as quantifica¸c˜oes de utiliza¸c˜ao.
O diagrama da figura 4.3 mostra o uso do processador pelo processo P1 durante v´arios
ciclos. A dura¸c˜ao de cada ciclo ´e definida como sendo 1 (um) segundo.
Geralmente ´e atrav´es das prioridades dos processos e de compartilhamento de tempo
que os sistemas operacionais modernos implementam o mecanismo de compartilhamento
do uso do processador. Comumente s˜ao definidos pequenos per´ıodos de tempo, menores
que um ciclo, chamados quantum, que correspondem ao per´ıodo de tempo de execu¸c˜ao de
um processo durante o ciclo. A escolha de qual processo ir´a utilizar o processador ´e feita
atrav´es da prioridade do processo e de quanto ainda resta de seu quantum.
Esse mecanismo n˜ao consegue ser restritivo pois s´o estabelece prioridades na execu¸c˜ao
do processo. Se n˜ao existe disputa para a obten¸c˜ao do processador, um processo de baixa
prioridade ainda ir´a obter 100% de uso do processador, o que pode n˜ao ser o desejo
do administrador do sistema. Da mesma forma que tamb´em n˜ao ´e poss´ıvel garantir
a utiliza¸c˜ao m´ınima do processador por um processo ou grupo de processos, pois caso a
concorrˆencia pelo uso do processador seja grande, o sistema operacional tentar´a balancear
a utiliza¸c˜ao do processador entre os processos, de acordo com suas prioridades.
4. Um modelo de gest˜ao de recursos 42
40
50
60
70
80
90
100
0 1 2 3 4 5
Uso da CPU (%)
Tempo em segundos
P1
Figura 4.3: Utiliza¸c˜ao do processador por P1 durante N ciclos.
O que se prop˜oe para o controle do uso do processador nesse modelo ´e uma nova pol´ıtica
pela qual o sistema operacional determina a utiliza¸c˜ao do processador atrav´es de regras
definidas pelo administrador do sistema. Essas regras definem em valores percentuais a
utiliza¸c˜ao do processador durante um ciclo por um processo ou grupo de processos.
Para que isso seja poss´ıvel ´e necess´aria a defini¸c˜ao de um novo m´etodo de escalo-
namento de processos. Essa pol´ıtica estabelece que um processo deve deixar de usar o
processador se:
• um processo de tempo-real torna-se apto a executar;
• o percentual de utiliza¸c˜ao do processador seja atingido, se a regra define um limite
superior, n˜ao po dendo novamente obter o processador nesse ciclo;
• o percentual de utiliza¸c˜ao do processador for ultrapassado, se a regra define um
limite inferior e h´a outros processos esperando para execu¸c˜ao
2
;
2
´
E necess´ario que o processo que possui um limite m´ınimo libere o processador a fim de n˜ao monopoliz´a-
lo, e assim, outros processos possam tamb´em ser executados. Caso n˜ao haja outro processo na fila
de execu¸c˜ao, pode haver continuidade na execu¸c˜ao deste mesmo processo, no entanto, a partir deste
momento, ele concorre pelo uso do processador da mesma maneira que processos n˜ao afetados por regras
o fazem.
4. Um modelo de gest˜ao de recursos 43
• o processo termine ou seja bloqueado em uma opera¸c˜ao de entrada e sa´ıda ou de
sincroniza¸c˜ao.
Em outras palavras, um processo ou grupo de processos que s˜ao afetados por uma
regra de limite inferior devem ser executados at´e que o percentual especificado pela regra
seja ultrapassado. Ap´os esse evento ocorrer, eles podem concorrer com os outros processos
normalmente. Para um grupo de processos o percentual de utiliza¸c˜ao ´e definido pela soma
do uso do processador de todos os comp onentes do grup o durante o ciclo.
J´a uma regra de limites superior ´e satisfeita se o processo ou grupo de processos a que
ela se refere n˜ao ultrapassar o percentual de uso definido na regra. Se se trata de uma
regra de grupo de processos, a utiliza¸c˜ao do processador ´e encontrada atrav´es da soma do
uso do processador pelos integrantes do grupo.
Os processos que n˜ao s˜ao pertinentes a nenhuma regra continuam sendo escalonados
na forma usual do sistema operacional em quest˜ao. N˜ao s˜ao necess´arias mudan¸cas no
mecanismo convencional de escalonamento.
Com esse m´etodo implementado ´e poss´ıvel definir pol´ıticas de decis˜ao de aloca¸c˜ao
do processador e escalonamento de processos segundo o percentual de uso da CPU. O
administrador pode tanto criar regras de limites superiores quanto inferiores de forma que
os processos com menos ou mais relevˆancia sejam executados de maneira quantificada.
No momento da defini¸c˜ao de regras de limite inferior, deve-se verificar que a soma
dos limites de todas as regras de limite inferior n˜ao ultrapasse a quantidade m´axima de
utiliza¸c˜ao do recurso. Por exemplo, n˜ao ´e poss´ıvel criar regras definindo limites inferiores
de uso de processador nas quais a soma dos limites seja superior a 100%. Portanto, regras
que excederem a capacidade dispon´ıvel do recurso em quest˜ao devem ser descartadas.
´
E bom notar que, ao utilizar regras de limites inferiores, o sistema primeiro executa os
processos pertencentes `a regra, n˜ao liberando o processador para os outros processos at´e
que eles tenham utilizado todo o tempo ao qual eles possuem direito. Assim sendo, ao se
ajustar 70% de utiliza¸c˜ao do processador para um processo, ele executar´a por 700ms antes
de deixar a CPU. Isso pode n˜ao ser desej´avel em alguns sistemas onde essa quantidade
de tempo sem executar outro processo seja inaceit´avel. Essa caracter´ıstica do modelo ´e
alvo de trabalhos futuros, onde o sistema possa detectar se ainda h´a tempo suficiente para
executar os pro cessos da regra, e liberar a CPU para outros processos antes que a regra
4. Um modelo de gest˜ao de recursos 44
tenha sido satisfeita, ao mesmo tempo que garanta o cumprimento dela.
4.2.2 Mem´oria
Todos os recursos possuem mecanismos que hierarquizam os processos a fim de permitir
o uso adequado. A mem´oria, no entanto, possui mecanismos pouco configur´aveis que, na
maioria das vezes, n˜ao permitem a interferˆencia do administrador.
Com o intuito de permitir que o administrador possa interagir na pol´ıtica de decis˜ao
de uso da mem´oria, esse modelo prevˆe trˆes abordagens para o controle desse recurso:
• Quantidade de p´aginas do processo (ou grupo) residentes em mem´oria f´ısica (RSS -
resident set size);
• O n´umero de faltas de p´agina que ocorre;
• Quantidade de p´aginas em mem´oria virtual.
O primeiro especifica quantos quadros de p´aginas um processo (ou grupo) pode utilizar,
o que equivale a dizer quantos KBs o processo pode utilizar da mem´oria RAM. O segundo
especifica com que freq¨uˆencia ocorrer´a as faltas de p´agina para o processo (ou grupo) e o
´ultimo define o limite de p´aginas que podem estar residentes na mem´oria virtual.
Mem´oria f´ısica
Como j´a foi dito, um processo tem seu c´odigo e seus dados armazenados em p´aginas,
que podem estar tanto alocadas na mem´oria f´ısica quanto em disco. A quantidade de
p´aginas que o processo possui alocada em mem´oria f´ısica ´e conhecida como RSS, ou
tamanho do conjunto residente.
O modo de controle, quando utilizando esse m´etodo para tratar as regras de limite
inferior e superior, ´e limitar o valor m´ınimo e m´aximo, respectivamente, que o RSS pode
atingir. Esse recurso ´e considerado preempt´ıvel, visto que se uma p´agina de processo n˜ao
tem o direito de permanecer em mem´oria f´ısica ela pode ser transferida para a ´area de
swap sem corromper a execu¸c˜ao do processo.
As regras de limite superior delimitam o RSS m´aximo para o processo (ou grupo).
Assim, n˜ao ´e permitido ao processo manter mais p´aginas em mem´oria f´ısica do que o
4. Um modelo de gest˜ao de recursos 45
especificado pela regra. Caso isso ocorra ele ter´a algumas de suas p´aginas transferidas
para o swap a fim de satisfazer a condi¸c˜ao da regra.
Para regras de limite inferior o que ´e especificado ´e o n´umero m´ınimo de p´aginas
alocadas em mem´oria f´ısica para o processo (ou grupo). Isso significa que se o processo
possuir p´aginas suficientes para ocupar todo o valor estipulado pelo limite inferior, elas
ficar˜ao alocadas em mem´oria f´ısica. Por´em, se o processo n˜ao possuir p´aginas suficientes,
o recurso ser´a utilizado por outros processos at´e que sejam requeridas novas aloca¸c˜oes de
p´agina pelo processo (ou grup o) controlado por esse tip o de regra.
Deve-se notar que a soma dos valores de todas as regras de limite inferior n˜ao pode
ultrapassar o n´umero m´aximo de quadros dispon´ıveis no sistema. Caso isso ocorra a regra
deve ser descartada.
Freq¨uˆencia das faltas de p´agina
Uma falta de p´agina ocorre quando um processo que est´a sendo executado possui uma
das p´aginas necess´arias para sua execu¸c˜ao alocada em swap. A falta de p´agina ocorre para
informar ao sistema operacional que uma p´agina necess´aria para a execu¸c˜ao do processo
se encontra em disco, e dessa forma, ele possa transfer´ı-la para a mem´oria f´ısica.
Um n´umero grande de faltas de p´agina pode significar que uma ou mais p´aginas
de mem´oria que um processo usa constantemente est˜ao sendo transferidas para a ´area
de swap pela necessidade que o sistema tem de utiliza¸c˜ao de mem´oria f´ısica por outros
processos devido a escassez de mem´oria livre. Tamb´em pode significar que um processo
seja demasiadamente grande e est´a fazendo uso de v´arias p´aginas diferentes que ainda
est˜ao em disco. Impor limites sobre a quantidade de faltas de p´agina que ocorrem traduz-
se por manter um determinado n´umero de p´aginas ou em mem´oria f´ısica ou em swap de
acordo com o que especificar a regra.
Para quantificar a freq¨uˆencia de faltas de p´agina deve-se encontrar a rela¸c˜ao do n´umero
de faltas de p´agina, que ocorrem para um ou mais processos, com um determinado per´ıodo.
Como n˜ao ´e poss´ıvel saber quantas faltas de p´agina ocorrer˜ao em um per´ıodo de tempo
pr´e-definido, visto que n˜ao se pode prever a necessidade de uso das p´aginas, deve-se
utilizar uma outra maneira de estipular um per´ıodo. Neste modelo foi utilizado uma
quantidade c de faltas de p´agina ocorridas como per´ıodo. Assim sendo, um processo tem
a sua freq¨uˆencia de faltas de p´agina medida pelo n´umero de faltas de p´agina que ele gerou
4. Um modelo de gest˜ao de recursos 46
durante c faltas de p´agina ocorridas no sistema. Por exemplo, se c = 100, um processo
P1 que gerou 15 faltas de p´agina durante as 100 ´ultimas faltas ocorridas no sistema todo,
tem 15% de freq¨uˆencia de faltas de p´agina. Neste modelo, as faltas de p´agina do sistema
devem ser contadas na forma de ciclos de tamanho c.
O limite inferior de uma regra de controle da freq¨uˆencia das faltas de p´aginas especifica
que de todas as faltas de p´agina ocorridas no sistema durante o per´ıodo c, o processo
(ou grupo) a qual a regra se refere pode no m´aximo gerar a quantidade de faltas de
p´agina especificado pela pr´opria regra. Um m´etodo para se implementar isso ´e manter em
mem´oria f´ısica uma quantidade suficiente de p´aginas do processo (ou grupo) pertinentes
a regra de forma que se ele necessitar de algum dado ou instru¸c˜ao eles j´a estejam em
mem´oria f´ısica, e se estiverem em swap, a quantidade de p´aginas transferidas n˜ao vai ser
suficiente para ultrapassar o valor especificado pela regra neste ciclo c.
O algoritmo para substitui¸c˜ao das p´aginas pode ser o mesmo utilizado pelo sistema
operacional hospedeiro. Assim sendo, caso a p´agina retirada seja de um processo per-
tencente a regra, pode-se acarretar no descumprimento da regra se a p´agina retirada for
requerida novamente antes de se completar o ciclo. No entanto, um algoritmo que n˜ao
permita a retirada dessa p´agina da mem´oria se tornaria um simples m´etodo de manter
todas as p´aginas do processo na mem´oria, o que pode n˜ao ser desejado.
J´a o limite superior determina a quantidade m´axima de faltas de p´agina que os pro-
cessos pertencentes `a regra podem gerar durante o per´ıodo c. Caso os processos atinjam o
limite de faltas de p´agina permitido, eles devem esperar um novo ciclo c para continuarem
a sua execu¸c˜ao, ficando bloqueados.
´
E fato que se houver demora para a conclus˜ao do
ciclo, os processos bloqueados devido a regras de limite superior podem tamb´em demo-
rar para tornarem-se prontos para execu¸c˜ao novamente. Assim sendo, ´e bom que o ciclo
expire ap´os um tempo pr´e-determinado.
Os processos que n˜ao participam de nenhuma regra continuam a seguir a mesma
pol´ıtica de decis˜ao estipulada pelo sistema operacional.
Mem´oria virtual
A utiliza¸c˜ao da mem´oria virtual tamb´em pode ser controlada de forma que n˜ao se
permita que um processo (ou grupo) possua uma quantidade de p´aginas em mem´oria
virtual maior do que especificado, ou que se garanta espa¸co de aloca¸c˜ao para as p´aginas
4. Um modelo de gest˜ao de recursos 47
do processo (ou grup o) mesmo quando a mem´oria virtual esteja alcan¸cando seu limite
(mem´oria f´ısica + ´area de swap saturadas).
As regras para este controle devem estipular valores absolutos do n´umero m´ınimo ou
m´aximo de p´aginas que podem ser alocadas na mem´oria virtual.
Para as regras de limite superior, os processos que s˜ao alvo das regras n˜ao podem
manter um n´umero maior de p´aginas em mem´oria virtual do que o imposto pela regra.
Assim sendo, quando estes processos alocarem mem´oria, o limite estipulado ´e verificado
e, caso seja ultrapassado, o sistema n˜ao permite a nova aloca¸c˜ao de mem´oria e retorna
um c´odigo de erro.
Se no momento da cria¸c˜ao de uma regra de limite superior, os processos afetados pela
regra j´a ultrapassam o limite fixado, deve-se permitir que os processos executem acima
do limite, negando qualquer nova tentativa de aloca¸c˜ao at´e que eles liberem espa¸co em
mem´oria virtual e o limite seja satisfeito.
Os processos que fazem parte de regras de limite inferior tem o privil´egio de reserva de
espa¸co na ´area de swap no momento da cria¸c˜ao da regra de acordo com o valor definido
por esta, se houver espa¸co livre suficiente. Caso n˜ao haja, a regra n˜ao ´e criada. As p´aginas
em swap dos processos que j´a est˜ao em execu¸c˜ao no momento da cria¸c˜ao da regra tamb´em
devem ser contadas e marcadas como reservadas.
Ao transferir uma p´agina da mem´oria f´ısica para a ´area de swap, deve-se verificar se a
p´agina pertence a um processo de uma regra de limite inferior. Se o for, deve-se aloc´a-la
no espa¸co previamente reservado.
4.2.3 Disco
Basicamente pode-se fazer dois tipos de controle sobre as unidades de disco:
• banda de disco;
• espa¸co de disco utilizado.
O controle da utiliza¸c˜ao da banda de disco estabelece o quanto de dados podem ser
transferidos do sistema computacional para o disco e vice-versa por um processo ou grupo
de processos.
4. Um modelo de gest˜ao de recursos 48
O controle da utiliza¸c˜ao do espa¸co em disco geralmente destina-se a quanto um usu´ario
ou grupo de usu´arios podem armazenar de dados em seus pr´oprios diret´orios, o que a
maioria dos sistemas operacionais j´a implementa. No entanto, pode-se querer controlar
o espa¸co de disco utilizado por um ou mais processos, que ´e o objetivo deste modelo de
gest˜ao de recursos.
Banda de disco
Na maioria dos sistemas operacionais de mercado a escolha de qual dado deve ser
escrito ou lido primeiro depende somente da posi¸c˜ao da cabe¸ca de leitura e grava¸c˜ao sobre
as superf´ıcies magn´eticas do disco. Isso se deve ao fato de minimizar o deslocamento da
cabe¸ca de leitura, o que resulta em um melhor desempenho do disco.
´
E claro que a eficiˆencia na leitura e escrita em discos r´ıgidos est´a relacionada tamb´em
ao limite m´aximo da banda de disco imposta pelo hardware.
Para implementar um novo mecanismo de prioriza¸c˜ao de entrada e sa´ıda de dados em
discos r´ıgidos que considere as regras impostas pelo administrador, primeiramente deve-se
conhecer qual a banda m´axima do disco, levando em conta a sobrecarga do sistema de
arquivos. Com isso, ´e poss´ıvel aceitar limita¸c˜oes inferiores e superiores de banda de disco,
tanto em termos de percentuais de uso como valores absolutos de utiliza¸c˜ao de banda.
Como a banda ´e medida atrav´es do tempo, tamb´em aqui ´e necess´aria a defini¸c˜ao de ciclos
para que se possa mensurar o uso da banda de disco.
As regras n˜ao podem ultrapassar o limite f´ısico da banda, logo os valores de utiliza¸c˜ao
da banda de disco das regras devem estar entre 0 e 100%, sendo que o primeiro significa a
n˜ao utiliza¸c˜ao do disco e o segundo a banda m´axima de transferˆencia. Como h´a diferen¸cas
de banda de disco de sistema para sistema, ou mesmo de disco para disco, deve-se avaliar
qual ´e a banda f´ısica localmente, possivelmente na inicializa¸c˜ao do sistema.
O novo mecanismo de agendamento de utiliza¸c˜ao do disco estabelece que as requisi¸c˜oes
de leitura e grava¸c˜ao ser˜ao satisfeitas na seguinte ordem:
1. se a requisi¸c˜ao pertence a um processo ou grupo de processos que possuem uma
regra de limite inferior que ainda n˜ao foi ultrapassada nesse ciclo;
2. se a requisi¸c˜ao pertence a um processo ou grupo de processos que possuem uma
regra de limite superior que ainda n˜ao foi atingida nesse ciclo.
4. Um modelo de gest˜ao de recursos 49
Em se tratando de regras de limite superior, os processos ter˜ao suas requisi¸c˜oes aten-
didas at´e que o limite superior seja alcan¸cado. Assim que isso ocorrer, n˜ao ser´a permitido
que haja outra grava¸c˜ao ou leitura para os processos da regra at´e o in´ıcio do pr´oximo
ciclo.
As requisi¸c˜oes de processos que n˜ao fazem parte de nenhuma regra ser˜ao agendadas
segundo o algoritmo padr˜ao de escalonamento de disco. Contudo, ser˜ao satisfeitas depois
que as requisi¸c˜oes de processos participantes de regras de limite inferior sejam atendidas
e antes dos processos afetados por regras de limite superior.
Espa¸co em Disco
O controle do espa¸co em disco ´e feito sem o uso de ciclos, visto que ´e um recurso com
m´etricas absolutas. O controle aqui proposto n˜ao se destina `a limita¸c˜ao de quanto um
usu´ario pode alocar de espa¸co no sistema de arquivos, como ´e o caso do utilit´ario quota
[Kar01]. O que se deseja aqui ´e impor limites, seja superior ou inferior, de tamanho dos
arquivos abertos por um processo ou grupo de processos, que podem ser de um mesmo
usu´ario, grupo de usu´ario ou de um grupo de processos correlatos, n˜ao necessariamente
de um mesmo propriet´ario. Os valores dos limites das regras s˜ao expressos em tamanho
f´ısico real (KBs, MBs, GBs).
Esse tipo de controle pode ser utilizado quando se deseja garantir espa¸co em disco
para uma determinada aplica¸c˜ao, como por exemplo um sistema gerenciador de banco
de dados, que necessita primordialmente desse recurso para seu correto funcionamento.
Tamb´em pode ser necess´ario impedir que usu´arios criem arquivos de tamanho elevado
em pastas do sistema que n˜ao s˜ao geralmente gerenciadas por cotas, como por exemplo a
pasta /tmp em sistemas Unix.
Para implementar esse tipo de controle ´e necess´ario saber antes da cria¸c˜ao das re-
gras o espa¸co dispon´ıvel em disco. Isso porque n˜ao se pode reservar o recurso caso n˜ao
haja espa¸co suficiente de armazenamento. Assim sendo, as regras de espa¸co em disco
especificam tamanhos entre 0 e o espa¸co m´aximo dispon´ıvel no momento da cria¸c˜ao da
regra.
Para as regras que especificam valores m´aximos de utiliza¸c˜ao do espa¸co ´e necess´ario
somar o tamanho dos arquivos que est˜ao sendo manipulados pelo processo (ou grupo), de
forma a n˜ao permitir que mais dados sejam inseridos nos arquivos, nem tampouco outros
4. Um modelo de gest˜ao de recursos 50
arquivos sejam abertos, caso essa soma ultrapasse o valor definido na regra. Por se tratar
de um recurso n˜ao preempt´ıvel, n˜ao ´e poss´ıvel fechar os arquivos ou deletar dados sem
que haja comprometimento da continuidade de execu¸c˜ao dos processos envolvidos. Logo,
as ´unicas a¸c˜oes poss´ıveis de serem tomadas caso o valor da regra seja alcan¸cada s˜ao a
restri¸c˜ao de abertura de novos arquivos e grava¸c˜ao de dados.
Em regras de limite inferior ´e feita a reserva do espa¸co em disco, que pode ser feita
facilmente pelo sistema operacional sem a necessidade de grandes modifica¸c˜oes no n´ucleo
do sistema operacional.
´
E l´ogico que o sistema op eracional dever´a manter a reserva atuali-
zada `a medida em que dados v˜ao sendo gravados ou deletados pelos processos participantes
da regra.
4.2.4 Rede
O gerenciamento da banda de rede funciona de maneira an´aloga ao controle de banda
de disco. Aqui tamb´em ´e necess´ario saber qual a banda de rede m´axima no momento da
cria¸c˜ao da regra para impedir que as regras especifiquem valores que ultrapassem a banda
m´axima.
Como outros recursos com m´etricas relativas, o controle de banda de rede requer a
utiliza¸c˜ao de ciclos para estabelecer limites, que podem ser definidos p or percentual de
uso ou valores de banda (Kb/s, Mb/s, Gb/s).
O mecanismo para controle do uso da banda de rede consiste em:
1. enviar e entregar primeiramente os pacotes dos processos (ou grupos) controlados
por regras de limite inferior, at´e que o limite seja ultrapassado;
2. enviar e entregar os pacotes dos processos n˜ao controlados por regras de acordo com
a ordem de chegada (FIFO);
3. por ´ultimo, enviar e entregar os pacotes dos processos (ou grupos) controlados p or
regras de limite superior enquanto o limite n˜ao for alcan¸cado.
Deve-se notar que s´o se pode garantir a satisfa¸c˜ao das regras de limite inferior local-
mente, j´a que n˜ao se pode interferir em outros sistemas que podem estar sobrecarregados
ou mesmo n˜ao ter a banda requerida para a regra. Mais ainda, sendo o sistema dinˆamico,
4. Um modelo de gest˜ao de recursos 51
Interface
de rede
Apache Postfix SSH WUFTP
30% 20% 40% 10%
Figura 4.4: Compartilhamento da banda de rede atrav´es de regras.
n˜ao se pode pensar em um sistema de negocia¸c˜ao no momento da cria¸c˜ao da regra, visto
que o processo pode ainda n˜ao ter feito suas conex˜oes.
O modelo dinˆamico para controle da banda externa que possibilite regras de limite
inferior deve implementar um mecanismo de auto-negocia¸c˜ao durante a cria¸c˜ao das co-
nex˜oes
3
capaz de garantir o limite estabelecido pela regra ou, caso n˜ao consiga cumprir
o limite, cancelar a conex˜ao ou ainda informar ao administrador que o limite n˜ao foi
atingido e qual o novo limite que est´a sendo usado.
Para que isso funcione pode-se utilizar o RSVP (Protocolo de Reserva de Recursos)
em conjun¸c˜ao com WFQ (Weight Fair Queueing), que ´e um disciplinador para filas de
pacotes, e assim construir uma arquitetura de servi¸cos integrados capaz de garantir a
banda de rede de um fim para outro em redes IP. O WFQ ´e o disciplinador padr˜ao nos
roteadores Cisco, e pode classificar o tr´afego em diferentes fluxos baseado no endere¸co
MAC, protocolo, portas de origem e destino, etc [Bal02].
As regras s˜ao definidas em termos de processos, ou seja, n˜ao s˜ao utilizadas as portas
como m´etodo de classifica¸c˜ao. Isso porque o modelo ´e implementado tendo processos
como unidade b´asica. A figura 4.4 mostra a estrutura de compartilhamento de banda de
rede entre os processos.
A implementa¸c˜ao real desse controle pode ser baseado no CBQ (Class-Based Queu-
eing), um modelo de gerˆencia de pacotes de rede j´a dispon´ıvel para Linux e outros sistemas
operacionais [FJ95].
3
Todos os sistemas envolvidos na conex˜ao devem possuir o mesmo mecanismo de controle de banda
para que seja poss´ıvel a negocia¸c˜ao, ou que seja utilizado um mecanismo padr˜ao de aloca¸c˜ao de banda
de rede.
4. Um modelo de gest˜ao de recursos 52
4.2.5 Recursos internos
Os descritores, os sockets e os sem´aforos s˜ao recursos internos do sistema operacional
e podem ser controlados pela quantidade de cada um deles dispon´ıvel para os processos.
J´a a mem´oria compartilhada, al´em desse controle, ainda permite estipular o tamanho
da mem´oria compartilhada destinada a um ou mais processos.
Descritores
J´a foi visto que os descritores s˜ao utilizados p elos processos para obterem acesso aos
arquivos, sockets, pipes, entre outras coisas. Para fazer isso o processo invoca a chamada
de sistema open(). Essa chamada retorna um n´umero inteiro que identifica de forma
´unica o recurso acessado.
Usualmente os desenvolvedores de sistemas operacionais limitam o n´umero de descri-
tores que podem ser manipulados por um processo. No Linux, por padr˜ao, um processo
pode manter aberto no m´aximo 1024 descritores. Por´em, esse valor pode ser facilmente
alterado tanto para mais quanto para menos.
Para criar limites inferiores basta fazer a reserva do n´umero requerido de descritores
que ser˜ao usados para garantir este recurso aos processos da regra. Existe, no entanto, uma
quest˜ao ao impor limites inferiores de descritores abertos por um processo (ou grupo) que
deve ser levada em considera¸c˜ao: h´a um limite m´aximo de descritores abertos no sistema
como um todo. Assim sendo, ao se criar uma regra de limite inferior deve-se verificar se
este limite n˜ao vai ser atingido. Se for, a regra n˜ao deve ser criada.
As regras de limite superiores somente restringem quantos descritores podem ser aber-
tos por um pro cesso (ou grupo). O problema maior no controle dinˆamico dos descritores
est´a quando um processo j´a possui um determinado n´umero x de descritores abertos e, de
repente, o sistema recebe uma regra de limite superior informando que aquele processo (ou
grupo) pode ter no m´aximo y descritores abertos, sendo y um valor inteiro positivo menor
que x. N˜ao se pode simplesmente negar o acesso aos descritores que j´a est˜ao abertos, j´a
que isso poderia acarretar problemas para a integridade daquele processo (ou grup o).
Para tratar desse problema, o sistema de controle dinˆamico deve limitar o n´umero
de descritores abertos em x, n˜ao permitindo que novos descritores sejam abertos. Ao
passo que os descritores v˜ao sendo liberados, vai se decrementando o limite m´aximo de
4. Um modelo de gest˜ao de recursos 53
descritores para aquele processo (ou grupo) at´e que o limite y seja atingido, resolvendo o
problema e mantendo a integridade do processo.
Sockets e sem´aforos podem ser tratados de maneira an´aloga ao controle dos descritores.
Assim, para implementa¸c˜ao deste mo delo para esses recursos pode-se utilizar o mesmo
conceito aqui definido.
Mem´oria compartilhada
A quantidade de ´areas de mem´oria compartilhadas que podem ser abertas por um
processo (ou grupo) tamb´em pode ser tratada de maneira semelhante aos descritores. No
entanto, a quantidade de espa¸co (bytes) que cada uma delas utiliza deve ser tradado por
controle espec´ıfico, pois este deve levar em considera¸c˜ao o tamanho de mem´oria alocada
pelo processo (ou grupo) para o compartilhamento.
As regras de limite inferior devem garantir que um processo (ou grupo) poder´a alocar
mem´oria para a ´area compartilhada, reservando espa¸co em mem´oria para tanto. Enquanto
as regras de limite superior devem impedir que o processo (ou grupo) aloque mais espa¸co
de mem´oria compartilhada, em tamanho total, do que o definido pela regra.
4.3 Implementa¸c˜ao do modelo
O modelo apresentado pode ser implementado modificando partes espec´ıficas do
n´ucleo, como o escalonador para o controle do processador, o gerenciador de mem´oria
para o controle da utiliza¸c˜ao da mem´oria f´ısica, da freq¨uˆencia de faltas de p´agina e uso
da mem´oria virtual, o classificador dos pacotes de rede para a gest˜ao do uso de banda de
rede, etc.
Essas modifica¸c˜oes feitas no n´ucleo n˜ao afetariam o sistema de forma alguma at´e
o momento que uma mensagem de cria¸c˜ao de uma regra fosse recebida. A partir desse
momento, os processos das regras estariam sob a pol´ıtica de controle dinˆamico de recursos,
obedecendo, ent˜ao, aos crit´erios das regras.
As opera¸c˜oes sobre regras po dem ser feitas por chamadas de sistema que possuem as
fun¸c˜oes de:
1. criar regras:
4. Um modelo de gest˜ao de recursos 54
int setresourcelimits(recurso, escopo, identificacao, valor, tipo);
2. remover regras:
int rmresourcelimits(recurso, escopo, identificacao);
3. saber o estado da regra de um processo (ou grupo):
int getresourcelimits(recurso, escopo, identificacao, resposta).
Os argumentos necess´arios para a chamada de sistema de cria¸c˜ao de regras s˜ao: o
recurso, o escopo, a identifica¸c˜ao do escopo, o valor do limite e o tipo do limite a ser
imposto.
O primeiro argumento informa ao sistema sobre qual controle deve ser aplicado ao
recurso especificado. Pode-se assumir valores como utiliza¸c˜ao do processador, uso da
mem´oria f´ısica, freq¨uˆencia das faltas de p´agina, utiliza¸c˜ao da mem´oria virtual, da banda
de rede e de disco, do espa¸co em disco, quantidade de descritores, de sem´aforos, de sockets,
de ´areas de mem´oria compartilhada e a utiliza¸c˜ao da mem´oria compartilhada.
O parˆametro escopo notifica sobre qual granularidade a regra dever´a agir. Poss´ıveis
valores s˜ao: processo, usu´ario, grupo de usu´arios, grupo de processos ou sess˜ao.
Para identificar os pro cessos atingidos pelo escopo, o argumento identifica¸c~ao re-
cebe o id do alvo, como, por exemplo, o pid do pro cesso, o id do usu´ario, o gid do grupo
de usu´arios, etc.
Os ´ultimos dois argumentos definem, respectivamente, o valor estabelecido para regra
e o tip o do limite a ser imposto, inferior ou superior. O valor pode ser tanto percentual
quanto absoluto, dependendo somente de recurso.
A chamada de sistema para remo¸c˜ao de uma regra deve possuir os seguintes
parˆametros: o recurso, o escopo e a identifica¸c˜ao do alvo. Esses parˆametros s˜ao utili-
zados para encontrar a regra dentro do modelo dinˆamico.
Essa chamada deve primeiramente mover todos os processos alvo da regra em quest˜ao
da pol´ıtica de controle dinˆamico de recursos para a pol´ıtica de decis˜ao comum do recurso,
para depois apagar definitivamente a regra. Dessa forma, essa regra deixa de existir e os
processos continuar˜ao a sua execu¸c˜ao de acordo com as pol´ıticas do sistema operacional
utilizado.
A chamada de sistema de consulta a uma regra possui os mesmos argumentos da
chamada de sistema de remo¸c˜ao de regra, que s˜ao utilizados para achar a regra no sistema,
4. Um modelo de gest˜ao de recursos 55
Tabela 4.1: Diferen¸cas entre os modelos alternativos de gest˜ao de recursos e o modelo
proposto.
Limits CKRM Linux-SRT DSRT CPUCap Este Modelo
Dinˆamico N˜ao Sim N˜ao N˜ao Sim Sim
Limite Superior Sim Sim Sim N˜ao Sim Sim
Limite Inferior N˜ao Sim Sim Sim N˜ao Sim
Granularidade Sess˜ao Classe Classe Aplica¸c˜ao Processo Processo
Usu´ario
Grupo de usu´arios
Grupo de processos
Sess˜ao
Recursos CPU CPU CPU CPU CPU CPU
Mem´oria Mem´oria Disco Mem´oria
Internos Disco Disco
Rede Internos
Outros Rede
mais a resposta a consulta, que ´e uma estrutura com os valores da regra, sobre qual
recurso ela afeta, o escopo, o valor do limite que ela aplica, e se ´e uma regra de limite
inferior ou superior. Um modelo de estrutura pode ser encontrado na se¸c˜ao 5.4.
Pode-se pensar tamb´em em uma chamada de sistema para altera¸c˜ao dos limites de
uma regra. Ela deve receber como parˆametro, al´em do recurso, escopo e identifica¸c˜ao, o
novo limite a ser aplicado (inferior ou superior) e seu valor.
Com essas chamadas ´e poss´ıvel manipular as regras do sistema para que o modelo seja
utilizado segundo as necessidades do administrador do sistema ou da organiza¸c˜ao.
4.4 Conclus˜oes
Este cap´ıtulo apresentou a proposta do modelo de gest˜ao dinˆamica de recursos, a
finalidade do controle da maioria dos recursos computacionais e como tratar as excess˜oes
que ocorrem ao se impor limites de utiliza¸c˜ao dos recursos.
Pˆode-se verificar a necessidade de um controle mais sofisticado nos recursos de maior
importˆancia para que o sistema possa ter o desempenho adequado `as necessidades da
organiza¸c˜ao ou do administrador do sistema.
As principais diferen¸cas encontradas entre este modelo e as alternativas de controle de
recursos apresentadas na se¸c˜ao 3.3 est˜ao apresentadas na tabela 4.1.
Nota-se que o CKRM ´e o modelo alternativo de gest˜ao de recursos que mais se apro-
4. Um modelo de gest˜ao de recursos 56
xima desta proposta, no entanto a sua arquitetura visa tratar classes de processos criadas
pelo administrador, enquanto este modelo define o controle dos recursos em estruturas
pr´e-existentes em ambientes Unix. Ainda assim, o CKRM especifica um arcabou¸co para
cria¸c˜ao de controles para v´arios recursos diferentes, n˜ao os determinando, enquanto este
modelo determina quais os recursos devem ser controlados e como isso deve ser feito.
No pr´oximo cap´ıtulo ser´a descrita em detalhes a implementa¸c˜ao do controle de recursos
para o processador e como s˜ao utilizadas essas fun¸c˜oes para o seu gerenciamento dinˆamico.
Tamb´em ser´a validada a efic´acia do modelo apresentado e as conclus˜oes obtidas quando
o modelo est´a em execu¸c˜ao.
Cap´ıtulo 5
Controle dinˆamico de processador
Para validar as propostas que o modelo dinˆamico oferece, foi implementado um
prot´otipo cuja finalidade ´e aplicar este modelo na gest˜ao de processadores no sistema
operacional Linux e verificar se seu funcionamento ´e adequado e se sua utiliza¸c˜ao ´e vi´avel
em sistemas operacionais de mercado.
Este cap´ıtulo apresenta a constru¸c˜ao desse prot´otipo, as mudan¸cas realizadas no sis-
tema, a avalia¸c˜ao dos resultados obtidos e custo computacional da implementa¸c˜ao.
5.1 Descri¸c˜ao do problema
Na se¸c˜ao 2.2.1 foi visto como os sistemas operacionais de mercado gerenciam o uso
do processador. Foi mostrado tamb´em que estes sistemas n˜ao fornecem uma forma de
controle que permita aplicar regras de limites inferiores e superiores na utiliza¸c˜ao do
processador de forma dinˆamica.
Nota-se que com o mecanismo utilizado pelos sistemas atuais, um processo de baixa
prioridade pode obter qualquer percentual de utiliza¸c˜ao do processador, incluindo a
m´axima, dependendo somente da disputa que h´a pelo uso da CPU. N˜ao h´a meios de con-
trolar isto, o que pode ser um problema para as organiza¸c˜oes e tamb´em para os usu´arios
que desejam que processos espec´ıficos tenham um limite superior de utiliza¸c˜ao do proces-
sador.
Tamb´em nota-se que com este mesmo mecanismo n˜ao se pode estipular que um ou
mais processos tenham garantido um valor percentual m´ınimo de utiliza¸c˜ao da CPU. Isso
porque a pol´ıtica de escalonamento dos processos ´e baseada nas prioridades, o que n˜ao
5. Controle dinˆamico de processador 58
permite predizer a utiliza¸c˜ao da CPU pelos processos.
`
As vezes, no entanto, ´e necess´ario
que alguns processos obtenham o processador por uma determinada quantidade de tempo
para que ele possa ser adequadamente executado, como ´e o caso de processos com QoS.
Uma das defini¸c˜oes de sistema com QoS ´e que esse sistema deve ser capaz de interpretar,
garantir e executar um servi¸co requisitado adequadamente [BB96], e isso s´o pode ser
obtido por um modelo de controle que tolere e cumpra as especifica¸c˜oes do software.
Outro problema que ocorre diz respeito ao impacto que cada processo sofre ao inserir
um novo processo. A tabela 3.1 mostra o impacto na utiliza¸c˜ao do processador por
processos de diferentes prioridades. Como pode-se perceber, todos os processos absorvem
de forma semelhante o impacto no uso da CPU, diminuindo o tempo que cada processo
tem de execu¸c˜ao proporcional e aproximadamente igual. Isso pode n˜ao ser a decis˜ao mais
justa na divis˜ao do uso do recurso, j´a que o processo de maior prioridade tem reduzida
sua utiliza¸c˜ao do processador na mesma propor¸c˜ao que o processo de menor prioridade.
A seguir ser´a apresentada a descri¸c˜ao da implementa¸c˜ao do prot´otipo que utiliza o
modelo de controle dinˆamico para o gerenciamento do uso do processador visando resolver
os problemas aqui descritos.
5.2 O escalonador de processos no Linux
Um algoritmo comumente utilizado para o escalonamento de processos ´e o de priori-
dades. Nesse algoritmo, os processos s˜ao classificados por um valor atribu´ıdo a eles de
acordo com a sua relevˆancia ou necessidade de uso do processador. Processos com alta
prioridade s˜ao executados antes dos que possuem prioridade menor, enquanto processos
de igual prioridade s˜ao escalonados de acordo com o algoritmo Round Robin. O Linux, em
sua vers˜ao 2.4, da qual este trabalho trata, implementa esse m´etodo, sendo que quanto
maior ´e a prioridade do processo, maior ´e o quantum que ele recebe. Enquanto o pro-
cesso de mais alta prioridade possuir quantum para execu¸c˜ao, ele mant´em a posse do
processador [Lov03].
Como outros sistemas operacionais, o Linux ´e um sistema multiprogramado, onde
mais de um processo pode estar em execu¸c˜ao ao mesmo tempo, no qual o quantum des-
ses pro cessos ´e definido como um m´ultiplo dos ticks do rel´ogio de hardware [NFC
+
03].
Um contador denominado jiffies indica quantos ticks ocorreram no sistema desde sua
5. Controle dinˆamico de processador 59
inicializa¸c˜ao.
O escalonamento no Linux ´e do tipo preemptivo, ou seja, o processo ´e retirado de
execu¸c˜ao sem conhecimento ou interferˆencia do pr´oprio processo quando o seu quantum
estiver esgotado
1
.
O algoritmo de escalonamento do Linux divide o tempo de processamento em ´epocas
(epochs). Uma ´epoca termina quando todos os processos capazes de serem executados tem
seu quantum exaurido. Cada processo recebe um quantum calculado no in´ıcio da ´epoca,
que vai ser o tempo m´aximo de sua execu¸c˜ao nesse per´ıodo. Diferentes processos podem
possuir diferentes valores de quantum [dOCT01]. Um processo pode ser selecionado para
execu¸c˜ao v´arias vezes em uma ´epoca, contanto que seu quantum n˜ao tenha acabado.
O n´ucleo do Linux implementa duas classes de prioridades: a primeira ´e aquela de
valor nice, que ´e um n´umero de -20 a 19, sendo que quanto menor o n´umero mais alta ´e a
prioridade, e antes o processo vai ser escolhido para execu¸c˜ao. A fatia de tempo que um
processo recebe para execu¸c˜ao ´e calculada com base no valor nice do processo.
A segunda classe de prioridades ´e a utilizada exclusivamente por processos de tempo-
real, e v˜ao de 0 a 99. Esses processos s´o podem ser criados pelo super-usu´ario. Enquanto
existirem processos de tempo-real a serem executados, os processos da primeira classe de
prioridades n˜ao s˜ao selecionados para execu¸c˜ao. A maioria dos sistemas Unix modernos
implementam um esquema similar a este [Var96].
Com a finalidade de balancear o uso do processador, o escalonador monitora o uso da
CPU pelos processos comuns. Se um processo ocupar o processador por muito tempo,
ele tem sua prioridade diminu´ıda para que processos com menor prioridade possam ser
executados. Do mesmo modo, se um processo ficar muito tempo sem ser executado, a sua
prioridade ´e aumentada. Essa caracter´ıstica do sistema Linux ´e chamada de prioridade
dinˆamica. O c´aculo da prioridade dinˆamica ´e feita como base no valor nice do processo,
juntamente com o seu quantum restante.
Existem trˆes pol´ıticas diferentes de escalonamento[dOCT01]:
A primeira pol´ıtica, que ´e chamada de SCHED_FIFO ´e utilizada somente por processos
de tempo-real. Aqui um processo obt´em o processador e n˜ao o deixa at´e que:
1
O n´ucleo do Linux n˜ao ´e preemptivo, o que significa que um pro cesso po de ser preemptado somente
enquanto executando em user mode [BC00]. Processos do pr´oprio n´ucleo ou pro cessos de usu´arios que
est˜ao executando em kernel mode devido a uma chamada de sistema n˜ao s˜ao preempt´ıveis.
5. Controle dinˆamico de processador 60
• um processo de tempo-real de prioridade superior torna-se apto a executar;
• o processo libere esp ontaneamente o processador para processos de prioridade igual
`a sua;
• o processo termine, ou seja bloqueado, em uma opera¸c˜ao de entrada e sa´ıda ou de
sincroniza¸c˜ao.
SCHED_RR ´e a segunda pol´ıtica, tamb´em ´e v´alida somente para processos de tempo-real
e consiste na execu¸c˜ao do processo at´e que uma das quatro situa¸c˜oes ocorra:
• seu quantum tenha se esgotado;
• um processo de prioridade superior torna-se apto a executar;
• o processo libere esp ontaneamente o processador para processos de prioridade igual
`a sua;
• o processo termine ou seja bloqueado.
A pol´ıtica utilizada por processos comuns ´e a SCHED_OTHER . Consiste de um conjunto
de filas de prioridades dinˆamicas, sendo que os processos com maior prioridade s˜ao exe-
cutados antes, e os que possuem prioridades iguais s˜ao escalonados um ap´os o outro,
repetidamente.
O escalonador do Linux ´e executado quando h´a uma chamada expl´ıcita `a rotina do
escalonador. Essa chamada ocorre quando o sistema:
• detecta que um processo dever´a ser bloqueado em decorrˆencia de uma opera¸c˜ao de
entrada e sa´ıda ou de sincroniza¸c˜ao;
• detecta que um processo esgotou seu quantum de execu¸c˜ao;
• um processo de mais alta prioridade ´e desbloqueado pela ocorrˆencia do evento que
esperava;
• um processo explicitamente invoca o escalonador atrav´es de uma chamada de sis-
tema do tipo yield
2
.
2
A chamada expl´ıcita `a fun¸c˜ao de escalonamento feita a partir de um processo ´e conhecida como
m´etodo lazy de execu¸c˜ao.
5. Controle dinˆamico de processador 61
5.3 O algoritmo de escalonamento proposto
O algoritmo proposto diferencia-se dos modelos comuns de escalonamento por permitir
ao administrador do sistema quantificar o tempo de uso do processador pelos processos,
e poder aplicar regras para o controle desse recurso dinamicamente.
Como j´a foi visto, uma regra ´e o meio de estabelecer quais s˜ao os recursos que devem
ser dinamicamente controlados, sobre quais processos o controle incide e as condi¸c˜oes de
atua¸c˜ao. A regra p ode ser aplicada diretamente sobre um processo ou uma thread, para
os processos de um determinado usu´ario, para os processos de um grupo de usu´arios, para
um grupo de processos, ou mesmo para uma sess˜ao, conforme foi visto na figura 4.2. Esse
m´eto do foi escolhido por utilizar estruturas nativas de ambientes Unix. Poderiam ter sido
criadas novas formas de agrupar processos, tal como foi feito por [NFC
+
03], p or´em, para
aproveitar os recursos j´a dispon´ıveis no sistema, preferiu-se manter o padr˜ao Unix.
Seguindo o que foi definido no modelo, para que seja poss´ıvel notificar o n´ucleo da
existˆencia de uma nova regra, foi criada uma nova chamada de sistema, denominada
resourcelimits, que possui os seguintes parˆametros:
• resource: identifica qual o recurso a ser controlado. No prot´otipo implementado
somente o valor CPUPERC (percentual de uso do processador) est´a dispon´ıvel.
• scope: define quem ser´a afetado pela regra, ou seja, o seu escopo. Pode assumir
os valores: RLPROCESS, RLPROCESSGROUP, RLSESSION, RLUSER e RLGROUP, correspon-
dendo respectivamente ao controle de um processo, de um grupo de processos, de
uma sess˜ao e dos processos de um usu´ario ou de um grupo de usu´arios.
• target: informa o identificador do escopo em quest˜ao, ou seja, o id do processo, do
usu´ario, do grupo de usu´arios, do grupo de processos ou da sess˜ao.
• value: especifica o valor num´erico do limite a ser imposto.
• type: define o tipo do limite, que pode ser UPPER, para limite superior, e LOWER,
para limite inferior.
O valor de retorno da chamada de sistema depende do sucesso ou do erro ocorrido
na execu¸c˜ao da chamada de sistema. O valor 0 (zero) representa ˆexito, enquanto valores
negativos informam que um erro ocorreu. Entre os erros poss´ıveis est˜ao a inexistˆencia do
5. Controle dinˆamico de processador 62
identificador definido por target e a impossibilidade de definir um limite inferior, caso a
soma dos limites j´a definidos com o novo limite ultrapasse 100% de uso do recurso.
Assim que a chamada de sistema resourcelimits ´e executada, o sistema reage sobre
os processos pertinentes, colocando-os sob uma nova pol´ıtica chamada SCHED_RL (escalo-
namento via ResourceLimits) e controlando os recursos para que sejam respeitadas as
condi¸c˜oes da regra. A condi¸c˜ao se refere ao uso m´aximo permitido daquele recurso, ou ao
m´ınimo reservado para aquele recurso. Nesse caso, ´e um percentual relativo a um per´ıodo
de tempo pr´e-determinado, CPUPERC.
SCHED_RL segue a pol´ıtica definida pelo modelo, que p ode ser encontrada na se¸c˜ao
4.2.1.
Assim como proposto, o controle de acesso ´e feito durante a inser¸c˜ao ou altera¸c˜ao da
regra. Uma regra que restrinja o uso do recurso pode ser feita pelo usu´ario propriet´ario dos
processos em quest˜ao. J´a as regras que privilegiam o uso do recurso podem ser aplicadas
somente pelo administrador do sistema. Regras de limite m´aximo que reflitam sobre
processos de mais de um usu´ario tamb´em s´o podem ser aplicadas pelo super-usu´ario.
Como poder´a ser visto no apˆendice A, no momento da defini¸c˜ao de regras de limite
inferior ´e feita a verifica¸c˜ao para garantir que a soma de todas as regras de limite superior
n˜ao ultrapasse 100% de utiliza¸c˜ao de CPU, para evitar que as regras excedam a capacidade
f´ısica m´axima de execu¸c˜ao dos processos.
Na se¸c˜ao 5.4 poder´a ser visto que a reserva de recursos est´a impl´ıcita no algoritmo
desenvolvido, pois quando houver uma regra de limite inferior, os processos pertinentes
a ela s˜ao executados antes de todos os outros, garantindo o cumprimento da regra. No
entanto, esse m´etodo acarreta atraso na execu¸c˜ao de outros processos que n˜ao fazem parte
de regras de limite inferior.
A pr´oxima se¸c˜ao entrar´a mais em detalhes da implementa¸c˜ao do mecanismo de controle
dinˆamico do processador.
5.4 Descri¸c˜ao da implementa¸c˜ao
O prot´otipo de controle dinˆamico do processador foi implementado no Conectiva 9.0
sobre n´ucleo do Linux vers˜ao 2.4.21. A maior parte das altera¸c˜oes feitas foram aplicadas
sobre o pr´oprio escalonador do sistema. A lista de arquivos do n´ucleo alterados para a
5. Controle dinˆamico de processador 63
cria¸c˜ao do prot´otipo e suas modifica¸c˜oes ´e a seguinte:
• entry.S: defini¸c˜ao da chamada de sistema resourcelimits;
• init_task.c: inclus˜ao da inicializa¸c˜ao das listas e vari´aveis utilizadas pelo
prot´otipo;
• unistd.h: defini¸c˜ao do n´umero da chamada de sistema resourcelimits;
• sched.h: cria¸c˜ao da pol´ıtica SCHED_RL e inclus˜ao de um novo campo na estrutura
dos processos;
• exit.c: dele¸c˜ao de regras na finaliza¸c˜ao dos processos, se necess´ario;
• fork.c: inclus˜ao de novos processos em suas respectivas regras;
• sched.c: implementa¸c˜ao da pol´ıtica SCHED_RL;
• sys.c: implementa¸c˜ao da chamada de sistema resourcelimits;
• timer.c: verifica¸c˜ao do cumprimento das regras a cada tick do rel´ogio de hardware.
Tamb´em foi inclu´ıdo o arquivo resourcelimits.h que possui defini¸c˜oes de estruturas
utilizadas em outras partes do sistema.
No prot´otipo apresentado foi definida uma nova estrutura para armazenar as in-
forma¸c˜oes espec´ıficas para regras de controle do uso do processador. Essa estrutura ´e
chamada de TRLGroup. Com essa estrutura, foi criada uma lista que em cada n´o guarda,
al´em dos parˆametros de uma regra, mais um campo para armazenar informa¸c˜oes perti-
nentes ao uso do processador e outro campo para apontar para o pr´oximo n´o de regras.
Cada n´o ´e chamado de grupo.
struct TRLGroup {
int r es ou r c e ;
int sc ope ;
int t a r g e t ;
long va lu e ;
int type ;
int RLUSEDTICKS ;
int a c t i v e ;
int nu mb er of ele ments ;
5. Controle dinˆamico de processador 64
struct l i s t h e a d l i s t ;
} ;
Houve tamb´em a inser¸c˜ao de uma nova vari´avel no Bloco de Controle de Processos
(PCB) para que cada processo aponte para o seu grupo, caso perten¸ca a um deles.
Uma vari´avel global, RLNEXT, armazena a informa¸c˜ao de quando se iniciar´a o pr´oximo
ciclo do sistema. Um ciclo do sistema ´e definido por um determinado n´umero de vezes
que ocorre uma interrup¸c˜ao de tempo, sendo que no Linux a vari´avel HZ (freq¨uˆencia do
timer) armazena esse valor
3
. O tempo de dura¸c˜ao do ciclo ´e de 1 (um) segundo
4
. A
cada ciclo do sistema a regra deve manter a utiliza¸c˜ao do processador dentro do limite
especificado. Quando jiffies for maior que RLNEXT, o valor de RLNEXT ´e atualizado de
acordo com RLNEXT = jiffies + HZ . Nesse mesmo momento o escalonador ´e chamado
para recalcular os valores de utiliza¸c˜ao do processador por cada grupo.
Esse c´alculo consiste em determinar quantos ticks de rel´ogio essa regra possui nesse ci-
clo. A vari´avel da regra que armazena esse valor ´e RLUSEDTICKS, e ´e um valor normalizado
de acordo com HZ j´a que este pode assumir diversos valores dependendo da arquitetura
ou da pr´opria distribui¸c˜ao.
A cada tick do rel´ogio a vari´avel RLUSEDTICKS ´e decrementada. Se a regra especifica
um limite m´aximo, quando RLUSEDTICKS atinge zero os processos do escopo da regra s˜ao
impedidos de executar at´e o pr´oximo ciclo. Isso ´e feito na fun¸c˜ao update_one_process()
do controle de tempo do sistema, e pode ser visto na listagem de c´odigo abaixo.
void u p d a t e o n e p r o c e s s ( struct t a s k s t r u c t ∗p , unsigned long user ,
unsigned long system , int cpu )
{
/∗ r e s o u r c e l i m i t ∗/
i f (RLNEXT < j i f f i e s ) {
RLNEXT = j i f f i e s + HZ;
n e e d r e c a l c u l a t e = 1 ;
i f ( t h e r e a r e l o w e r r u l e s )
p−>co unter = 0 ;
}
3
No Linux 2.4, HZ ´e igual 100 para arquitetura x86.
4
O tempo de 1 (um) segundo foi utilizado por ser o valor pelo qual o timer ´e ajustado. Ao se ajustar,
por exemplo, HZ para 100, o timer ir´a gerar 100 interrup¸c˜oes de rel´ogio no sistema durante um segundo,
ou seja, de 10 em 10ms. Isso define a granularidade do sistema: timers ajustados em intervalos de 10ms,
quantum medido em intervalos de 10ms, etc [Lov02].
5. Controle dinˆamico de processador 65
i f (p−>p o l i c y == SCHED RL) {
i f (−−p−>rl gr ou p −>RLUSEDTICKS == −1) {
struct t a s k s t r u c t ∗pp ;
p−>rlgro up −>RLUSEDTICKS=0;
f o r e a c h t a s k ( pp ) {
i f (pp−>r l g r o up == p−>r l g r ou p )
pp−>c ou nte r = 0 ;
}
}
}
p−>pe r cpu u ti me [ cpu ] += u se r ;
p−>p e r c p u s t i me [ cpu ] += system ;
d o p r o c e s s t i m e s ( p , user , system ) ;
. . .
}
A fun¸c˜ao goodness() do n´ucleo do Linux ´e respons´avel por atribuir peso aos processos
para que eles possam ser escolhidos pelo escalonador. Esse peso ´e baseado em quanto
tempo de execu¸c˜ao o processo ainda possui. Essa fun¸c˜ao foi alterada de forma que pudesse
fornecer pesos muitos baixos caso o processo atingisse seu limite superior. No Linux,
um processo n˜ao ´e executado se o seu peso for igual a −1000. No caso de regras de
limite inferior, o processo ter´a o seu peso aumentado para que sempre seja escolhido
para execu¸c˜ao enquanto o limite requerido n˜ao for atingido. A listagem abaixo mostra a
parte da fun¸c˜ao goodness() que ´e respons´avel pela atribui¸c˜ao dos pesos aos processos.
Os processos que sofrem essa altera¸c˜ao de peso s˜ao aqueles que fazem parte da pol´ıtica
SCHED_RL.
i f (p−>p o l i c y == SCHED RL) {
/∗ r e s o u r c e l i m i t s ∗/
weight = p−>co un te r ;
i f ( ! n e e d r e c a l c u l a t e ) {
i f ( p−>rl gr ou p −>type == L UPPER) {
i f ( ! p−>rl gr ou p −>RLUSEDTICKS)
weight =−1001;
}
el se
i f (p−>rl gr ou p −>RLUSEDTICKS) {
weight += (KEEP RUNNING + p−>co unt er ) ;
5. Controle dinˆamico de processador 66
}
el se {
p−>co unter = NICE TO TICKS( 20 ) ; //menor
p r i o r i d a d e
weight = p−>co un te r ;
}
}
goto out ;
}
i f (p−>p o l i c y & SCHED YIELD)
goto out ;
Na inicializa¸c˜ao dos processos, foi necess´ario avaliar se os processos que est˜ao sendo
criados est˜ao associados a alguma regra. Se isso ocorrer, os processos em quest˜ao s˜ao
adicionados ao grupo pertinente e s˜ao executados nos limites impostos pela regra. Essa
verifica¸c˜ao ´e feita na fun¸c˜ao do_fork().
A figura 5.1 mostra como ´e o funcionamento do sistema de controle dinˆamico de
recursos e os principais locais de altera¸c˜oes feitas no n´ucleo do Linux. A ordem de execu¸c˜ao
do controle dinˆamico ´e mostrado na figura pela numera¸c˜ao nos objetos do fluxograma. A
lista abaixo explica cada um dos passos de acordo com sua referˆencia num´erica:
1. Ao ocorrer um tick do rel´ogio ´e disparada a verifica¸c˜ao dos limites do processo em
execu¸c˜ao se ele pertencer a uma regra;
2. Se o ciclo se completou, o escalonador ´e chamado para escolher um novo processo e
os tempos de uso do processador s˜ao recalculados;
3. Caso o ciclo ainda n˜ao tenha terminado, o grupo do processo em execu¸c˜ao tem o
seu tempo de uso do processador atualizado;
4. Se a regra for de limite superior e o limite foi atingido, o processo ´e tirado de
execu¸c˜ao, sen˜ao continua sua execu¸c˜ao se o seu quantum n˜ao for zero;
5. Se a regra for de limite inferior e o limite n˜ao foi atingido, um processo do grupo
recebe o processador para continuar sua execu¸c˜ao, sen˜ao continua a execu¸c˜ao con-
correndo pelo processador junto com os processos comuns;
5. Controle dinˆamico de processador 67
CPU
Grupos
Regra
Atingida?
Escalonador Timer
Quantum
Zera
Completo?
Ciclo
Recalcula
Ciclo
Tick
gasto
pelo
grupo
igua a 0?
Quantum
Sim
Sim
Não
Não
Cumprida?
Regra
Sim
Não
Sim
Jiffies + Tick
Processo
Tick
1
2
3
4
5
6
Regra de Limite
Regra de Limite
Inferior
Superior
Não
Figura 5.1: Fluxograma do controle dinˆamico de recursos.
5. Controle dinˆamico de processador 68
6. O escalonador escolhe o processo mais apropriado para execu¸c˜ao seguindo as de-
fini¸c˜oes das regras.
Com essa implementa¸c˜ao, os processos de regras de limite inferior s˜ao executados antes
de todos os outros processos no in´ıcio do ciclo, sendo classificados para execu¸c˜ao de acordo
com sua prioridade, seguido dos processos pertencentes `a regras de limites inferiores,
superiores e processos normais, sendo que a partir desse momento eles disputam a CPU
de acordo com suas prioridades, no entanto, os processos de regras de limite superior s´o
s˜ao executados at´e o momento que atingem seu limite.
Na pr´oxima se¸c˜ao ser˜ao vistos os testes e resultados obtidos com esse prot´otipo.
5.5 Avalia¸c˜ao do prot´otipo
O prot´otipo foi testado em um servidor Athlon XP 1700+, com 256 MBytes de
mem´oria, rodando a distribui¸c˜ao Slackware 9 com o n´ucleo 2.4.21. Foi criado um pe-
queno programa com um la¸co infinito, chamado usecpu para que se pudesse avaliar efic´acia
do sistema. Esse programa faz uso intenso da CPU, de forma que se n˜ao estiver sendo
executado nenhum outro processo ele utilizar´a 100% do processador.
As informa¸c˜oes sobre uso do pro cessador foram obtidas pelo utilit´ario top, com taxa
de atualiza¸c˜ao de 1 (um) segundo e por um monitor de utiliza¸c˜ao da CPU implementado
especificamente para este projeto que permite selecionar intervalos de tempos em escala
de nanosegundos
5
. O c´odigo fonte desse monitor encontra-se em anexo, no apˆendice B.
Um pequeno programa foi escrito para que se pudesse iniciar e alterar as regras. Ele
possui os mesmos parˆametros da chamada de sistema resourcelimits e somente repassa
as informa¸c˜oes recebidas para a chamada. Esse programa tamb´em pode ser encontrado
no apˆendice C.
V´arios experimentos foram executados para validar a proposta. O primeiro experi-
mento consistiu em executar v´arios processos usecpu, sendo aplicado um limite superior
de uso da CPU a um deles. Na figura 5.2 o processo P1 est´a sendo limitado a 10% da CPU
por esta regra. Mostra-se o comportamento temp oral deste processo quando disputando
5
A fidelidade a essa escala depende exclusivamente da implementa¸c˜ao da fun¸c˜ao nanosleep. Como ela
´e baseada no mecanismo normal de timers, sua resolu¸c˜ao ´e de 1/HZ, ou no n´ucleo 2.4 do Linux, 10ms
[Pro99b].
5. Controle dinˆamico de processador 69
0
10
20
30
40
50
60
70
80
90
100
0 0.5 1 1.5 2 2.5 3 3.5 4
Uso da CPU (%)
Tempo em Segundos
N = 1
N = 2
N = 3
N = 4
N = 5
N = 6
Figura 5.2: Uso da CPU p or P1, com N processos disputando a CPU.
o uso do processador com N processos, e N variando de 1 (somente P1) a 6 (P1 e mais 5
processos). A regra de defini¸c˜ao do limite ´e aplicada sobre P1 em t=0.
Pode-se observar que o sistema leva cerca de 2 segundos para estabilizar o processo
no limite estabelecido. Esse per´ıodo de transi¸c˜ao decorre do algoritmo de escalonamento
do Linux, do valor do ciclo escolhido e da pr´opria granularidade das medidas efetuadas
(1 segundo).
O mesmo experimento foi repetido com grupos de processos, sess˜oes e usu´arios, com
resultados bastante similares. Em nenhuma das execu¸c˜oes realizadas algum processo com
limite m´aximo imposto excedeu o especificado pela regra. A figura 5.3 apresenta P1 e P2
em execu¸c˜ao, sendo que eles pertencem a um usu´ario que tem a utiliza¸c˜ao do processador
limitada para 5% no m´aximo. Pode-se observar que a soma da utiliza¸c˜ao do processador
por esses processos n˜ao foi superior ao estipulado pela regra.
Para os testes com limites m´ınimos de utiliza¸c˜ao do processador foi empregado o
mesmo processo usecpu. Fixando o limite inferior de uso da CPU para P1 em 90% e
variando o n´umero total de processos disputando o processador (de 1 a 6), foram obtidas
as curvas apresentadas na figura 5.4.
Foram tamb´em realizados testes de limite m´ınimo para outros escopos. Na figura 5.5
podem ser vistos os processos P1 e P2 que fazem parte de uma mesma sess˜ao, que possui
5. Controle dinˆamico de processador 70
0
2
4
6
8
10
12
0 1 2 3 4 5
Uso da CPU (%)
Tempo em Segundos
P1
P2
Figura 5.3: Uso da CPU p or P1 e P2 pertencentes a uma regra limite superior.
10
20
30
40
50
60
70
80
90
100
0
0.5 1 1.5 2 2.5 3 3.5 4
Uso da CPU (%)
Tempo em Segundos
N = 1
N = 2
N = 3
N = 4
N = 5
N = 6
Figura 5.4: Uso da CPU p or P1, com N processos disputando a CPU.
5. Controle dinˆamico de processador 71
0
10
20
30
40
50
60
70
0 0.5 1 1.5 2 2.5 3 3.5 4
Uso da CPU (%)
Tempo em Segundos
P2
P1
Figura 5.5: Uso da CPU por P1 e P2 pertencentes a uma regra limite inferior.
uma regra que define o uso m´ınimo do processador para 60%.
Pode-se notar que o sistema n˜ao faz o balanceamento do uso do processador entre
os processos internos do grupo durante o per´ıodo de um ciclo. Isso ocorre porque ao se
iniciar a execu¸c˜ao de um processo com limite m´ınimo, ele mant´em a posse do processador
at´e atingir o limite. Por´em, no pr´oximo ciclo ele ter´a peso diminu´ıdo em rela¸c˜ao aos
outros integrantes do ciclo, tornando a execu¸c˜ao balanceada entre os processos do grupo
no per´ıodo total de execu¸c˜ao.
Devido a arquitetura de grupos empregada no modelo, a dinˆamica de adapta¸c˜ao do
sistema foi similar para todos tipos de regras, sejam de limite inferior ou superior sobre
qualquer escopo.
Como pode ser visto, em nenhum momento o algoritmo deixou de cumprir os limites
definidos nas regras. Tamb´em ´e poss´ıvel comprovar que o modelo implementa um meca-
nismo dinˆamico, visto que as altera¸c˜oes nas regras s˜ao aplicadas rapidamente, entre 1 e
2 segundos, sem que seja necess´ario reiniciar os processos. Nota-se tamb´em que com esse
modelo o impacto de uso da CPU durante a inser¸c˜ao de um novo processo ser´a distribu´ıdo
somente entre processos que n˜ao possuam regras de limite inferior, j´a que os processos
que a possuem respeitar˜ao os limites das regras.
5. Controle dinˆamico de processador 72
0
0.5
1
1.5
2
2.5
3
2 4 8 16 32 64 128 256
Sobrecarga de processamento (%)
Quantidade de processos
128KBs
256KBs
512KBs
Figura 5.6: Acr´escimo de tempo de execu¸c˜ao imposto pelo mecanismo de aplica¸c˜ao das
regras.
5.5.1 O desempenho e custo da implementa¸c˜ao
Para quantificar a sobrecarga de processamento no n´ucleo do Linux foi utilizada a
ferramenta de an´alise de desempenho lmbench [MS96]. Esta ferramenta compara os de-
sempenhos para ambientes Unix e ´e capaz de examinar a latˆencia da troca de contexto,
da cria¸c˜ao de processos, da manipula¸c˜ao de sinais, da leitura de mem´oria e de muitos
outros parˆametros.
O benchmark foi realizado primeiramente no mesmo sistema com o n´ucleo inalterado
(kernel 2.4.21). Logo em seguida, o mesmo experimento foi feito sobre o n´ucleo com o
modelo implementado. Os parˆametros analisados foram o n´umero de processos disputando
a CPU (de 2 a 256) e tamanho dos processos em mem´oria (de 128 Kbytes a 512 Kbytes).
O gr´afico da figura 5.6 apresenta os resultados obtidos. Nele pode-se observar que o custo
da implementa¸c˜ao desse modelo quando n˜ao h´a regras criadas ´e normalmente abaixo de
1% do tempo total de processamento.
A ferramenta lmbench n˜ao apresentou nenhuma outra altera¸c˜ao no desempenho do
sistema durante a realiza¸c˜ao dos testes, tampouco foi sentido qualquer decr´escimo na
velocidade de execu¸c˜ao dos aplicativos.
5. Controle dinˆamico de processador 73
5.6 Conclus˜oes
Neste cap´ıtulo foi apresentada a implementa¸c˜ao de um prot´otipo com o modelo de
controle dinˆamico do uso do processador. Ele permite que o administrador ou usu´arios
dos sistemas possam quantificar o uso do processador por um processo ou v´arios processos.
Conforme observado, o prot´otipo confirma o que o modelo propunha, tornando-o vi´avel.
Com ele, aplicativos que necessitem de controle dinˆamico de recursos, como por exemplo
aplicativos com QoS, podem ser mais facilmente implementados, bem como o sistema
pode ser customizado para um melhor atendimento dos requisitos da organiza¸c˜ao que
o utiliza. Tamb´em ´e poss´ıvel atrav´es dele implementar um mecanismo de respostas a
ataques de nega¸c˜ao de servi¸co [dAMF03], restringindo o uso dos recursos por processos que
estejam comprometidos, mas mantendo-os ativos o tempo necess´ario para uma auditoria
de seguran¸ca ou an´alise forence.
Do ponto de vista funcional, o prot´otipo segue o previsto no modelo. Em termos
pr´aticos v´arias melhorias podem ser feitas, como, por exemplo, o balanceamento da uti-
liza¸c˜ao da CPU pelos processos que pertencem a um grupo com limite inferior durante o
ciclo. Tamb´em ´e poss´ıvel fazer algumas otimiza¸c˜oes no c´odigo para que a sobrecarga seja
ainda menor.
O desempenho do prot´otipo foi satisfat´orio tanto em rela¸c˜ao a velocidade quanto aos
resultados. Ele n˜ao afetou a integridade dos processos que n˜ao s˜ao gerenciados por regras,
mesmo quando diminuindo o acesso que possu´ıam aos recursos em prol dos que possu´ıam
regras de uso m´ınimo do processador, ao mesmo tempo que preservou os processos sob
gerˆencia de regras.
A disponibilidade e a estabilidade do sistema n˜ao foram em nada comprometidas, visto
que uma nova pol´ıtica de execu¸c˜ao foi criada, mantendo inalterada as pol´ıticas originais
que ainda s˜ao usadas pelo processos comuns do sistema. A p ol´ıtica SCHED_RL tamb´em
mostrou-se est´avel, n˜ao prejudicando o sistema em qualquer forma.
Nesse ponto, verifica-se que ´e necess´aria a implementa¸c˜ao do controle de outros re-
cursos, tais quais mem´oria, descritores, banda de disco, banda de rede e etc., para que
o modelo esteja completamente funcional e assim poder estar dispon´ıvel em sistemas
operacionais de mercado.
Cap´ıtulo 6
Considera¸c˜oes finais
6.1 Resumo do trabalho realizado
Este trabalho visou apresentar um modelo de controle dinˆamico de recursos do sistema
operacional. Ele tem por objetivo permitir que os usu´arios do sistema quantifiquem o uso
dos recursos pelos processos, aplicando condi¸c˜oes de utiliza¸c˜ao. O modelo define limites
inferiores e superiores para uso dos recursos, tornando poss´ıvel a garantia ou a restri¸c˜ao
de uso dos recursos, respectivamente.
Este modelo permite a co-existˆencia de outros m´etodos de escalonamento no mesmo
sistema operacional, mantendo as caracter´ısticas do sistema operacional hospedeiro.
O modelo tamb´em permite agrupar os processos de diversas maneiras para que regras
de limites inferiores e superiores possam ser aplicadas a grupos de processos relacionados,
conforme a necessidade da organiza¸c˜ao. Isso tudo ´e feito de forma dinˆamica, ou seja, sem
que haja necessidade de reiniciar o processo ou a sess˜ao do usu´ario para que as condi¸c˜oes
sejam aplicadas. As regras come¸cam a atuar assim que s˜ao criadas, tomando somente um
pequeno per´ıodo de adequa¸c˜ao do sistema at´e que as condi¸c˜oes possam ser atingidas.
A viabilidade do modelo foi verificada pelo prot´otipo aqui apresentado, onde o uso do
processador ´e controlado conforme o modelo proposto. Os testes realizados mostraram
que o comportamento do sistema como um todo correspondeu ao esperado, garantindo e
restringindo a utiliza¸c˜ao do processador pelos processos.
Pode-se afirmar que o custo de implementa¸c˜ao do modelo ´e baixo, e que o impacto no
desempenho do sistema ´e modesto, tornando o modelo vi´avel de implementa¸c˜ao e, muito
6. Considera¸c˜oes finais 75
possivelmente, de aplica¸c˜ao em sistemas operacionais de rede de mercado.
6.2 Principais contribui¸c˜oes
Entre as principais contribui¸c˜oes do modelo, a quantifica¸c˜ao expl´ıcita do uso dos re-
cursos ´e a que mais se destaca. Com isso uma melhor no¸c˜ao de compartilhamento dos
recursos ´e obtida, provendo um mecanismo de controle de recursos de alto n´ıvel mais
adaptativo `as necessidades da organiza¸c˜ao.
O modelo p ermite que programas que desejam definir expressamente o uso dos recursos
do sistema possam ser desenvolvidos sem que sejam necess´arias altera¸c˜oes no n´ucleo do
sistema, ou mesmo conhecimento espec´ıfico sobre o controle interno dos recursos.
Isso ´e v´alido, por exemplo, para programas que exigem limites superiores na utiliza¸c˜ao
dos recursos, como um sistema de respostas a ataques, limitando a execu¸c˜ao de processos
que estejam comprometidos e com isso preservando o valor forense das informa¸c˜oes do
sistema [dAMF03].
E finalmente, o sistema permite que haja um melhor dimensionamento no uso do sis-
tema, inclusive no modo do n´ucleo, o que n˜ao ocorre nos sistemas operacionais modernos.
Assim, o administrador pode ter mais clareza na decis˜ao de onde alocar suas aplica¸c˜oes e
qual o uso que elas far˜ao dos recursos computacionais do sistema em que est˜ao hospedadas.
Outra contribui¸c˜ao deste trabalho foi a publica¸c˜ao dos resultados preliminares desta
proposta em [SMJ04].
6.3 Limita¸c˜oes
Uma das principais limita¸c˜oes do sistema consiste em n˜ao poder agrupar processos
que de alguma forma est˜ao relacionados, mas n˜ao possuem nenhum escopo fornecido
pelo modelo em comum. Dessa forma, para que esses processos relacionados possam ser
juntamente controlados ´e necess´aria a cria¸c˜ao de mais de uma regra, n˜ao permitindo que
esses processos compartilhem o uso dos recursos. Por exemplo, seja o processo P1 e P2
pertencentes a uma aplica¸c˜ao relevante para a organiza¸c˜ao. O administrador deseja que
o processo P1 e P2 juntos possuam um limite superior de 60% para o uso do processador.
Por´em, P1 e P2 n˜ao possuem nenhum escopo em comum (usu´ario, grupo de usu´ario,
6. Considera¸c˜oes finais 76
grupo de processo ou sess˜ao).
´
E, ent˜ao, criada duas regras, uma para o processo P1 e
outra para o processo P2, que especificam que o limite superior de cada um deles ´e de
30%, o que significa que o uso total do processador seria de no m´aximo 60%. Mas como
os processos s˜ao controlados por regras distintas, eles n˜ao compartilham o uso do recurso,
assim, se o processo P1 for bloqueado, P2 utilizar´a no m´aximo 30% do processador, sendo
que se participassem da mesma regra, P2 poderia utilizar os 60% destinados `aquela regra.
A ´unica solu¸c˜ao para esse problema ´e fazer os processos possu´ırem um escopo em comum,
o que nem sempre ´e poss´ıvel.
Outra limita¸c˜ao que ocorre no prot´otipo ´e que um processo pode fazer parte apenas
de uma regra do uso de cada recurso. Assim, limitar o uso dos recursos pelo processo
entre um intervalo m´ınimo e m´aximo n˜ao ´e poss´ıvel. Por exemplo, se se deseja ter P1
utilizando o processador entre 30% e 50%, poderia-se criar uma regra de limite superior
a 50% e outra de limite inferior a 30%, por´em no est´agio atual de desenvolvimento do
prot´otipo isso n˜ao ´e poss´ıvel, j´a que cada processo s´o pode ser afetado p or uma regra.
Isso pode levar ao ap erfei¸coamento do modelo para permitir que sejam criadas regras
de intervalo, que seriam utilizadas para a defini¸c˜ao de limites superiores e inferiores ao
mesmo tempo em uma ´unica regra, a fim de resolver esse problema.
Outra limita¸c˜ao s˜ao os recursos que s˜ao compartilhados por mais de um processo e
que pertencem `a regras distintas para o controle do recurso compartilhado. Esses recursos
podem ser mem´oria compartilhada, arquivos de mapeamento de mem´oria e mem´oria de
thread. Impor limites a esse tipo de recursos pode ser complicado. Se, por exemplo, ao
ajustar o limite superior de mem´oria compartilhada de um pro cesso para 4 p´aginas, e
outro processo que utiliza o mesmo compartilhamento de mem´oria possui uma regra de
uso de mem´oria compartilhada com limite superior definida em 6 p´aginas, pode fazer
com que uma das regras n˜ao seja satisfeita, visto que a mem´oria compartilhada pode
atingir at´e 6 p´aginas, n˜ao cumprindo a regra que diz que deveria usar no m´aximo 4. Esse
problema pode ser resolvido definindo que ser´a adotado o menor limite entre as regras
dos processos envolvidos no compartilhamento dos recursos.
6. Considera¸c˜oes finais 77
6.4 Trabalhos correlatos
V´arios esfor¸cos vˆem sendo realizados para um melhor controle dos recursos do sistema
operacional, por´em, essas estruturas precisam ser incorporadas dentro do sistema operaci-
onal [DS96]. A maioria das pesquisas sobre controle de recursos est˜ao ligadas `a qualidade
de servi¸co, j´a que esta necessita daquela.
At´e o momento foram encontrados alguns trabalhos correlatos a este que foram apre-
sentados no cap´ıtulo 3, na se¸c˜ao 3.3, que s˜ao o CKRM, o Linux-SRT e o DSRT. Na mesma
linha de pesquisa, pode-se citar ainda:
• o escalonador hier´arquico de CPU para sistemas operacionais multim´ıdia [GV96]:
a banda de CPU ´e particionada em v´arias classes de aplica¸c˜oes, onde os processos
s˜ao alocados. Implementado para o Solaris, ele ´e capaz de dinamicamente garantir
a aloca¸c˜ao de uso do processador. Uma implementa¸c˜ao desse modelo tamb´em est´a
dispon´ıvel para Linux em [Dei05].
• o QLinux [SCG
+
00]: tamb´em dividindo a banda de CPU em classes, o QLinux pode
prover uma taxa garantida de uso do processador, com ajustes dinˆamicos. O mesmo
pode ser feito para a banda de disco.
Esses dois trabalhos foram citados aqui, e n˜ao na se¸c˜ao 3.3, devido as suas semelhan¸cas
com o Linux-SRT, tornando redundante naquele momento a sua descri¸c˜ao.
Outros trabalhos aqui descritos s˜ao de esfor¸cos em sistemas com QoS, pois para po-
der garantir a execu¸c˜ao adequada de um servi¸co, o sistema operacional deve fornecer
mecanismos de controle dinˆamico de recursos.
Um controle mais sofisticado dos recursos de rede foi proposto por [GR02]. O proposto
´e que o gerenciamento dos pacotes de rede deixe de ser feita por uma thread que utiliza
o tempo do processador reservado para a execu¸c˜ao do n´ucleo, e passe a ser executado no
tempo destinado ao processo que requisitou aqueles pacotes de rede. Com a velocidade de
placas de redes cada vez mais r´apidas, por muitas vezes os processadores n˜ao conseguem
receber todos os pacotes por n˜ao poderem processar todos eles. Retirando o controle da
thread do n´ucleo, menos computa¸c˜ao ´e necess´aria, j´a que o processo que recebe os pacotes
de rede est´a utilizando o processador no momento da chegada, n˜ao sendo necess´ario fazer
uma interrup¸c˜ao de software para os receber.
6. Considera¸c˜oes finais 78
[BB96] sugere um modelo de QoS gen´erico em um sistema operacional e implementa a
proposta sobre o SunOS, utilizando para tanto uma classe de programa¸c˜ao em tempo-real.
´
E sugerido um modelo de gerenciamento de recursos que pode trabalhar com reserva de
recursos e tamb´em com preemp¸c˜ao de recursos. No primeiro caso, antes de ser confirmada
a execu¸c˜ao do servi¸co ´e feita a reserva dos recursos necess´arios, caso n˜ao seja p oss´ıvel
executar o processo nas condi¸c˜oes m´ınimas requisitadas, o processo n˜ao ´e executado. J´a no
segundo caso, se um processo deseja utilizar os recursos do sistema e o m´ınimo requisitado
n˜ao est´a dispon´ıvel, processos com prioridade menor ter˜ao seus recursos restringidos para
que ele possa ser executado.
No gerenciamento de aplica¸c˜oes distribu´ıdas, [NBB97] implementa um prot´otipo que
consegue garantir qualidade de servi¸co para aplica¸c˜oes multim´ıdia em um sistema opera-
cional distribu´ıdo. Desenvolvido sobre Chorus/Mix, que ´e um sistema modular baseado
em Unix, o prot´otipo gerencia os recursos do computador, tais como processador, rede e
disco, a partir de componentes individuais, para poder prover QoS ao sistema operacional.
[YC01] apresenta o modelo e a implementa¸c˜ao de gerˆencia de recursos em sistemas
operacionais de roteadores.
´
E definida uma abstra¸c˜ao da aloca¸c˜ao de recursos, que pode
escalonar v´arios recursos de tempo e espa¸co compartilhado com garantia e diferencia¸c˜ao
de qualidade de servi¸co. Um classificador flex´ıvel e escal´avel de pacotes habilita a aloca¸c˜ao
dinˆamica de recursos durante o processamento dos pacotes recebidos. Foram integrados
tamb´em o controle de tempo de processamento, banda de forwarding , capacidade de
armazenamento em mem´oria e em dispositivos de armazenamento secund´ario.
Para garantir qualidade de servi¸cos em sistemas de arquivos, [Bar97] prop˜oe um me-
canismo para controlar o acesso ao disco. Controles de banda, prote¸c˜ao e acesso compar-
tilhado ao sistema de arquivos s˜ao fornecidos por um m´odulo de controle. Esse m´odulo
recebe as informa¸c˜oes do m´odulo de dados que ´e respons´avel por prover ao usu´ario um
m´eto do de acesso ao sistema de arquivos. Com esse m´etodo, foi poss´ıvel dar suporte `a
qualidade de servi¸co no sistema de arquivos.
Muitos outros trabalhos est˜ao relacionados a suporte de QoS em sistemas operacionais,
mas n˜ao foi encontrado nenhum outro que, especificamente, controle os recursos do sistema
permitindo aplica¸c˜ao de limites superiores e inferiores.
6. Considera¸c˜oes finais 79
6.5 Perspectivas e trabalhos futuros
As perspectivas deste trabalho s˜ao relativas `a extens˜ao do prot´otipo no sentido de
implementar o controle de outros recursos, como quantidade de mem´oria f´ısica (RAM),
banda de disco e de rede.
Tamb´em h´a necessidade da implementa¸c˜ao do controle dinˆamico do processador no
novo escalonador O(1) [Mol05] do n´ucleo do Linux 2.6. O novo escalonador ´e baseado
em filas m´ultiplas, onde cada fila de execu¸c˜ao ´e associada a um processador, tornando o
sistema mais r´apido em sistemas SMP (shared memory multiprocessor machines - m´aquina
multiprocessadas com mem´oria compartilhada).
Tamb´em devem ser realizadas otimiza¸c˜oes no c´odigo para diminuir o custo do meca-
nismo.
Pode-se p ensar, como trabalho futuro, a implementa¸c˜ao de um meta-escalonador uti-
lizado em grades (grids
1
) computacionais a partir desta proposta. Os meta-escalonadores
centralizam o controle dos processos e dos recursos da grade, permitindo aos usu´arios
submeterem processos para serem executados na grade computacional [Mau05]. O meta-
escalonador determina onde o processo ir´a executar de acordo com as pol´ıticas da or-
ganiza¸c˜ao e o n´ıvel de servi¸co requerido. Para garantir a boa utiliza¸c˜ao dos recursos, o
meta-escalonador deve dinamicamente restringir ou privilegiar a utiliza¸c˜ao dos recursos
em cada computador da grade computacional. Essas caracter´ısticas s˜ao encontradas neste
modelo de gest˜ao de recursos.
Este modelo permite que meta-escalonadores sejam mais facilmente implementados,
visto que as primitivas necess´arias para o desenvolvimento desses softwares j´a est˜ao im-
plementadas.
Al´em de um desenvolvimento mais aprimorado do modelo, a maior perspectiva ´e a
incorpora¸c˜ao do modelo ao n´ucleo do sistema Linux e de outros sistemas operacionais.
1
Grades s˜ao plataformas para computa¸c˜ao geograficamente distribu´ıdas. Elas provˆem poder compu-
tacional acima de qualquer outro sistema de computa¸c˜ao paralela atrav´es da uni˜ao dos recursos f´ısicos
de diferentes computadores em um ´unico recurso virtual [Ski02].
Referˆencias Bibliogr´aficas
[Bal02] Leonardo Balliache. Quality of service. Na internet:
http://opalsoft.net/qos/QOS.htm, September 2002.
[Bar97] Paul Barham. A fresh approach to file system quality of service. In 7th
International Workshop on Network and Operational Systems Support for
Digital Audio and Video. IEEE, 1997.
[BB96] H. Bentaleb and C. B´etourn´e. QoS generic mechanisms in an operating
system. In WFCS’97 IEEE International Workshop on Factory Communi-
cation Systems, pages 49–58. IEEE, 1996.
[BC00] Daniel P. Bovet and Marco Cesati. Understanding the Linux Kernel.
O’Reilly, Sebastopol, CA, 2000.
[CI01] Stephen Childs and David Ingram. The Linux-SRT integrated multimedia
operating system: bringing QoS to the desktop. In RTAS’01 IEEE Real
Time Technology and Applications Symposium. IEEE, 2001.
[dAMF03] Diego de Assis Monteiro Fernandes. Resposta autom´atica em um sistema de
seguran¸ca imunol´ogico computacional. Master’s thesis, Instituto de Com-
puta¸c˜ao, Universidade Estadual de Campinas, 2003.
[Dei05] Borislav Deianov. Hierarchical fair scheduler for linux.
http://fairsched.sourceforge.net/, Jun 2005.
[DNFW02] Will Dinkel, Douglas Niehaus, Michael Frisbie, and Jacob Woltersdorf.
KURT Linux user manual, 2002.
Referˆencias Bibliogr´aficas 81
[dOCT01] Rˆomulo de Oliveira, Alexandre Carissimi, and Sim˜ao Toscani. Sistemas
Operacionais. Editora Sagra-Luzzato, 2001.
[DS96] Michael B. Davis and Jaroslaw J. Sydir. Position paper: Resource manage-
ment for complex distributed system. In 2nd Workshop on Object-Oriented
Real-Time Dependable Systems, pages 113–115, 1996.
[FJ95] Sally Floyd and Van Jacobson. Link-sharing and resource management mo-
dels for packet networks. ACM Transations on Network, 3(4), August 1995.
[FM02] Ida M. Flynn and Ann McIver McHoes. Introdu¸c˜ao aos Sistemas Operacio-
nais. Pioneira Thompson Learning, 1 edition, 2002.
[Fou01] Beet Foundation. The free on-line dictionary of computing. Na internet:
http://www.beetfoundation.com, 2001.
[Gol05] Karol Golab. Cpu - cap processor usage. Na internet:
http://rshk.co.uk/projects/cpucap/, 2005. TLS Technologies.
[GR02] Sourav Glosh and Ragunathan Rajkumar. Resource management of the
OS network subsystem. In 5th IEEE International Symposium on Object-
Oriented Real-Time Distributed Computing. IEEE, 2002.
[GV96] Pawan Goyaland Xingang Guo and Harrick M. Vin. A hierarchical cpu
scheduler for multimedia operating systems. In 2nd Symp. on Operating
Systems Design and Implementation, Oct 1996.
[Jac02] Jim Jackson. Multiprocessor soft real time cpu resource manager and its
validation with hypermedia applications. Master’s thesis, Department of
Computer Science, University of Illinois at Urbana-Champaign, May 2002.
[Kar01] Jan Kara. Disk Quota System for Linux, 2001. Na internet:
http://doc.alejandro.codina.nom.br/quota-3.08/quotado c.html.
[Lib01] GNU C Library. Process group functions. Na internet: http://www.gnu.org,
May 2001.
Referˆencias Bibliogr´aficas 82
[Lov02] Robert Love. Robert love explains variable hz. Na internet:
http://kerneltrap.org/node/464, October 2002.
[Lov03] Robert Love. Linux Kernel Development. Sams, 1 edition, Sep 2003.
[Mau05] Jeff Mausolf. Grid in action: Managing the resource mana-
gers. Developerworks - IBM, Jul 2005. Na internet: http://www-
128.ibm.com/developerworks/grid/library/gr-metasched/.
[Mol05] Ingo Molnar. Ultra-scalable o(1) smp and up scheduler.
http://www.uwsg.iu.edu/hypermail/linux/kernel/0201.0/0810.html, Jun
2005.
[Mon02] M´ario A. Monteiro. Introdu¸c˜ao `a Organiza¸c˜ao de Computadores. LTC, 4
edition, 2002.
[MR95] C. W. Mercer and R. Rajkumar. An interactive interface and RT-Mach
support for monitoring and controlling resource management. In RTAS’01
IEEE Real-Time Technology and Applications Symposium, pages 134–139.
IEEE, 1995.
[MS96] Larry McVoy and C. Staelin. Lmbench: Portable to ols for performance
analysis. In Winter USENIX Conference, 1996.
[NBB97] Hong Quang Nguyen, Christian Bac, and Guy Bernard. Integrating QoS
management in a micro-kernel based UNIX operating system. In Proceedings
of the 23rd Euromicro Conference, pages 371–378. IEEE, 1997.
[NFC
+
03] Shailabh Nagar, Hubertus Franke, Jonghyuk Choi, Chandra Seetharaman,
Scott Kaplan, Nivedita Shinghvi, Vivek Kashyap, and Mike Kravetz. Class-
based prioritized resource control in linux. Ottawa Linux Symposium, 2003.
[Noe98] GJ Noer. Cygwin: A free win32 porting layer for unix applications. In 2d
USENIX NT Symposium, 1998.
[NvRF
+
04a] Shailabh Nagar, Rik van Riel, Hubertus Franke, Chandra Seetharaman,
and Vivek Kashyap. Advanced workload management support for linux.
LinuxTag, 2004.
Referˆencias Bibliogr´aficas 83
[NvRF
+
04b] Shailabh Nagar, Rik van Riel, Hubertus Franke, Chandra Seetharaman,
Vivek Kashyap, and Haoqiang Zheng. Improving linux resource control
using CKRM. In Proceedings of the Linux Symposium, volume 2, pages
511–524, 2004.
[OCT02] Rˆomulo Oliveira, Alexandre Carissimi, and Sim˜ao Toscani. Organiza¸c˜ao
de sistemas operacionais convencionais e de tempo real. XXI JAI, XXII
Congresso da SBC, 2002.
[Pro99a] Linux Documentation Project. Linux Programmer’s Manual, 1999. setrlimit
Manual Page.
[Pro99b] Linux Documentation Project. Linux Programmer’s Manual, 1999. NanoS-
leep Manual Page.
[Roe99] Martin Roesch. Snort: Lightweight intrusion detection for networks. In
Proceedings of XIII LISA’99, 1999.
[SCG
+
00] V. Sundaram, A. Chandra, P. Goyal, P. Shenoy, J. Sahni, and H. Vin.
Application performance in the qlinux multimedia operating system. In
Proceedings of the Eighth ACM Conference on Multimedia, Nov 2000.
[SGG02] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne. Operating Sys-
tem Concepts. Wiley Text Books, 2002.
[Ski02] D.B. Skillicorn. Motivating computational grids. In Proceedings of the 2nd
IEEE/ACM International Symposium on Cluster Computing and the Grid.
IEEE, 2002.
[SMJ04] M´arcio Starke, Carlo Maziero, and Edgard Jamhour. Controle dinˆamico de
recursos em sistemas operacionais. In Sociedade Brasileira de Computa¸c˜ao,
Anais do I Workshop de Sistemas Operacionais, volume 1, pages 1–10, Porto
Alegre, RS, 2004.
[SNK05] Chandra Seetharaman, Shailabh Nagar, and Vivek Kashyap. Design details
of CKRM. Na internet: http://ckrm.sourceforge.net/ckrm design.htm, feb
2005.
Referˆencias Bibliogr´aficas 84
[Tro99] Erik Troan. The linux file access primitives. Linux Magazine, 1999.
[TW97] Andrew S. Tannenbaum and Albert S. Woodhull. Sistemas Operacionais:
Projeto e Implementa¸c˜ao. Bookman, 1997.
[Var96] Uresh Varalia. Unix Internals: The new frontiers. Prentice Hall, 1996.
[YC01] David K. Y. Yau and Xiangjing Chen. Resource management in software
programmable router operating systems. IEEE Journal on Selected Areas
in Communications, 19(3), March 2001.
[Yod99] Victor Yodaiken. The rtlinux manifesto. In Proc. of The 5th Linux Expo,
1999.
[ZDE
+
93] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP: A new
Resource ReSerVation Protocol. IEEE Network, Sep 1993.
Apˆendice A
C´odigo fonte do prot´otipo
d i f f −Naur l i n u x − 2 .4 . 2 1 / ar c h / i 3 8 6 / k e r n e l / e n t r y . S l i n u x −2.4.21 − r l / a r ch / i 3 8 6 / k e r n e l / e n t r y . S
−−− li n u x − 2 .4 . 2 1/ a rc h / i 3 8 6 / k e r n e l / e n t r y . S 2003−06−13 1 1 : 5 1 : 2 9 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / a rc h / i 3 8 6 / k e r n e l / e n t r y . S 2004−07−28 1 7 : 4 8 : 0 0 . 0 0 0 0 0 0 0 0 0 −0300
@@ −663 ,6 +663 ,7 @@
. long SYMBOL NAME( s y s n i s y s c a l l ) /∗ s y s e p o l l w a i t ∗/
. long SYMBOL NAME( s y s n i s y s c a l l ) /∗ s y s r e m a p f i l e p a g e s ∗/
. long SYMBOL NAME( s y s n i s y s c a l l ) /∗ s y s s e t t i d a d d r e s s ∗/
+ . lo ng SYMBOL NAME( s y s r e s o u r c e l i m i t ) /∗ 25 9 s y s r e s o u r c e l i m i t m ar c i o @p p g ia . p uc p r . b r ∗/
. r e p t N R s y s c a l l s −(.− s y s c a l l t a b l e ) /4
. long SYMBOL NAME( s y s n i s y s c a l l )
d i f f −Naur l i n u x − 2 .4 . 2 1 / ar c h / i 3 8 6 / k e r n e l / i n i t t a s k . c l i n u x −2.4.21 − r l / a r ch / i 3 8 6 / k e r n e l / i n i t t a s k . c
−−− li n u x − 2 .4 . 2 1/ a rc h / i 3 8 6 / k e r n e l / i n i t t a s k . c 2001−09−17 1 9 : 2 9 : 0 9 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / a rc h / i 3 8 6 / k e r n e l / i n i t t a s k . c 2004−07−29 1 4 : 0 4 : 5 8 . 0 0 0 0 0 0 0 0 0 −0300
@@ −6 ,11 +6 ,15 @@
#i n c l u d e <asm/ p g t a b l e . h>
#i n c l u d e <asm/ d e s c . h>
+#d e f i n e INIT RLGROUPS
+#i n c l u d e < l i n u x / r e s o u r c e l i m i t s . h>
+
s t a t i c st ruct f s s t r u c t i n i t f s = INIT FS ;
s t a t i c st ruct f i l e s s t r u c t i n i t f i l e s = INIT FILES ;
s t a t i c st ruct s i g n a l s t r u c t i n i t s i g n a l s = INIT SIGN ALS ;
s t r u c t mm st ruct i n it mm = INIT MM( ini t m m ) ;
+
/∗
∗ I n i t i a l t a s k s t r u c t u r e .
∗
@@ −31 ,3 +35 ,10 @@
∗/
s t r u c t t s s s t r u c t i n i t t s s [ NR CPUS ] c a c h e l i n e a l i g n e d = { [ 0 . . . NR CPUS−1] = INIT TSS } ;
+
+/∗ r e s o u r c e l i m i t s ∗/
+unsigned lo ng RLNEXT = 0 ;
+s t r u c t l i s t h e a d r l g r o u p s ;
+i n t n e e d r e c a l c u l a t e = 0 ;
+i n t t h e r e i s l o w e r r u l e s = 0 ;
+/∗ r e s o u r c e l i m i t s ∗/
d i f f −Naur l i n u x − 2 .4 . 2 1 / i n c l u d e /asm−i 3 8 6 / u n i s t d . h l i n u x −2.4.21 − r l / i n c l u d e /asm−i 3 8 6 / u n i s t d . h
−−− li n u x − 2 .4 . 2 1/ i n c l u d e /asm−i 3 8 6 / u n i s t d . h 2002− 11−28 2 1 : 5 3 : 1 5 . 0 0 0 0 0 0 0 0 0 −0200
A. C´odigo fonte do prot´otipo 86
+++ l i n u x −2.4.21 − r l / i n c l u d e /asm−i 3 8 6 / u n i s t d . h 2004−07−28 1 7 : 4 8 : 0 0 . 0 0 0 0 0 0 0 0 0 −0300
@@ −257 ,6 +257 ,7 @@
#d e f i n e N R a l l o c h u g e p a g e s 250
#d e f i n e N R f r e e h u g e p a g e s 251
#d e f i n e N R e x i t g r o u p 252
+#d e f i n e N R r e s o u r c e l i m i t 259 /∗ m a rc i o @pp g i a . p u c p r . b r r e s o u r c e l i m i t s ∗/
/∗ u s e r − v i s i b l e e r r o r n umbe r s ar e i n t h e r a n g e −1 − −124: s e e <asm−i 3 8 6 / e r r n o . h> ∗/
d i f f −Naur l i n u x − 2 .4 . 2 1 / i n c l u d e / l i n u x / r e s o u r c e l i m i t s . h l i n u x −2.4.21 − r l / i n c l u d e / l i n u x / r e s o u r c e l i m i t s . h
−−− li n u x − 2 .4 . 2 1/ i n c l u d e / l i n u x / r e s o u r c e l i m i t s . h 1969− 12−31 2 1 : 0 0 : 0 0 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / i n c l u d e / l i n u x / r e s o u r c e l i m i t s . h 2004−07−30 1 3 : 4 5 : 4 3 . 0 0 0 0 0 0 0 0 0 −0300
@@ −0,0 +1 ,40 @@
+#i f n d e f LINUX RESOURCELIMITS H
+#d e f i n e LINUX RESOURCELIMITS H
+
+#i n c l u d e < l i n u x / l i s t . h>
+
+#d e f i n e L UPPER 1
+#d e f i n e L LOWER 2
+
+#d e f i n e L CPU 3
+#d e f i n e L VM 4
+
+#d e f i n e RLPROCESS 1
+#d e f i n e RLUSER 2
+#d e f i n e RLUSERSGROUP 3
+#d e f i n e RLPROCESSGROUP 4
+#d e f i n e RLSESSION 5
+
+#d e f i n e KEEP RUNNING 1000
+#d e f i n e HALF KEEP RUNNING 500
+
+s t r u c t TRLGroup {
+ i n t r e s o u r c e ;
+ i n t sc o p e ;
+ i n t t a r g e t ;
+ long v a l u e ;
+ i n t type ;
+ i n t RLUSEDTICKS;
+ i n t a c t i v e ;
+ i n t n u m b e r o f e l e m e n t s ;
+ s t r u c t l i s t h e a d l i s t ;
+};
+
+#i f n d e f INIT RLGROUPS
+extern unsigned long RLNEXT;
+extern s t r u c t l i s t h e a d r l g r o u p s ;
+extern i n t n e e d r e c a l c u l a t e ;
+extern i n t t h e r e i s l o w e r r u l e s ;
+#e n d i f
+
+#e n d i f
d i f f −Naur l i n u x − 2 .4 . 2 1 / i n c l u d e / l i n u x / s che d . h l i n u x −2.4.21 − r l / i n c l u d e / l i n u x / s ch e d . h
−−− li n u x − 2 .4 . 2 1/ i n c l u d e / l i n u x / s c he d . h 2003−06−13 1 1 : 5 1 : 3 9 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / i n c l u d e / l i n u x / s c h ed . h 2004− 07−30 1 3 : 4 5 : 4 3 . 0 0 0 0 0 0 0 0 0 −0300
@@ −108 ,6 +108 ,7 @@
#d e f i n e SCHED OTHER 0
#d e f i n e SCHED FIFO 1
#d e f i n e SCHED RR 2
+#d e f i n e SCHED RL 3 /∗ r e s o u r c e l i m i t s ∗/
/∗
∗ T h is i s an a d d i t i o n a l b i t s e t when we wa n t t o
@@ −415 ,6 +4 16 ,11 @@
A. C´odigo fonte do prot´otipo 87
/∗ j o u r n a l l i n g f i l e s y s t e m i n f o ∗/
void ∗ j o u r n a l i n f o ;
+
+/∗ r e s o u r c e l i m i t s ∗/
+/∗ m a rc i o @ pp g i a . p u c p r . b r 11 /11 / 2 0 0 3 ∗/
+ stru c t TRLGroup ∗ r l g r o u p ;
+/∗ en d r e s o u r c e l i m i t s ∗/
} ;
/∗
@@ −435 ,6 +441 ,7 @@
#d e f i n e PF USEDFPU 0 x0 0 1 0 00 0 0 /∗ t a s k u s e d FPU t h i s quantum (SMP) ∗/
+
/∗
∗ P t r a c e f l a g s
∗/
@@ −509 ,6 +516 ,8 @@
b l o c k e d : {{0}} , \
a l l o c l o c k : SPIN LOCK UNLOCKED, \
j o u r n a l i n f o : NULL, \
+/∗ r e s o u r c e l i m i t s ∗/ \
+ r l g r o u p : NULL \
}
d i f f −Naur l i n u x − 2 .4 . 2 1 / i n c l u d e / l i n u x / u n i s t d . h l i n u x −2.4.21 − r l / i n c l u d e / l i n u x / u n i s t d . h
−−− li n u x − 2 .4 . 2 1/ i n c l u d e / l i n u x / u n i s t d . h 20 01−10−17 1 5 : 2 4 : 2 3 . 0 0 0 0 0 0 0 0 0 −0200
+++ l i n u x −2.4.21 − r l / i n c l u d e / l i n u x / u n i s t d . h 2004−07−28 1 7 : 4 8 : 0 0 . 0 0 0 0 0 0 0 0 0 −0300
@@ −8,4 +8 ,5 @@
∗/
#i n c l u d e <asm/ u n i s t d . h>
+
#e n d i f /∗ LINUX UNISTD H ∗/
d i f f −Naur l i n u x − 2 .4 . 2 1 / k e r n e l / e x i t . c l i n u x −2.4.21 − r l / k e r n e l / e x i t . c
−−− li n u x − 2 .4 . 2 1/ k e r n e l / e x i t . c 2002−11−28 2 1 : 5 3 : 1 5 . 0 0 0 0 0 0 0 0 0 −0200
+++ l i n u x −2.4.21 − r l / k e r n e l / e x i t . c 2004−07−29 1 7 : 0 1 : 0 2 . 0 0 0 0 0 0 0 0 0 −0300
@@ −20 ,6 +20 ,7 @@
#i n c l u d e <asm/ u a c c e s s . h>
#i n c l u d e <asm/ p g t a b l e . h>
#i n c l u d e <asm/ mmu context . h>
+#i n c l u d e < l i n u x / r e s o u r c e l i m i t s . h>
extern void s e m e x i t ( void ) ;
extern s truc t t a s k s t r u c t ∗ c h i l d r e a p e r ;
@@ −424 ,8 +425 , 11 @@
NORET TYPE void d o e x i t ( long code )
{
− st r u c t t a s k s t r u c t ∗ t s k = c u r r e n t ;
−
+ s t r u c t t a s k s t r u c t ∗ t s k = c u r r e n t , ∗p ;
+ i n t m o r e t a s k s = 0 ;
+ s t r u c t l i s t h e a d ∗ head ;
+ s t r u c t TRLGroup ∗ node ;
+
i f ( i n i n t e r r u p t ( ) )
p a ni c ( ” A iee , k i l l i n g i n t e r r u p t h a n d l e r ! ” ) ;
i f ( ! t s k−>pi d )
@@ −456 ,6 +460 , 26 @@
i f ( t s k −>bi n fmt && ts k −>bi n fmt−>module )
MOD DEC USE COUNT( t s k −>binf m t−>module ) ;
A. C´odigo fonte do prot´otipo 88
+ i f ( t s k−>p o l i c y == SCHED RL) {
+ f o r e a c h t a s k ( p ) {
+ i f ( p−>r l g r o u p == tsk−>r l g r o u p && p != t s k )
+ m o r e t a s k s = 1 ;
+ }
+ i f ( ! m o r e t a s k s ) {
+ l i s t f o r e a c h ( head , &r l g r o u p s ) {
+ node = l i s t e n t r y ( head , s truc t TRLGroup , l i s t ) ;
+ i f ( t s k −>r l g r o u p −>sc o p e == node−>sc o p e && t sk−>r l g r o u p −> t a r g e t == node
−>t a r g e t ) {
+ i f ( node−>t y p e == L LOWER)
+ t h e r e i s l o w e r r u l e s −−;
+// l i s t d e l (&( node−> l i s t ) ) ;
+ }
+ }
+ k f r e e ( t s k −>r l g r o u p ) ;
+ }
+ e l s e
+ tsk−>r l g r o u p −>n u m b e r o f e l e m e n t s −−;
+ }
+
tsk −>e x i t c o d e = c o d e ;
e x i t n o t i f y ( ) ;
s c h e d u l e ( ) ;
d i f f −Naur l i n u x − 2 .4 . 2 1 / k e r n e l / f o r k . c li n u x −2.4.21 − r l / k e r n e l / f o r k . c
−−− li n u x − 2 .4 . 2 1/ k e r n e l / f o r k . c 2003−06−13 1 1 : 5 1 : 3 9 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / k e r n e l / f o r k . c 2004−07−29 1 7 : 0 4 : 0 8 . 0 0 0 0 0 0 0 0 0 −0300
@@ −28 ,6 +28 ,7 @@
#i n c l u d e <asm/ u a c c e s s . h>
#i n c l u d e <asm/ mmu context . h>
#i n c l u d e <asm/ p r o c e s s o r . h>
+#i n c l u d e < l i n u x / r e s o u r c e l i m i t s . h>
/∗ The i d l e t h r e a d s d o n o t c o u n t . . ∗/
i n t n r t h r e a d s ;
@@ −742 ,6 +743 , 18 @@
i f ( ! c u r r e n t −>c o u n t e r )
c u r r e n t −>n e e d r e s c h e d = 1 ;
+ /∗ r e s o u r c e l i m i t ∗/
+ i f ( c u r r e n t −>p o l i c y == SCHED RL) {
+ i f ( c u r r e n t −>r l g r o u p −>s c o p e == RLPROCESS) {
+ c u r r e n t −>p o l i c y = SCHED OTHER;
+ c u r r e n t −>r l g r o u p = NULL ;
+ }
+ e l s e
+ c u r r e n t −>r l g r o u p −>n u m b e r o f e l e m e n t s ++;
+ }
+ /∗ end r e s o u r c e l i m i t ∗/
+
+
/∗
∗ Ok , add i t t o t h e run−q u e u e s and make i t
∗ v i s i b l e t o t h e r e s t o f t h e s y s t e m .
d i f f −Naur l i n u x − 2 . 4 . 2 1/ k e r n e l / s c h e d . c l i n u x −2.4.21 − r l / k e r n e l / s c h e d . c
−−− l i n u x − 2 . 4 .2 1 / k e r n e l / s c h e d . c 2003−06−13 1 1 : 5 1 : 3 9 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / k e r n e l / s c h e d . c 2004−07−29 1 7 : 0 3 : 3 1 . 0 0 0 0 0 0 0 0 0 −0300
@@ −29 ,6 +29 ,7 @@
#i n c l u d e < l i n u x / c o m p l e t i o n . h>
#i n c l u d e < l i n u x / p r e f e t c h . h>
#i n c l u d e < l i n u x / c o m p i l e r . h>
+#i n c l u d e <l i n u x / r e s o u r c e l i m i t s . h>
#i n c l u d e <asm/ u a c c e s s . h>
A. C´odigo fonte do prot´otipo 89
#i n c l u d e <asm/ mmu c o n t e x t . h>
@@ −149 ,14 +15 0 ,37 @@
∗ s e l e c t t h e c u r r e n t p r o c e s s a f t e r e v e r y o t h e r
∗ r u n n a b l e p r o c e s s , b u t b e f o r e t h e i d l e t h r e a d .
∗ Also , d o n t t r i g g e r a c o u n t e r r e c a l c u l a t i o n .
− ∗/
+ ∗/
we i g ht = −1;
− i f ( p−>p o l i c y & SCHED YIELD)
− goto o u t ;
/∗
∗ Non−RT p r o c e s s − no rmal c a s e f i r s t .
∗/
+
+ i f ( p−>p o l i c y == SCHED RL) {
+ /∗ r e s o u r c e l i m i t s ∗/
+ wei g h t = p−>c o u n t e r ;
+ i f ( ! n e e d r e c a l c u l a t e ) {
+ i f ( p−>r l g r o u p −>ty p e == L UPPER) {
+ i f ( ! p−>r l g r o u p −>RLUSEDTICKS)
+ we i g ht =−1001;
+ }
+ e l s e
+ i f ( p−>r l g r o u p −>RLUSEDTICKS) {
+ we i g ht += (KEEP RUNNING + p−>c o u n t e r ) ;
+ }
+ e l s e {
+ p−>c o u n t e r = NICE TO TICKS ( 2 0 ) ; // menor p r i o r i d a d e
+ we i g ht = p−>c o u n t e r ;
+ }
+ }
+ goto o u t ;
+ }
+
+ i f ( p−>p o l i c y & SCHED YIELD)
+ goto out ;
+
+
i f ( p−> p o l i c y == SCHED OTHER) {
/∗
∗ Give t h e p r o c e s s a f i r s t −a p p r o x i m a t i o n g o o d n e s s v a l u e
@@ −165 ,9 +1 89 ,15 @@
∗ Don ’ t do an y o t h e r c a l c u l a t i o n s i f t h e t i m e s l i c e i s
∗ o v e r . .
∗/
+
we i g ht = p−>c o u n t e r ;
+
i f ( ! w ei g h t )
goto out ;
+
+
+ /∗ end r e s o u r c e l i m i t ∗/
+
#i f d e f CONFIG SMP
/∗ Give a l a r g i s h a d v a n t a g e t o t h e same p r o c e s s o r . . . ∗/
@@ −571 ,9 +601 ,9 @@
∗ o n l y one p r o c e s s p er CPU .
∗/
s c h e d d a t a = & a l i g n e d d a t a [ t h i s c p u ] . s c h e d u l e d a t a ;
−
+
s p i n l o c k i r q (& r u n q u e u e l o c k ) ;
A. C´odigo fonte do prot´otipo 90
−
+
/∗ m ove an e x h a u s t e d RR p r o c e s s t o b e l a s t . . ∗/
i f ( u n l i k e l y ( pre v−>p o l i c y == SCHED RR) )
i f ( ! pre v−>co u n t e r ) {
@@ −613 ,13 +643 ,23 @@
}
/∗ Do we need t o re−c a l c u l a t e c o u n t e r s ? ∗/
− i f ( u n l i k e l y ( ! c ) ) {
+ i f ( u n l i k e l y ( ! c ) | | n e e d r e c a l c u l a t e ) {
s t r u c t t a s k s t r u c t ∗p ;
−
s p i n u n l o c k i r q (& r u n q u e u e l o c k ) ;
r e a d l o c k (& t a s k l i s t l o c k ) ;
− f o r e a c h t a s k ( p )
− p−>c o u n t e r = ( p−>c o u n t e r >> 1) + NICE TO TICKS ( p−>n i c e ) ;
+ f o r e a c h t a s k ( p ) {
+ i f ( p−> p o l i c y != SCHED RL) {
+ p−>c o u n t e r = (p−>c o u n t e r >> 1 ) + NICE TO TICKS( p−>n i c e ) ;
+ }
+ e l s e {
+ i f ( n e e d r e c a l c u l a t e ) {
+ p−>r l g r o u p −>RLUSEDTICKS = p−>r l g r o u p −> v a l u e ;
+ p−>c o u n t e r = ( p−>r l g r o u p −>RLUSEDTICKS / p−>r l g r o u p −>
n u m b e r o f e l e m e n t s ) ;
+ }
+ }
+
+ }
+ n e e d r e c a l c u l a t e = 0 ;
r e a d u n l o c k (& t a s k l i s t l o c k ) ;
s p i n l o c k i r q (& r u n q u e u e l o c k ) ;
goto r e p e a t s c h e d u l e ;
@@ −636 ,7 +676 ,8 @@
i f ( u n l i k e l y ( p r ev == next ) ) {
/∗ We won ’ t g o t h r o u g h t h e normal t a i l , s o do t h i s b y hand ∗/
− prev−>p o l i c y &= ˜SCHED YIELD ;
+ i f ( prev−>p o l i c y != SCHED RL)
+ prev−>p o l i c y &= ˜SCHED YIELD ;
goto s a m e p r o c e s s ;
}
@@ −1133 ,6 +1174 ,7 @@
ca se SCHED RR:
r e t = 9 9 ;
break ;
+ ca se SCHED RL:
ca se SCHED OTHER:
r e t = 0 ;
break ;
@@ −1149 ,6 +1191 ,7 @@
ca se SCHED RR:
r e t = 1 ;
break ;
+ ca se SCHED RL:
ca se SCHED OTHER:
r e t = 0 ;
}
d i f f −Naur l i n u x − 2 .4 . 2 1 / k e r n e l / s y s . c l i n u x −2.4.21 − r l / k e r n e l / s y s . c
−−− li n u x − 2 .4 . 2 1/ k e r n e l / s y s . c 2003−06−13 1 1 : 5 1 : 3 9 . 0 0 0 0 0 0 0 0 0 −0300
+++ l i n u x −2.4.21 − r l / k e r n e l / s y s . c 2004−07−30 1 3 : 4 6 : 5 8 . 0 0 0 0 0 0 0 0 0 −0300
@@ −14 ,6 +14 ,7 @@
#i n c l u d e < l i n u x / p r c t l . h>
A. C´odigo fonte do prot´otipo 91
#i n c l u d e < l i n u x / i n i t . h>
#i n c l u d e < l i n u x / h i g h u i d . h>
+#i n c l u d e < l i n u x / r e s o u r c e l i m i t s . h>
#i n c l u d e <asm/ u a c c e s s . h>
#i n c l u d e <asm/ i o . h>
@@ −1286 ,6 +1287 ,11 6 @@
return e r r o r ;
}
+
+a s m l i n k a g e long s y s r e s o u r c e l i m i t ( i n t r e s o u r c e , i n t sc o pe , i n t t a r g e t , long val u e , i n t t y p e )
+{
+ i n t cpu us e d = 0 ;
+ stru c t t a s k s t r u c t ∗p ;
+ s t r u c t TRLGroup ∗ node ;
+ s t a t i c i n t FIRS T TIME = 1 ;
+
+ i f ( FIRST TIME ) {
+ FIRST TIME = 0 ;
+ INIT LIST HEAD(& r l g r o u p s ) ;
+ }
+
+
+ i f ( v a l u e < 0 | | v a l u e > 10 0 )
+ return −EINVAL ;
+
+ /∗ n o r m a l i z e v a l u e ∗/
+ i f ( v a l u e < 1 )
+ v a l u e = 1 ;
+ i f ( v a l u e > 1 00 )
+ v a l u e = 1 0 0 ;
+
+ /∗ v e r i f i c a l i m i t e s de u t i l i z a c a o Maxima 100%∗/
+ f o r e a c h t a s k ( p ) {
+ i f ( p−> p o l i c y == SCHED RL && p−>r l g r o u p −>type == L LOWER)
+ c p u u s ed += p−>r l g r o u p −>va l u e ;
+ }
+
+ i f ( c pu us e d + v a l u e >= 1 00)
+ ret urn −EINVAL ;
+
+ /∗ c o n v e r t t o j i f f i e s , c h e c k l i m i t s as a p r e c a u t i o n ∗/
+ v a l u e = ( v a l u e ∗ HZ) / 1 0 0 ;
+ i f ( v a l u e < 1 )
+ v a l u e = 1 ;
+ i f ( v a l u e > HZ)
+ ret urn −EINVAL ;
+
+
+ node = ( s t r u c t TRLGroup ∗) k ma l l o c ( s i z e o f ( s t r u c t TRLGroup ) ,GFP KERNEL) ;
+
+ node−>va l u e = v a l u e ;
+ node−>t y p e = ty p e ;
+ node−>s c o p e = s c o pe ;
+ node−>RLUSEDTICKS = −1;
+ node−>a c t i v e = 1 ;
+ node−>t a r g e t = t a r g e t ;
+ node−>r e s o u r c e = L CPU ;
+ node−>nu m b e r o f e l e m e n t s = 0 ;
+
+ l i s t a d d (&node−> l i s t , &r l g r o u p s ) ;
+/∗ POR PROCESSO ∗/
+ i f ( s c o p e == RLPROCESS) {
+ p = f i n d t a s k b y p i d ( t a r g e t ) ;
A. C´odigo fonte do prot´otipo 92
+ i f ( ! p )
+ return −ESRCH;
+ r e a d l o c k (& t a s k l i s t l o c k ) ;
+ p−> p o l i c y = SCHED RL;
+ p−>r l g r o u p = node ;
+ p−>r l g r o u p −>n u m b e r o f e l e m e n t s ++;
+ r e a d u n l o c k (& t a s k l i s t l o c k ) ;
+
+ }
+
+/∗ USUARIO ∗/
+ i f ( s c o p e == RLUSER) {
+ f o r e a c h t a s k ( p ) {
+ i f ( p−>u id == t a r g e t ) {
+ r e a d l o c k (& t a s k l i s t l o c k ) ;
+ p−>p o l i c y = SCHED RL ;
+ p−>r l g r o u p = node ;
+ p−>r l g r o u p −>n u m b e r o f e l e m e n t s ++;
+ r e a d u n l o c k (& t a s k l i s t l o c k ) ;
+ }
+ }
+ }
+
+/∗ GRUPO ∗/
+
+ i f ( s c o p e == RLPROCESSGROUP) {
+ f o r e a c h t a s k ( p ) {
+ i f ( t a r g e t == p−>g i d ) {
+ r e a d l o c k (& t a s k l i s t l o c k ) ;
+ p−>p o l i c y = SCHED RL ;
+ p−>r l g r o u p = node ;
+ p−>r l g r o u p −>n u m b e r o f e l e m e n t s ++;
+ r e a d u n l o c k (& t a s k l i s t l o c k ) ;
+ }
+ }
+ }
+
+/∗ GRUPO DE GRUPO ∗/
+ i f ( s c o p e == RLSESSION) {
+ f o r e a c h t a s k ( p ) {
+ i f ( t a r g e t == p−>s e s s i o n ) {
+ r e a d l o c k (& t a s k l i s t l o c k ) ;
+ p−>p o l i c y = SCHED RL ;
+ p−>r l g r o u p = node ;
+ p−>r l g r o u p −>n u m b e r o f e l e m e n t s ++;
+ r e a d u n l o c k (& t a s k l i s t l o c k ) ;
+ }
+ }
+ }
+
+ i f ( t y pe == L LOWER)
+ t h e r e i s l o w e r r u l e s ++;
+ retur n 0 ;
+}
+
EXPORT SYMBOL( n o t i f i e r c h a i n r e g i s t e r ) ;
EXPORT SYMBOL( n o t i f i e r c h a i n u n r e g i s t e r ) ;
EXPORT SYMBOL( n o t i f i e r c a l l c h a i n ) ;
d i f f −Naur l i n u x − 2 .4 . 2 1 / k e r n e l / t i m e r . c l i n u x −2.4.21 − r l / k e r n e l / t i m e r . c
−−− li n u x − 2 .4 . 2 1/ k e r n e l / t i m e r . c 2002−11−28 2 1 : 5 3 : 1 5 . 0 0 0 0 0 0 0 0 0 −0200
+++ l i n u x −2.4.21 − r l / k e r n e l / t i m e r . c 2004−07−29 1 6 : 5 2 : 5 7 . 0 0 0 0 0 0 0 0 0 −0300
@@ −22 ,6 +22 ,7 @@
#i n c l u d e < l i n u x / s mp l oc k . h>
#i n c l u d e < l i n u x / i n t e r r u p t . h>
#i n c l u d e < l i n u x / k e r n e l s t a t . h>
A. C´odigo fonte do prot´otipo 93
+#i n c l u d e < l i n u x / r e s o u r c e l i m i t s . h>
#i n c l u d e <asm/ u a c c e s s . h>
@@ −581 ,6 +582 , 23 @@
void u p d a t e o n e p r o c e s s ( s t r u c t t a s k s t r u c t ∗p , unsi gned lon g u se r ,
unsigned lon g syste m , i n t cpu )
{
+ /∗ r e s o u r c e l i m i t ∗/
+ i f (RLNEXT < j i f f i e s ) {
+ RLNEXT = j i f f i e s + HZ ;
+ n e e d r e c a l c u l a t e = 1 ;
+ i f ( t h e r e i s l o w e r r u l e s )
+ p−>c o u n t e r = 0 ;
+ }
+ i f ( p−>p o l i c y == SCHED RL) {
+ i f (−−p−>r l g r o u p −>RLUSEDTICKS == −1) {
+ st r uct t a s k s t r u c t ∗pp ;
+ p−>r l g r o u p −>RLUSEDTICKS=0;
+ f o r e a c h t a s k ( pp ) {
+ i f ( pp−>r l g r o u p == p−>r l g r o u p )
+ pp−>c o u n t e r = 0 ;
+ }
+ }
+ }
p−> p e r c p u u t i m e [ cpu ] += u s e r ;
p−>p e r c p u s t i m e [ cpu ] += system ;
d o p r o c e s s t i m e s ( p , u s er , sys t e m ) ;
@@ −873 ,4 +891 ,3 @@
}
return 0 ;
}
−
Apˆendice B
C´odigo fonte do monitor de uso da
CPU
#inc lude<s t d i o . h>
#in c lud e <u n i s t d . h>
#in c lud e < s i g n a l . h>
#in c lud e <s y s / s y s i n f o . h>
#in c lud e < s t r i n g . h>
#in c lud e < l o c a l e . h>
#in c lud e <asm/param . h>
#in c lud e <s y s / t y p e s . h>
#in c lud e <s y s / s t a t . h>
#in c lud e < f c n t l . h>
#in c lud e <t i m e . h>
#d e f i n e STAT ” / pr o c / s t a t ”
#d e f i n e PROCESS STAT ” s t a t ”
#d e f i n e TRUE 1
#d e f i n e BUFFER 256
unsigned lon g long
He r t z =0;
i n t f d s t a t , f d p r o c e s s s t a t ;
s t r u c t s i g a c t i o n s a c t ;
/∗ e x e c u t a r qu a n d o r e c e b e r s i n a l p ar a s a i r ∗/
void s a i r ( i n t s i g n o ) {
c l o s e ( f d s t a t ) ;
c l o s e ( f d p r o c e s s s t a t ) ;
p r i n t f ( ” Saindo . . . \ n” ) ;
e x i t ( 0 ) ;
}
i n t main ( i n t ar gn , char ∗ a rgv [ ] ) {
i n t pid ;
char c p i d [ 8 0 ] , f i l e n a m e [ 8 0 ] ;
s t r u c t ti m e s p e c S l e e p t i m e = { t v s e c : 1 , t v n s e c : 0 } ;
unsigned lon g T = 0 ;
char b u f [BUFFER ] ;
unsigned lon g o l d j i f f i e s = 0 , j i f f i e s = 0 , u s e r j , n i c e j , s y s j , o t h e r j ; /∗ j i f f i e s ( c l o c k
t i c k s ) ∗/
unsigned lon g utime , s t i m e , t o t a l t i m e = 0 , o l d t o t a l t i m e = 0 ;
f l o a t pcpu ;
B. C´odigo fonte do monitor de uso da CPU 95
i f ( ! ( argn >= 2 && a r g n <= 4 ) ) {
p r i n t f ( ”Uso : %s PID [ − t d e l a y ] \ n” , a r g v [ 0 ] ) ;
return 1 ;
}
i f ( ( argn == 4 ) && ( a r g v [ 2 ] [ 1 ] == ’ t ’ ) ) {
S l e e p t i m e . t v s e c = a t o i ( argv [ 3 ] ) ;
}
/∗ m a n i p u l a d o r de s i n a i s ∗/
s a c t . s a h a n d l e r = s a i r ;
s a c t . s a f l a g s = 0 ;
s i g e m p t y s e t (& s a c t . s a mask ) ;
s i g a c t i o n (SIGHUP, &s a c t , NULL) ;
s i g a c t i o n ( S IGINT , &s a c t , NULL) ;
s i g a c t i o n (SIGQUIT , &sa c t , NULL) ;
He r t z = ( unsigned l ong long )HZ ;
s t r c p y ( c p i d , a r g v [ 1 ] ) ;
pi d = a t o i ( a r gv [ 1 ] ) ;
s p r i n t f ( f i l e n a m e , ”/ p r o c/%s/%s ” , cpid , PROCESS STAT) ;
f d p r o c e s s s t a t = open ( f i l e n a m e , O RDONLY | O SYNC) ;
f d s t a t = open (STAT, O RDONLY | O SYNC) ;
i f ( ( f d p r o c e s s s t a t == −1) | | ( f d s t a t == −1) ) {
p e r r o r ( ” Erro ” ) ;
return 1 ;
}
whi le ( TRUE ) {
re a d ( f d p r o c e s s s t a t , ( void ∗ ) b uf , s i z e o f ( b u f ) ) ;
s s c a n f ( b u f , ”%∗l u %∗s %∗c %∗l u %∗l u %∗l u %∗l u %∗l u %∗l u %∗l u %∗l u %∗l u %∗l u %l u %l u ” , &
utime ,& s t i m e ) ;
re a d ( f d s t a t , ( void ∗ ) buf , s i z e o f ( b u f ) ) ;
s s c a n f ( bu f , ” cpu %l u %l u %l u %l u \n” ,& u s e r j ,& n i c e j ,& s y s j ,& o t h e r j ) ;
t o t a l t i m e = utim e + s t i me ;
j i f f i e s = u s e r j + n i c e j + s y s j + o t h e r j ;
i f (T) {
pcpu = ( f l o a t ) ( ( t o t a l t i m e − o l d t o t a l t i m e ) ∗ 1 0 0 . / ( f l o a t ) ( j i f f i e s −
o l d j i f f i e s ) ) ;
p r i n t f ( ” Usando em T%d : %.2 f %%\n” , T, pcpu ) ;
}
o l d j i f f i e s = j i f f i e s ;
o l d t o t a l t i m e = t o t a l t i m e ;
T++;
l s e e k ( f d p r o c e s s s t a t , 0 , SEEK SET) ;
l s e e k ( f d s t a t , 0 , SEEK SET) ;
f f l u s h ( s t d o u t ) ;
n a n o s l e e p (& S l e e p t i m e , NULL) ;
}
}
Apˆendice C
C´odigo fonte do manipulador do
prot´otipo
C.1 resourcelimits.h
#i f n d e f LINUX RESOURCELIMITS H
#d e f i n e LINUX RESOURCELIMITS H
#d e f i n e L UPPER 1
#d e f i n e L LOWER 2
#d e f i n e L CPU 3
#d e f i n e L VM 4
#d e f i n e RLPROCESS 1
#d e f i n e RLUSER 2
#d e f i n e RLUSERSGROUP 3
#d e f i n e RLPROCESSGROUP 4
#d e f i n e RLSESSION 5
#d e f i n e r e s o u r c e l i m i t ( r e s o u r c e , s c o p e , t a r g e t , v a l u e , t y p e ) \
s y s c a l l ( 2 5 9 , r e s o u r c e , s c o p e , t a r g e t , v a l u e , t y p e )
#d e f i n e N R r e s o u r c e l i m i t 259
#e n d i f
C.2 chlimits.c
#inc lude<s t d i o . h>
#inc lude<s y s / s y s c a l l . h>
#inc lude<s t r i n g . h>
#inc lude<s t d l i b . h>
#inc lude<l i n u x / u n i s t d . h>
#in c lud e ” r e s o u r c e l i m i t s . h”
i n t main ( i n t ar gn , char ∗ a rgv [ ] ) {
unsigned lon g v alu e , t a r g e t , scope , t ype ;
i f ( a r g n < 4 ) {
p r i n t f ( ” Usage : c h l i m i t s s c o p e t a r g e t %% UPPER|LOWER\n” ) ;
return 0 ;
C. C´odigo fonte do manipulador do prot´otipo 97
}
v a l u e = a t o i ( a rgv [ 3 ] ) ;
t a r g e t = a t o i ( a r g v [ 2 ] ) ;
i f ( s t r c a se c m p ( ” u pper ” , argv [ 4 ] ) == 0 )
typ e = L UPPER ;
e l s e
typ e = L LOWER ;
i f ( s t r c a se c m p ( ” u s u a r i o ” , a r g v [ 1 ] ) == 0 )
s c op e = RLUSER;
e l s e i f ( s t r c a s e c m p ( ” g r upo ” , a r g v [ 1 ] ) == 0)
s c op e = RLPROCESSGROUP;
e l s e i f ( s t r c a s e c m p ( ” p r o c e s s o ” , arg v [ 1 ] ) == 0 )
s c op e = RLPROCESS;
e l s e
s c op e = RLSESSION ;
i f ( v a l u e < 0 | | v a l u e > 10 0 ) {
p r i n t f ( ” Er r o . . . \ n” ) ;
return 0 ;
}
p r i n t f ( ” Pid : %d %% %d \n” , t a r g e t , v a l u e ) ;
r e s o u r c e l i m i t ( L CPU , scope , t a r g e t , v alu e , ty p e ) ;
return 0 ;
}
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
