CMP50(x) - Tópicos Especiais em Computação (x)

  Escalonamento: Teoria e Aplicações

 

SÚMULA
 Motivação, conceitos básicos e classificação geral. Modelos Determinísticos:
problemas clássicos e soluções. Modelos Estocásticos: problemas clássicos e soluções.
Escalonamento em monoprocessadores. Escalonamento em máquinas paralelas.
Escalonamento em ambientes distribuídos. Escalonamento em sistemas de tempo real:
conceitos, classificação, soluções com garantia, soluções do tipo melhor esforço.

OBJETIVOS
 O objetivo da disciplina é discutir o problema geral de escalonamento e
apresentar várias abordagens e algoritmos existentes. Inicialmente são descritos os
conceitos básicos da área e seus problemas clássicos. Em seguida, problemas de
escalonamento presentes em diferentes contextos dentro da computação são discutidos.
Esta disciplina possui um caráter amplo, uma vez que são estudados algoritmos de
escalonamento que poderão ser aplicados tanto no contexto da computação em si
(escalonamento de processador, de disco, etc) como no contexto dos sistemas
produtivos (escalonamento de máquinas, de pessoas, etc). Ao final da disciplina o aluno
deverá conhecer os principais problemas e várias abordagens de escalonamento, devendo
ser capaz de identificar formas de ataque apropriadas para uma  situação em particular.

CONTEÚDOS PROGRAMÁTICOS
* Introdução
        * Motivação
        * Conceitos básicos
        * Classificação geral dos problemas
* Modelos Determinísticos
        * Conceitos básicos
        * Problemas clássicos e soluções
* Modelos Estocásticos
        * Conceitos básicos
        * Problemas clássicos e soluções
* Escalonamento de tarefas de software em monoprocessadores
        * Objetivos
        * Exemplos de algoritmos
* Escalonamento de tarefas de software em máquinas paralelas
        * Objetivos
        * Exemplos de algoritmos
* Escalonamento de tarefas de software em ambientes distribuídos
        * Objetivos
        * Problemas característicos da distribuição
        * Exemplos de algoritmos
* Escalonamento de tarefas de software em sistemas de tempo real
        * Conceitos básicos, objetivos, tipos de sistemas
        * Classificação das abordagens
        * Exemplos de soluções com garantia
        * Exemplos de soluções do tipo melhor esforço

BIBLIOGRAFIA
M. J. Quinn. Parallel Computing Theory and Practice. McGraw-Hill, 1994.
 
T. G. Lewis. Foundations of Parallel Programming. IEEE Computer Society Press, 1993.
 
M. Pinedo. Scheduling: Theory, Algorithms and Systems. Prentice-Hall, 1995.
 
N. C. Audsley, A. Burns, A. J. Wellings. Deadline Monotonic Scheduling Theory and
Application. Control Engineering Practice, Vol. 1, No. 1, pp. 71-78, feb. 1993.
 
C. L. Liu, J. W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-
Time Environment. Journal of the ACM, Vol. 20, No. 1, pp. 46-61, jan 1973.
 
J. W.-S. Liu, W.-K. Shih, K. J. Lin, R. Bettati, J.-Y. Chung. Imprecise Computations.
Proceedings of the IEEE, Vol. 82, No. 1, pp. 83-94, january 1994.
 
C. D. Locke. Software Architecture for Hard Real-Time Applications: Cyclic Executives
vs. Fixed Priority Executives. The Journal of Real-Time Systems, Vol. 4, pp. 37-53, 1992.
 
K. Ramamritham, J. A. Stankovic. Scheduling Algorithms and Operating Systems
Support for Real-Time Systems. Proc. of the IEEE, Vol.82, No.1, pp.55-67, january  1994.
 
J. Xu, D. L. Parnas. On Satisfying Timing Constraints in Hard-Real-Time Systems.
IEEE Transactions on Software Engineering, Vol. 19, No. 1, pp. 70-84, Jan 1993.
 
A. S. Tanenbaum. Distributed Operating Systems. Prentice-Hall, 1995.
 
A. Silberschatz, P. Galvin. Operating Systems Concepts. 4th ed. Addison-Wesley, 1994.
 
G. Coulouris, J. Dollimore, T. Kindberg. Distributed Systems: Concepts and Design.
Addison-Wesley, 2nd ed., 1994.
 
Artigos de revistas e anais de congressos.
 
AVALIAÇÃO: Trabalhos teóricos ou práticos envolvendo escalonamento.
CARGA HORÁRIA TOTAL: 30 horas/aula
CRÉDITOS: 2 (dois)
SEMESTRE: 99/2