Tag: SO1

SO1 – modelo de programação unix, processos, sinais, redireccionamento

[so1t]

modelo de programação unix, processos, sinais, redireccionamento

Fundamentos de sistemas operativos, 3º edição, capítulos 6 e 11
Begining Linux programming, capítulos 10, 11 e 12

um programa:
é um conjunto de instruções, que descrevem como o computador deve proceder para cumprir um determinado algoritmo
um programa pode ser executado em diferentes processos e em simultâneo

um processo (figSO1_10):


é um ambiente de trabalho com recursos para que um programa seja executado
um processo pode faz parte sempre de um programa, mas pode mudar para outro programa

um processo tem como recursos:
atributos
espaço de memória organizada, tem o heap (variáveis e blocos de memoria dinâmica), tem a pilha (variáveis locais e os endereços de retorno das funções)
tem uma identificação (PID)
recursos, como uma tabela de ficheiros abertos

um processo é criado:
através de um um fork, e o fork só é possivel de ser executado porque já existe um processo
após o fork, o novo processo fica com uma cópia do processo anterior

um novo programa é executado:
com o mecanismo exec (execl, execlp, execle, execv, execvp, execve)
com o exec, o novo processo executa o novo programa, perdendo-se o anterior
se existir a necessidade de não perder o anterior, o novo processo tem que executar nele o programa pretendido (fork+exec)

o fork:
devolve -1, se existir erro
0, estou no contexto do filho
outro valor, estou no contexto do pai

comandos importantes
getpid, obtém o id do processo
getppid, obtém o id do processo pai

como proceder à sincronização simples de processos:
comando wait, espera que o processo filho termine
comando waitpid, espera que o processo filho especifico termine

o waitpid:
-1, pelo primeiro filho que terminar
>0, espera pelo determinado pid que foi o indicado

#sinais
os sinais são um mecanismo de notificação, mecanismo de comunicação assíncrono
os sinais desbloqueiam e execução do processos que os recebem (scanf, pause, sleep,..)

exemplo do tratamento de sinais:

#include <stdio.h>;
#include <stdlib.h>;
#include <signal.h>;

int a =0;
void trata_sinal(int s){
a++;
printf("ouch %d ", a);
if(a==5){
printf("ate logo..");
exit(0);
}
}

int main(){
setbuf(stdout, NULL);
signal(SIGINT, trata_sinal);
while(1){
pause();
}
retrun 0;
}

exemplo de interrupção com um sinal:

#include <stdio.h>; 
#include <stdlib.h>; 
#include <signal.h>;

int recebeuSinal;

void atendeSinal(int snum){
printf("\nSinal recebido..");
printf("\nProcessar acontecimento, ler named pipes, etc \n");
recebeuSinal=1;
}

int main(){
char buffer[50];
int res;
printf("\n\nPID=%d\n, getpid());
recebeuSinal=0;
signal(SIGUSR1, atendeSinal);

while(1){
printf("Favor de escrever algo (\"Fim\2 para sair)\n---> ");
res=scanf("%s", buffer);
printf("scanf leu isto: %s\n", buffer);
printf("resultado dos scanf = %d\n", res);

if(recebeuSinal==1){
recebeuSinal=0;
printf("Parece que entretanto foi atendido ");
printf("um sinal qualquer \n");
printf("Lamentamos a eventual cofusao na ");
printf("interface com o utilizador\n");
}
if(strcmp(buffer,"fim")==0){
break;
}
}
printf("ok\n\n");
return 0;
}

Existe outro mecanismo, uma segunda versão, dentro dos sinais que acrescentam funcionalidades adicionais:
sigaction, define o comportamento dos sinais
sigqueue, envia sinais

o sigaction:
int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact);
signum, sinal a ser tratato
struct sigaction *act, ponteiro para a estrutura que descrever o que fazer com o sinal
struct sigaction *oldact, ponteiro para a estrutura preenchida com a descrição de como era feito o tratamento do sinal

o sigqueue:
int sigqueue(pid_t pid, int sig, const union sigval value);
pid, é o pid do processo alvo
sig, sinal a enviar
value, valor a passar ao processo alvo juntamente com o sinal

funções relacionadas com mecanismos de sinais:
int pause, aguarda que o processo receba um sinal
in alarm( int seconds), faz uso do sinal SIGALRM, passados x segundos
int sleep( int seconds), faz com que um processo adormeça até que chegue um sinal, ou que passe o numero de segundos

#redireccionamento
o redireccionamento está relacionado com ficheiros unix, funções de entrada e sa+ida, tratamento de input/output e pipes anónimos.

a tabela de ficheiro aberta, tem na sua ordem:
posicao 0, operações de read, stdin
posicao 1, operações de write, stdou
posicao 2, operações de stderr

exemplo, na sheel, de redireccionamento de stdin:

close(0); //libertar o stdin
open("ficheiro.txt", O_RDONLY); //abre o ficheiro, que fica na posição zero
execlp("sort","sort", NULL); //executa o programa

exemplo, na sheel, de redireccionamento de stdout:

close(1); //libertar o stdout
open("ficheiro.txt", O_WDONLY); //abre o ficheiro, que fica na posição um
execlp("ls","ls", NULL); //executa o programa

exemplo, de redireccionamento entre programas usando pipes anónimos:

antes de criar os filhos
int mat[2]; // mat[0], descritor do lado da leitura, mat[1] descritor do lado da escrita
pipe(mat);// criar o pipe

fork... // os filhos vão herdar a tabela de descritores
//no filho que escreve:
close(1); //liberta o stdout
dup(mat[1]); // duplica a extremidade do pipe para escrita, para 1
close(mat[1]); // fecha extremidade de escrita, porque foi duplicada
close(mat[0)); // fecha extremidade de leitura do pipe que nao vai ser usada
execlp("ls","ls",NULL);

//no filho que lê:
close(0); //liberta o stdin
dup(mat[0]); // duplica a extremidade do pipe para leitura, para 0
close(mat[0]); // fecha extremidade de leitura, porque foi duplicada
close(mat[1)); // fecha extremidade de escrita do pipe que nao vai ser usada
execlp("sort","sort",NULL);

questões:
o que acontece ao atendimento de sinais quando é feito fork()?
o que acontece ao atendimento de sinais quando é feito exec()?


Capítulo: 6 (comunicação entre processos) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

os mecanismos de comunicação permitem generalizar as interacções entre processo associando a sincronização e a transferência de informação.
o modelo de comunicação dos processos, produtor e consumidor, implica que ambos devem conhecer a estrutura de mensagens e o protocolo que utilizam na comunicação. a transferência de informação é suportada por um canal.
um processo pode possuir vários canais atribuindo-lhes significados específicos de forma a construírem canais de comunicação especializado, e um canal pode ser partilhado por diversos processos
quando um canal é criado fica a pertencer a um determinado processo com poderes para determinar quais os processo que se lhe poderão associar e para eliminar o canal
a primitiva de envio de menagem pode ter diversas semânticas:
assíncrona – o cliente envia o pedido e continua em execução
síncrona – o cliente fica bloqueado até o processo servidor leia a mensagem
cliente/servidor – o cliente fica bloqueado até que o servidor envie uma mensagem de resposta

Relações entre processo produtor e processo consumidor
comunicação mestre/escravo
a comunicação mestre/escravo tem a seguinte estrutura:
a actividade do escravo é totalmente controlada pelo mestre
o mestre não tem de pedir permissão para utilizar o escravo mas não lhe pode atribuir nova tarefa antes que este tenha terminado a anterior. a sincronização é portanto estrita entre as operações de envio e recepção de informação
o canal que define a associação entre o mestre e o escravo é fixo

Relações entre processo produtor e processo consumidor – mecanismo de correio
trata-se da transferência assíncrona de informação sob a forma de mensagens em que:
o emissor não tem de pedir permissão para enviar mensagens. pode contudo ficar bloqueado se a capacidade de memorização do canal tiver sido excedida
o emissor não tem qualquer controlo sobre o ou os receptores
o canal deve memorizar as mensagens durante o intervalo de tempo que decorre entre a sua produção e o seu consumo

Relações entre processo produtor e processo consumidor – mecanismo de diálogo
é estabelecido um canal de comunicação permanente entre dois processos, mas este é criado de forma dinâmica a associação durará o tempo da interacção, e ao terminar a ligação entre os dois processos é eliminada.
o diálogo é então:
existe um canal de comunicação fixo entre os processos, mas a sua criação é dinâmica
um dos processo deve requisitar o estabelecimento da ligação
a associação entre cliente e servidor é temporária
dialogo

Relações entre processo produtor e processo consumidor – mecanismo de difusão
na difusão pretende-se enviar a mesma informação a um conjunto de processos.

Comunicação do modelo computacional
Comunicação do modelo computacional – memória partilhada
a zona de memória faz parte simultaneamente do espaço de endereçamento de dois ou mais processos que lhe acedem como às suas variáveis internas. a memória partilhada permite a difusão de informação e quando complementada com os mecanismos de sincronização adequados a implementação de um modelo mestre/escravo.

Comunicação do modelo computacional – caixas de correio

Comunicação do modelo computacional – ligações virtuais

Capítulo: 11 (modelo computacional do unix) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

Processos
os processos são os elementos activos, existindo mecanismos para sincronização e comunicação. um processo executa uma imagem, em que imagem designa o ambiente de execução do processo. este ambiente é constituído por um conjunto de três unidades:
texto (código do programa)
dados (do utilizador)
pilha do utilizador (user stack)

um processo é identificado no sistema por um valor inteiro atribuído na criação do processo designado por process identifier – pid
a protecção no acesso a recurso é feito de acordo com as categorias:
dono (utilizador normalmente criou o recurso)
grupo (conjunto de utilizadores com afinidades de trabalho que justificam direitos semelhantes
restantes utilizadores

um processo tem associados dois identificadores que definem o seu numero de utilizador user identification (UID) e o seu número de grupo group identificanon (GID)

os processos são criados explicitamente através da primitiva fork. fork cria um novo processo absolutamente idêntico ao processo pai. o processo filho herda todo o contexto (nucleo e utilizador) do processo pai e continua a executar o mesmo código na instrução seguinte ao fork

IDProcesso = fork()
para o processo pai a primitiva fork retorna o identificador do novo processo enquanto o valor retornado para o processo filho é sempre zero. a primitiva retorna -1 se o fork não for possivel/erro

#include <stdio.h>
#include <unistd.h>
int main()
{
  int pid;
  pid = fork();
  if(pid == 0){
      printf("\nprocesso filho %d", getpid());
  }else{
    printf("\nprocesso pai %d", getpid());
  }
      printf("\no resto do ... %d", getpid());
  return 0;
}
saida:
processo filho 123
no resto do ... 123
processo pai 321
no resto do ... 123

a primitiva exec permite substituir o programa por outro, lido a partir de um ficheiro especificado como argumento da chamada.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int main()
{
  int pid;
  pid = fork();
  if(pid == 0){
      printf("\nprocesso filho %d", getpid());
      execl("./testeE2","./testeE2", NULL);
      //execl, primeiro é o executavel e a seguir são os argumentos
      exit(1);
  }else{
    printf("\nprocesso pai %d", getpid());
  }
      printf("\no resto do ... %d", getpid());
  return 0;
}

 

#include <stdio.h>
#include <unistd.h>
void main()
{
  printf("\nsou o testeE2 ... %d", getpid());
}

 

saida:
processo pai 321
no resto do ... 321
sou o testeE2 ... 111

a primitiva exec modifica o segmento de dados e de texto do processo, contudo o contexto núcleo mantém-se inalterado. o novo processo tem o mesmo código de protecção (UID, GID) e ficheiros abertos que o processo possuía antes da execução de exec

Processos – terminar com processo
a função de sistema exit permite a um processo terminar normalmente a sua execução
o processo pai pode bloquear-se à espera da terminação do processo filho, através da primitiva wait

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
int main()
{
  int pid, estado, numero;
  pid = fork();
  if(pid == 0){
      printf("\nprocesso filho %d", getpid());
      exit(0);
  }else{
    printf("\nprocesso pai %d", getpid());
    pid = wait (&estado);
    //wait, fica bloqueado o pai à espera do filho
  }
    printf("\no resto do ... %d", getpid());
  return 0;
}
saida:
processo filho 123
processo pai 321
no resto do ... 321

Processos – acontecimentos assíncronos – signals
acontecimentos assíncronos e excepções podem ser assinalados a um processo em execução através da activação de um signal

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main()
{
  int pid, pid_term, estado;
  pid = fork();
  if(pid == 0){
      printf("\nprocesso filho %d", getpid());
      execl("./testeE2","./testeE2", NULL);
      printf("\n filho: erro no exec");
      exit(-1);
  }else{
    printf("\n processo pai %d", getpid());
    pid_term = wait (&estado);
    printf("\n pai terminou o processo %d com o estado %i", pid_term, estado);
  }
    printf("\no resto do ... %d", getpid());
  return 0;
}
sou o testeE2 ... 1111
processo pai 123
pai terminou o processo 1111 com o estado 5888
o resto do ... 123

alguns signals estão relacionada com interrupções provocadas pelo hardware.
existem também as excepções, como a divisão por zero ou número errado de argumentos numa chamada ao sistema
existem signals que estão relacionados com a interacção com os terminais tecla del, break ou detecção de linha não operacional.

Processos – acontecimentos assíncronos – tratamento de signals
para associar uma rotina ao signal enviado pela interrupção do terminal

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <signal.h>

void ApanhaCTRLC(){
    char ch;
    printf("\n quer termina a execucao? s/n");
    ch = getchar();
    if(ch == 's'){
        exit(1);
    }else{
        printf("\nvamos continuar");
        signal(SIGINT,ApanhaCTRLC);
    }
}

int main()
{
  signal(SIGINT, ApanhaCTRLC);
  printf("associou-se um tratamento de SIGINT");
  for(;;){
      sleep(10);
  }
  return 0;
}
saida:
d 
d
d
CTRL+C
s
saiu

Um sinal pode também ser ignorado usando o SIG_IGN
Quando se executa um fork, o tratamento dos signals é herdado pelo processo filho. este tem a liberdade de modificar o seu tratamento. a primitiva exec mantém o estado dos signals ignorados mas obviamente perde as rotinas de tratamento

Processos – acontecimentos assíncronos – envio explicito de signals
os signals podem ser enviados a outros processos através da primitiva kill, e que termina com o processo destinatário se o signal estiver a ser tratado
kill(pid, sig)
quando um processo bloqueado num semáforo, num mecanismo de comunicação ou leitura de um ficheiro recebe um signal, é automaticamente desbloqueado
o signal SIGKILL não pode ser ignorado ou tratado pelo processo destinatário e conduz sempre à respectiva terminação.
se o PID especificado na rotina kill for 0, o signal é enviado a todos os processos que pertencem ao mesmo grupo
um processo pode bloquear-se à espera de um sginal através da função pause
e pode requerer que lhe seja enviado um sinal do tipo SIGALARM
alarm(segundos)
para adormecer um processo durante um determinado intervalo de tempo que utiliza as primitivas alarm e pause
sleep(segundos)

Sistema de ficheiros – ficheiros especiais
é possivel fazer a redirecção das operações sobre ficheiros para as E/S. apesar de nem todas as operações sobre ficheiros fazerem sentido, as mais importantes (opne, read, write, close) funcionam transparentemente sobre os gestores de periféricos

Comunicação entre processos – pipes
os pipes foram o mecanismo inicial para intercomunicação entre processos. um pipe pode ser visualizado como um canal ligando dois processos e permitindo um fluxo de informação unidireccional. funcionamento é idêntico à de uma caixa de correio em que as mensagens são sequenciais de qualquer dimensão
um processo é bloqueado quando escreve um pipe já cheio a primitiva de leitura, lê sempre o que já existe no pipe mesmo que o seu número seja inferior aos especificado na chamada a read. no caso em que o pipe está vazio o processo leitor é bloqueado.

um pipe pode ser utilizado como um ficheiro ou em substituição do periférico de entrada ou saída do programa.
(ver código abaixo)
é feita a redirecção da entrada para um processo filho. o processo cria um pipe antes de criar o processo filho, para o qual é passado todos os descritores. o processo filho fecha o seu descritor de entrada (deixando a entrada 0 na tabela livre) e duplica o descritor de leitura do pipe que irá ocupar a primeira posição na tabela de descritores (a posição 0 deixada livre pelo close executado anteriormente) o programa a executar-se no processo filho efectuara leituras sobre stdin, estas serão efectuadas transparentemente sobre o pipe que ocupou o seu lugar

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

#define TAMMSG 1000

char mens[] = "mensagem de teste";
char buf[TAMMSG];

int main()
{
    int fd[2];

    if (pipe(fd) < 0)
    {
        printf("erro pipe\n");
    };
    if (fork() == 0)
    {
        //processo do filho
        //fecha stdin libertanto a posição zero da tabela
        close(0);
        //redireciona o stdin para o pipe de leitura
        dup(fd[0]);
        //fecha os descritores nao utilizados pelo filho
        close(fd[0]);
        close(fd[1]);

        read(0, buf, sizeof(mens));
        printf("filho %s\n", mens);
        exit(1);
    }
    else
    {
        write(fd[1], mens, sizeof("mens"));
        wait(0);
    }

    return 0;
}

saida:
filho: mensagem de teste

Comunicação entre processos - pipes com nome
utiliza-se o serviço de nomes do sistema de ficheiros para manter o identificador do pipe
o pipe com nome (named pipes) comporta-se como um ficheiro, existindo para o referenciar uma entrada na directoria do sistema de ficheiros
a maior limitação do uso de pipes advém da limitação baseada no sistema de ficheiros que não só restringe a funcionalidade (unidirecionalidade, interface byte stream) como limita o desempenho.

Comunicação entre processos - espera alternativa
a função selecte indica ao sistema que o processo pretende ficar bloqueado até que uma operação ou várias operações se tenham realizado.
este mecanismo é extremamente poderoso, pois possibilita tratar as operações de entrada/saída de forma assíncrona evitando manipulações complexas dos signals

Tags : , ,

SO1 – gestão de memória, endereçamento virtual, memória virtual

#gestão de memória, endereçamento virtual, memória virtual

bibliografia especifica:
fundamentos de sistemas operativos, 4º edição, capítulos 4 e 5
operating systems concepts, capítulos 8 e 9
operating systems – internals and design principles, capitulo 7 e 8

#gestão de memória
os mecanismos de gestão de memória:
determinam a organização da memória do computador
identificam o modo de endereçamento: real ou virtual
qual o tamanho dos blocos (de páginas ou segmentos)
e quais os mecanismos de protecção e validação de endereços
e é da responsabilidade do sistema operativo configurar de forma eficiente esses mecanismos proporcionados pelo hardware

os algoritmos de gestão de memória:
são técnicas para fazer a gestão da memória principal e secundária
e é da responsabilidade do sistema operativo usar de forma eficiente esses mecanismos proporcionados pelo hardware

o sistema de endereçamento real:
os endereços correspondem a posições na memória física
um programa é preparador para correr numa determinada gama de endereços
e todos os programas vão querer usar essa gama (sistemas multi-programados)
para o sistema operativo surge uma fragmentação da memória
para o sistema operativo surge limites ao tamanho dos programas
para o sistema operativo surge dificuldades no isolamento e segurança

o sistema de endereçamento virtual:
surgem os endereços virtuais: que podem não corresponder a um espaço de memória física
o processador traduz esses endereços virtuais como se fosse endereços físicos para os programas (tradução transparente)
os endereços de cada processo são subdivididos em conjuntos de blocos
os endereços virtuais do mesmo bloco têm as mesmas regras de tradução para os endereços reais
os blocos mapeados na memória física podem estar em zonas diferentes, sem a necessidade de manter a mesma ordem
é o sistema operativo que gere as transferências e de forma transparente, entre a zona virtual e física
é o sistema operativo que liberta a memoria física
é o sistema operativo que indica ao processador de que forma é feita a tradução de endereços virtuais para reais

surgem as tabelas de segmentos:
são criadas pelos sistema operativo
servem para traduzir os endereços virtuais para reais, e é feito pelo processador através das tabelas de segmentos

surgem os descritores de segmentos:
são as entradas numa tabela
indicam o tamanho e localização da memória física
indicam o tipo de acesso que é permitido (leitura, escrita, execução)
indicam o estado de presença em memória física (bit “P”)

assim o descritor de segmento (figSO1_07):

P, Prot, Base, Lim
em que:
p, indica se o segmento se encontra na memória principal
Prot, indica o tipo de protecção e privilégios (RWX)
Base, indica o endereço real do segmento de memoria
BTS, endereço base da tabela de segmentos
LTS, tamanho da tabela

vantagens da memoria segmentada:
adequa-se à lógica da divisão dos programas
permite trabalhar de forma eficiente sobre uma zona de memória inteira

desvantagens da memoria segmentada:
pode não ser criado um espaço de endereçamento linear e continuo de forma transparente para o processo
são usados algoritmos de gestão complexos
o mapeamento de segmentos pode gerar fragmentação
falta de eficiência se os blocos transferidos entre a memória principal e secundárias forem grandes.

os endereços de memória virtual:
têm um conjunto de bits que indicam qual o descritor de segmento dentro da tabela
e um conjunto de bits que indica qual o deslocamento dentro desse segmento

vantagens da memoria virtual:
facilidade de implementação de sistemas multi-programados
implementação automática de segurança e isolamento
a partilha de zonas de memória entre processos distintos é simples

a memória paginada:
os blocos têm todos o mesmo tamanho
funciona como a tabela segmentada
ao invés de se usarem tabelas de segmentos surgem as tabelas de páginas
cada entrada na tabela de páginas é um PTE (page table entry)
se o endereçamento for muito grande é ineficaz o uso de memoria paginada, surge como solução o uso de tabelas de páginas (em cascata)

assim o descritor o PTE (figSO1_08):

P, indica se a pagina se encontra em memoria principal
Prot, indica o tipo de protecção (RWX)
R, indica se a pagina foi referida
M, indica se a pagina foi modificada
Base, é o endereço real da pagina em memória
BTP, endereço base da tabela de segmentos
LTP, tamanho da tabela

vantagens da memoria paginada:
transparente para o programador
transparente para o processo
como todas as paginas têm o mesmo tamanho os algoritmos de gestão são mais simples e eficientes
as transferências entre a memoria principal e a secundária são feitas por páginas individuais

desvantagens da memoria paginada:
não se adequa à divisão lógica dos programas
as faltas de páginas representam uma perda de eficiência maior do que as faltas de segmento

a memória segmentada-paginada:
junta o melhor de: memoria segmentada e memória paginada

o endereço virtual da memória segmentada-paginada (figSO1_09):

segmento, que indica o descritor dentro da tabela de segmentos que deve ser usado na tradução do endereço
uma página, contém a informação acerca da tabela de página que deve ser usada na tradução do endereço
e o deslocamento

#algortimos de gestão de memória

os algoritmos de atribuição (alocação)
determinam na memoria física, onde fica mapeado um bloco de memoria virtual

os algoritmos de atribuição (alocação) em memória paginada:
as páginas têm todos o mesmo tamanho
é usada a page-frame que está livre
existe uma estrutura que indica quais as páginas que estão ocupadas
a primeira livre é a escolhida

os algoritmos de atribuição (alocação) em memória segmentada:
cada segmento tem um tamanho diferente
surgem algoritmos para que não ocorram problemas de fragmentação, na atribuição de blocos

algoritmo best-fit
pesquisa a lista à procura do bloco cuja dimensão seja a mais próxima
procura o melhor bloco que se adapte as dimensões necessárias
a lista de blocos está ordenada de forma crescente

algoritmo worst-fit
procura o maior bloco disponivel
quer evitar que surjam blocos pequenos (com o que “sobra”)
blocos grandes são todos ocupados
a lista de blocos está ordenada de forma decrescente

algoritmo first-fit
procura o bloco que satisfaz
a lista de blocos está ordenada por endereço de blocos

algoritmo next-fit
procura o bloco que satisfaz
continua a pesquisa no ponto onde esteve antes

algoritmo buddy
todos os blocos são do tamanho 2^n
usa o método de recursão para encontrar o bloco ideal
leva à reconstrução de blocos maiores

os algoritmos de transferência
determinam a politica quanto à transferência entre a memoria principal e a secundária

os algoritmos de substituição:
determinam qual o bloco de memória física que deve ser retirado para dar lugar a outro

#politicas de transferência
as politicas por transferência podem ser feitas por:
pedido, o sistema operativo ou o processo, determina quando se deve carregar um loco em memória
necessidade, é necessário carregar o bloco para a memória física, pois é necessário aceder a ele
antecipação, através do factor probabilidade o bloco é transferido para a memoria física pois vai ser usado brevemente

a transferência de páginas:
são feitas por necessidade
o processo quando é criado, surgem a inicialização das tabelas de páginas, mas não são colocadas em memória
à medida que um processo vai progredindo, o sistema operativo vai disponibilizar páginas em memoria de forma transparente para o processo

a transferência de segmentos (swapping):
quando o sistema coloca o processo em execução, coloca também em memória os seus segmentos
as transferências de segmentos são feitas por pedido

a substituição de páginas:
a decisão de retirar páginas está relacionado com a sua utilização
idealmente retira-se aquelas que serão necessárias em ultimo lugar
para se ter uma precisão maior pode-se fazer uso de um dos seguintes algoritmos:
FIFO (quando uma página é carregada, vai para o fim da lista, quando se remove, remove-se a que está no inicio, o que pode ser um problema pois pode ser uma que está a ser usada várias vezes)

LRU, last recently used (o tempo a que a página foi acedida, idade da página, significa que está a ser acedida várias vezes)
ainda no LRU:
a página é carregada, o contador fica a zero
quando for acedida, o bit “R” fica a 1
o contador é incrementado, se o bit “R” estiver a zero
o contador passa a zero, se o bit “R” estiver a um
página fica inválida, se o bit “P” atingir o valor máximo, ficando a memória livre

NRU, not recently used (averigua se a pagina foi acedida ou modificada)
ainda no NRU:
quando for acedida, o bit “R” fica a 1
quando for modificada, o bit “M” fica a 1

R e M a 0, sai de memória
R a 0, e M a 1, sai de memória de seguida
R a 1, e M a 0, sai de memória de seguida, se não existir nenhum dos casos anteriores
R a 1, e M a 1, ultima versão a sair nesta ordem

a substituição de segmentos:
normalmente retiram-se segmentos em função do processo a que pertencem, sendo que essa retirada depende:
da importância / prioridade
da sua utilização pelo processador
da sua dimensão (total de segmentos)

O modelo de espaço de trabalho:
é um modelo que está relacionada com a quantidade de páginas que um processo deve ter presente em memória
compensa nunca colocar em memória, mais do que uma determinada percentagem das suas páginas
o espaço criado vai sendo criado à medida que o processo vai decorrendo, sem nunca ultrapassar o valor máximo de trabalho
se atingir o valor máximo, o espaço para outras das suas páginas são retirados a outros processos
se descer a quantidade de páginas para uma valor mínimo, o processo é enviado para memória secundária

Questões:
quais as desvantagens do endereçamento real face ao endereçamento virtual
descreve o mecanismo de tradução de endereço de memória
elabore uma análise comparativa de memoria segmentada e memoria paginada salientando as vantagens e desvantagens de um face ao outro
descreva o conceito de espaço de trabalho e diga como pode ser usado para aumentar o desempenho do seu computador
porque razão o mecanismo de excepções é fundamental para a construção de memória virtual?
como é que se constrói o isolamento entre processos recorrendo à memória segmentada? Em em memória paginada, há alguma diferença significativa?
quais as vantagens de memória segmentada-paginada face à memória segmentada pura e memória paginada pura?
dado este conjunto de páginas e os tempos em que foram acedidos e modificados, diga qual será a primeira a sair de acordo com o algoritmo FIFO/LRU/NRU e porquê?
dada esta tabela de páginas e estas instruções a serem executadas no espaço de endereçamento que lhe corresponde, diga quais irão ser os endereços reais manipulados e se existirá algum comportamento especifico por parte do sistema operativo
dado este processo (código) diga qual acha que será a dimensão (%) do seu espaço de trabalho
dado este cenário de ocupação de memória real em memória segmentada, diga onde irá ser encaixado um novo segmento de tamanho segundo o algoritmo


Capítulo: 4 (mecanismos de gestão de memória) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

Os mecanismos de gestão de memória: determinam a organização da memória do computador. são em geral executados pelo hardware de gestão de memória do processador, devidamente programado pelo sistema operativo
Os algoritmos de gestão de memória: são da exclusiva responsabilidade do do sistema operativo. determinam que decisões devem ser tomadas e quando devem ser tomadas, usando os mecanismos de baixo nível para as levar a cabo.

Processo e espaço de endereçamento
o espaço de endereçamento de um processo é o conjunto de posições de memória que um programa executado por esse processo pode referenciar/aceder. a memória divide-se em memória física e memória secundária, os programas só se executam em memória física, sendo a secundária (discos) para guardar a informação persistente

Endereços reais e virtuais
o endereçamento real tem um relação directa com os endereços da memória física do computador. este tipo de endereçamento tem desvantagens:
a dimensão dos programas é limitada pela dimensão da memória física do computador
um programa só pode funcionar nos endereços físicos para onde foi escrito
a multiprogramação fica bastante dificultada

o endereçamento virtual são endereços gerados pelo programa que são convertidos pelo processador e em tempo de execução em endereços físicos. é função do hardware de gestão de memória e do sistema operativo fazer a transferência entre o endereço virtual e o endereço físico. a palavra referenciada pelo endereço virtual pode estar em memória física ou em memoria secundária. se estiver em memoria física a unidade de gestão de memoria traduz automaticamente o endereço virtual em endereço físico e a palavra é a acedida; mas se a palavra estiver em memória secundárias a unidade de gestão de memoria avisa o sistema operativo para este carregar a palavra em memoria física.

Endereçamento real – sistemas monoprogramados
os computadores eram monoprogramados, e tinham endereçamento real. o principal inconveniente do endereçamento real é o tamanho dos programas ser limitado pela dimensão da memória física do computador. para ultrapassar este problema usa-se a técnica da sobreposição (overlay), o programa é divido numa parte residente que está sempre em memoria, e em overlays, que são módulos independentes uns dos outros e que são carregados em memória a pedido do programa.

Endereçamento real – sistemas multiprogramados com partições fixas
para permitir a multiprogramação é necessário que vários programas possam coexistir em memória central
a forma mais simples é dividir a memória do computador em partições, carregando cada programa numa delas.

Endereçamento real – sistemas multiprogramados com partições variáveis
neste caso aloca-se uma zona de memória de dimensão suficiente para colocar o programa.
quando um programa se começar a executar, será alocada uma zona de memória para o colocar, ficando a existir duas participações, aquela onde está o programa em execução e a que compreende o restante da memória

endereçamento virtual
o principal objectivo da memória virtual é dissociar os endereços gerados pelo programa dos endereços físicos acedidos na memória da máquina
o mecanismo de tradução de endereços virtuais em endereços virtuais em endereços reais é efectuado pelo hardware, mais precisamente pela unidade de gestão de memoria do processador
as outras componentes do processar só manipulam os endereços virtuais

endereçamento virtual – segmentação
o objectivo da segmentação é a divisão dos programas em segmentos lógicos que reflictam a sua subdivisão funcional. se um endereço for inválido, o hardware interrompe a tradução do endereço e gera uma excepção que será tratada pelo sistema operativo.

endereçamento virtual – paginação
o principal objectivo da arquitectura de memória paginada é oferecer ao programador um espaço de endereçamento (virtual), linear, em geral bastante maior que a dimensão da memória física da máquina. desta forma o programador não precisa de se preocupar com a gestão de memória quando escreve um programa.

endereçamento virtual – paginação – mecanismos de tradução de endereços
a memória é dividida em blocos do mesmo tamanho, chamados páginas, em que cada página contém o número da página e deslocamento, e o deslocamento indica dentro da página.

Capítulo: 5 (algoritmos de gestão de memória) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

os algoritmos de gestão de memória determinam as decisões tomadas pelo SI, e são utilizados para decidir onde se deve colocar um bloco de programa dada a memória livre, quando se transferir uma página ou segmento de memória secundária para a memória principal e vice-versa e quando não existe mais memória livre que bloco retirar para lá colocar outro mais prioritário.

O sistema operativo e em relação à memória tem que ter em conta:
alocação: onde colocar um bloco na memória
transferência: decidir quando transferir um bloco de memória secundária para memória primária e vice-versa
substituição: quando não existe mais memória livre, qual o bloco a retirar de memória para satisfazer o pedido

Alocação de memória
os algoritmos de alocação de memória, decidem, dada a memória livre, onde colocar um bloco de memória de uma determinada dimensão. o sistema operativo faz uso desses algoritmos para:
na criação e terminação de processos
por extensão do espaço de endereçamento

Alocação de memória – Alocação de páginas
como as páginas são todas do mesmo tamanho, no caso da paginação este algoritmo é trivial: aloca-se qualquer página que esteja livre
as páginas livres são mantidas numa lista, geralmente gerida em FIFO, na alocação retira-se a primeira página da lista, na libertação coloca-se a página no fim da lista

Alocação de memória – Alocação de segmentos
a alocação de segmentos é mais complicada pois é necessário analisar a memória livre para encontrar um bloco desocupado com dimensão suficiente para satisfazer o pedido.  mas tem algumas vantagens:
evita que se gerem fragmentos muito pequenos
os blocos devolvidos ficam naturalmente alinhados
os registos da lista livres precisam de menos bits para guardar o endereço e o comprimento dos blocos

Algoritmos de transferência
os algoritmos de transferência determinam quando um bloco de memória deve ser transferido entre memória secundária e memória central, e essa transferência pode ocorrer quando:
a pedido (request): o programa ou o sistema operativo determinam explicitamente quando se deve carregar o bloco em memória
por necessidade (on demand): o bloco é acedido e gera-se uma falta de página ou segmento, sendo necessário carregá-lo em memória
por antecipação: o bloco é carregado em memória pelo sistema operativo pois este considera fortemente provavelmente que ele venha a ser acedido nos próximo instantes

Algoritmos de transferência – transferência de segmentos (swapping)
em sistemas de memória segmentada, um processo é composto por vários segmentos lógicos: código, dados, pilha e dados do sistema operativo respeitantes ao processo.
um segmento é sempre transferido como um todo entre memória e disco, nunca é transferida apenas parte do segmento
a transferência de segmentos (swapping) permite que de uma forma simples e sem hardware sofisticado, se ofereça um ambiente de multiprogramação.

Algoritmos de transferência – transferência de página
o mecanismo normal de transferência de páginas é por necessidade (on demand): uma página é transferida para memória primária quando se dá uma falta nessa página

Algoritmos de substituição
quando a memória física fica cheia, o sistema operativo tem que retirar um bloco de memória primária (enviar para o disco) para arranjar espaço livre

Algoritmos de substituição – de páginas
quando um processo tenta aceder a uma página que não esteja carregada em memória primária, e não haja páginas livres mas modificadas. as páginas livres podem ser reutilizadas em qualquer momento. as páginas livres mas modificadas têm de ser escritas em disco antes de serem reutilizadas.
dado um conjunto de páginas em memória, a escolha óptima é retirar a que for acedida mais tarde no tempo

Algoritmos de substituição – de páginas, menos usada recentemente (LRU)

Algoritmos de substituição – de páginas, FIFO

Análise comparativa da segmentação e paginação
vantagens segmentação:
adapta-se à estrutura lógica do programa
permite a realização de sistemas simples sobre hardware simples
permite realizar eficientemente as operações que agem sobre um segmento inteiro

desvantagens segmentação:
o programador tem de ter sempre algum conhecimento dos segmentos subjacentes
os algoritmos tornam-se bastante complicados em sistemas mais sofisticados
o tempo de transferência de segmentos entre memória central e disco torna-se incomportável para segmentos muito grandes
a dimensão máxima dos segmentos é limitada

vantagens paginação:
o programador não tem que se preocupar com a gestão de memória
os algoritmos de alocação, substituição e transferência são mais simples e eficientes
o tempo de leitura de uma página de disco é razoavelmente pequeno
a dimensão dos programas é virtualmente ilimitada

desvantagens paginação:
o hardware é mais complexo que o de memória segmentada, não permitindo a realização de máquinas de muito baixo custo
operações sobre segmentos lógicos são mais complexas e menos elegantes, pois têm de ser realizadas sobre um conjunto de páginas
o tratamento das faltas de páginas representa uma sobrecarga adicional de processamento

Tags : , ,

SO1 – Escalonamento – Conceitos e Algoritmos

[so1t]

#conceitos de multi-programação

o pseudo-paralelismo:
consistem em ter varias actividades a decorrer ao mesmo tempo
disponivel em sistemas multi-programados (com tempo partilhado ou não)

algoritmos preemptivos:
forçam o processo a deixar o processador não bloqueado
usados em sistemas de tempo partilhado

exemplos de algoritmos preemptivos:
fim de quantum
processo prioritários
processos mais curtos

sistemas preemptivos:
o processo em execução pode ser interrompido e colocar em estado de “executável” pelo sistema operativo
e pode acontecer porque:
um novo processo esta no estado executável
surge uma interrupção que termina um determinado bloqueio
face à imposição do tempo partilhado
exemplo: windowsNT, Unix

desvantagens dos sistemas preemptivos:
maior comutação de processos, menor desempenho global
maior complexidade dos sistemas operativos

algoritmos não preemptivos:
não forçam o processo a sair do processador
exemplo: ms-dos

exemplos de algoritmos não preemptivos:
o programa terminou
o programa pediu acesso a um semáforo que está fechado
o programa requisitou uma operação de E/S demorada

sistemas não preemptivos:
um processo está em estado de execução e ele tem que terminar ou bloquear (por pedido do sistema operativo ou conclusão de operação de E/S)

escalonamento preemptivo:
usado em sistemas de tempo real
em sistemas multi-utilizador
permitem que um processo prioritário reaja a acontecimentos

como funciona o escalonamento preemptivo:
a) um processo prioritário está bloqueado num semáforo
b) é provocado um acontecimento no semáforo
c) o processo prioritário passa a executável
d) o processo em execução é retirado do processador
e) o processo prioritário entra em execução

a acção da preempção implica que o despacho seja chamado na sequência de alterações ao estado do processo e que podem ser:
fim do quantum
sinalização de periféricos
operações de sincronização

as prioridades:
é um atributo dos processos e das threads
um processo pode ser atendido por uma determinada ordem
usada em algoritmos de escalonamento

e as prioridades podem ser:
fixas, associadas à importância de acontecimentos, definidas pelo programador ou utilizador
dinâmicas, associadas ao comportamento do processo no sistema (evitar a monopolização de recursos levando a starvation), e é atribuída pelo escalonamento de acordo com o seu comportamento no sistema

os escalonadores:
longo prazo, admite ou não um processo a execução
médio prazo, determina quando e qual o processo que está no estado executável e que vai obter o processador (swaping)
curto prazo (ou despachos), efectua a comutação entre o processo que está a executar e o próximo (fim do quantum)

no despacho:
tempo de latência = tempo de parar um processo + tempo de recomeçar outro processo

a comutação faz com que:
invoca o despacho
salvaguarda o contexto de software e hardware do processo anterior em execução
recuperar o contexto do software e hardware
salta para a localização onde estava antes dentro do processo que vai para execução

sistema multi-programado simples:
são não preemptivos
executa os processos de forma colaborativa
não forçam os processos a sair do processador
faz uso das interrupções voluntárias (inputs) para executar outro processo pronto no processador

desvantagens:
processo que nunca bloqueiem
não optimiza os tempos de execução

questões:
qual a diferença entre multi-programação simples e multi-programação preemptiva
que tipos de preempção pode haver no escalonamento preemptivo?
como é que um computador só com um processador/núcleo consegue executar vários programas em simultâneo”?
se um programa entrar num ciclo infinito “encalha” a maquina toda? dê a sua resposta no contexto de multi-programação simples e depois multiplicação preemptiva
o que é o pseudo-paralelismo?
quais são as vantagens que a multi-programação preemptiva traz em relação à multi-programação simples?
num cenário real, poderá um sistema preemptivo ter menos performance global em relação a um sistema multi-programado mas não preemptivo? explique
qual destes é mais estável e porquê?: mono-processamento, multi-programação simples, multi-programação preemptiva?
que tipo de prioridades conhece. Para que serve cada tipo. Dê exemplos de aplicação.
Existem vários escalonadores? quais/para quê?

#conceito de estado de processos
em sistemas multi-programados os processo não estão apenas no estado em execução, mas podem estar em: execução, bloqueado não executável, ou executável (à espera de vez no processador)

os processos, num sistema monoprogramado (figSO1_01):

existem dois estados: parado e em execução
o processo quando é criado vai para o estado parado
o processo sai do estado parado (da fila de espera) pelo despacho
o processo quando está no estado de execução e termina, vai para processo termina
o processo quando está no estado de execução e não termina, fica suspenso, e vai para a fila de espera

os processos, num sistema multi-programado:
existem três estados: em execução, bloqueado, e executável (pronto a correr mas à espera do processador)
o processo está em execução: está a ser executado pelo processador
o processo está bloqueado: o processo não precisa do processador, e liberta-o
o processo está executável: o processo está pronto mas entrar em execução, mas o processador está ocupado

se dois processos estiverem prontos para irem para o processador, é o algoritmo de escalonamento que determina quem vai.

os processos, num sistema multi-programado (figSO1_02):

o processo quando é criado vai para o estado executável
o processo sai do estado executável (da fila de espera) pelo despacho
o processo quando está no estado de execução e termina, vai para processo termina
o processo quando está no estado de execução e aguarda um evento, vai para o estado de bloqueado
o processo quando está no estado de bloqueado e acontece um evento, vai para o estado de executável
o processo quando está no estado de execução e é retirado da execução, vai para o estado de executável (timeslice, quantum)

os processos, num sistema multi-programado, modelo completo (figSO1_03):

o processo quando é criado vai para o estado executável
o processo sai do estado executável (da fila de espera) pelo despacho
o processo sai do estado executável pode ser suspenso, vai para o estado de suspenso (fila processos suspensos)
o processo quando está no estado de execução e termina, vai para processo terminado
o processo quando está no estado de execução e aguarda um evento, vai para o estado de bloqueado (fila processos bloqueados)
o processo quando está no estado de bloqueado e acontece um evento, vai para o estado de executável (fila processos executáveis)
o processo quando está no estado de bloqueado e é suspenso, vai para o estado de suspenso (fila processos suspensos)
o processo quando está no estado de suspenso e é des-suspenso, vai para o estado de bloqueado (fila processos bloqueados)
o processo quando está no estado de suspenso e é des-suspenso, vai para o estado de executável (fila processos executáveis)
o processo quando está no estado de execução e auto-suspende-se, vai para o estado de suspenso (fila processos suspensos)
o processo quando está no estado de bloqueado e acontece um evento, vai para o estado de executável (fila processos executáveis)
o processo quando está no estado de execução e é retirado da execução, vai para o estado de executável (timeslice, quantum)(fila processos executáveis)

questões:
descreva o conceito de “estado de um processo” e indique a sua utilidade
quais os estados que conhece e respectivo significado?
que transições de estado podem ocorrer e em que circunstâncias
um processo pode passar directamente de bloqueado para em execução? em que circunstâncias/porquê?
qual diferença entre suspenso e bloqueado?
o que é o escalonamento por níveis e para que serve?

#conceitos gerais usados em escalonamento
a gestão do processador tem que ter em conta:
desempenho
suporte para multi-utilizador
robustez e fiabilidade

na gestão do processador tem que ser ter em conta:
previsibilidade
equilíbrio de recursos (evitar picos de uso dos recursos)
justiça (todos os processos devem ter a mesma utilização dos recursos) e starvation
processos I/O bound (processos que fazem muitas operações de E/S, bloqueando-se) e CPU bound (processos que usam de forma intensiva o processador, nunca se bloqueando)

questões:
o que se entende por conceito de justiça no escalonamento?
no contexto de escalonamento, indique cenários em que a justiça é desejável e cenários em que a justiça não é desejável
o que entende pelo conceito de starvation?
descreva o que entende por processo CPU bound e por processo I/O bound? Explique.
o que entende por equilíbrio de recursos?
qual a relação entre a gestão do processador e a gestão do resto da máquina?

#indicadores de desempenho
aferir como o sistema gere o uso do processador

as métricas que existem acerca do desempenho:
utilização do processador (é a percentagem de tempo que o processador está a ser usado, pouco interessante em sistemas interactivos, mono-utilziador ou sistemas de tempo real)
throughput (quantidade de processos concluídos por unidade de tempo, é interessante se os processos tiverem a mesma carga)
tempo de conclusão (touraround) (intervalo de tempo desde que se cria o processo até ele terminar)
prazos / deadlines (interessa maximizar a percentagem de prazos cumpridos, usado em sistemas de tempo real)
tempo de resposta / latência (tempo que demora a obtenção de uma resposta a uma acção do utilizador, usado em sistemas multi-programados interactivos)
razão da penalização / penalty ratio (é a razão entre o tempo de existência total sobre o tempo que levaria a executar-se se estivesse sozinho no sistema)
tempo de espera (tempo total que um processo esteve no estado executável)
previsibilidade (implementação complexa, o tempo de execução deve ser sempre o mesmo independentemente da carga no processador, necessidade de recorrer a registos de tempos de execução)

assim e acerca da gestão do processador e sendo um objectivo do escalonamento do sistema operativo:
minimizar a latência
maximizar o throughput
maximizar o equilíbrio da utilização dos periféricos
justiça

problemas e dificuldades que podem surgir nesta gestão:
dificuldade de prever o tipo de processos (CPU bound ou I/O bound), ficando os dispositivos de E/S inactivos
uma optimização pode provocar starvation
ocorrência de deadlocks

questões:
explique o que significa e qual o cenário de uso do indicador de desempenho de utilização do processador
explique o que significa e qual o cenário de uso do indicador de desempenho de throughput
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de conclusão (touraround)
explique o que significa e qual o cenário de uso do indicador de desempenho de prazos / deadlines
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de resposta / latência
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de razão da penalização / penalty ratio
explique o que significa e qual o cenário de uso do indicador de desempenho de tempo de espera
explique o que significa e qual o cenário de uso do indicador de desempenho de previsibilidade
dado um cenário com alguns processos e dois algoritmos de escalonamento, calcule cada uma das várias métricas de indicadores explicados e identifique qual o melhor algoritmo
verifique, para um dado cenário, identifique quais os indicadores de desempenho mais adequados e menos adequados. justifique.

#algoritmos de escalonamento
os algoritmos de escalonamento podem ser: não preemptivos e preemptivos

os não preemptivos são:
FCFS (first come first serve)
SPN (shortest process next)
HRRN (highest response ratio)

os preemptivos são:
Round Robin
SRT (shortest remaining time)
FEEDBACK

algortimo FCFS (first come first serve):
algoritmo não preemptivo
os processos são atendidos por ordem de chegada
favorece processos CPU bound
bloqueia os processos I/O bound
adequado para processos que não são interactivos
adequado para processos com a mesma duração de tempo
em arquitecturas de um só processador, deve usar-se com a variante de prioridades

algortimo Round Robin:
algoritmo preemptivo
os processos são atendidos por ordem de chegada
tem por base um quantum, sendo que depois volta para a lista dos executáveis
garantia que todos os processos são atendidos (não vai existir a starvation)
se existir uma variação de tempo nos processos, então este algoritmo é melhor que o FCFS
problema, definir o quantum (muito grande fica como o FCFS, já muito pequeno pode haver a necessidade de mais quantum)
adequado em arquitecturas com sistemas multi-programados

exemplo 1, de um cenário FCFS vs Round Robin (figSO1_04):

três processos, A, B e C, do tipo CPU bound
tempo total, de 18q
duração dos processos: A(12q), B(3q) e C(3q)
ordem de chegada: A, instante 0; B, instante 1; C, instante 2

exemplo 2, de um cenário FCFS vs Round Robin (figSO1_05):

três processos, A, B e C, do tipo CPU bound
tempo total, de 18q
duração dos processos: 6q para todos
ordem de chegada: A, instante 0; B, instante 1; C, instante 2

algortimo SPN (shortest process next):
não é preemptivo
similar ao FCFS, mas o próximo processo a ser executado é aquele que supostamente vai demorar menos tempo a executar
favorece os processos CPU bound
pode levar à starvation dos processos longos
tem um melhor touraround médio
não serve para sistemas multi-programados de tempo partilhado
problema: necessidade de ter um registo estatisito dos tempos dos processos

algoritmo SRT (shortest remaining time):
é preemptivo
similar ao SPN
o próximo processo a ser executado é aquele em que o tempo restante de processamento é menor
não é baseado no quantum
pode existir starvation dos processos longos
menor interactividade do que o RR
menor overhead que o RR
melhor touraround
problema: necessidade de ter um registo dos tempos de execução

algoritmo HRRN (highest response ratio):
eliminar o problema da starvation (que acontece no SPN e SRT)
surge o response ratio (RR)
RR = tempo de espera do processador + tempo de execução esperado / tempo de execução esperado
é escolhido o processo que tiver o maior RR
problema: como saber o tempo de execução de um processo?

algoritmo de FEEDBACK:
é preemptivo
é feita uma análise no passado recente
uso de prioridades dinâmicas (processo curto nunca perde a prioridade, processo longo vai perdendo a prioridade)
quantum variável (uso de diferentes quantums para recuperar processos, se este estiver a ser penalizado)

algoritmo de escalonamento escalável (a escabilidade):
algoritmo não escalável: pequenos aumentos no numero de processos levam a grandes aumentos no custo de execução do escalonador
algoritmo escalável pesado: pequenos aumentos no numero de processos levam a aumentos grandes mas proporcionais no custo de execução do escalonador (comum)
algoritmo escalável leve: pequenos aumentos no numero de processos levam a aumentos pequenos e proporcionais no custo de execução do escalonador (melhor cenário que se consegue)
algoritmo escalável muito bom (mas é fantasia): cada aumento no numero de processos causa pesos de execução cada vez menores

a técnica do escalonamento multi-lista (figSO1_06):

o nível superior é naquele cujos processos vão para execução
periodicamente, ir passando os processos para níveis mais superiores
ou despromovendo os processos do nível superior

problemas com qualquer escalonamento:
tempo de comutação de processos

questões:
explique como funciona um algoritmo
explique quais as vantagens face aos restantes, de um algoritmo
explique quais as desvantagens face aos restantes, de um algoritmo
exemplifique um cenário onde o algoritmo é o mais indicado, de um determinado algoritmo
exemplifique um cenário onde o algoritmo é não é o indicado, de um determinado algoritmo
o que é o escalonamento por níveis (multi-lista) e para que serve?
o que entende pela questão de escabilidade no escalonamento. indique uma forma de lidar com essa questão.

#escalonamento nos sistemas unix, linux, e windows NT

o escalonamento em unix:
round robin, com prioridades dinâmicas
privilegia os processos I/O bound
não pretendente atrasar os processos CPU bound
tem um quantum
a prioridade varia consoante o comportamento recente do processo
escalonamento multi-lista

o escalonamento em linux:
quantum são cerca de um conjunto de 20 notificações do relógio
e o quantum é modificado em cada época para um determinado processo

o escalonamento em windows nt:
o escalonamento é nas thread
round robim, com prioridades fixas e dinâmicas
escalonamento multi-lista
quantum é um conjunto de notificações do relógio

questões:
explique o funcionamento do escalonamento em unix, no linux e no windowsNT. Relacione com os conceitos dados nesta matéria
explique de que forma o windowsNT evita situações de starvation
explique de que forma o linux evita situações de starvation
poder-se-á dizer que os algoritmos de escalonamento do linux e do windowsNT são 100% justos= é isso é bom ou mau= Explique.
explique como são usadas as prioridades do windowsNT
os quantuns no linux têm sempre a mesma duração? porquê?
no contexto de escalonamento, indique uma diferença entre a edição desktop e a edição server do windowsNT. Explique essa diferença.

Outras questões:
descreva o que é um quantum
descreva o que é a preempção
explique o conceito de justiça
descrever o que é o cpu bound e o i/o bound
explicar o que é o tempo de espera, throughput, penalty ratio, conceito de justiça
descrever o modo de funcionamento de cada um dos algoritmos estudados
descrever os objectivos dos escalonamento e duas principais dificuldades na obtenção de uma gestão óptima absoluta
explicar e justificar a influencia de preempção ou ausência dela num sistema
comparação entre dois ou mais algoritmos, vantagens/desvantagens. Para uma determinado cenário, qual é o melhor e porquê?
descrever a influência da optimização de alguns indicadores de desempenho sobre os outros. explicar se é/não é possivel melhorar dois ou mais determinados indicadores e porquê.

Tags : , ,

SO1 – Fundamentos de sincronização, problema de exclusão mútua e semáforos binários

[so1t]

Fundamentos de sincronização, problema de exclusão mútua e semáforos binários

motivos de sincronização:
processos e threads, que querem fazer uso dos mesmos recursos

usar a exclusão mútua:
porque se partilha zona de dados
apenas uma entidade activa deve utilizar o recurso
resolver então o problema de concorrência, do acesso concorrente a dados

surge então a secção critica:
que são o conjunto de operações que deve ser efectuado de forma atómica (invisível)

os semáforos:
são uma solução para garantir o acesso em exclusão mutua a uma secção critica
é um recurso que é controlado pelo sistema operativo
tem a capacidade para ter um “numero de autorizações”
tem na sua estrutura: o numero de autorizações, e a fila de espera (processos bloqueados)
tem como operações: esperar (requisita o recurso, diminui o contador) e assinalar (liberta o recurso, aumenta o contador)
os processos ficam bloqueados se não existirem mais autorizações disponíveis, ficando desbloqueado assim que houver uma autorização livre
este bloqueio ou desbloqueio é sempre transparente para o processo

e relembrar que bloquear um processo:
é retirado de execução
é salvaguardado o seu contexto (software e hardware)
o seu estado passa a bloqueados
fica em fila de espera

e relembrar que desbloquear um processo:
é retirado da fila dos bloqueados
passa para o estado de executável
vai para o fim de lista dos executáveis
é fica em execução quando o despacho o seleccionar

vantagens dos semáforos:
bloquear o processo não ocupa o processador
é um mecanismo justo
é compatível com politicas de prioridades
elimina a espera activa

a verificar semáforos vs mutex (resolve o problema de exclusão mutua)!!!

questões:
identifique problemas de sincronização (exclusão mútua)
identifique a forma de resolver a novel abstracto com recurso a semáforos/mutexs

Tags : ,

SO1 – conceitos fundamentais de SO

Capítulos: 1, 2 e parte do 3 do livro: Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença
Capitulo 1 do livro: Operating Systems Concepts – 6-º edição – Addison-Wesley

#objectivos, constituição e tipos de sistema operativos
Um sistema operativo é um programa ou conjunto de programas que efectua a gestão de tudo o que há na máquina

Posicionamento do sistema operativo
utilizador
programas utilizador (aplicações, interface utilizador)
sistema operativo (interface com aplicações (API), componentes do S.O, interface com hardware)
hardware

objectivos dos sistemas operativos:
efectuar a gestão da máquina (gestão de recursos da máquina, implementação de politicas de optimização)
virtualizar o hardware
prestação de serviços e ambiente de trabalho
garantir a estabilidade da máquina (recursos)

Posicionamento do sistema operativo (camada mais alta):
utilizador
aplicações e interface utilizador
sistema operativo (API, componentes do SO, interface com hardware)
hardware

Entidades que interagem com o sistema operativo:
utilizador (requer serviços e obtém feedback)
aplicações (requer serviços e recursos, e obtém serviços e recursos, e controlo do comportamento das aplicações)
hardware (faz notificações e recepção de dados, e recebe a configuração do hardware, instruções aos dispositivos, envio de dados)

qualquer programa obtém recursos ou serviços através de chamadas ao sistema. Essas funções acessíveis são a API do sistema
as aplicações devem ter acesso ás funções sem serem obrigadas a conhecer o endereço exacto onde residem
as aplicações não devem poder saltar para locais arbitrários dos códigos das funções de sistema
as aplicações não devem ter a possibilidade de alterar o código das funções

tarefas do sistema operativo:
configurar o hardware no arranque do sistema
controlar o estado do hardware e efectuar a gestão de erros
receber notificaçõs enviadas pelos periféricos (hardware)

os device-drivers, são sub-programas que que executam estas tarefas

Tipos de sistemas operativos:
(relação tempo da maquina e tempo real)
sistema de tempo virtual
sistema de tempo real
(quanto ao numero de processadores)
sistemas paralelos (memoria e relógio partilhado)
sistemas distribuídos (memoria e relógio independentes)

Questões:
o que é um sistema operativo?
que pontos de vista existe, acerca do que é ou deixa de ser um sistema operativo?
que entidades interagem com o sistema operativo=
em que condições um programa pode aceder ao hardware?
o ser humano interage com o sistema operativo? de que forma?
como é que o hardware interage com o sistema operativo?
quais os objectivos principais de um sistema operativo moderno?
o que é um API?
como é que os programas-utilizador utilizam os recursos do sistema operativo?
o que é o isolamento de um processo?
o que é isso de abstrair o hardware? dê exemplos
o que é que impede um programa-utilizador de tornar o controlo da máquina?
que tipos de sistema existem? dê exemplos de aplicação para cada um.

#arquitecturas de sistemas operativos

núcleo do sistema operativo:
conjunto de funcionalidades (camadas) dos sistema onde se incluem as funções mais importantes e mais privilegiadas
deve ser sempre executado no modo mais privilegiado
porquê?
necessidade de executar instruções privilegiadas,
necessidade de protecção quanto a interferências do resto do sistema ou programas utilizador
execução prioritária

funções do núcleo:
gestão de processos (controlo de interrupções, escalonamento, despacho, mecanismos de sincronização)
gestão de memória

os sistemas monolíticos:
não existe um encapsulamento funcional
o sistema operativo é constituído por um conjunto de procedimentos ou funções que se podem chamar uns aos outros
vantagens: mais rápidos
desvantagens: não têm uma estrutura, logo é difícil implementar
desvantagens: dificuldade em isolar responsabilidades no sistema

os sistema em camadas:
as tarefas e responsabilidades do sistema operativo são atribuídas a uma camada especifica

as camadas:
gestão de processos
gestão de memoria
comunicação E/S
sistemas de ficheiros
interface do sistema (funções de sistema e interpretador de comandos)
aplicações

tarefas da camada de processos:
criar a terminar processos
escalonamento e despacho de processos
comutação de processos e tratamento de interrupções
suporte para sincronização de processos

tarefas da camada de memória:
controlo da utilização da memória física e memória virtual

tarefas da camada de comunicação e E/S:
mecanismos de comunicação entre processos
comunicação com o exterior E/S

tarefas da camada de sistemas de ficheiros:
virtualização dos dispositivos de massa

tarefas da camada da interface dos sistema:
serviços proporcionados pelo sistema
interpretador de comandos

vantagens:
protecção, impedir a interferência com outros processo ou com o próprio sistema
se o hardware suportar, cada camada terá o seu próprio modo de execução
actualmente, arquitectura mista, sistemas não monolíticos e poucas camadas

desvantagens:
não é fácil determinar a hierarquia das camadas

arquitectura das máquinas virtuais:
são uma evolução dos sistemas de tempo partilhado

surge o hypervisor:
serve para a funcionalidade de virtualização
é um sistema operativo não genérico
hypervisor tipo 1 (nativo: sistema que faz a gestão do hardware)
hypervisor tipo 2 (hospede: virtualbox)

vantagens:
separação da multiprogramação e do virtualização do hardware
ter várias máquinas numa só
hypervisor tipo 1: melhor gestão do hardware, independentes de um sistema operativo genérico
hypervisor tipo 2: menor investimento, integração com um sistema que já existe

desvantagens:
difícil de implementar em alguns hardwares
hypervisor tipo 1: menor facilidade de interacção por parte dos utilizadores (só através de remote)
hypervisor tipo 2: menor performance, dependência do sistema operativo onde está instalado

arquitectura do cliente/servidor:
divisão lógica do sistema operativo em unidades funcionais
núcleo reduzido e simplificado: micro-kernel
os serviços do sistema são proporcionados por programas
os serviços são solicitados através de mensagens entre processos
o núcleo: faz o escalonamento e despacho; e a gestão da comunicação entre processos
fora do núcleo: fica a gestão a de memoria e a gestão de ficheiros

existem dois modos:
modo de utilizador: aplicações, servidor de display, sistema de ficheiros, etc
modo de núcleo: hardware, e micro-kernel

vantagens:
núcleo simplificado e rápido
sistema mais estável
adaptável a sistemas distribuídos
portabilidade melhorada

desvantagens:
???

Questões:
quais as características de cada arquitectura de sistemas?
quais as vantagens e desvantagens de cada arquitectura de sistemas?
o que é um núcleo? como pode identificar facilmente?
o núcleo corresponde ao sistema operativo? justifique e dê exemplos
quais as arquitecturas de sistemas operativo que conhece? descreva-as detalhadamente e de forma coerente. para cada ima indique uma vantagem e uma desvantagem
qual é o melhor? um sistema monolítico ou um sistema em micro-kernel?
identifique exemplos de aplicação em sistemas de máquinas virtuais.
qual a diferença principal entre um sistema de tempo virtual e um sistema de tempo real?
qual a diferença principal entre um sistema paralelo e um distribuído?
aplicaria um sistema de tempo virtual para controlar o sistema de direcção de um míssil? Porquê?

#implementação de funções sistema e mecanismo de interrupções
o mecanismo de interrupções, serve para notificar de forma assíncrona a ocorrência de situações
as interrupções não são explicitas, podem ocorrer a qualquer momento
o programador nem o compilador sabem que interrupções são usadas em que funções
o uso do mecanismo de interrupções e os privilégios de execução, fazem com que as interrupções sejam usadas com segurança (protecção)

exemplos das situações:
fim de operação de E/S
houve uma tentativa de utilização de um endereço inválido
o processador encontrou uma instrução que não conhece
é preciso ir buscar um bloco de memória ao disco e colocá-lo em memória
é preciso transferir a execução do código de um processo para o código do sistema operativo
terminou o tempo máximo concedido a um processo

mecanismos de interrupções:
interrupções: gerada por periféricos e essencial para operações de E/S
traps: pedidas pelo próprio programa, úteis para chamadas ao sistema
excepções: pedidas pelo processador, essenciais para tratar erros do sistema operativo

como funcionam:
a) um dispositivo (controlador) activa a linha de IRQ
b) o processador interrompe a execução e executa uma rotina de serviço de interrupção (ISR)
o serviço de rotina está numa tabela fixa (e conhecida) na memória, é a tabela de interrupções
e pode existir um esquema de interrupções hierarquizado, inibindo as interrupções de menor prioridade
c) a rotina de serviço de interrupção averigua a causa da interrupção

as traps:
similares as interrupções
são explicitas
uma trap é uma determinada chamada ao sistema

como implementar as chamadas ao sistema com interrupções:
as traps, sabem qual é o endereço da rotina, que está numa tabela e não é conhecido pelo processo, destam forma pode mudar de kernel
as traps, protegem contra saltos indevidos, a trap salta para o endereço que consta na tabela de interrupções. Essa tabela está protegida conta escrita no modo de utilizador
as traps, pode passar do modo de utilizador para modo de núcleo, permitindo assim uma passagem para um modo mais privilegiado

as excepções:
funcionam como as interrupções e as traps
é desencadeada pelo processador

exemplos das situações:
operações inválidas
tentativa de acesso a zonas de memoria de outros processos
falta de página
tentativa de execução de uma instrução privilegiada em modo de utilizador

Questões:
como é que os programas-utilizador encontram as rotinas do sistema operativo?
o que é o modo núcleo? em que difere do modo de utilizador?
é possivel implementar um linux ou windows moderno num 8086? porquê?
o que é uma trap e para que serve?
como é que o sistema detecta que um programa está a tentar usar um endereço inválido?
como é que o controlador dos disco rígido (por exemplo) avisa o sistema que ocorreu um erro?
o que é uma função sistema?
qual a diferença entre uma função sistema e função biblioteca?
dê um exemplo de função de biblioteca
dê um exemplo de função de sistema
o que é a fase de linkagem e que se serve (o que faz)?

#processos e threads
um programa é uma sequência de instruções, é uma entidade passiva
os processos são entidades activas que partilham o processador , que está em execução
o escalonamento é efectuado em termos de processos (o mesmo programa pode estar a ser executado em diferentes processos)
e um processo pode ser dividido em threads

um processo é constituído por regiões (top down):
pilha (colocadas as variáveis locais, a serem executadas pelo processador)
espaço de endereçamento não utilizado
heap (zonas de memória dinâmicas, por exemplo mallocs)
dados inicializados (variáveis estáticas ou locais)
código (instruções que vão ser executadas pelo processador)

o processo pode ser executado em:
modo utilizador (instruções definidas pelo programador)
modo núcleo (a execução decore dentro de funções de sistema invocadas pelo processo)

Questões:
qual a diferença entre processo e programa?
em que circunstâncias pode um processo estar associado a nenhum programa?
um programa pode estar a ser executado em vários processos?
um processo pode estar a executar vários programas?
descreva as zonas de memória típicas de um processo. Para que serve cada uma?
qual a diferença entre processo e thread?
é possivel um processo ter zero threads?
dê um exemplo concreto onde seja útil ter mais que uma thread.


Capítulo: 1 (introdução) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

Os sistemas de tratamento por lotes procuram resolver a principal limitação do desempenho resultante da diferença considerável entre o tempo de execução do processador e das operações de E/S sobre periféricos mecânicos. As operações lentas de E/S foram relegadas para equipamentos auxiliares permitindo que o processador central executasse um fluxo continuo de trabalho.

Multiprogramação
todos os sistemas anteriores (antes da Multiprogramação) só se tornaram possíveis através da utilização dos mecanismos de interrupção que permitem multiplexar o processador entre diversas actividades executadas concorrentemente. estes sistemas permitem o desenvolvimento de sistemas de tratamento por lotes de grande eficácia.
O sistema multiprogramado permite que diversos programas estejam simultaneamente activos. A multiprogramação só é eficaz se os diversos programas residirem na memória central, pois só assim a mudança de contexto se poderá processar rapidamente. Mas a memória física é limitada e pode ser impossível manter simultaneamente em memória diversos programas com tamanhos variados. a solução passa pela existência de uma hierarquia de memória que permita, quando se torne necessário carregar um novo programa e salvaguardar na memória secundária alguns dos programas bloqueados (é o swapping).
a atribuição cíclica do tempo do processador os vários utilizadores permitiu ultrapassar esta limitação dando a cada programador a ilusão de dispor de uma máquina própria, surgindo os sistemas de tempo partilhado.

Sistemas interactivos
são sistemas onde podem existir vários utilizados que sem quaisquer conhecimentos de especialização conseguem interagir com os sistemas dos computadores.
a multiplexagem entre vários utilizadores impõe a divisão do tempo disponível do processador entre os diferentes utentes, atribuindo-lhes fatias de tempo que permitam dar-lhes a sensação de dispor de uma máquina dedicada.
surge nestes sistemas a necessidade de dar importância: sistemas de ficheiros, a protecção, a linguagem de interacção com o sistema.

Memória virtual
diversos algoritmos foram desenvolvidos com o objectivo de rentabilizar a utilização da memória física disponivel.
com a evolução do hardware de gestão de endereços existiu a possibilidade de trabalhar sobre um espaço de endereçamento virtual de dimensões muito superiores e independentes da memória física existente na máquina.

Tipos de Sistemas Operativos
os sistemas de tempo virtual, o tempo de execução dos programas não tem relação com o tempo cronológico exterior à máquina (os job-shop)
os sistemas de tempo real, os sistemas onde a noção de tempo é relevante, este têm como objectivo conseguir ao fim de um intervalo de tempo limitado e previamente especificado. No sistemas de tempo real podem ser englobados ainda os sistemas transaccionais, onde o tempo de resposta aos pedidos dos utilizadores continua a ser critico, se bem que numa escala mais lata e com muito menor responsabilidade associada.

Arquitectura do Sistema Operativo
existe uma decomposição do sistema em camadas funcionais. cada camada constitui um nível de abstracção que implementa uma máquina virtual com uma interface bem definida. sobre esta máquina pode constituir-se uma outra que utiliza os serviços da camada precedente para implementar o próximo nível de abstracção. Cada camada encapsula a implementação dos níveis inferiores fazendo que seja possivel modifica-los sem afectar as camadas exteriores.

níveis do sistemas operativo

gestão de processos: cada processo pode ser considerado como uma máquina virtual que executa um programa. multiplexa o processador entre os processos activos que se comportam como máquinas executando um programa. a gestão dos processos encarrega-se do tratamento das interrupções, despacho dos processo e da respectiva sincronização
gestão de memória: controla a utilização da memória física, e a sua relação com o espaço de endereçamento virtual onde se desenrola a execução dos processos
comunicação e entradas/saídas: os processos necessitam de comunicar para poderem gerir recursos comuns ou controlar a execução das aplicações
sistema de ficheiros: a gestão de ficheiros é responsável pela implementação eficiente de uma organização lógica que virtualiza os dispositivos de memória de massa
interface de sistema: funções sistema (as funções de sistema constituem a interface dos serviços providenciados pelas camadas internas do sistema operativo. as interfaces às funções são agrupadas em bibliotecas de rotinas que podem ser ligadas com os programas dos utilizadores de forma a permitir-lhes aceder aos mecanismos sistema); interpretador de comandos (a aplicação interpreta um conjunto de comandos que permitem fazer executar as operações mais vulgares de interacção com o sistema)
Os mecanismos de protecção também são presentes em todos os níveis. o sistema tem que garantir que os processos não podem realizar operações que ponham em risco o próprio funcionamento do sistema ou interfiram indevidamente com os objectos pertencentes a outros processos. os mecanismos de protecção podem ser implementados de diversas formas adaptadas ao tipo de informação manipulada em cada nível.

Modelo computacional
o modelo computacional é o conjunto de objectos do sistema operativo e as operações que os permitem manipular. é o conjunto de funções do sistema de que o programador dispõe para o desenvolvimento de aplicações e que lhe possibilitam estender a capacidade das linguagens de programação sequenciais. quando se entra no domínio das aplicações complexas, é necessário utilizar as capacidades oferecidas pelos sistemas operativos para obter o desempenho, a interactividade e o paralelismo de que numerosas aplicações necessitam.

Capítulo: 2 (a gestão dos processos) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

O pseudoparalelismo
os sistemas com múltiplas actividades paralelas são designados por sistemas concorrentes. a concorrência advém da existência de diversos fluxos de actividade que vão disputar acesso aos recursos dos sistema e que são limitados.
a multiplexagem do processador é feita internamente com critérios perfeitamente bem definidos.
um processo é um fluxo de actividade que desde a sua criação se executa continuadamente, excepto quando podemos considerar cada processo como uma máquina virtual que executa um determinado algoritmo definido pelo seu programa
o não determinismo como é feita a multiplexagem do processador é uma característica fundamental a ter em conta na utilização do modelo computacional. um programador que estruture uma aplicação em várias actividades concorrentes não pode assumir uma sequência predeterminada de utilização do processador.

Processador, processo e programa
um processo, é a entidade activa no sistema. executa um conjunto de acções que são determinadas por um programa. um processo pode durante a sua vida executar diversos programas. um processo é uma entidade activa controlada por um programa e que necessita de um processador para pode executar-se. um processo define:
um conjunto de operações: operações elementares (proporcionadas pelo hardware da máquina física. o sistema operativo não pode permitir que os processos interfiram com os seus próprios mecanismos de gestão. as instruções normalmente vedadas aos processos, relacionam.se com as interrupções entradas/saídas e mecanismos de protecção); e operações de interacção com as outras máquinas virtuais (os outros processos existentes no sistema)
um espaço de endereçamento: um processo executa-se dentro de um espaço de endereçamento bem delimitado, evitando que possa interactuar de forma indevida com os outros processos ou com ao próprio sistema operativo. surgem assim os mecanismos de protecção que o sistema operativo implementa. a protecção garante que um processo nunca poderá interferir com outro ou com o próprio sistema sem ser através de mecanismos seguros e fiáveis, controlados pelo próprio sistema.
um processo em cada instante encontra-se numa determinada etapa de execução. associado a cada processo existe um vector de estado ou contexto que mantém toda a informação de que os sistema operativo necessita para poder retomar a execução de um processo interrompido.  No contexto é memorizada a informação relacionada com o processador e com o ambiente de software no qual o processo se executa. a informação relativa ao processador é mantida no contexto, vulgarmente designado de hardware. o contexto de software contém informações que permitem gerir os recursos do sistema e conhecer os atribuídos a um processo e que são: identificação do processo e do utilizador, prioridade, estado do processo, periféricos utilizados, ficheiros abertos, programa em execução, directoria actual e por omissão, cotas de utilização dos recursos, contabilização da utilização dos recursos. O contexto de um processo é uma estrutura de dados, interna ao sistema operativo que mantém todas as informações sobre o estado e ambiente de execução, recursos utilizados e respectiva contabilização. A criação de processos estabelece uma relação hierárquica entre os processos, podendo o processo pai interferir sobre a execução dos seus filhos.
um programa não é mais que uma sequência de instruções sem actividade própria que seja executado em contexto de um processo. uma sequência coerente de instruções. um programa ou partes de um programa podem ser partilhados por diversos processos.

A função dos mecanismos de sincronização
determinadas aplicações só podem ser eficientemente implementadas quando suportadas por diversas actividades independentes. a decomposição do algoritmo em actividades paralelas permite também esperar obter um melhor desempenho global da aplicação. a sincronização da actividade dos processos podem acontecer por:
cooperação entre processos: que resulta da necessidade de interacção entre diversas actividades para executarem uma aplicação comum. por exemplo um processo só poderá prosseguir depois de outro ter executado uma determinada operação.
competição por um recurso: a competição pela obtenção de um recurso único ou limitado impõe também a necessidade de mecanismos de sincronização.
exclusão mutua: é um caso particular da competição por um recurso, o acesso exclusivo a uma estrutura de dados. A manipulação de estruturas de dados partilhadas deve ser realizada de forma atómica. as diferentes variáveis que constituem a estrutura de dados têm de ser actualizadas em conjunto, não se podendo permitir actualizações parciais (secção critica). é assim um caso particular de competição para um recurso único que corresponde ao direito de efectuar a actualização de uma estrutura de dados partilhada.

Semáforos
os semáforos devem ser considerados como parte integrante da camada do núcleo do sistema operativo que multiplexa o processador.
espera activa: o processo que espera a possibilidade de entrar na secção critica detém o recurso único no sistema, o processador, sem o qual não pode ser libertado o trinco. pare evitar esta situação, o processo que espera a libertação de um recurso deve ser bloqueado ficando no sistema memorizada a razão que motivou o bloqueio. o processo permanece nesse estado até que a libertação do recurso lhe permita prosseguir a execução.

espera activa
o semáforo implementa um mecanismos de sincronização sem espera activa. um semáforo é constituído por uma estrutura de dados composta por uma variável de controlo e por uma fila de espera destinada a conter os descritores dos processo bloqueados. os semáforos são facilmente implementados com base no mecanismo de exclusão mutua e numa lista onde são colocados os contextos dos processos bloqueados.
diagrama de estados do processo
estados dos processos:
em execução:
executável: à espera de uma oportunidade de dispor do processador
bloqueado: o processo é retirado da lista dos que concorrem para a obtenção do processador. significa retirar de execução, salvaguardar o seu contexto, marcar o seu estado como bloqueado e colocar o contexto na fila de espera que mantém os descritores dos processo bloqueados no semáforo.
desbloquear: corresponde a retirar o processo da fila de espera do semáforo, modificar o seu estado para executável e transferi-lo para a fila dos processo executáveis. o processo voltará a executar-se quando o despacho o seccionar.
O FIFO é o método mais concorrente para a gestão da fila do semáforo.

Cooperação entre processos
consiste em bloquear um processo P1 até que um processo P2 lhe assinale que uma determinada acção ou acontecimento se produziu. Para isso é necessário que exista num processo activo: bloquear-se à espera de um sinal a ser emitido por outro processo e activar um processo bloqueado.

Sincronização directa
Surge uma nova fila de espera onde o processo pode ser colocado. É usado um par de primitivas (Suspender e Acordar) que actua directamente sobre o processo bloqueando-o numa fila de processos suspensos ou acordando-o.
estado dos processos
Têm de existir mecanismos para evitar que um processo possa arbitrariamente suspender outro sobre o qual não detém qualquer privilégio, permitindo o uso de sincronização directa entre processos relacionados hierarquicamente.

Sincronização indirecta
Tem como vantagem garantir a igualdade de tratamento a todos os processos com os mesmos privilegiados. Surge o conceito de semáforo privado.

Capítulo: 3 (o núcleo do sistema operativo) – Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença

As interrupções
As interrupções permitem desviar assincronamente a execução de um programa para outro. Tem que haver: controlo de aceitação das interrupções (acontecimentos de maior prioridade interrompem os de menor); salvaguarda do contexto (o contexto do programa interrompido deve ser salvaguardada); selecção da rotina de tratamento da interrupção. As interrupções podem ser provocadas pelo hardware; por situações de excepção ou desencadeadas por instruções especiais.

A protecção estabelece-se a dois níveis: o primeiro está relacionado com a possibilidade de impedir aos processos utilizador a execução de instruções que podem afectar o funcionamento global da máquina; o segundo está relacionado com a unidade de gestão de memória, sendo que o espaço de endereçamento dos processos utilizador e dos sistema sejam perfeitamente delimitados, impedindo que os respectivos dados possam ser corrompidos.

O sistema operativo estrutura-se em camadas com as funções necessários ao modelo computacional: gestão de processos, gestão de memória, comunicação de entradas e saídas, sistema de ficheiros, suporte  utilizadores.

A gestão de processos –  executada no núcleo do SO
a gestão de processos activos pode ser: controlo das interrupções, despacho, sheduling e primitivas de sincronização.

A multiplexagem do processador é efectuada conjuntamente por duas entidades funcionais:
gestão do processador , escalonamento: implementa a politica global de gestão e optimiza a utilização de todos os recursos da máquina
e o despacho: tem por função determinar o próximo processo a executar-se e efectuar a comutação do contexto

assim a gestão dos processos tem que ter em conta o seguinte:
multiplexagem do processador:
funções de sincronização:
gestão de interrupções: as interrupções são o mecanismo que permite a comunicação assíncrona entre o processador e o sistema, e sem elas diminuiria a possibilidade de efectuar simultaneamente várias actividades. A mudança de contexto de uma actividade para outra ocorre devido à activação de uma interrupção que retira o controlo do processador ao processo em execução para o transferir para uma rotina de interrupção. As interrupções são globais, não são dirigidas a um determinado processo. As excepções relacionam-se apenas com o processo que as provoca e deverão, portanto, ser tratadas no seu contexto.
O processo tem um contexto de hardware (acumuladores, registo de uso geral, contador de programa, apontador de pilha, registo de estado do processador) e de software (identificador do processo e do utilizador, prioridade, estado do processo, periféricos utilizados, ficheiros abertos, programa em execução, directoria actual, quotas de utilização de recursos, contabilização da utilização dos recursos).
Os contextos dos processos activos são mantidos na Lista dos Processos Executáveis que procura reflectir o algoritmo de selecção do despacho.

Despacho
A rotina de despacho é chamada sempre que o processo actual deve ser comutado ou exista a possibilidade de ser comutado. a comutação de processos é o mecanismo básico para implementação da pseudoconcorrência, o seu funcionamento apenas necessita de uma gestão cuidada das interrupções.

Gestão do processador , escalonamento
o processador é um recurso crítico do sistema pelo que o escalonamento tenta optimizar a sua utilização mantendo-o tanto quanto possivel ocupado.

O escalonamento tem três objectivos:
procurar equilibrar a carga do sistema por forma a dar um serviço relativamente uniforme aos utilizadores interactivos
dotar o sistema de grande reactividade às condições externas
conseguir que o sistema execute determinadas acções em intervalos de tempo pré-determinados

Existem assim os seguintes modos/politicas de gestão do processador:
gestão do tempo partilhado (atribuir um período de tempo predeterminado a cada processo)
gestão do tempo real relaxado (soft real time)
gestão do tempo real estrito (hard real time)
preempção (politica que retira de execução um processo quando outro mais prioritário se tornou executável)
multilista (listas com diferentes prioridades onde os processo são colocados de acordo com o modo como utilizam o processador)
prioridades dinâmicas (modificação da prioridade dos processos em função do modo como utilizam os recursos)
quantum variável (modificação do valor do quantum para permitir reduzir o número de comutações do processador quando são executados processos de processamento intenso)

Tempo de execução partilhado (Tempo partilhado)
Para tornar equitativa a partilha do processador, a maioria dos sistemas apenas permite que o processo em execução utilize durante um intervalo de tempo limitado (time-slice ou quantum).
Surge um algoritmo de gestão que atribui a cada processo um quantum de tempo do processador gerindo circularmente (round robin) a lista dos processos executáveis. Esta solução tem um problema de facilmente conduzir a tempos de resposta elevados em situações de carga intensa, dado o tamanho sempre crescente da lista, e não permite reagir a qualquer acontecimento prioritário.

Multilista
A prioridade do processo varia durante a execução em função do modo como é utilizado o processador.
Um evolução do algoritmo anterior consiste na utilização de várias listas de acordo com o tipo de processo em execução. Assim os sistemas mistos de tempo partilhado e tratamento por lotes conciliam os dois tipos de gestão. O despacho implementa um algoritmo hierárquico seleccionando sempre um processo da lista mais prioritária. A lista mais prioritária corresponde aos processos que utilizam pouco tempo de interactividade (I/O bound). A utilização intensiva do processador conduz o processo para listas menos prioritárias, para onde serão naturalmente relegados os processos não interactivos que utilizam intensivamente o processador (CPU bound). Mas retirar sempre da lista mais prioritária pode conduzir a que os processos menos prioritários nunca tenham hipótese de se executarem (starvation).

Prioridades dinâmicas
A prioridade do processo pode ser alterada dinamicamente em função do comportamento no sistema. Uma optimização possivel em situações de carga é aumentar a duração do quantum, por forma a diminuir o número de comutações de contextos e aumentar a probabilidade de um processo terminar.

Preempção
designa a acção de retirar o processador a um processo em execução devido à existência de outro mais prioritário. isto permite que os processos mais prioritários reajam rapidamente a um acontecimento. a preempção é indispensável nos sistemas de tempo real sendo normalmente implementada nos sistemas multiutilizador. A preempção pode também ser associada ao esquema de partilha de tempo do processador, sendo consideradas várias politicas quanto à forma como o processo é reinserido na lista e ao valor dos seu próximo quantum.

Tempo real
Nos sistemas de tempo real a preempção é fundamental para garantir que um processo com elevada prioridade se execute quando é desbloqueado.

Implementação da Sincronização – secções criticas – inibição das interrupções
A solução mais simples para implementar a exclusão mútua consiste em eliminar a causa do problema impedindo a concorrência, para tal bastando inibir as interrupções durante a sequência de instruções de teste e posicionamento de uma variável partilhada. não havendo interrupções não é possivel dar-se uma troca de contexto de execução. Uma das desvantagens desta solução com a ineficácia da gestão da maquina que resulta da paragem de todas as acções externas susceptíveis de fazerem evoluir o estado do sistema.

Implementação da Sincronização – secções criticas – implementação dos trincos
os trincos podem ser usados para garantir a exclusão mutua.

Tags : , , ,

SO1 – comunicação inter-processos em unix com named pipes (FIFOs)

[so1t]

#comunicação inter-processos em unix com named pipes (FIFOs)

bibliografia especifica:
Begining linux programming: mathew & stones, caps 10,11, e 12

#FIFOs/Named pipes:
é um mecanismo semelhante aos pipes anónimos mas com capacidade de identificação própria (visivel a processos independentes)
utilizam-se normalmente ficheiros
os pipes anónimos têm a desvantagem de não poderem ser utilizado por processos não relacionados entre si
isto acontece porque os identificadores de acesso às extremidades dos pipes são meros handles (índices na tabela de ficheiros abertos) e assim sendo:
os pipes anónimos só fazem sentido no contexto do processo que os criou (ou processos filhos)
os pipes anónimos que também fazem uso de ficheiros, não têm acesso à tabela de ficheiros abertos de outros processos independentes, sendo também o descritor de um pipe criado por um processo distinto e não relacionado não acessível

surgem assim os pipes não anónimos, com nome (ou FIFOs)
são pipes: com um mecanismo de comunicação similar aos pipes, mas existe um nome que por ser utilizado por processos não relacionados para a obtenção de acesso ao FIFO
são pipes: similar ao uso de um ficheiro, em que qualquer processo pode abrir/ler/escrever se souber o seu pathname ( e tiver permissões)

os FIFOs usam as funções de ficheiros:
open (ficheiro que já existe)
write (ficheiro previamente aberto)
read (ficheiro previamente aberto)
mkfifo (cria um FIFO)
unlink (remove um FIFO)
fcntl (manipula as propriedades do FIFO)

#a sincronização
pode ser realizada de duas formas: bloqueante (comportamento síncrono) e não bloqueante (comportamento assíncrono)

FIFO para leitura bloqueado
open(ficheiro, O_RDONLY);
_FIFO fica bloqueado até que alguém o abra para escrita
_o uso do read() com o FIFO vazio bloqueia o processo

FIFO para leitura não bloqueado
open(ficheiro, O_RDONLY | O_NONBLOCK);
_retorna de imediato
_o usod o read() com o FIFO vazio retorna 0

FIFO para escrita bloqueado
open(ficheiro, O_WRONLY);
_FIFO fica bloqueado até que alguém o abra para leitura
_o uso do write() com o FIFO cheio bloqueia até poder escrever todos os dados

FIFO para escrita não bloqueado
open(ficheiro, O_WRONLY | O_NONBLOCK);
_retorna de imediato
_o usod o write() tem que ter em conta o seguinte:
__ bytes a escrever <= PIPE_BUF -> falha
__ bytes a escrever > PIPE_BUF -> escreve o que ainda couber e retornar

#Exemplo de aplicação do FIFO – o dicionário (cliente – servidor)

no cliente:
quando faz um pedido ao servidor tem que enviar sempre o nome do pipe para o qual o servidor deve responder;
deve criar o seu pipe antes de fazer o pedido;
não deve abrir o seu pipe para leitura, pois o servidor ainda não abriu para escrita, nem o conhece;
deve abrir o seu pipe como não bloqueantes e deve logo de seguida alterar para bloqueante (uso do fcntl)

no servidor:
o servidor deve abrir o seu pipe sempre para leitura, mesmo quando todos os clientes sairem (técnica keep-alive)

algoritmo do cliente:
abre o FIFO do servidor para escrita
cria o FIFO para receber a resposta
abre o FIFO das respostas para leitura (como não bloqueante)
muda o FIFO para bloqueante com a função fcntl
repete durante uma certa condição
obtém palavra a traduzir
constrói pergunta = palavra + nome do FIFI para a resposta
fica à espera da resposta (efectua uma leitura no FIFO para a resposta)
fecha o FIFO do servidor
fecha o FIFO para as respostas
remove o FIFO das respostas

algoritmo do servidor:
cria o FIFO do servidor para obter as perguntas
repete durante uma certa condição
obtém a próxima pergunta (efectua leitura do FIFO do servidor)
obtém a tradução da palavra
obtém a identificação do FIFO para a resposta abre o FIFO do cliente que enviou a pergunta
envia a resposta(escreve no FIFO para a resposta)
fecha o FIFO para a resposta
fecha o FIFO do servidor
remove o FIFO do servidor

dict.h

 

 

Tags : , ,

SO1 – Fundamentos de sincronização, problema de exclusão mútua e semáforos binários

Fundamentos de sincronização, problema de exclusão mútua e semáforos binários

motivos de sincronização:
processos e threads, que querem fazer uso dos mesmos recursos

usar a exclusão mútua:
porque se partilha zona de dados
apenas uma entidade activa deve utilizar o recurso
resolver então o problema de concorrência, do acesso concorrente a dados

surge então a secção critica:
que são o conjunto de operações que deve ser efectuado de forma atómica (invisível)

os semáforos:
são uma solução para garantir o acesso em exclusão mutua a uma secção critica
é um recurso que é controlado pelo sistema operativo
tem a capacidade para ter um “numero de autorizações”
tem na sua estrutura: o numero de autorizações, e a fila de espera (processos bloqueados)
tem como operações: esperar (requisita o recurso, diminui o contador) e assinalar (liberta o recurso, aumenta o contador)
os processos ficam bloqueados se não existirem mais autorizações disponíveis, ficando desbloqueado assim que houver uma autorização livre
este bloqueio ou desbloqueio é sempre transparente para o processo

e relembrar que bloquear um processo:
é retirado de execução
é salvaguardado o seu contexto (software e hardware)
o seu estado passa a bloqueados
fica em fila de espera

e relembrar que desbloquear um processo:
é retirado da fila dos bloqueados
passa para o estado de executável
vai para o fim de lista dos executáveis
é fica em execução quando o despacho o seleccionar

vantagens dos semáforos:
bloquear o processo não ocupa o processador
é um mecanismo justo
é compatível com politicas de prioridades
elimina a espera activa

a verificar semáforos vs mutex (resolve o problema de exclusão mutua)!!!

questões:
identifique problemas de sincronização (exclusão mútua)
identifique a forma de resolver a novel abstracto com recurso a semáforos/mutexs

Tags : ,

SO1 – conceitos básicos de Unix

#conceitos básicos de Unix
Cada programa que se executa ocorre no contexto de um processo
Um processo define: zona de memória, prioridade, identificação do utilizador, directoria de trabalho variáveis de ambiente
Um processo é criado sempre por outro processo
O processo filho adquire algumas das características do processo pai: variáveis de ambiente, ficheiros abertos, programa em execução
O processo pai pode controlar várias das características que o processo filho vai ter
As variáveis de ambiente definem aspectos operacionais do ambiente de trabalho do ambiente de execução dos programas e do ambiente do utilizador

Gestão de utilizadores
/etc/passwd
contem a identificação das contas de utilizador
está em formato “clear text”

/etc/group

/etc/shadow
contem a password dos utilizadores, acesso apenas pelo administrador

/etc/gshadow

comandos especiais para lidar com execução privilegiada temporária:
setuid, set user ide upon execution
setgig
sudo

Tags : ,

SO1 – introdução_ programa

Parte teórica
Introdução ao ambiente unix/linux
_aspectos gerais do sistema: lógica de funcionamento e operação
_sistema de ficheiros, componentes, estrutura
_operação em linha de comandos
_sheel scripintg
_aspectos gerais do sistema: lógica de funcionamento interno e configuração, permissões e segurança

Modelo de programação UNIX
_criação e gestão de processos
_mecanismo de sinais
_mecanismos de comunicação: named pipes (aplicações cliente servidor com named pipes)
_programação multithreaded
_sincronização de exclusão com semáforos binários

conceitos fundamentais de sistemas operativos
_conceitos básicos. objetivos e gestão da máquina
_elementos constituintes de sistemas operativos
_gestão de processo. algoritmos de escalonamento
_gestão de memória. mecanismos de algoritmos de gestão de memória. memória real e memória virtual

Parte prática
Programação para Unix (Linux)
_gcc/gdb. processo de compilação
_criação e gestão de processos
_notificações assíncronas: sinais
_named pipes: aplicações cliente servidor
_multi-threading e semáforos binários

Operarão do sistema Unix (com Linux)
_comandos Unix de consola /linha de comandos
_Introdução a shell scripting em Bash

Bibliografia
Fundamentos de Sistemas Operativos, José Alves Marques, Paulo Guedes – 3ª edição – Editorial Presença
Sistemas Operativos, José Marques, Paulo Ferreira, Carlos Godinho, Luís Veiga, Rodrigo Rodrigues, FCA
Operating Syems Concepts – 6-º edição – Addison-Wesley
Operating Systems: internal and Design Principles (3º edição) – Prentice-Hall
Begining Linux Programming, Wrox Press
Unix curso completo João Garrot, Jorge Amador, João Castos – FCA

Tags : ,

SO1 – Escalonamento – Conceitos e Algoritmos

Escalonamento – Conceitos e Algoritmos

a multiprogramação simples consegue-se com:
dispositivos de memoria secundária e rápida;
boa gestão de E/S por parte do SO
mecanismo de gestão e partilha de memória
mecanismos no SO para partilhar e gerir recursos partilhados na maquina, entre todos os programas que estão em execução

a multiprogramação simples (não preemptiva: que prevê ou antecipa situações),
baseia-se na cedência voluntária (que pode ou não acontecer) do CPU, por parte do programa que está a ser executado

a multiprogramação preemptiva (ou “interactiva” ou “de tempo partilhado”),
o sistema força a cedência do CPU por parte do programa actualmente em execução, passado a CPU a outro programa e posteriormente voltando ao programa inicial

exemplo de algortimos preemptivos:
fim de quantum (interrupção do relógio, tempo partilhado)
processo mais prioritário
processo mais curto

objetivos do escalonamento preemptivo:
permitir que processos prioritários possam reagir rapidamente a um acontecimento
exemplo: windows NT, já o MSDOS é não preemptivo

exemplo de algortimos nao preemptivos:
o programa que terminou
o programa pediu acesso a um semáforo que estava fechado
o programa requisitou uma operação de E/S demorada

assim a preempção pode ser baseada em:
_intervalos de tempo fixo (um bocado de tempo à vez de todos)
_prioridade (o mais importante primeiro)
_critérios de performance (o mais pequeno/rápido primeiro)

o escalonamento multiprogramado simples:
consegue aproveitar esses tempo de E/S sem garantia que um programa impede outros de serem executados
aproveita melhor o CPU do que o monoprocessamento

o escalonamento multiprogramado:
o sistema consegue aproveitar os tempos de I/O de um programa para executar instruções de outros programas
existe a cedência do CPU

mas se existir um escalonamento preemptivo, baseado em intervalo de tempo, o utilizador obtém a garantia que todos os programas têm oportunidade de execução concorrente

Evolução dos sistemas operativos e do escalonamento
processamento em série (eniac)
processamento em lote on-line (uso de cartões perfurados junto do CPU, só existe um processo em cada instante)
processamento em lote off-line (uso de computadores auxiliares para ler os cartões perfurados, falhas na sincronização entre estes e o CPU, só existe um processo em cada instante)
processamento em lote o spooling (uso de mecanismos de interrupção, uso de discos)
multiprogramação (são sistemas de lote multi-programados ou concorrentes) e interactividade (são sistemas de tempo partilhado/time-sharing, com rotatividade de processos. Existe a pseudo execução em paralelo dos processos)

Parte 3 – conceitos de multiprogramação
o pseudo-paralelismo, consiste em ter várias actividades a decorrer ao mesmo tempo (em sistemas multiprogramados)
(existe um tempo de vista pelos processos e o que é a real desdestruição do processador)

Monoprocessamento vs multiprogramação simples

com esta acção de mutilprogramação simples o tempo total de execução diminui

Tempo não partilhado vs tempo partilhado (ou muliprogramação simples VS multiprogramação preemptiva)

resultados visíveis são errados, já que apesar do tempo de execução no tempo não partilhado (multiprogramação simples) ser menor que no tempo partilhado (multiprogramação preemptiva) o tempo apenas é explicado pelo aumento do numero de trocas entre os processos

Resumo das figuras:
sistemas multi-programados: optimização do processador
sistemas de tempo partilhado: optimizar a interactividade

As prioridades
surgem nos algoritmos de escalonamento e permite ao processo ser atendido que não fazendo uso do FIFO

As prioridades podem ser:
prioridades fixas (tem em conta o tipo de processo, associadas à importância dos acontecimentos. por exemplo: processo paginador)
prioridades dinâmicas (têm em conta o comportamento do processo, com o objectivo de ser justo, evitar a monopolização ou starvation. Neste caso são dadas prioridades aos processo que melhor se encaixam nos critérios de optimização global da máquina)

Os escalonadores
Os escalonadores podem ser:
escalonador de longo prazo (responsável por admitir um processo a execução. quantos mais processo maior a latência da máquina)
escalonador de médio prazo (através de um algoritmo determina quando e qual o processo, no estado de executável, que deve obter o processador)
escalonador de curto prazo (ou despacho, comuta os processos, após decisão do escalonado de médio prazo). O tempo de latência do despacho = tempo de parar um processo + tempo de recomeçar um processo

Quando se comuta de processo temos que ter em conta várias actividades:
invocação do despacho
salvaguarda do contexto do processo que estava a ser executado
recuperação do contexto para colocar o novo processo em execução
saltar para a localização do processo

Parte 4 – conceito de estado de processos

Modelo de dois estados:
faz uso do algoritmo de escalonamento, para determinar qual de dois processos que fica com o processo primeiro

Modelo de três estados:
surge o estado “novo” – serve para manter a informação acerca do processo, cuja criação foi pedida mas não foi admitido a execução
surge o estado “terminado” – serve para manter a informação acerca do processo, já terminado mas ainda não foi aproveitado
surge o estado de “suspenso” – pedido pelo próprio processo ou de outro processo

Modelo completo:

Parte 5 – conceitos usados em escalonamento

os diferentes algoritmos de escalonamento estão relacionados com respostas diferentes à forma como a gestão do processador tem que ser feita (desempenho, suporte, fiabilidade, robustez..).
qualquer algoritmo de escalonamento tem que manter todos os recursos do sistema. igualmente ocupados (para evitar picos de utilização)

aquando da gestão do processador tem que ter em conta os seguintes conceitos:
previsibilidade,
equilíbrio dos recursos,
justiça e starvation,
processos I/O bound e CPU bound

Existem dois tipos de processos/threads:
processos/threads I/O bound (que fazem muitas operações de E/S, bloqueando-se frequentemente)
processos/threads CPU bound (utilizam intensivamente o processador, quase nunca se bloqueando)

a Justiça
todos os processos/threads devem ter a mesma utilização dos recursos do sistema

a starvation
Surge quando o processo/thread nunca obtém o recurso pretendido, ou porque o recurso esta bloqueado ou porque o próprio processo/thread esta bloequeado
solução do starvation:
uso de prioridades dinâmicas (aumentar a prioridade para processos que estão à mais tempo à espera)

Parte 6 – indicadores de desempenho

este tipo de indicadores permitem que se verifique como está a eficiência com que o sistema gere a informação

exemplos de métricas/indicadores:
utilização do processador (importante para sistemas multiprogramados),
throughput (quantidade de processos concluídos por unidade de tempo)
tournaround (tempo de execução/conclusão. Desde a criação do processo/thread até à sua conclusão)
prazos (aplica-se em sistemas de tempo real). Exemplo:
três processos com um prazo de 15 minutos e outros com 3 com um prazo e 120 minutos
algoritmoA: todos os prazos são cumpridos à tangente
algoritmoB: os prazos dos processos de 15 minutos são ligeiramente excedidos enquanto os de 120 minutos são cumpridos com grande margem. Aparentemente o algortimo B seria melhor pois, em média, o throughput e o turnaround são melhores, mas a percentagem de prazos cumpridos é pior, pelo que o algortimo A é melhor

latência (tempo de resposta. Só se aplica a sistemas multiprogramados interactivos. É mais significado em sistemas interactivos que o throughut)
razão de penalização (é a razão entre o tempo total do processo e o tempo que demoraria se não tivesse outros processos)
exemplo:

tempo de espera (tempo total que um processo passou para o estado de executável)
previsibilidade (medida qualitativa do que quantitativa, e de implementação complexa, já que deve sempre necessitar do mesmo tempo para se executar independentemente da carga)

O escalonador tem que ser capaz de:
minimizar a latência,
maximizar o throughput,
maximizar o equilibro de uso dos periféricos,
justiça

Mas podem surgir problemas por via de:
dispositivos de E/S
optimização levar à starvation.
ocorrência de deadlocks

Parte 7 – algoritmos de escalonamento
Os algortimos de escalonamento podem ser:
preemptivos (round robin e SRT e Feedback)
não preemptivos (FCFS, SPN e HRRN) -> não servem para sistemas multiprogramados de tempo partilhado

algoritmo FCFS – Firts Come First Served
em que:
favorece o CPU Bound bloqueando os processos I/O Bound
não optimiza a utilização de dispositivos
para processos/threads nao interactivas, que têm o mesmo tempo de execução
tempo de conclusão não é importante

algoritmo RoundRobin
em que:
tem por base um quantum (intervalo de tempo)
força a interrupção de uma thread ao fim de um tempo
tempo partilhado em sistemas multiprogramados
é justo, independentemente do tamanho dos processos todos são atendidos da mesma forma
não surge o starvation
tournaround e tempo de espera melhors que o FCFS, quando a duração dos processos varia

Exemplo1 de FCFS e RoundRobin em que:
três processos do tipo CPU bound
existem um quantum
a duração do processo A=12q, do B=3q e do C=3q
ordem de chegada: A, instante 0; B, instante 1; C, instante 2

Exemplo2 de FCFS e RoundRobin em que:
duração dos processo igual para todos = 6q

algoritmo SPN, Shortest Process Next
em que:
o próximo processo a ser executado é o que se espera que demore menos tempo;
não é preemptivo, não serve para sistemas multiprogramados,
situação de starvation dos processos longos face aos curtos
tem um melhor tournaround

algoritmo SRT, Shortest Remaining Time
em que:
o próximo processo/thread a ser executada é aquele cujo tempo restante de processamento é menor,
preemptivo (se um processo que estava bloqueado passar a executável e tiver tempo restante de processamento menor do que actualmente em execução, ocorre a preempção),
não é baseado em quantum
dificuldade: e qt tempo demoram os processos

algoritmo HRRN, Highest response Ratio Next
em que:
eliminar a starvation dos processos longos
valoriza o tempo esperado e a idade do processo no sistema
escolhe sempre o processo que tiver maior response ratio

RR (response ratio) = tempo de espera (w) + tempo de execução esperado (s) / tempo de execução esperado (s)

algoritmo de Feedback
em que:
quando quando não é possivel estimar o tempo de processamento
faz-se uso de uma análise na máquina no passado, para prever o que vai acontecer
faz uso de prioridades dinâmicas: a prioridade vai diminuindo ao longo da idade do processo
faz uso de quantum variável: atribui um quantum maior ao processo que esteja a ser penalizado e vice-versa

A escalabilidade:
uma solução em engenharia é escalável, se o custo for proporcional à dimensão do problema
um algoritmo de escalonamento é escalável se o seu overhead de execução for proporcional ao numero de processo em execução

Para evitar que o escalonamento se torne não escalável usamos a técnica de escalonamento multi-lista: agrupando os processos executáveis em conjuntos, promovendo os que estão mais perto do que está a ser analisado (primeiro nível e despromovendo para o nível mais baixo os que estão no primeiro nível.

coisas maybe importantes:
descrever o que é um quantum
o que é a preempção
conceito de justiça
o que é o CPU bound e i/o bound
o que é o tempo de espera, throughput, penalty ratio, conceito de justiça,
descrever o modo de funcionamento de cada um dos algoritmos estudados,
objectivos do escalonamento e duas principais dificuldades na obtenção de uma gestão óptima absoluta
explicar a influencia da preempção ou ausência dela num sistema
comparar dois algoritmos, para um cenário, e explicar qual o melhor e porquê
descrever a influencia da optimização de alguns indicadores de desempenho sobre os outros..
calcular tempos e indicadores..

Tags :

Sistemas operativos – o inicio (SO1)

Instalar o software:
VirtualBox-5.2.18-124319-Win (LINK)
e o Oracle_VM_VirtualBox_Extension_Pack-5.2.18 (LINK)

de seguida criar uma virtualização do sistema operativo debian-9.5.0-i386-xfce-CD-1 (LINK) ou o torrent (LINK)

Aquando da instalação do VirtualBox em Windows ter em atenção:
desligar primeiro o sistema Hyper-V do windows;
e durante a instalação do VirtualBox solicitar/aceitar a instalação das extensões.

A configuração da máquina virtual deve ser feita tendo em conta os seguintes aspectos:
reservar/verificar 10 gigas de espaço em disco;
colocar a imagem do disto numa pasta perto do root (sem caracteres complexos);
instalar na maquina virtual um SSH server;
sistema de caracteres de UTF8;

já depois de instalado é necessário fazer:
sudo pico /etc/apt/sources.list e comentar o cdrom com #
apt install sudo
adduser username sudo
sudo apt update
sudo apt upgrade

Na interface do VirtualBox fazer clique em devices e escolher insert guest aditions..  e depois na janela de terminal fazer:
cd /media/cdrom
sudo sh ./VboxLinuxAdditions.run

instalar ferramentas de desenvolvimento:
sudo apt-get install build-essential module-assitant dkms
e
sudo m-a prepare

instalação de software adicional na máquina virtual:
1. (netbeans)
na máquina virtual fazer o download do ficheiro e na linha de comandos escrever sudo sh netbeans-8.2-cpp-linux-x86.sh

2. (cliente dropbox)
para instalar o dropbox (32 bits)no debian fiz o seguinte:
cd ~ && wget -O – “https://www.dropbox.com/download?plat=lnx.x86” | tar xzf –
e para correr
~/.dropbox-dist/dropboxd
ou
activar o autostart dropbox autostart y

se for de 64 bits é fazer:
cd ~ && wget -O – “https://www.dropbox.com/download?plat=lnx.x86_64” | tar xzf –

3.( SSH server)
para instalar o SSH server fiz o seguinte:
sudo apt-get install openssh-server
e para correr
sudo systemctl status ssh
ou
sudo systemctl start ssh
e para parar
sudo systemctl stop ssh
e retirar a sua inicialização
sudo systemctl disable ssh

4.(instalar o ncurses):
sudo apt-get install libncurses5-dev libncursesw5-dev
não esquecer que para compilar com o ncurses é necessário fazer:
gcc E1.c -o E1 -lncurses

e Coisas importantes a rever:
sistemas de ficheiros em disco, particionamento, processo de arranque da máquina, sectores MBR e sector boot
Sistema de ficheiros unix, Partições: /, /boot, /home, /etc, /dev, /opt
Comando básicos Unix para navegação no sistema de ficheiros
Gestão de software com apt / apt-get
Noção iniciais de atributos de utilizadores e de segurança em ficheiros Unix. Comando sudo

 

Tags : ,

exercicios de SO – Exemplo Teste Bash