Mudanças entre as edições de "SOP-EngTel 2018 2"

De MediaWiki do Campus São José
Ir para navegação Ir para pesquisar
(Criou página com '= Sistemas Operacionais = *'''Professor:''' André D'Amato *'''Encontros:''' Segundas às 15:40 e quintas às 13:30 no LabSid. *'''Atendimento paralelo:''' a definir. *[[S...')
 
Linha 10: Linha 10:
  
  
 +
<!--
  
 
== Listas de exercícios ==
 
== Listas de exercícios ==
Linha 1 457: Linha 1 458:
  
 
{{collapse bottom}}
 
{{collapse bottom}}
 +
 +
-->

Edição das 13h15min de 26 de julho de 2018

Sistemas Operacionais

  • Professor: André D'Amato
  • Encontros: Segundas às 15:40 e quintas às 13:30 no LabSid.
  • Atendimento paralelo: a definir.


|}

Trocas de mensagens com pipes (Atividade 3)

Trocas de mensagens com pipes

Troca de mensagens

Um mecanismo disponibilizado por sistemas UNIX para troca de mensagens entre processos é o PIPE. Pipes são mecanismos de comunicação indireta onde mensagens são trocadas através de mailboxes. Cada mailbox possui um identificador único, permitindo que processos identifiquem o canal de comunicação entre eles. O fluxo de mensagens em um Pipe é:

  • unidirecional: sobre um mesmo pipe, apenas um processo envia mensagens e um processo recebe mensagens;
  • FIFO: as mensagens são entregues na ordem de envio;
  • não-estruturado: não há estrutura pré-definida para o formato da mensagem.

No UNIX, pipes são inicializados através da SystemCall pipe, que possui a seguinte sintaxe:

  • int pipe(int pipefd[2]): pipe inicializa um novo pipe no sistema e retorna, no array pipefd, os descritores identificando cada uma das pontas do pipe. A primeira posição do array, i.e. pipefd[0], recebe o descritor que pode ser aberto apenas para leitura, enquanto a segunda posição do array, i.e. pipefd[1], recebe o descritor que pode ser aberto apenas para escrita. A função retorna zero no caso de sucesso, ou -1 se ocorrer erro.

As primitivas send/receive para uso de um pipe no UNIX são implementadas por SystemCalls read/write, conforme segue:

  • ssize_t read(int fd, void *buf, size_t count): “puxa” dados do pipe identificado pelo descritor fd. Os dados recebidos são os apontados pelo ponteiro buf, sendo count a quantidade máxima de bytes a serem recebidos. A função retorna o número de bytes recebidos.
  • ssize_t write(int fd, const void *buf, size_t count): “empurra” dados no pipe identificado pelo descritor fd. Os dados transmitidos são os apontados pelo ponteiro buf, sendo count a quantidade de bytes a serem transmitidos. A função retorna o número de bytes transmitidos.

Abaixo há um exemplo de programa criando um pipe e compartilhando os descritores entre dois processos (criados via fork()).

#include <unistd.h>   
#include <fcntl.h>
#include <stdio.h>
#include <string.h>

char *message = "This is a message!!!" ;

main()
{
    char buf[1024] ;
    int fd[2];
    pipe(fd);    /*create pipe*/
    if (fork() != 0) { /* I am the parent */
        write(fd[1], message, strlen (message) + 1) ;
    }
    else { /*Child code */
        read(fd[0], buf, 1024) ;
        printf("Got this from MaMa!!: %s\n", buf) ;
    }
}
  • Exercício 1: construa um “pipeline”. Crie um programa que conecta 4 processos através de 3 pipes. Utilize fork() para criar vários processos.
  • Exercício 2: cópia de arquivo. Projete um programa de cópia de arquivos chamado FileCopy usando pipes comuns. Esse programa receberá dois parâmetros: o primeiro é o nome do arquivo a ser copiado e o segundo é o nome do arquivo copiado. Em seguida, o programa criará um pipe comum e gravará nele o conteúdo do arquivo a ser copiado. O processo filho lerá esse arquivo do pipe e o gravará no arquivo de destino. Por exemplo, se chamarmos o programa como descrito a seguir:
$ FileCopy entrada.txt copia.txt
o arquivo entrada.txt será gravado no pipe. O processo filho lerá o conteúdo desse arquivo e o gravará no arquivo de destino copia.txt. Escreva o programa usando os pipes da API POSIX no Linux.


Exercício (Algoritmo de Peterson)

Exercício (Algoritmo de Peterson)

Exercício 1: Sincronize o código a seguir, de maneira que o processo pai imprima apenas os números impares e o processo filho os números pares. Para isso utilize o algoritmo de Peterson visto em aula. Utilize memória compartilhada para comunicação entre os processos.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
  
main()
{    
	     	

	if (fork() != 0) { /* I am the parent */
		int i;	
			
		for(i = 0;i < 10;i=i+2){	
			printf("Processo pai %d  \n", i);      
	   			
		}	
		

	}

	else { /*Child code */
	        int i;                
		for(i = 1;i < 10;i=i+2){		    		
			printf("Processo filho %d  \n", i);    
		
	        }
		
			         	
	}
	
	exit(0);

}


Exercício 2: Considerando o exercício anterior faça a mesma sincronização, no entanto desta vez utilize a modelagem em software do TSL.

  • Em sua experiência, depois de testar diversas vezes as execuções de suas soluções baseadas no algoritmo de Peterson e Tsl, qual sua opinião sobre as abordagens?

Explique seu raciocínio.


Exercício (Semáforos)

Exercício (Semáforos)

Exercício 1: Sincronize o código a seguir, de maneira que o processo pai imprima apenas os números impares e o processo filho os números pares. Para isso utilize Semáforos de acordo com a implementação em semaforo.h. Utilize memória compartilhada para comunicação entre os processos.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
  
main()
{    
	     	

	if (fork() != 0) { /* I am the parent */
		int i;	
			
		for(i = 0;i < 10;i=i+2){	
			printf("Processo pai %d  \n", i);      
	   			
		}	
		

	}

	else { /*Child code */
	        int i;                
		for(i = 1;i < 10;i=i+2){		    		
			printf("Processo filho %d  \n", i);    
		
	        }
		
			         	
	}
	
	exit(0);

}


SEMAFORO.H


int criar_semaforo(int val, int chave)  
{
     int semid ;
	
     union semun {
          int val;
          struct semid_ds *buf ;
          ushort array[1];
     } arg_ctl ;
	
     key_t ft = ftok("/tmp", chave);
 	
     semid = semget(ft,1,IPC_CREAT|IPC_EXCL|0666);
     if (semid == -1) {
	  semid = semget(ft,1,0666); 
          if (semid == -1) {
               perror("Erro semget()");
               exit(1) ;
          }
     }
     
     arg_ctl.val = val; //valor de início
     if (semctl(semid,0,SETVAL,arg_ctl) == -1) {
          perror("Erro inicializacao semaforo");
          exit(1);
     }
     return(semid) ;
}

void P(int semid){

     struct sembuf *sops = malloc(10*sizeof(int));
     sops->sem_num = 0;
     sops->sem_op = -1;
     sops->sem_flg = 0;
     semop(semid, sops, 1);  
     free(sops);

}


void V(int semid){

     struct sembuf *sops = malloc(10*sizeof(int));
     sops->sem_num = 0;
     sops->sem_op = 1;
     sops->sem_flg = 0; 
     semop(semid, sops, 1);  
     free(sops);

} 



void sem_delete(int semid) 
{
     	
     if (semctl(semid,0,IPC_RMID,0) == -1)
       perror("Erro na destruicao do semaforo");
}
Programação concorrente (Atividade 4)

Programação concorrente (Atividade 4)

POSIX Threads

A API POSIX disponibiliza uma biblioteca de threads chamada pthread. As threads são implementadas pela estrutura pthread_t, e manipuladas pelas funções (acesse as man-pages das chamadas para maiores detalhes):

  • pthread_create: cria uma thread;
  • pthread_kill: força a terminação de uma thread;
  • pthread_join: sincroniza o final de uma thread (qual a diferença/semelhança com o wait que usamos para processos?);
  • pthread_exit: finaliza uma thread.

Para utilizar estas funções é necessário linkar o programa à libpthread (-lpthread). A classe C++ abaixo abstrai estas operações:

#ifndef __thread_h
#define __thread_h

#include <pthread.h>
#include <signal.h>

class Thread
{
public:
    Thread(int ( * const entry)(int), int arg) {
	if(pthread_create(&thread, 0, (void*(*)(void*))entry, (void *)arg))
	    thread = 0;
    }
    ~Thread() {}

    int join(int * status) { return pthread_join(thread, (void **)status); }
    friend void exit(int status = 0) { pthread_exit((void *) status); }

private:
    pthread_t thread;
};

#endif


POSIX pthread mutex

A biblioteca pthread implementa um tipo pthread_mutex_t, que garante a exclusão mútua entre threads. Estes mutex são manipulados através das funções (acesse as man-pages das chamadas para maiores detalhes):

  • pthread_mutex_lock: acessa um mutex.
  • pthread_mutex_trylock: tenta acessar um mutex (retorna valor indicando sucesso ou falha no lock).
  • pthread_mutex_unlock: libera um mutex.


#ifndef __mutex_h
#define __mutex_h

#include <pthread.h>

class Mutex
{
public:
    Mutex() {}
    ~Mutex() {}

    void lock() { pthread_mutex_lock(&mut); }
    bool try_lock() { return (pthread_mutex_trylock(&mut) == 0); } // true when succeeds.
    void unlock() { pthread_mutex_unlock(&mut); }

private:
    pthread_mutex_t mut;


};

#endif


POSIX Semaphores

Nos sistemas POSIX, semáforos são implementados pelo tipo sem_t e manipulado através das funções (acesse as man-pages das chamadas para maiores detalhes):

  • sem_init: inicializa um semáforo;
  • sem_destroy: destroy um semáforo;
  • sem_wait: implementa a operação p;
  • sem_post: implementa a operação v.

Para utilizar estas funções é necessário linkar o programa à librt ou à libpthread (-lrt ou -lpthread). A classe C++ abaixo abstrai estas operações:


#ifndef __semaphore_h
#define __semaphore_h

#include <semaphore.h>

class Semaphore
{
public:
    Semaphore(int i = 1) { sem_init(&sem, 0, i); }
    ~Semaphore() { sem_destroy(&sem); }

    void p() { sem_wait(&sem); }
    void v() { sem_post(&sem); }

    operator int()
    {
        int ret;
        sem_getvalue(&sem, &ret);
        return ret;
    }

private:
    sem_t sem;
};

#endif

Exemplo de uso do operator:

Semaphore sem;
cout << (int)sem << endl;



Exercício 1

O programa abaixo cria 5 threads, e cada uma destas threads atualiza uma variável global (memória compartilhada).

#include <iostream>
#include "thread.h"

#define NUM_THREADS 5

using namespace std;

int saldo = 1000;

int AtualizaSaldo(int n)
{
	int meu_saldo = saldo;
	int novo_saldo = meu_saldo + n*100;
	cout << "Novo saldo = " << novo_saldo << endl;
	saldo = novo_saldo;
}

int main()
{
	Thread * threads[NUM_THREADS];

	for(int t = 0; t < NUM_THREADS; t++)
		threads[t] = new Thread(&AtualizaSaldo, t+1);

	

	cout << "Saldo final é " << saldo << "." << endl;
}


  1. Compile este programa. Você precisará da classe Thread.
  2. Execute este programa várias vezes. Ele funciona? Será que ele gera as saídas esperadas?
  3. Identifique as seções críticas do programa.
  4. Corrija o programa utilizando mutex. Utilize a classe Mutex implementada na aula passada.
  5. Analise a função AtualizaSaldo() com a sua solução. Lembre-se que o uso do mutex implica em apenas uma thread acessar a seção crítica por vez, enquanto outras threads ficam bloqueadas, esperando. Disso vem que, quanto menor o trecho de código entre um lock e um unlock, menos tempo uma thread necessita ficar esperando.
  6. Modifique o programa para usar um semáforo binário ao invés de um mutex em sua solução. Utilize a classe Semaphore da aula passada.
Exercício 2

O programa abaixo manipula uma matriz de tamanho MxN (veja os defines para o tamanho da matriz). A função SumValues soma todos os valores em uma linha da matriz. A linha a ser somada é identificada pela variável i. Modifique o programa principal (main) nos locais indicados para:

  1. Criar N threads, uma para somar os valores de cada linha.
  2. Receber o resultado do somatório de cada linha e gerar o somatório total da matriz.
  3. Analise o programa: há problemas de sincronização que precisam ser resolvidos? Se sim, resolva-os.
#include <iostream>
#include "thread.h"

/* number of matrix columns and rows */
#define M 5
#define N 10

using namespace std;

int matrix[N][M];
Thread *threads[N];


/* thread function; it sums the values of the matrix in the row */
int SumValues(int i)
{
	int n = i; /* number of row */
	int total = 0; /* the total of the values in the row */
	int j;
	for (j = 0; j < M; j++) /* sum values in the "n" row */
		total += matrix[n][j];
	cout << "The total in row" << n << " is " << total << "." << endl;
	/* terminate a thread and return a total in the row */
	exit(total);
}

int main(int argc, char *argv[])
{
	int i, j;
	int total = 0; /* the total of the values in the matrix */

	 /* initialize the matrix */
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			matrix[i][j] = i * M + j;

	/* create threads */
	/* COLOQUE SEU CÓDIGO PARA CRIAR AS THREADS AQUI! */

	/* wait for terminate a threads */
	/* COLOQUE SEU CÓDIGO PARA PEGAR O SOMATÓRIO DE LINHAS E TOTALIZAR A SOMA DA MATRIZ AQUI! */

	cout << "The total values in the matrix is " << total << endl;

	return 0;
}
Problemas clássicos de coordenação de processos

Problemas clássicos de coordenação de processos

Produtor/Consumidor

O problema clássico Produtor/Consumidor consiste em dois fluxos de execução (threads/processos), sendo que um dos fluxos (consumidor) só pode executar a partir do momento em que seus dados de entrada foram produzidos pelo outro fluxo (produtor).

  • DESAFIO 1: O programa abaixo implementa um produtor/consumidor utilizando semáforos para sincronização. Contudo, as chamadas para as operações v e p foram removidas, conforme comentários no código. Corrija este programa, garantindo a coerência da variável compartilhada buffer.
  • DESAFIO 2: Após resolver a sincronização no acesso ao buffer, utilize um Mutex para resolver a concorrência no acesso ao cout no programa abaixo.
#include <iostream>
#include "thread.h"
#include "semaphore.h"
 
using namespace std;
 
const int REP = 5;
char buffer;
 
Semaphore empty(1);
Semaphore full(0);
 
int producer(int n)
{
    cout << "Producer was born!\n";
 
    // Faltam, no laço abaixo:
    //  - uma chamada para empty.p()
    //  - uma chamada para full.v()
    char data = -1;
    for(int i = 0; i < REP; i++) {

	cout << "Producing ...\n";
	data = (char) i + 0x61;

	buffer = data;
	cout << "Stored... " << data << endl;

    }

    return n;
}
 
int consumer(int n)
{
    cout << "Consumer was born!\n";
 
    // Faltam, no laço abaixo:
    //  - uma chamada para full.p()
    //  - uma chamada para empty.v()
    char data = -1;
    for(int i = 0; i < REP; i++) {

	cout << "Retrieving ...\n";
	data = buffer;

	cout << "Consumed... " << data << endl;

    }

    return n;
}
 
int main()
{
    cout << "The Producer x Consumer Problem\n";
 
    Thread prod(&producer, REP);
    Thread cons(&consumer, REP);
 
    int status;
    prod.join(&status);
    if(status == REP)
	cout << "Producer went to heaven!\n";
    else
	cout << "Producer went to hell!\n";
 
    cons.join(&status);
    if(status == REP)
	cout << "Consumer went to heaven!\n";
    else
	cout << "Consumer went to hell!\n";
 
    return 0;
}
Jantar dos Filósofos

O problema clássico Jantar dos Filósofos consiste em que n fluxos (n filósofos) disputam n recursos (n talheres). No problema, para conseguir "jantar" (ou executar), cada filósofo precisa pegar dois talheres adjascentes a ele. Cada recurso é compartilhado por dois filósofos.

  • DESAFIO: O programa abaixo implementa um Jantar dos Filósofos utilizando semáforos para sincronização. Contudo, as chamadas para as operações v e p foram removidas, conforme comentários no código. Re-insira as operações no código e analise a solução. Esta modificação é suficiente para garantir que não haverá deadlock? Se sim, mostre o porque. Se não, proponha uma solução completa.
#include <iostream>
#include "thread.h"
#include "semaphore.h"

using namespace std;

const int DELAY = 10000000;
const int ITERATIONS = 5;

Semaphore chopstick[5];

int philosopher(int n)
{
    cout << "Philosopher " << n << " was born!\n";

    int first = (n < 4)? n : 0; // left for phil 0 .. 3, right for phil 4
    int second = (n < 4)? n + 1 : 4; // right for phil 0 .. 3, left for phil 4

    // Foram removidos do laço abaixo:
    //  - uma chamada para chopstick[first].p()
    //  - uma chamada para chopstick[second].p()
    //  - uma chamada para chopstick[first].v()
    //  - uma chamada para chopstick[second].v()
    for(int i = 0; i < ITERATIONS; i++) {
	cout << "Philosopher " << n << " thinking ...\n";
	for(int i = 0; i < DELAY * 10; i++);

	cout << "Philosopher " << n << " eating ...\n";
	for(int i = 0; i < DELAY; i++);
    }

    return n;
}

int main()
{
    cout << "The Dining-Philosophers Problem\n";

    Thread * phil[5];
    for(int i = 0; i < 5; i++)
	phil[i] = new Thread(&philosopher, i);

    int status;
    for(int i = 0; i < 5; i++) {
	phil[i]->join(&status);
	if(status == i)
	    cout << "Philosopher " << i << " went to heaven!\n";
	else
	    cout << "Philosopher " << i << " went to hell!\n";
    }

    return 0;
}
Softwares básicos, caso Hello Word! (Atividade 5)

Softwares básicos, caso Hello Word!

O objetivo do experimento de hoje é pesquisar e entender os processos de atribuição de endereços de programas realizados em tempo de compilação pelos softwares básicos como: compilador, linker, e assembler. Sendo assim, neste experimento vamos utilizar os seguintes softwares para criação e análise de código:

  • GCC: compilador para gerar código objeto a partir de um código de programa escrito na linguagem c;
  • GNU Linker (LD): Para vincular os códigos (módulos) objetos do programa;
  • Linker
  • GNU Assembler: Para gerar o código executável a partir do código objeto;
  • | assembler
  • OBJDUMP: Para mostrar informações do código;
  • | Objdump


A seguir segue descrito o programa a ser utilizado no exercício 1:

#include <stdio.h>
int main()
{
   printf("Hello, World!");
   return 0;
}

Trata-se do programa hello word, este programa apenas exibe uma mensagem na tela. No entanto, vamos analisar como são as etapas confecção do executável a partir deste código simples.

Exercício 1:

  • Compile o programa hello word, e o transforme em código objeto utilizando o programa GCC. Para esta tarefa execute o seguinte comando:

gcc -o hello hello.c </syntaxhighlight>

  • Agora abra o código objeto utilizando o programa OBJDUMP.

objdump -D hello </syntaxhighlight>

  • Identifique quais são as seções de código obtidas a partir do hello.c.
  • Pesquise e entenda o significado destas seções de código.
  • Faça uma análise e identifique o endereço de memória que o programa hello world vai ser carregado.
  • Este código objeto é relocável? Justifique sua resposta.
  • Agora gere o código assembly do hello world.

gcc -S hello.c </syntaxhighlight>

  • Agora gere o código executável utilizando o programa AS e o programa LD.

as -o hello.o hello.s </syntaxhighlight>

  • Como a etapa de linkagem para a construção do código executável está sendo executada sem o auxílio do GCC, necessitamos vincular manualmente as bibliotecas necessárias. Para criar apropriadamente o executável vamos precisar das bibliotecas ld-linux-x86-64.so.2, crt1.o, crti.o, crtn.o.
  • Para descobrir suas respectivas localizações use o comando LOCATE. Por exemplo:

locate crti.o

</syntaxhighlight>

ou

find /usr/ -name crti*

</syntaxhighlight>

  • Agora que já sabemos a localização das bibliotecas necessárias vamos vincular essas a nossa aplicação.

ld --dynamic-linker /caminho/ld-linux-x86-64.so.2 /caminho/crt1.o /caminho/crti.o /caminho/crtn.o hello.o -lc -o hello.exe </syntaxhighlight>

  • Agora abra o código objeto utilizando o programa OBJDUMP.
  • Faça uma análise e identifique o endereço de memória em que o programa hello world inicializa suas estruturas na memória.
  • Dica!

objdump -D -s -j .init hello.exe </syntaxhighlight>

  • Houve diferença entre os endereços do programa executável em relação ao código objeto? Explique.
  • Explique as principais diferenças entre o arquivo objeto .o e o executável final. (dica utilize o objdump para fazer essa análise)
Permissões de sistema de arquivos no Linux

Permissões de sistema de arquivos no Linux

Neste estudo de caso são realizados alguns exercícios práticos que permitem verificar como o sistema de arquivos é organizado no Linux. Acesse o estudo de caso através deste roteiro do Prof. Maziero da UTFPR.

Lista de exercícios

Lista de exercícios

Lista de exercícios referente ao dia 22/06 | Lista de exercícios.

-->