Skip navigation

Escalonadores

Gerência do Processador

O escalonador é a entidade do SO responsável por selecionar um processo apto para executar no processador

O objetivo é dividir o tempo do processador de forma justa

Típicos de sistemas multiprogramados

Duas partes:

     Escalonador: política de seleção

     Dispatcher: efetua a troca de contexto

Objetivos do Escalonamento

Maximizar a utilização do processador Maximizar a produção do sistema

N° de processos executados por unidade de tempo

Minimizar o tempo de execução

Tempo total para executar um processo

Minimizar o tempo de espera

Tempo em que o processo permanece na fila de aptos

Minimizar o tempo de resposta

Tempo decorrido entre a requisição e sua realização

Quando Escalonar

Quando se cria um novo processo, é necessário tomar uma decisão entre executar o processo pai ou o processo filho

Quando se termina um processo, algum outro processo deve ser escolhido entre processos prontos

Quando um processo bloqueia para E\S

Quando ocorre uma interrupção de E\S

Algoritmos de Escalonamento

– Existem duas categorias de algoritmos de escalonamento:

Não preemptivos – escolhe um processo para executar e então o deixa executar até que seja bloqueado ou até que ele voluntariamente libere a CPU

Preemptivos – escolhe um processo e o deixa em execução por um tempo máximo fixado

Ambientes de escalonamento

 Lote (Batch)

Algoritmos não preemptivos ou preemptivos com longo intervalo de tempo

 Interativo

Preempção é essencial!

 Tempo real

Algumas vezes a preempção é desnecessária

Objetivos do algoritmo de escalonamento

Todos os Sistemas:

Justiça – dar a cada processo um porção justa da CPU

Aplicação da política – verificar se a política estabelecida é cumprida

Equilíbrio – manter ocupadas todas as partes do sistema

Sistemas em Lote:

Vazão (throughput) – maximizar o n° de processos por hora

Tempo de retorno – minimizar o tempo entre a submissão e o término

Utilização de CPU – manter a CPU ocupada o tempo todo

Sistemas Interativos

Tempo de resposta – responder rapidamente às requisições

Proporcionalidade – satisfazer às expectativas dos usuários

Sistemas de Tempo Real

Cumprimento dos prazos – evitar a perda de dados

Previsibilidade – evitar a degradação da qualidade em sistemas multimídia

Considerações

Vazão – é o número de processos por hora que o sistema termina

Tempo de resposta – indica quanto tempo, em média, o usuário tem de esperar pelo fim de um trabalho

Despacho (Dispatch) ou Troca/Chaveamento de contexto

  • Mudança do processo em execução
  • O S.O. deve salvar o estado do processo atual e carregar o estado do novo processo
    • Pergunta: Onde salvar e de onde recuperar?
  • Troca de contexto é overhead
  • Tempo gasto depende do hardware e da estrutura do processo no S.O.

Captura de Tela 2014-09-16 às 23.42.35

 

Escalonamento em Sistemas em Lote (Batch)

Captura de Tela 2014-09-16 às 23.13.33

Escalonamento em Sistemas Interativos

Captura de Tela 2014-09-16 às 23.14.02

Níveis de Escalonamento

Longo Prazo

  • Executado quando um novo processo é criado;

  • Determina quando um processo novo passa a ser considerado no sistema;

  • Controla o grau de multiprogramação do sistema

    • Quanto maior o n° de processos ativos, menor a porcentagem de tempo de uso do processador por processo

Médio Prazo

  • Associado a gerência de memória

    • Participa do mecanismo de swapping

  • Suporte adicional a multiprogramação

    • Grau de multiprogramação efetiva (diferencia aptos dos aptos suspensos)

Curto Prazo

  • Mais importante;

  • Determina qual processo apto deverá utilizar o processador;

  • Executado sempre que eventos importantes ocorrem

    • Interrupção de relógio

    • Interrupção de E\S

    • Chamadas de sistemas

    • Sinais (interrupção de software)

 

Diagrama de Escalonamento

 

Captura de Tela 2014-09-16 às 23.19.10

 

Algoritmos de escalonamento

FIFO

     Simples de Implementar (Fila)

     Funcionamento:

             Processos aptos são inseridos no fim da fila

             Processo no início da fila é o próximo a executar

             Processo executa até que:

                         Libere o processador

                         Realize uma chamada de sistema (bloqueado)

                         Termine sua execução

Round Robin

      Similar ao algoritmo FIFO, só que:

               Cada processo recebe um tempo limite máximo para executar um ciclo do processador

      Fila de processos aptos é uma fila circular

      Necessidade de um relógio para delimitar as fatias de tempo

Shortest Job First (SJF)

  • Associa-se a cada processo seu próximo pulso
    • Próximo processo será o de menor pulso
  • SJF Preemptivo:
    • Um processo que possui um pulso menor que o restante de pulsos do correntemente em execução força a preempção
    • Chamado de Shortest Remaining Time First (SRTF)
  • SJF não preemptivo
    • Processos que chegam são comparados apenas com aqueles à espera da CPU
  • SJF é ótimo quanto ao tempo médio de espera

 

Problema: Duração do próximo pulso

Como resolver?

 

Escalonamento com prioridades

  • um valor inteiro de prioridade para cada processo
  • A CPU é alocada para o processo de maior prioridade
    • Usualmente quanto menor o valor, maior a prioridade
    • Preemptivo ou não preemptivo
  • SJF é um escalonamento com prioridade, onde a prioridade é o tamanho previsto do pulso de CPU
  • Problema: Inanição (Starvation)
    • Processos de baixa prioridade podem nunca ser executados
  • Solução: Envelhecimento (aging)
    • Prioridade de cada processo que fica na fila aumenta à medida que o tempo passa

 

Escalonamento por Filas Multi-Nível

  • Fila de processos prontos é dividida:
    • Processos interativos (Foreground) – RR
    • Processos em lote;batch(background) – FIFO
  • Escalonamento entre filas
    • Prioridade fixa
      • P. Ex: Atender sempre processos interativos primeiro
      • Possibilidade de inanição
    • Fatias de Tempo
      • Cada fila é escalonada por uma fração do tempo total

Captura de Tela 2014-09-16 às 23.33.06

 

Filas Multinível com realimentação

  • Um processo pode se mover entre filas
    • Forma de interpretar o envelhecimento
  • Escalonamento pode ser definido por:
    • No de filas
    • algoritmo de escalonamento de cada fila
    • método usado para promover um processo
    • método usado para rebaixar um processo
    • método usado para decidir em que fila cada processo entra no sistema

Escalonamento de multi-processadores

Multiprocessamento Simétrico (SMP)

  • Todas as CPUs acessam dados e recursos de forma igual

Multiprocessamento assimétrico (AMP):

  • Só um processador acessa as estruturas de dados do sistema, reduzindo a complexidade do sistema

 

Escalonamento de tempo real

  • Processos podem estabelecer demandas em termos de tempo de ativação de tarefas
  • Essencial para sistemas de controle de processos de precisão e multimídia
  • Hard real-time (tempo rígido) – Devem completar tarefas em um tempo garantido
  • Soft real-time (tempo maleável) – requerem que processos críticos recebam prioridade superior aos demais

 

Latência de despacho

  • Tempo gasto até que um processo de tempo real que solicita a CPU realmente a receba
  • Técnicas podem reduzir essa latência
    • Pontos de interceptação: Pontos onde operações potencialmente longas podem ser interrompidas
    • Kernel interceptável (interrompível)
    • Liberação forçada de recursos de processos de baixa prioridade (resolução de conflitos)Captura de Tela 2014-09-16 às 23.39.53

 

 

 

Processos no Unix (Linux)

Objetivos:

 

  • Apresentar a estrutura de processos no Unix
  • Descrever as principais funções associadas à gerência de processos
  • Discutir questões sobre estruturas de dados relacionadas e comunicação entre processos

Unix: Um pouco de História

  • Bell Labs, Ken Thompson, Dennis Ritchie
  • 1971: PDP-7, assembly
  • 1972: PDP 11: C — código fonte disponível
  • 197?: Univ. de Berkeley? Mem. Virtual, TCP/IP
  • 1980: AT&T – System V
  • POSIX: Padrão de portabilidade

Versões Atuais

  • Sun Solaris (Open Solaris): Um dos mais estáveis
  • SCO Unix: Um dos mais antigos
  • Linux: Um dos mais populares
  • freeBSD: Um dos mais eficientes
  • netBSD: o com mais plataformas
  • IBM AIX: um dos mais controversos
  • Apple Mac OS X: um dos mais diferentes

Unix: Estrutura geral do sistema

Captura de Tela 2014-09-16 às 22.36.21

 

Unix: O Processo de Boot

Captura de Tela 2014-09-16 às 22.36.52

 

Unix: O processo de boot (Bootloader)

Captura de Tela 2014-09-16 às 22.37.21

 

Unix: O processo de Boot no Kernel

Captura de Tela 2014-09-16 às 22.37.36

Unix: O processo de boot (Init)

  • Primeiro a executar
  • Nunca termina (Causa Shutdown se morrer)
  • Lê arquivos de configuração
  • Dispara demais processos

 

Unix: Processos

  • Hierarquia de processos pais e filhos
    • fork(): Cria uma cópia do processo pai
    • exec(): Substitui o processo corrente por um novo programa
  • Várias formas de comunicação entre processos: Memória, Semáforos, Pipes, Msgs
  • Processos, Threads de aplicação (pthreads)
  • Alguns tem Threads de núcleo (Solaris, Linux)

 

Criação de Processos no Unix

  • fork()
    • S.O. cria um novo PCB
    • Cria-se uma cópia na memória do processo pai, mas com novo PID
    • Recursos de E/S são compartilhados
  • exec()
    • Mantém o PID
    • SO busca um programa do disco, o carrega na memória e sobre a área do programa que fez a chamada
    • Execução passa para o início do programa principal

Criação de processos no Unix: Exemplo

if((child_pid=fork())>0) {

/*Aqui é o processo pai*/

} else

if(child_pid==0) {

//Estamos no processo filho

if(execl(programfile,/*…*/)<0){

perror(“Erro no Execl“);

exit(1);

}

fprintf(stderr,”Não chega aqui“);

} else {

perror(“Erro no Fork“);

exit(2);

}

 

Unix: Processos (A partir do Init) 1

Captura de Tela 2014-09-16 às 22.57.32

 

Unix: Processos (A partir do Init) 2

Captura de Tela 2014-09-16 às 22.57.36

 

Unix: Processos (A partir do Init) 3

Captura de Tela 2014-09-16 às 22.57.41

 

Unix: Processos (A partir do Init) 4

Captura de Tela 2014-09-16 às 22.57.53

 

Tipos de SO

Finalizar Nota Anterior
Apresentar os Tipos de SO
     Quanto ao Uso:
Monotarefa – Monousuário
Multitarefa – Multiusuário
Multitarefa – Multiusuário
     Quanto à Arquitetura:
Monolítico
Microkernel

O que é um Sistema Residente?

Arquitetura de um SO:
Usuários
Camada de Aplicações
Sistema Operacional
Camada de Usuário do SO
Chamadas de Sistema comunicam a de cima e a de baixo
Camada de Núcleo (Kernel do SO)
Camada de Hardware

Sob ponto de vista do usuário: Executa programas requeridos
Sob ponto de vista do Hardware: Requisita recursos (e geralmente é prontamente atendido salvo em alguns casos: Usuário, IRQ, DMA)

Sistemas Operacionais com o Tempo:
     Mainframes
          Programação Direta (Sem SO, software gerenciava o HW)
– Altair 8800
          Monitores de Execução (quase-SO)
– Cartões
          Batch
               Primeiros SO
               Monitor Residente
Inicializa Sistema, controla Hw
Aloca Recursos
Transfere Controle pra um programa (tarefa)
Ao final reassume o controle
Problemas ao se trocar a aplicação

91b82acaaa1cec7a2804b13ae83493f8
          Batch Multiprogramados
Tenta resolver a ociosidade de carregar programas
Carregando varios simultaneamente na memória
Quando um programa para esperando por dados outros podem ser executados
Tudo era manual

1d0b97c99af2cb37be15d318ca39908b

3c3feabc12d136ac9e4104311a73759f

          Tempo Compartilhado
Um computador
Vários Usuários “Simultaneamente”

          Sistemas de Mesa
Surgiu com os computadores pessoais ou estações de trabalho
Dedicados a apenas um usuário
Voltados à conveniência e resposta ao usuário
Podem ou não adotar soluções de sistemas de grande porte

          Sistemas Multiprocessados
Sistemas com multiplas CPU’s próximas
Paralelos ou fortemente acoplados
Processadores compartilham memória e clock
Comunicação entre CPU’s pela memória
Aumento de desempenho
Economia de Escala
Aumento de Confiabilidade
Podem ser:
                     Simétrico
Cada processador executa a mesma tarefa
                     Assimétrico
Cada processador executa tarefas diferentes

          Sistemas Distribuídos
Sistemas fracamente acoplados
Cada processador tem sua memória local
Comunicação se dá por canais de transmissão. Ex: Rede
Distribuem-se a computação entre diversos processadores fisicamente independentes
Podem se organizar como Cliente-Servidor ou Peer-to-Peer (par a par)
Compartilham recursos em uma rede
Aumenta o desempenho por dividir a carga de trabalho
Confiável
Provê comunicação entre usuários e aplicativos

Clusters (Agregados)
          Embutidos

Programa Interface: Shell ou GUI
Permite a Interação Usuário-Máquina
Shell (ou Interpretador de Comandos)
Alfanumérico
Baseado em Texto
Aguarda digitação do comando e enter
Permite digitar mais de um comando em uma única linha
Geralmente permite que a saída de um comando seja a entrada de outro

GUI (Graphical User Interface)
Interface Iconográfica
Baseada em Ícones ou Imagens
(Geralmente) Bidimensional
Permite clicar em um local da tela para efetuar operações
Executar um comando
Executar um programa
Não permite concatenação de operações (como na interface de texto)

Nenhum dos dois fazem parte específica do SO
Ambos se encontram na camada de Aplicação

Níveis de Operação
A maioria dos computadores (e PC’s a partir dos 286) tem 2 níveis de operação
Modo Nucleo (Kernel ou Supervisor)
     Modo Usuário

Modo Núcleo
Nível de Operação do SO em si
Programa nesse nível tem acesso completo a todo hardware e pode executar qualquer instrução que a máquina seja capaz de executar
Sistema Operacional impede que programas utilizem o modo Kernel

Modo Usuário
Disponibiliza apenas um subconjunto de instruções que a máquina é capaz de realizar
Instruções que afetam controle da máquina ou realizam E/S são proibidas
Tais funções são requisitadas ao Sistema Operacional via Chamada de Sistema

Chamada de Sistema
São métodos utilizados pelos programas para solicitar serviços específicos de hardware ao sistema operacional
Cada chamada corresponde a um procedimento definido em uma biblioteca de software disponibilizada pelo e contida no sistema operacional
As chamadas de sistema executam em modo protegido sem a interferência do usuário

     Processo de Execução de uma chamada de sistema:
Serviços são requisitados por se atribuir parâmetros adequados aos seus locais determinados, ex: Em registradores
Executa-se uma instrução especial de trap, uma chamada especial indicando que se deseja utilizar o modo kernel
A máquina é chaveada para o modo kernel, mas o controle vai para o SO, não para o programa
O SO examina os parâmetros para determinar qual das chamadas de sistema executar
Uma tabela é consultada para verificar o endereço do procedimento que executa a chamada ao sistema
Após a conclusão da chamada de sistema o controle retorna ao modo usuário e devolve a execução ao programa.
Exemplo:
          count=read(file,buffer,nbytes);
ptr=(int*)malloc(sizeof(int)*4);

Processo
Conceito fundamental para todos os SO’s
Ambiente onde se executa um programa
Consiste na área de memória alocada ao programa e a seus dados
Basicamente podemos dizer que é um programa em execução
SO indica a existência de um processo através de uma tabela chamada de tabela de processos
Cada entrada da tabela é chamada de bloco de controle do processo (Process Control Block PCB)
Um PCB é responsável por manter todas as informações referentes a um determinado processo
     Informações de um Processo
Ponteiros
Estado do Processo
Prioridade do Processo
Limites de Memória
Registradores Usados (e valores)
Estado dos Arquivos Abertos
Lista de Arquivos Abertos
Contabilidade do Processo no Uso de Recursos
Outras Informações
Estados do Processo
Num sistema multiprogramável (Multiprocessado), um processo passa por uma série de estados durante sua existência.
Esses estados determinam qual o comportamento do processo no sistema e se limitam a 3:
Pronto: Um processo encontra-se pronto para executar, apenas esperando o processador chamá-lo para iniciar
Executando: O processador está destinando seus recursos ao processo e efetivamente processando suas instruções
Bloqueado/Espera: Um processo está nesse estado quando aguarda a ocorrência de determinado evento para continuar sua execução

Um processo pode ser bloqueado por:
Apesar de estar pronto para executar, ainda necessita de alguma entrada ainda não disponível (DMA, scanf,…)
Estava executando, mas precisou realizar alguma operação de E/S, desocupou o processador, realizou a operação e aguarda a retomada.

Um processo muda diversas vezes de estado durante seu ciclo de vida em função de eventos gerados por ele próprio (Eventos Voluntários) ou pelo sistema operacional (Eventos Involuntários)

Basicamente existem quatro mudanças de estado que podem ocorrer a um processo:

8edddd2462cbe21143ca09114b6578af

Por que precisamos de Sistema Operacional?

Por que precisamos de um Sistema Operacional?
Para gerenciar diversos recursos. Vejamos quais são e depois me respondam o por quê.
Arquitetura de um Computador
Hardware: O que é?
equipamento físico usado para
atividades de entrada, processamento, saída
e armazenamento de um sistema de
computador
Hardware: Quais são (os fundamentais)
CPU, Armazenamento Primário, Armazenamento Secundário, Tecnologias de Entrada, Tecnologias de Saída, Tecnologias de Comunicação
CPU: O que é e quais os componentes que a compõe?
Unidade Central de Processamento
Realiza a computação propriamente dita
É um microprocessador (ex: Pentium)
composto de milhões de transistores
embutidos em um circuito sobre um chip
Manipula dados e controla as tarefas realizadas
pelos outros componentes
Formada por: ULA, UC e Registradores
ULA
Unidade Lógica e Aritmética
UC
Unidade de Controle: Processa instrução e mantêm o rastreio da próxima instrução
Instruções: Mover um dado na memória, Enviar dado à ULA, Enviar comando à ULA, Escrever um dado na memória, Ler um dado da memória, enviar um dado a um dispositivo de Saída, Ler um dado de um dispositivo de entrada, comparar dados
Registradores
Unidades temporárias de armazenamento. Pouco espaço, altíssima velocidade

ee4c92efa15bd8ded9f4fcddddb54735
Ciclo de Instrução
período de tempo no qual um computador lê e processa uma instrução em linguagem de máquina da sua memória
Seqüência de ações que a CPU realiza para executar cada instrução em código de máquina num programa
Ocorre milhões de vezes por segundo
Avanços nos projetos de Microprocessadores
Goordon Moore previu em 1965 que a complexidade dos processadores dobraria a cada dois anos
O avanço vem das mudanças
– Miniaturização
-Projetos de Larga Escala
– Materiais mais eficientes
– Multiplos processadores em um unico chip
– Uso da tecnologia (e do conhecimento) para melhorar a tecnologia (e a produção do conhecimento)
Impactos da Lei de Moore
Em 1988 um PC chip Intel 80386 de 16 MHZ, 1 MB de RAM, disco rígido de 40 MB e SO DOS 3.31 custava U$ 5.200 (sem monitor) (Nos EUA!)
Em 2005 um PC chip Intel Pentium 4 de 3.4 GHZ, 2 GB de RAM, disco rígido de 160 GB, SO Windows XP e monitor tela plana de 19 polegadas custava cerca de U$ 2.000 (Nos EUA!)
Memória do Computador
Tipos de Memória
Armazenamento Básico (ou primário)
Armazenamento Secundário
O que pode afetar
Tipos de programas que o computador pode executar
Trabalho que ele pode realizar
Velocidade
Custo da Máquina
Custo do Processamento (Tempo x Energia x Recursos)
Capacidade da Memória
CPU processa apenas 0s e 1s
Os dados são traduzidos por meio de linguagens de computador para dígitos binários -> bits
Combinações específicas de bits pode representar  determinado caractere alfanumérico ou um número
São necessários 8 bits para representar qualquer caractere -> Byte
A capacidade de armazenamento é medida em bytes
Hierarquia da Capacidade em termos quantitativos
Kilobyte – Mil bytes (em informações de disco) -> 1024 bytes (em informações de processamento)
Megabyte – 1 milhão de bytes -> 1024 Kilobytes
Gigabyte – 1 bilhão de bytes -> 1024 Megabytes
Terabyte – 1 trilhão de bytes -> 1024 Gygabytes
Petabyte – 1 Quatrilhão de bytes -> 1024 Terabytes
Exabyte – 1 Quintilhão de bytes -> 1024 Petabytes
Tipos de Informações Armazenadas
Código
Dados
Sistema Operacional
Armazenamento Primário
Armazena temporariamente os dados e as instruções de programas durante o processamento
Dados armazenados (geralmente) estão em Uso
Códigos do SO
Instruções do Programa Corrente
Dados em uso do programa corrente
4 tipos de Armazenamento
Registradores
Parte da CPU
A menor capacidade de armazenamento
Armazenam dados imediatamente antes e imediatamente após o processamento de uma instrução
Temporária e extremamente volátil
Memória de Acesso Aleatório (RAM)
Armazena programas e pequenas quantidades de dados para processamento
Ao iniciar, um programa é trazido do armazenamento secundário para a RAM
Armazena mais informações que os registradores
Está mais distante da CPU que os registradores
Não faz parte da CPU
precisa de um barramento para enviar e receber os dados e um barramento para saber de onde enviar ou para onde receber os dados (Barramento de Dados + Barramento de Endereços)
Mais Lenta
Temporária e volátil
Memória Cache
Tipo de memória de alta velocidade que permite o armazenamento temporário de blocos de dados que são usados frequentemente
Mais Rápida que a Ram
Menos Quantidade de Dados que a Ram
Dados pouco utilizados ficam na RAM
Entre a CPU e a RAM
Memória Somente de Leitura
É o local em que certas instruções críticas são guardadas com segurança
Não é volátil (Permanente)
Instruções podem apenas serem lidas
(Instruções para iniciar o computador: BIOS)
Armazenamento Secundário
Armazena os dados e programas para uso futuro
Projetado para armazenar grandes quantidades de dados por longos períodos
Não é volátil
Demorada (leva muito tempo para se recuperar os dados)
Mais barata que o de armazenamento primário
Tendencias de melhoria de velocidade, aumento de capacidade e redução de custos com o tempo
Tipos:
Meios Magnéticos
Fitas Magnéticas
DAT, K7
Meio mais Barato
Lento (pois é sequencial)
Discos Rígidos
Armazenamento em um disco dividido em trilhas e setores que fornecem acesso a vários fragmentos de dados (Bidimensional)
Acesso mais rápido que a fita
É o mais usado atualmente
Baixo custo, alta velocidade e grande capacidade de armazenamento
Lêem e escrevem em pilhas de discos magnéticos giratórios
Trilhas Concêntricas
Trilhas divididas em setores
bf0ad923347acd2241173bec779b9896
Discos Flexíveis
Semelhante aos discos rígidos
Capacidade limitada
Mais lentos
apenas 1 disco
Dispositivo Óptico
CD/DVD/Blue Ray
Feixe concentrado de luz sendo refletido e incidindo sobre um transceptor (ou não)
Mais lentos que os Discos Rígidos (principalmente para escrita)
Podem ser usados para o armazenamento de grande capacidade de dados
Memórias Flash
Memória de rápido acesso, cujos chips são semelhantes àqueles utilizados em memórias RAM
A principal diferença é que a memória flash conserva seu estado mesmo sem alimentação de energia, permitindo o armazenamento permanente de informações
Limitada em tamanho e mais lento que os HDs
Utilizada em larga escala por
Cartões de máquinas fotográficas digitais
P Pen drives
celulares
etc.
Memórias de Estado Sólido
Melhoria das Memórias Flash
Aumento na Capacidade de Armazenamento
Aumento na rapidez de comunicação
Modelo Empresarial de Armazenamento
É um sistema externo e independente com inteligência que inclui dois ou mais dispositivos de armazenamento
Oferecem:
– Grandes quantidade de armazenamento
Transferências de alto desempenho
Alto grau de disponibilidade
Proteção contra perda (de dados)
Ferramentas de gerenciamento sofisticadas
1956: 450 quilogramas, peso de dois refrigeradores, alugada por U$ 3.200/mês e capacidade de 5 megabytes
2005: microdrive IBM/Hitachi 1 polegada quadrada, custava U$300 e armazenava 6 gigabytes

Hierarquia de Computação
O modo tradicional de comparar classes de computadores é por poder de processamento
Os limites entre essas categorias têm se tornado indistintos
Supercomputadores
Indica os mecanismos de computação mais rápidos disponíveis em qualquer momento específico
Usado para tarefas computacionalmente exigentes e dados extremamente grandes
Uso aplicações militares, científicas e meteorológicas
Mainframes
Visto às vezes como um tipo de servidor
São populares em grandes empresas para aplicações de intenso acesso a dados ou intensa quantidade de requisições de processamentos (transações) acessados por milhares de usuários
Ex de aplicações: reserva de vôo e folha de pagamento corporativo ou aplicações de sistemas financeiros
São menos poderosos e menos dispendiosos que os supercomputadores
Medianos
São um tipo de servidor
Relativamente pequenos, baratos e compactos
Flexibilidade para organizações que não desejam aplicar recursos de TI em mainframes (menos escaláveis)
Ex: comércio eletrônico e provedores de páginas web (Amazon Web Service, Microsoft Azure…)
Estações de Trabalho
Executam aplicações científicas, de engenharia e financeiras computacionalmente intensas
(podem ter) Gráficos de alta resolução e cálculos de alta velocidade
Geralmente são dedicados
Ex: Antigas estações Irix (Silicon Graphics)
Micro Computadores (Computadores Pessoais)
São a categoria menor e mais barata de computadores de aplicação geral
Desktop, Notebook, Laptop
Dispositivos móveis (celulares, PDA’s, Tablets)
Tecnologias de Entrada e Saída
Recebe dados e os converte em um formato que o computador pode entender ou converte dados do computador para que possamos entender
Dispositivos de Entrada
Teclado, Joystick, Mouse, Touchscreen
Kinect, Wiimote (sensores de orientação/deslocamento)
Entrada de Dados pode ser Automatizada
Aumenta a Eficiência e Reduz Erros
Ex: Leitor de Código de Barras ou de RFID
Dispositivos de Saída
Monitores ou impressoras
Atualmente com tecnologia multimídia:
Integração de sons, textos e imagens
Mistura habilidades dos computadores com elementos de entretenimento como TV, Aparelho Estereofônico, Rádio, Jogos, etc.
Tecnologias Emergentes
Computação em Grade
Utilizar diversos computadores para resolver partes de um problema maior
Ex: SETI
Computação Quântica
Utilização dos conhecimentos da física quântica sobre estado dos elétrons para a representação de bits

Ementa: SO

Parte 1 – Histórico e Visão Abrangente de SOs
Introdução;
Organização e Arquitetura de Computadores;
Objetivo de um SO
Tipos de Sistemas Operacionais;
Quanto à Arquitetura
Micro-Kernel
Monolítico
Quanto ao Funcionamento
Por Batches
Em Tempo Real
Mono-Usuário, Mono-Tarefa
Mono-Usuário, Multi-Tarefa
Multiusuário
Arquitetura de Sistemas Operacionais;
Parte 2 – Gerenciamento de Processos
Conceito de Processo;
Controle de Processos;
Troca de Contexto de Processos;
Conceito de Threads;
Comunicação, Concorrência e Sincronismo de Processos;
Deadlocks;
Escalonamento de Tarefas;

Prova 1 

Parte 3 – Gerenciamento de Memória
Endereçamento de Processos;
Gerenciamento de Memória;
Memória Virtual;
Parte 4 – Sistema de Arquivos
Interface do Sistema de Arquivos;
Implementação de Sistemas de Arquivos;
Parte 5 – Entrada e Saída
Sistema de E/S;
Estrutura de Armazenamento em Massa;

Prova 2 –

Avaliação
2 provas de 30 pontos cada
2 Trabalhos de 15 pontos cada
2 Trabalhos integradores de 5 pontos cada

8. BIBLIOGRAFIA
Básica
1. SILBERSCHATZ, A.; GALVIN, P. B. GAGNE, G.; Fundamentos de Sistemas Operacionais, 6a.
ed.; Editora Campus, 2004.

2. TANENBAUM, A. S. and Woodhull, A. S. Sistemas Operacionais – Projeto e Implementação.
Bookman, 2000.

3. STALLINGS, W. Operating Systems – Internals and Design Principles. 3.ed. Englewood Cliffs, NJ : Prentice-Hall, 1998.

Complementar
1. Rômulo Silva de Oliveira, Alexandre da Silva Carissimi, Simão Sirineo Toscani, Sistemas
Operacionais, Editora Bookman, Porto Alegre, 3a Edição, 2008. (reimpressão)
 ISBN: 9788577803378

3. BACH, M. The design of the Unix Operating System. Englewood Cliffs, N.J., Prentice-Hall,
 1990.
4. LEWIS, B.; BERG, D. J. Threads primer: a guide to multithreaded programming. New Jersey,
Prentice-Hall, 1996.

Lista de Exercícios e Trabalhos do 1o. Bimestre

Olá Alunos, apresento a vocês a lista de exercícios para a prova do 1o. bimestre.

Essa lista também será considerada para o trabalho referente ao total de 15 pontos distribuídos de acordo com as normas acadêmicas.

Esse trabalho deve ser realizado individualmente e entregue manuscrito em folha de papel almaço pautada ou não, devidamente identificada sendo que o processo se divide em 3 etapas:

1a. Etapa (5 Pontos): Desenvolvimento de 30 % dos exercícios da lista 1

2a. Etapa (5 Pontos): Desenvolvimento de 30% dos exercícios da lista 2

3a. Etapa (5 Pontos): Desenvolvimento de 40% dos exercícios da lista 3

Ou seja, considere que cada lista possua 10 exercícios, você deverá escolher e desenvolver 3 exercícios da lista 1, 3 da lista 2 e 4 da lista 3 para entregar no dia da prova.

Se uma lista der um número com casas decimais, arredondar para cima. Ex: A lista 2 tem 7 exercícios. 30% de 7 = 2.1 exercícios, portanto, deverá ser resolvido 3 exercícios.

Bons Estudos.

 

Lista 1:

1) Sejam as proposições: p: Gosto de viajar e q: Visitei o Chile. Escreva as sentenças verbais que estão
representadas pelas proposições abaixo:
(a) p → q              (b) ¬ q → ¬ p       (c) (p ^ ¬ q) → ¬ p       (d) q ^ ¬ p
(e) ¬(p ^ q)       (f) q → p              (g) ¬ p v ^ q                   (h) (p v ¬ q) ^ (¬ p → q)

Ex: p^¬q : Gosto de viajar e não visitei o Chile.

 

2) Construa a tabela da verdade para a seguinte proposição: E = (p ∨ (¬p ∨ q)) ∧ ¬(q ∧ ¬r)

 

3) Descreva as sentenças abaixo em termos de proposições simples e operadores lógicos:
Exemplo: Se 1>2 então qualquer coisa é possível.
.        p: 1>2

.         q: qualquer coisa é possível

.         frase: p → q

(a) Se elefantes podem subir em árvores, então 3 é um número irracional.
(b) É proibido fumar cigarro ou charuto.
(c) Não é verdade que ∏>0 se e somente se ∏ >1.

(d) Se as laranjas são amarelas, então os morangos são vermelhos.(e) É falso que se Montreal é a capital do Canadá, então a próxima copa será realizada no Brasil.
(f) Se é falso que Montreal é a capital do Canadá, então a próxima copa será realizada no Brasil.

 

4) Considerando que a proposição “todos os pelicanos comem peixe” seja verdadeira, quais das proposições
abaixo são verdadeiras?
(a) Se uma ave é um pelicano, então ela come peixe.
(b) Se uma ave não é um pelicano, então ela não come peixe.
(c) Se uma ave come peixe, então ela é um pelicano.
(d) Se uma ave não come peixe, então ela não é um pelicano.

 

5) Apresente uma negação para cada uma das proposições abaixo.
(a) 37 é um número primo.
(b) Bruno irá, mas ele não vai jogar.
(c) Nós venceremos o primeiro jogo ou o segundo.
(d) Se não há sanduíches, vou comer um cachorro-quente.
(e) Matemática é muito legal e computação é fundamental.
(f) Nem todas as pessoas têm acesso ao ensino superior.

 

6) Em cada um dos itens a seguir afirmações são dadas e aceitas como verdadeiras. Deduza uma afirmação
delas, se possível.
(a) Se houver uma mosca em sua sopa, você deve tomar devagar cada colherada.
Você pode tomar rápido cada colherada.
(b) Nenhum disco voador voa a uma velocidade maior do que a da luz.
O objeto acima não é um disco voador.
(c) Se Nestor disse a verdade, Júlia e Raul mentiram.
Se Raul mentiu, Lauro falou a verdade.
Se Lauro falou a verdade, há um leão feroz nesta sala.
Não há um leão feroz nesta sala.

 

7) Sejam A,B e C as seguintes proposições:
A Rosas são vermelhas.
B Violetas são azuis.
C Açúcar é doce.
Escreva as proposições a seguir em notação simbólica:

(a) Rosas são vermelhas e violetas são azuis.
(b) Rosas são vermelhas, e ou bem violetas são azuis ou bem açúcar é doce.
(c) Sempre que violetas são azuis, rosas são vermelhas e açúcar é doce.
(d) Rosas são vermelhas apenas se violetas não forem azuis e se açúcar for amargo.
(e) Rosas são vermelhas e, se açúcar for amargo, então ou violetas não são azuis ou açúcar é doce.

 

8)  Considerando A, B e C com o mesmo significado visto acima, transcreva para o
português as seguintes fórmulas:

(a) B ∨¬C
(b) ¬B ∨ (A → C)
(c) (C ∧¬A) → B

(d) C ∧ (¬A ↔ B)
(e) ¬(B ∧¬C) → A

 

9) O número de linhas numa tabela-verdade de uma fórmula depende do número de proposições simples (A, B, C, …) que entram nesta fórmula. Responda:
(a) A tabela-verdade de uma fórmula com 10 proposições simples têm quantas linhas?

(b) A tabela-verdade de uma fórmula com 20 proposições simples têm quantas linhas?

 

10) Construa um argumento verbal apropriado para o seguinte argumento formal:
(A → (B → C)) ∧ (A ∨ ~D) ∧ B → (D → C)
Defina claramente que proposições verbais são simbolizadas por A, B, C e D.

 

 

Lista 2:

 

1) Seja H a fórmula a seguir e I uma interporetação:

H=((P→Q)→(((P^Q)←→P)^((PvQ)←→Q)))→P

a) Se I[P]=F, o que se pode concluir a respeito de I[H]?

b) Se I[P]=T, o que se pode concluir a respeito de I[H]?

 

2) Seja H uma fórmula da lógica proposicional, justifique a afirmação a seguir: Cada linha da tabela vrdade associada a H corresponde a uma interpretação diferente para H.

 

3) Seja I uma interpretação tal que I[P→Q]=T. O que se pode deduzir a respeito dos resultados das interpretações a seguir?

a) I[(PvR)→(QvR)]

b) I[(P^R)→(Q^R)]

c) I[(¬PvQ)→(PvQ)]

 

4) Repita o exercício 3 assumindo que I[P→Q]=F

 

5)　Considere as seguintes interpretações I[P]=T, I[Q]=T, I[R]=F e I[S]=F, determine o valor lógico das proposições abaixo

a) ((¬R^¬S)v(P→Q))←→(Rv¬Q)

b) ((P^Q)v(P^¬Q)v(¬P^Q)v(¬(P^¬Q)))→(RvS)

 

Lista 3:

1) Verifique a validade das equivalências abaixo:

a) (PvQ)→R <=> (P→R)^(Q→R)

b) (P→(Q→R)) <=> ((P^Q)→R)

 

2) Quais das proposições abaixo são tautologias (verdadeiras), quais são contradições (logicamente falsas) e quais não se encaixam em nenhuma das duas categorias?

(a) (p^q)v(¬p^¬q)

(b) ¬(p^¬p)

(c) p→(q→p)

(d) (pvq) →((p^q) v(p^¬q) v(¬p^q))

 

3) Mostre se as expressões E1 e E2 são equivalentes logicamente:
E1 = (s → (p ∧ ¬r)) ∧ ((p → (r ∨ q)) ∧ s)
E2 = (p ∧ q ∧ ¬r ∧ s) ∨ ¬(p ∨ s)

4) O famoso detetive Percule Hoirot foi chamado para resolver um assassinato misterioso. Ele determinou os
seguintes fatos:
(a) Lord Charles, o homem assassinado, foi morto com uma pancada na cabeça com um castiçal.
(b) Ou Lady Camila ou a empregada Sara estavam na sala de jantar no momento do assassinato.
(c) Se o cozinheiro estava na cozinha no momento do assassinato, então o açougueiro matou Lord Charles
com uma dose fatal de arsênico.
(d) Se Lady Camila estava na sala de jantar no momento do assassinato, então o motorista matou Lord
Charles.
(e) Se o cozinheiro não estava na cozinha no momento do assassinato, então Sara não estava na sala de
jantar quando o assassinato ocorreu.
(f) Se Sara estava na sala de jantar no momento do assassinato, então o ajudante pessoal de Lord Charles
o matou.
Pergunta: É possível para o detetive Percule Hoirot deduzir quem matou Lorde Charles? Se sim, quem é o assassino?

 

5) Demonstre, sem utilizar a tabela verdade, que as fórmulas a seguir são tautologias:
a) ((H → G) ∧ (G → H)) → (H → H)
b) (H ∧ (G ∨ E)) ↔ ((H ∧ G) ∨ (H ∧ E))
c) ¬(H → G) ↔ (H ∧ (¬G))
d) ((¬R ∨ Q) ∧ (¬Q ∨ P)) → (R → P)

 

 

Propriedades Semânticas Fundamentais da Lógica Proposicional

Propriedades Semânticas Fundamentais da Lógica Proposicional

Tautologia  Para toda interpretação I de uma formula G, I[G]=T

Factivel ou Satisfatível se Existe pelo menos uma interpretação I da fórmula G tal que I[G]=T

Contraditória se para toda interpretação I[G]=F

Dadas duas fórmulas H e G, H implica G se e somente se para toda interpretação I, se I[H]=T, então I[G]=T

Dadas duas fórmulas H e G, H equivale a G se e somente se para toda interpretação I, I[H]=I[G]

Dada uma fórmula H e uma interpretação I, então I satisfaz H se I[H]=T

Um conjunto de fórmulas ß={H1,H2,…,Hn} é satisfatível se e somente se existe uma interpretação I, tal que I[H1]=I[H2]=…=I[Hn]
Neste caso I satisfaz o conjunto de fórmulas, indicado por I[ß]=T. Dado um conjunto e fórmulas vazio, toda interpretação satisfaz esse conjunto

Semântica da Lógica Proposicional

Atribuição de Significado a um Símbolo (ou objeto) Sintático

A (P ^ Q), o significado está intrinsicamente ligado à interpretação atribuída aos símbolos P e Q.

Assim, I[(P^Q)] = I[P] ^ I[Q]

Nesse caso, a Interpretação nos trará os valores (lógicos) referentes à sentença e ao contexto.

Esses valores podem assumir duas propriedades, já vistas nas aulas anteriores: Verdadeiro (T) ou Falso (F)

É possível representar fatos como:

“Meu Tio Mora em São Paulo”

Mas não como:

“Essa Sentença é Falsa” (paradoxo de Epimênides)

Esse último, devido à auto-referência, é representado por outra competência da lógica, mas não pela preposicional.

Na língua portuguesa podemos ter mais de um significado (ou interpretação) para uma sentença
Na lógica proposicional há apenas um significado (ou interpretação) e ela se resume a um valor de Verdadeiro ou a um valor de Falso

A interpretação dos símbolos da lógica é definida a seguir:

Função Binária: Uma função é dita binária se seu contradomínio possuir apenas dois elementos
Interpretação: Uma interpretação I na lógica preposicional é uma função binária tal que:
O domínio de I é constituido pelo conjunto das fórmulas da lógica proposicional
O contradomínio de I é o conjunto formado pelos valores verdade {T,F}
Os valores dos símbolos de verdade (true, false) recuperados através da interpretação I[true]=T e I[false]=F
Dado um símbolo proposicional P, então I[P] pertence a {T,F}
Interpretação de Fórmulas

Fórmulas: Símbolos do alfabeto concatenados utilizando-se uma regra específica
Interpretação das Fórmulas é obtida através da interpretação desses símbolos
Procedimentos para se interpretar fórmulas:
Definição de Interpretação de fórmulas:
Dada uma fórmula E e uma interpretação I, o significado de E, indicado por I[E] é obtido através das seguintes regras:
se E=P, onde P é um símbolo proposicional, então I[E]=I[P] e I[P] pertence a {T,F}
se E=true, então I[E]=I[true]=T. Se E=false, então I[E]=I[false]=F
seja H uma fórmula. Se E=(¬H), então
I[E]=I[(¬H)]=T se I[H]=F
I[E]=I[(¬H)]=F se I[H]=T
Sejam H e G duas fórmulas. Se E=(HvG), então
I[E]=I[(HvG)] = F se I[H]=F e I[G]=F
I[E]=I[(HvG)] = T se I[H]=T e/ou I[G]=T
Sejam H e G duas fórmulas. Se E=(H^G), então
I[E]=I[(H^G)] = T se I[H]=T e I[G]=T
I[E]=I[(H^G)] = F se I[H]=F e/ou I[G]=F
Sejam H e G duas fórmulas. Se E=(H→G), então
I[E]=I[(H→G)]=T se I[H]=F e/ou I[G]=T
I[E]=I[(H→G)]=F se I[H]=T e I[G]=F
Sejam H e G duas fórmulas. Se E=(H←→G), então
I[E]=I[(H←→G)]=T se I[H]=I[G]
I[E]=I[(H←→G)]=T se I[H]<>I[G]
As regras semânticas determinam o significado de (H^G) a partir de I[H] e I[G], não a partir de I[^], que seria o significado do conectivo ^
Na lógica proposicional não existe o significado dos conectivos isoladamente
Para simplificar o significado de (H^G) é denotado o significado de ^.
As regras semânticas também são apresentadas em tabelas, denominadas tabela verdade
Considere H e G fórmulas da lógica proposicional, a tabela a seguir apresenta o significado das formulas obtidas através do processo de construção e dos conectivos utilizando essas duas fórmulas

(apresentar a tabela verdade separada dos símbolos considerando o significado da interpretação das fórmulas)

H G ¬H ¬G (HvG) (H^G) (H→G) (H←→G)
F F T T F F T T
F T T F T F T F
T F F T T F F F
T T F F T T T T

Exemplo: Tabela verdade da fórmula:

(((¬P)vQ)→(PvQ))

Explicar a causalidade e a semântica do conectivo →, indicando que não há necessariamente a causalidade do elemento antecedente ao consequente.
Ex:
(H)=O sol é redondo
(G)=A mídia é imparcial

Interpretações podem ser limitadas:

Considere:

E=(((¬P)^Q) → (RvP))

I[P]=T ,I[Q]=F , I[R]=T
J[P]=F ,J[Q]=T , J[R]=F

Assim, I interpreta E (I[E]) diferentemente de J (J[E])

*** Demonstrar utilizando tabela ***

(Exercícios Capitulo 2)

Sintaxe da Lógica Proposicional

+ Alfabeto
– Símbolos Proposicionais
P, Q, R, P1, Q1, R1, P2, Q2, R2, …
– Símbolos de Pontuação
(  )
– Símbolos de Verdade
True, False
Verdadeiro, Falso
– Conectivos Lógicos
v  ou Disjunção (também encontrada com o símbolo + )
^ ou Conjunção (também encontrada com o símbolo . )
¬ ou negação (não)
→ também conhecido como implicação ou se-então
←→  também conhecido como “iff”, “se e somente se” ou bi-implicação

+ Fórmulas

– Conjunto de símbolos do alfabeto da lógica proposicional concatenados seguindo um conjunto específico de regras:
– Todo Símbolo de Verdade é uma Fórmula
– Todo Símbolo proposicional é uma fórmula
– Se H é uma fórmula, (¬H) (a negação de H) é uma fórmula
– Se H e G são fórmulas, então (HvG) (a disjunção de H e G) é uma fórmula
– Se H e G são fórmulas, então (H^G) (a conjunção de H e G) é uma fórmula
– Se H e G são fórmulas, então (H→G) é uma fórmula e é dito que H é o antecedente e G é o consequente da fórmula
– Se H e G são fórmulas, então (H←→G) é uma fórmula e é dito que H é o lado (ou componente) esquerdo e G é o lado (ou componente) direito da fórmula

Cada item acima define uma regra para a construção de fórmulas.
Observe a obrigatoriedade do uso dos símbolos de pontuação ( e )

Exemplos de Fórmulas

P
Q
True

(PvQ)
((PvQ)→True)

Símbolos de pontuação
– São utilizados para eliminar ambiguidades nas fórmulas
– Quando não há possibilidade de ambiguidade tais símbolos podem ser omitidos
– Ambiguidade surge devido à precedência dos operadores (conectivos lógicos) na álgebra de boole
Ordem de precedência (maior para menor):
¬
→, ←→
v,^

Exemplo de Ambiguidade:

P→Q←→R

Pode ser interpretada como

(P→(Q←→R)) ou ((P→Q)←→R)

Pode-se utilizar várias linhas para eliminar ambiguidade:

P→Q
←→
R

Não se considera o significado dos símbolos. A manipulação é puramente simbólica e avalia-se o  relacionamento entre eles

+ Comprimento de uma Fórmula

Comp(H) define-se como:

– Se H é um símbolo de verdade ou um símbolo preposicional, então Comp[H]=1
– Se H é um símbolo de verdade, então Comp[¬H] = Comp[H]+1
– Se H e G são fórmulas, então Comp[HvG]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H^G]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H→G]=Comp[H]+Comp[G]+1
– Se H e G são fórmulas, então Comp[H←→G]=Comp[H]+Comp[G]+1

Ementa: Lógica

Lógica Proposicional: Sintaxe e Semântica. Álgebra de Boole. Portas Lógicas. Circuitos Lógicos.

BIBLIOGRAFIA BÁSICA
NUNES DE SOUZA, J. Lógica para Ciência da Computação. 1ª ed. São Paulo: Elsevier, 2002.
GERSTING, J. L. Fundamentos matemáticos para a ciência da computação. 5ª ed. Rio de Janeiro: LTC, 2004.
MENEZES, P.B.; Matemática discreta para Computação e Informática. Porto Alegre, Sagra-Luzzatto. Instituto de Informática da UFRGS, Série Livros Didáticos, número 16, 2004.
BIBLIOGRAFIA COMPLEMENTAR
Daghlian, Jacob. Lógica e álgebra de Boole. São Paulo: Atlas, 1995.
SKVARCIUS, Romualdes; ROBINSON, William B.. Discrete Mathematics with Computer Science Applications. Redwood City: Benjamin/Cummings, 1986.
EVARISTO, Jaime. Introdução à álgebra com aplicações à ciência da computação.EdUFAL, 1999.
SCHEINERMAN, E.R.. Matemática discreta: uma introdução. São Paulo. Thomson Learning
Ltda. 2003.
SCHEINERMAN, Edward R.: Matemática Discreta Uma Introdução. Thomson Pioneira, 2003.
BEZERRA, L.H; BARROS, P.H.V.; TOMEI. C.; WILMER, C.; Introdução à Matemática. Florianópolis. Editora da UFSC, 1995.