34

Escalonamento de Processos

Embed Size (px)

DESCRIPTION

EScalonamento de Processos

Citation preview

IntroduoO presente trabalho da cadeira de Sistemas Operativos tem como questes ligadas com o tema Escalonamento de Processos, um CPU quando entra em funcionamento ocorrem vrios processos, processos estes em cujo ele o ato de realizar o chaveamento dos processos ativos, de acordo com regras bem estabelecidas, de forma que todos os processos tenham chance de utilizar a UCP. Objetivos Especficos Otimizar o rendimento dos recursos durante o exerccio de Escalonamento; Priorizar o acesso aos recursos disponveis durante o processo de Escalonamento.Objetivo Geral Conhecer o que escalonamento de processos e como ela ocorre.

Escalonamento de processosO Processo: conceito, definies, estados e comportamento Um obstculo discusso de sistemas operacionais que existe dificuldade em denominar todas asatividades da UCP. Um sistema em lote (bach) executa jobs , Enquantoque um sistema de tempo compartilhado executa programas de usurio ou tarefas. Mesmo em um sistema monousurio, como o Microsoft Windows ou o Macintosh OS, um usurio pode executar vrios programas de uma vez: um processador de textos, um navegador Web e um pacote de email. Mesmo se usurio spuder executarum programa decada vez, o sistema operacional poder precisar dar suporte a suas prprias atividades internas programadas, comogerncia de memria. Em muitos aspectos, todas essasatividades so semelhantes, de modo que podem ser todas denominadas de processos (SILBERSCHATZ, A.; GALIN, P.; GAGNE,G., 2000, p. 63). O termo processo no contexto de sistemas operacionais foi usado pela primeira vez pelos projetistas do sistema Multics na dcada de 1960 (DALEY; DENNIS, 1967 apud DEITEL, H. M.; DEITEL,P.J.;CHOFFNES,DR.,2005,p.66). Desde aquela poca o termo processo, de certo modo usado intercambiavelmente como tarefa, ganhou muitas definies como: um programa emexecuo; uma atividade assncrona; o esprito animado de um procedimento; o locus De controle de um procedimento em execuo; aquilo que manifestado pela existnci de uma estrutura de dados denominada descritor De processo ou bloco De controle de processo (BCP) No sistema operacional; aquela entidade s quais os processadores so designados; e a unidade dedespacho(DEITEL, H.M.;DEITEL,P. J.;CHOFFNES, D. R., 2005,p 66).O escalonamento de processos ou Gerncia do Processador (em ingls scheduling) uma atividade organizacional feita pelo escalonador (scheduler) da CPU ou de um sistema distribudo, possibilitando executar os processos mais viveis e concorrentes, priorizando determinados tipos de processos, como os de I/O Bound e os CPU Bound. O escalonador de processos de 2 nveis escolhe o processo que tem mais prioridade e menos tempo e coloca-o na memria principal, ficando os outros alocados em disco; com essa execuo o processador evita ficar ocioso.Tipos bsicos de EscalonamentosEscalonador de curto prazoSeleciona entre os processos em estado de pronto que esto na memria, para serem executados pelo processador. O escalonador de curto prazo faz decises de escalonamento muito mais frequentemente que os de mdio e longo prazo.Escalonador de mdio prazoSeleciona entre os processos que esto na memria virtual, reduz o grau de multiprogramao. Ele temporariamente remove o processo da memria principal e o coloca na memria secundria (swap) fazendo as operaes de swapping in e swapping out.Escalonador de longo prazoSeleciona entre os processos novos, os que so limitados por entrada/sada e os que so limitados por CPU, dando prioridade aqueles limitados por I/O, j que utilizam menos tempo o processador. Este escalonador o responsvel pelo grau de multiprocessamento, ou seja a quantidade de processos que o sistema ir trabalhar.DefinioPara que a CPU no fique muito tempo sem executar tarefa alguma, os sistemas operacionais utilizam tcnicas para escalonar os processos que esto em execuo ao mesmo tempo na maquina.O escalonamento de processos uma tarefa complicada, pois nenhum algoritmo totalmente eficiente e a prova de falhas, principalmente em se tratando de sistemas interativos, como o Windows, pois a interao com o usurio fundamental para este sistema onde quem o utiliza procura respostas rpidas e a todo o momento processos so interrompidos pelo usurio.Um Escalonador de Processos um subsistema do Sistema Operacional responsvel por decidir o momento em que cada processo obter a CPU. utilizado algoritmos de escalonamento que estabelecem a lgica de tal deciso. Nesse momento de decidir qual escalonador ser utilizado no sistema operacional, cabe avaliar o cenrio que o sistema ser utilizado.O escalonador do SO utiliza alguns critrios de escalonamento, como: a taxa de utilizao de CPU, que a frao de tempo durante a qual ela est sendo ocupada; throughput que so nmeros de processos terminados por unidade de tempo; turnaround que o tempo transcorrido desde o momento em que o software entra e o instante em que termina sua execuo; tempo de resposta: intervalo entre a chegada ao sistema e inicio de sua execuo; tempo de espera: soma dos perodos em que o programa estava no seu estado pronto.Responsveis por essa tarefa so algoritmos que so entendidos mais facilmente, estudados separadamente, mas na pratica os sistemas operacionais utilizam combinaes deles para melhor escalonar os processos.Objetivos do EscalonamentoO projeto de um escalonador adequado deve levar em conta uma srie de diferentes necessidades, ou seja, o projeto de uma poltica de escalonamento deve contemplar os seguintes objetivos Ser justo: Todos os processos devem ser tratados igualmente, tendo possibilidades idnticas de uso do processador, devendo ser evitado o adiamento indefinido. Maximizar a produtividade (throughput): Procurar maximizar o nmero de tarefas processadas por unidade de tempo. Ser previsvel: Uma tarefa deveria ser sempre executada com aproximadamente o mesmo tempo e custo computacional. Minimizar o tempo de resposta para usurios interativos. Maximizar o nmero possvel de usurio interativos. Minimizar a sobrecarga (overhead): Recursos no devem ser desperdiados embora algum investimento em termos de recursos para o sistema pode permitir maior eficincia. Favorecer processos "bem comportados": Processos que tenham comportamento adequado poderiam receber um servio melhor. Balancear o uso de recursos: o escalonador deve manter todos os recursos ocupados, ou seja, processos que usam recursos sub- utilizados deveriam ser favorecidos. Exibir degradao previsvel e progressiva em situaes de intensa carga de trabalho.Como pode ser visto facilmente, alguns destes objetivos so contraditrios, pois dado que a quantidade de tempo disponvel de processamento (tempo do processador) finita, assim como os demais recursos computacionais, para que um proceso seja favorecido outro deve ser prejudicado. O maior problema existente no projeto de algoritmos de escalonamento est associado natureza imprevisvel dos processos, pois no possvel prevermos se um dado processo utilizar intensamente o processador, ou se precisar grandes quantidades de memria ou se necessitar numerosos acessos aos dispositivos e E/S.Qualidade do EscalonamentoExistem vrios critrios que permitem a avaliao da qualidade do servio oferecido por um algoritmo de escalonamento. So eles: uso do processador, tempo de resposta e tempo de permanncia. O tempo de permanncia, tempo de retorno ou turnaround time, um critrio simples dado pela soma do tempo de espera com o tempo de servio ou tempo de execuo. Em geral deseja- se que o tempo de permanncia seja o menor possvel.Uma outra forma de avaliar a qualidade do escalonamento utilizando-se do tempo de permanncia normalizado, ou seja, a razo entre o tempo de permanncia e o tempo de servio.Algoritmos escalonadoresExistem os algoritmos preemptivos e os no preemptivos. Os preemptivos so algoritmos que permitem que um processo seja interrompido durante sua execuo, quer seja por fora de uma interrupo de entrada/sada, quer seja em decorrncia da politica de escalonamento adotada e aplicada por parte do escalonador de processos ou simplesmente por fora do trmino da execuo do processo. Aps a interrupo deste processo, ocorre o que se chama de troca de contexto, que consiste em salvar o contedo dos registradores e a memoria utilizada pelo processo e conceder outro processo o privilgio de executar na CPU, restaurando assim o contexto deste ultimo processo. Cabe ressaltar que nos algoritmos no preemptivos, por serem utilizados exclusivamente em sistemas monoprocessados, esse fato no ocorre, sendo cada programa executado at o fim.Exemplos de Algoritmos: FIFO (First in, first out) ou FCFS (First come, first served): Onde como seu prprio nome j diz, o primeiro que chega ser o primeiro a ser executado; SJF (Shortest Job First): Onde o menor processo ganhar a CPU e atrs do mesmo formar uma fila de processos por ordem crescente de tempo de execuo; SRT (Shortest Remaining Time): Neste algoritmo escolhido o processo que possua o menor tempo restante, mesmo que esse processo chegue metade de uma operao, se o processo novo for menor ele ser executado primeiro; Algoritmo Loteria: O Sistema Operacional distribui tokens (fichas), numerados entre os processos, para o escalonamento sorteado um numero aleatrio para que o processo ganhe a vez na CPU, processos com mais tokens tm mais chance de receber antes a CPU. Escalonamento garantido: Este algoritmo busca cumprir promessas de alocao de CPU o mais preciso possvel. RR (Round-Robin): Nesse escalonamento o sistema operacional possui um timer, chamado de quantum, onde todos os processos ganham o mesmo valor de quantum para rodarem na CPU. Com exceo do algoritmo RR e escalonamento garantido, todos os outros sofrem do problema de Inanio (starvation). Mltiplas Filas: So usadas vrias filas de processos prontos para executar, cada processo e colocado em uma fila, e cada fila tem uma poltica de escalonamento prpria e outra entre filas.Todos os algoritmos classificam os processos em estados: Iniciando, Pronto, Executando, Entrada/ Sada e Terminado.Estados de processosPara o sistema operacional organizar os processos que sero atendidos eles so atribudos estados para os mesmos.Diagrama de Estados de ProcessosQuem armazena essas informaes como os estados de processos e outras como: tempo e execuo, por exemplo, o bloco de controle de processo (PCB - Process Control Block).Nveis de escalonamentoEm sistemas de tempo compartilhado, o kernel aloca a CPU a um processo por um perodo de tempo chamado "fatia de tempo"ou "quantum"; interrompe o processo e escalona outro quando o tempo atribudo expira e reescalona-o para continuar a execuo tempo depois. A parte do sistema operacional com as funes acima descritas chamada de escalonador e o algoritmo utilizado em sua programao chamado algoritmo de escalonamento. Os algoritmos de escalonamento se subdividem em trs nveis: Escalonamento a curto prazo; - Decide quem vai ganhar a CPU: Round robin; Escalonamento com prioridade; Filas Mltiplas. Escalonamento a mdio prazo; - Decide quem vai ocupar a memria: Escalonamento Em Dois Nveis. Escalonamento a longo prazo. - Decide quem vai virar processo. Usado em programas do tipo batch. Menor Job Primeiro; Escalonamento Garantido.Uma complicao que os escalonadores devem enfrentar o fato do comportamento de cada um dos processos ser nico e imprevisvel. Quando o escalonador coloca um processo para rodar, ele nunca tem certeza a respeito do tempo que tal processo vai levar executando at ser bloqueado. Para assegurar-se de que nenhum processo rode por um tempo muito grande, todos os computadores modernos possuem um relgio interno, que periodicamente gera um sinal de interrupo, denominado interrupo de tempo.A cada interrupo de tempo o sistema operacional posto para rodar, e decide se o processo corrente deve ser interrompido cedendo lugar a outro processo que esteja pronto para rodar e carregado na memria. Antes de analisar os algoritmos especficos, citaremos as principais caractersticas que devem estar presentes em um bom algoritmo de escalonamento, so elas: 1. Justia: garantir que todos os processos do sistema tero chances iguais do uso do processador; 2. Eficincia: manter o processador ocupado 100 por cento do tempo; 3. Tempo de Resposta: minimizar o tempo de resposta para usurios interativos; 4. Turnaround: minimizar o tempo que os usurios batch devem esperar pela sada; 5. Throughput: maximizar o nmero de jobs processados na unidade de tempo, usualmente uma hora. Passaremos agora a analisar alguns algoritmos especficos, classificado-os dentro dos nveis apresentados. Escalonamento de Processos a Curto Prazo Escalonamento Round Robin Um dos mais antigos, simples, justo e portanto muito usado, o chamado round robin. A cada processo atrubui-se um intervalo de tempo, quantum, durante o qual ele poder usar o processador. Se o processo ainda precisar rodar depois de esgotado seu quantum, ele perde o processador, dando lugar a um outro processo. Se o processo for bloqueado ou terminar antes de esgotado seu quantum, a comutao para um novo processo ser feita no exato momento do bloqueio ou do trmino do processamento.

O escalonamento round robin muito simples de implementar. Tudo que o escalonador precisa fazer manter uma lista de processos prontos para rodar. Quando o quantum de um processo se esgota, ele colocado no fim da fila de prontos. A nica coisa que pode dar um pouco de trabalho na implementao deste algoritmo a determinao do tamanho do quantum. Um quantum muito pequeno causa sucessivas trocas de contexto, troca do processador entre processos, baixando a eficincia do processador, enquanto faz-lo muito grande leva a um tempo de resposta no aceitvel para usurios interativos. Escalonamento Com Prioridade Ao contrrio do round robin, neste algoritmo fatores externos so considerados para a escolha do prximo processo a ganhar o processador.A idia bsica muito simples: a cada processo associada uma prioridade, e o processo pronto com maior prioridade ser aquele que vai rodar primeiro. Para evitar que processos com alta prioridade monopolizem o processador, o escalonador decrementa a prioridade do processo que est rodando, a cada interrupo de tempo. Se tal ao fizer com que a prioridade do processo corrente torne-se mais baixa que a do de mais alta prioridade da fila de prontos, deve ocorrer uma troca de contexto. Filas Mltiplas Devido ao problema de comutao do processador entre processos ser muito lenta, principalmente em computadores antigos que s podiam armazenar um nico processo na memria, necessitou-se de um outro algoritmo de escaloanmento que dividi-se os processos em classes de prioridade.Os processos da classe mais prioritria rodavam com quantum 1. Aqueles que estivessem na classe seguinte rodariam com quantum 2. Na prxima quantum 4, e assim por diante. Como exemplo, considere um processo que precise rodar continuamente por um tempo equivalente a 12 quanta. Inicialmente, ele receber 1 quantum, e aps decorrido este tempo ele ser suspenso. Da prxima vez, ele receber 2 quanta; aps isto ele ser suspenso novamente. Nas rodadas seguintes este processo receber sucessivamente quanta de 4 e 8, usando somente 5 das 8 entregues ele. Observe que s foram necessrios quatro passos para que o processo executasse seu priocessamento, em vez de doze que seriam necessrios usando o round robin puro. Observe tambm que quando usamos filas mltiplas, medida que o processo vai caindo em filas de prioridade mais baixa, ele ser escolhido para rodar com menos freqncia, favorecendo os processos interativos, normalmente pequenos.

Escalonamento de Processos a Mdio Prazo Escalonamento em dois nveis At agora temos assumido que todos os processos esto na memria principal. Se no houver memria disponvel para todos, alguns de tais processos devem ser mantidos em disco.Trocas de contexto envolvendo o disco algumas ordens de magnitude maior do que quando ambos os processos esto na memria principal. Uma forma mais prtica de tratar com o swapping de processos usando um escalonador de dois nveis, onde um subconjunto dos processos prontos carregado inicialmente na memria principal. Inicialmente, o escalonador de baixo nvel escolhe um entre esses processos. Periodicamente, o escalonador de alto nvel posto para rodar movimentando processos entre a memria principal e o disco. Seguem-se alguns critrios que o escalonador de alto nvel pode usar nas suas tomadas de deciso: 1. Quanto tempo se passou desde que o processo foi colocado no disco ou na memria principal? 2. Quanto tempo de processador o processo usou recentemente? 3. Qual o tamanho do processo? 4. Qual a prioridade do processo? 5. Qual o estado do processo? O escalonador de alto nvel pode usar qualquer algoritmo de escalonamento.

Escalonamento de Processos a Longo Prazo Menor Job Primeiro A maioria dos algoritmos acima foi projetado para sistemas iterativos. Vamos analisar a seguir um tipo de escalonamento apropriado para sistemas que rodam jobs em batch, nos quais o tempo de processamento de cada job conhecido com antecedncia. Nesta poltica, quando vrios jobs igualmente importantes estiverem esperando vez numa fila, o escalonador usa a poltica de alocar o procesador ao menor dos jobs da fila.

Escalonamento Garantido Uma forma completamente diferente de tratar a questo do escalonamento fazer certas promessas ao usurio a respeito da performance, e cumpri-las de alguma forma.Uma promessa bem realista e muito fcil de cumprir a de que se houver N usurios ativos na rede, cada um vai receber em torno de 1/N da capacidade de processamento que um usurio usou para todos os seus processos desde o momento em que tal usurio tornou-se ativo.Como o tempo que cada usurio gastou at o momento conhecido, fcil calcular a razo entre o tempo realmente concedido ao usurio e o tempo prometido. A idia do algoritmo por para rodar o processo com razes mais baixas, diminuindo, em conseqncia, as razes mais altas. Linha ou Encadeamento de execuo uma forma de um processo dividir a si mesmo em duas ou mais tarefas que podem ser executadas concorrencialmente. O suporte thread fornecido pelo prprio sistema operacional, no caso da linha de execuo ao nvel do ncleo Uma thread permite, por exemplo, que o usurio de um programa utilize uma funcionalidade do ambiente enquanto outras linhas de execuo realizam outros clculos e operaes.Em hardwares equipados com uma nica CPU, cada thread processada de forma aparentemente simultnea, pois a mudana entre uma thread e outra feita de forma to rpida que para o utilizador, isso est acontecendo paralelamente. Em hardwares com mltiplos CPUs ou multi-cores, as threads so realizadas realmente de forma simultnea.Os sistemas que suportam uma nica thread (em real execuo) so chamados de monothread enquanto que os sistemas que suportam mltiplas threads so chamados de multithread.ParticularidadesCada thread tem o mesmo contexto de software e compartilha o mesmo espao de memria (endereado a um mesmo processo-pai), porm o contexto de hardware diferente. Sendo assim o overhead causado pelo escalonamento de uma thread muito menor do que o escalonamento de processos. Entretanto, algumas linguagens (C, por exemplo) no fornecem acesso protegido memria nativa (sua implementao fica a cargo do programador ou de uma biblioteca externa) devido ao compartilhamento do espao de memria.Um dos benefcios do uso das threads advm do fato do processo poder ser dividido em vrias threads; quando uma thread est espera de determinado dispositivo de entrada/sada ou qualquer outro recurso do sistema, o processo como um todo no fica parado, pois quando uma thread entra no estado de 'bloqueio', uma outra thread aguarda na fila de prontos para executar.Uma thread possui um conjunto de comportamentos padro, normalmente encontrados em qualquer implementao ou sistema operativo.Uma thread pode: criar outra da mesma forma que um processo, atravs do mtodo thread-create, onde a thread retorna um ID como primeiro argumento (resultado da funo de criao); esperar outra thread se sincronizar, atravs do mtodo join; voluntariamente "desistir" da CPU por no precisar mais do processamento proposto pela prpria ou por vontade do utilizador. Feito atravs do mtodo thread-yield; replicar-se sem a necessidade de duplicar todo o processo, economizando assim memria, processamento da CPU e aproveitando o contexto (variveis, descritores, dispositivos de I/O).Estados de uma linha de execuoUma thread pode assumir os seguintes estados: Unstarted: logo aps ser criada (antes do Start()); Running: aps ser ativada (Start()) ou aps mtodo Resume(); Suspended: aps mtodo Suspended(); Stopped: aps mtodo Abort().ULT e KLTUsualmente as threads so divididas em duas categorias: thread ao nvel do utilizador (em ingls: User-Level Thread (ULT)), e thread ao nvel do ncleo (em ingls: Kernel-Level Thread (KLT)).Thread em modo usurio

Thread em modo kernel

As threads da primeira categoria (ULT) so suportadas pela aplicao, sem conhecimento do ncleo e geralmente so implementadas por pacotes de rotinas (cdigos para criar, terminar, escalonamento e armazenar contexto) fornecidas por uma determinada biblioteca de uma linguagem, como o caso da thread.h (biblioteca padro da linguagem C). Estas threads suportam as mesmas operaes que as threads KLT (criar, sincronizar, duplicar e abortar). Possuem como vantagens a possibilidade de implementao em sistemas operativos que no suportam nativamente este recurso, sendo geralmente mais rpidas e eficientes pois dispensam o acesso ao ncleo. Evita assim mudana no modo de acesso, e a estrutura de dados fica no espao do utilizador, levando a uma significativa queda de overhead, alm de poder escolher entre as diversas formas de escalonamento em que melhor se adequa.A gesto da thread (KLT) no realizada atravs do cdigo do prprio programa; todo o processo subsidiado pelo SO. Esse modelo tem a vantagem de permitir o suporte a multiprocessamento e o facto do bloqueio de uma linha de execuo no acarretar bloqueio de todo processo, no obstante, temos a desvantagem de ter que mudar o tipo de acesso sempre que o escalonamento for necessrio, aumentando assim o to temido overhead.H quatro operaes bsicas na gesto de threads: criar, terminar, thread join e thread yield.Criar (thread creation)Basicamente uma thread pode criar outra(s), sendo que depois essas mesmas threads so executas 'simultaneamente'. A thread criadora a thread-me e a thread criada a thread-filho. Threads includas na funo main quando executadas podem criar threads-filho. No diagrama a seguir h a thread A que executa inicialmente. Mais tarde criada a thread B indicada no ponto amarelo. Depois de criadas, a thread A e thread B executam simultaneamente. Em seguida a thread A pode criar uma ou mais threads (por exemplo uma thread C). Depois de criada a thread C, h trs threads executando simultaneamente e todas disputam o uso da CPU. Entretanto, a thread que pode ser executada a qualquer momento no de conhecimento da CPU.Terminar (thread termination)Para maioria dos casos, as threads no so criadas e executadas eternamente. Depois de terminado o seu objectivo, a thread termina. No facto, a thread que criou estas duas threads-filho termina tambm, porque sua tarefa atribuda se completa. Na matrix de multiplicao (matrix multiplication), uma vez que o valor de C[i,j] computado, a thread correspondente termina. Em geral quando a tarefa atribuda a thread completa, a thread pode ser terminada. Alm disso, se a thread-me terminar, todas as threads filho terminam tambm. Porque isso importante? Isso importante porque as threads-filho compartilham recursos com a thread-me, incluindo variveis. Quando a thread-me termina, todas as variveis so perdidas e a thread-filho no poder aceder aos recursos que a thread-me possua. Assim, se a thread-me terminar mais cedo que a thread-filho haver um problema! Uma thread pode terminar das seguintes maneiras: Retornando da sua rotina mais externa, a thread criadora. Quando termina a rotina em que foi comeada. Chamando pthread_exit, fornecendo um estado de sada. Terminando atravs da funo pthread_cancelSincronizar(Thread Join)Imagine a seguinte situao: Voc est estudando para uma prova. Ento voc pede o seu irmo mais novo para comprar uma pizza. Neste caso voc a thread principal e seu irmo a thread-filho. Uma vez que voc deu a ordem, voc e seu irmo comeam a executar uma tarefa simultaneamente. Agora h dois casos a se considerar: Primeiro: Seu irmo traz a pizza e termina enquanto voc estuda. Nesse caso voc pode parar de estudar e comer a pizza. Segundo: Voc acaba de estudar mais cedo e dorme e depois a pizza chegar.A juno de threads (thread join) destinada para resolver este problema. A thread pode executar o thread join e aguardar at a outra thread terminar. No caso acima, voc a thread principal (thread main) e deve executar o thread joinaguardando o seu irmo (thread-filho) terminar. Em geral o thread join utilizado para a thread-me se sincronizar com uma das threads-filho.Rendimento da thread (Thread Yield)Suponha que voc executa um certo nmero de programas o tempo todo no computador. Isso possvel devido a CPU escalonar pouco a pouco outros ciclos da CPU, assim outros programas podem ser executados. Isso pode ser um problema de poltica de planeamento do Sistema Operativo. Entretanto, quando escrevemos programas com mltiplas threads, temos que fazer correctamente para que algumas threads no ocupem a CPU eternamente, ou por um tempo muito longo sem abandon-lo. Seno terminar na situao acima quando uma ou duas threads executam enquanto outras simplesmente esperam para retornar. Liberamos espao na memria graas a thread yield. Quando a thread executa o thread yield, a execuo da thread suspensa e a CPU passa para uma outra thread em execuo. Essa thread aguardar at a CPU tornar-se disponvel novamente.EscalonamentoDa mesma forma que os processos sofrem escalonamento, as threads tambm tm a mesma necessidade. Quando vrios processos so executados em uma CPU, eles do a impresso que esto sendo executados simultaneamente. Com as threads ocorre o mesmo, elas esperam at serem executadas. Como esta alternncia muito rpida, h impresso de que todas as threads so executadas paralelamente.Linha de execuo ao nvel do usurioAs ULT so escalonadas pelo programador, tendo a grande vantagem de cada processo usar um algoritmo de escalonamento que melhor se adapte a situao, o sistema operacional neste tipo de thread no faz o escalonamento, em geral ele no sabe que elas existem. Neste modo o programador responsvel por criar, executar, escalonar e destruir a thread. Um exemplo prtico de processo chamado P1 que contm tais threads: P1T1, P1T2 e P1T3, quando o sistema operacinal da a CPU para o processo P1 cabe a ele destinar qual thread ser executada, caso esta thread use todo processo do quantum, o sistema operacional chamar outro processo, e quando o processo P1 voltar a executar, P1T1 voltar a ser executada e continuar executando at seu trmino ou interveno de P1, este comportamento no afetar outros processos pois o sistema continua escalonando os processos normalmente.Linha de execuo ao nvel do ncleoComparao entre linha de execuo e ProcessoUm sistema baseado em linha de execuo diferente de um sistema operacional multi-tarefa tradicional, em que processos so tipicamente independentes, carregam considervel estado da informao, tem endereo de memria separado e interagem somente atravs de mecanismos de inter-processos de comunicao. As threads, por outro lado, compartilham o estado da informao de processos nicos, e compartilham memria e outros recursos diretamente.A troca de contexto atravs de linha de execuo num mesmo processo tipicamente mais rpida que a troca de contexto entre processos diferentes. Sistemas como o Windows NT e o OS/2 so feitos para ter linha de execuo "baratas" e processos "caros", enquanto em outros sistemas operacionais no h grandes diferenas.O multithreading um modelo de programao popular que permite a execuo de mltiplas linha de execuo dentro de um contexto simples, compartilhando recursos do processo, e capazes de executar de forma independente. O modelo de programao em linha de execuo fornece ao desenvolvedor uma execuo simultnea. Entretanto, a aplicao mais interessante da tecnologia ocorre quando ela utilizada em um processo simples permitindo uma execuo paralela em sistemas multi-processados.Um sistema multi-threaded possui um melhor desempenho que um sistema de computadores com mltiplas CPUs e com mltiplos ncleos, ou que um cluster de mquinas. Isto acontece porque a linha de execuo empresta a ela mesma uma execuo simultnea. Em alguns casos, o programador precisa ter cuidado em evitar condies de concorrncia e outros comportamentos inesperados.Os sistemas operacionais implementam as linhas de execuo de duas formas: multithreading preemptiva ou multithreadingcooperativa. A multithreading preemptiva geralmente considerada uma implementao superior, porque permite ao sistema determinar quando uma troca de contexto pode acontecer. A multithreading cooperativa, por outro lado, confia nas threadspara ceder o controle, o que pode ser um problema caso uma tarefa monopolize o uso da CPU ou se houver espera pela disponibilidade de um recurso. A desvantagem da multithread preemptiva que o sistema pode fazer uma troca em um tempo inapropriado, causando uma inverso de prioridade ou outros efeitos ruins que podem ser evitados por uma multithreadingcooperativa.Em geral: Criar um processo pode ser caro em termos de tempo, memria, e sincronizao entre processos. As linhas de execuo podem ser criadas sem a replicao do processo inteiro. O trabalho de criar uma linha de execuo pode ser feito no espao do usurio. Como as linhas de execuo partilham o espao de endereamento a comunicao entre elas mais rpida. O tempo gasto para troca de linha de execuo menor, em parte por que no h necessidade de troca de espao de endereamento.CancelamentoO cancelamento de threads corresponde tarefa de terminar um thread antes que se complete. Por exemplo, se mltiplos threads esto pesquisando concorrentemente em um banco de dados e um thread retorna o resultado, os threads que ainda esto sendo executados podem ser cancelados. Uma outra situao pode ocorrer quando um usurio pressionar um boto em um navegador da Web. Com frequncia, uma pgina da Web carregada em um thread separado. Quando um usurio pressionar o boto stop, o thread que estava carregando a pgina cancelado. Um thread que est para ser cancelado frequntemente denominado thread-alvo.[]Exemploimport java.io.*;public class Example implements Runnable{ static Thread threadCalculate; // Cria o thread. static Thread threadListen; long totalPrimesFound = 0; public static void main (String[] args) { Example e = new Example(); threadCalculate = new Thread(e); threadListen = new Thread(e); threadCalculate.start(); threadListen.start(); } public void run() { Thread currentThread = Thread.currentThread(); if (currentThread == threadCalculate) calculatePrimes(); else if (currentThread == threadListen) listenForStop(); } public void calculatePrimes() { int n = 1; while (true) { n++; boolean isPrime = true; for (int i = 2; i < n; i++) if ((n / i) * i == n) { isPrime = false; break; } if (isPrime) { totalPrimesFound++; System.out.println(n); } } } private void listenForStop() { BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); String line = ""; while (!line.equals("stop")) { try { line = input.readLine(); } catch (IOException exception) {} } System.out.println("Found " + totalPrimesFound + " prime numbers before you said stop"); System.exit(0); }}

Concluso Diferentes tipos de sistemas exigem diferentes algoritmos de escalonamento de processos. Cada algoritmo deve funcionar de modo que leve ao alcance dos objetivos do sistema ao qual est vinculado.Os algoritmos devem funcionar de forma justa, ou seja, devem dar chance a todos os processos de receberem a UCP por uma quantidade de tempo o mais razovel possvel. Dependendo do tipo de processo, cada qual poder necessitar de mais ou menos tempo de UCP. Cabe ao escalonador decidir qual processo receber mais ou menos UCP de acordo com o que achar maisjusto. Assim, promover a alternncia adequada de processos de modo que todos eles executem seus servios de maneira eficiente queles que os requisitaram, fazem do escalonador de processos uma importante entidade do SO. Sem ele, os recursos seriam mal aproveitados, tempos de espera seriam acentuados e os usurios ficariam insatisfeitos.

Referncias BibliograficasSILBERSCHATZ, Abraham; GALVIN, Peter Baer; GAGNE, Greg. Fundamentos de sistemas operacionais. 6. ed. Rio de Janeiro: LTC, 2004 p.580.DEITEL, Harvey M.; DEITEL, Paul J.; CHOFFNES, David R. Sistemal Operacional. 3ed. So Paulo: Pearson Prentice Hall, 2005.

LAUDON, KennethC.LAUDON, Jane P. Sistemas de Informao Gerenciais: administrando a empresa digital. 5ed. SoPaulo: Pearson Prentice Hall,2004.

SILBERSCHATZ, Abraham; GALIN, Peter; GAGNE, Greg. Sistemas operacional: conceitos e aplicaes. 5tiragem. Rio de Janeiro: Campus,2000.

TANENBAUM Andrew S. Sistemas operacionais modernos.2ed.SoPaulo:Pearson Prentice Hall, 2003.

TANENBAUM Andrew S.; WOODHULL, Albert S. Sistemas operacional: Projeto e implementao2ed.PortoAlegre:Bookman, 2000.http://www.oficinadanet.com.br/post/12781-sistemas-operacionais-o-que-e-escalonamento-de-processoshttp://www.ic.unicamp.br/~islene/1s2008-mc514/sched/sched.pdf