P1 - SISOP 2

Prévia do material em texto

<p>Processos e Threads</p><p>1. Toda vez que vai ocorrer uma mudança de processo rodando(quando ambos estão</p><p>ainda rodando), ocorre um chaveamento de contexto entre processos, o que ele faz é</p><p>salvar todas informações do processo atual e carregar as informações do próximo</p><p>processo e executar.</p><p>a. As informações Salvas são:</p><p>i. Prioridade</p><p>ii. Local da memória caso o processo utilize</p><p>iii. Contexto (instrução em execução e valores nos registradores)</p><p>iv. Dono do processo</p><p>v. Tamanho da memória utilizada</p><p>vi. Contabilidade de recursos utilizados como I/O, memória e processador*</p><p>vii. Estado do processo</p><p>2. Multithreading ajuda principalmente a otimizar o uso do computador, por exemplo, ao</p><p>realizar uma soma o CPU vai fazer muito rápido, mas ao esperar uma I/O se a aplicação</p><p>for single thread ela ficará parada esperando, se for multithreading 1 thread pode cuidar</p><p>do I/O em questão e a outra pode continuar rodando e executando funções mais</p><p>rápidas enquanto espera a entrada ou saída terminar a comunicação.</p><p>Ou seja melhora o desempenho do software, visto que consegue utilizar melhor os</p><p>recursos.</p><p>3. 2^n​ onde N é o número de forks, logo, como temos 3 forks.</p><p>2³ = 8​ = número de processos criados.</p><p>Se não contar o pai, seriam 2^n -1.</p><p>4. t1:=3; t2:=3;</p><p>(contadores, para cada join triplo que tem no grafo)</p><p>P1; fork a2; fork a4; fork a3; quit;</p><p>(P1 é executada, tem um fork para P2, P4 e P3, quit no final de cada comando)</p><p>a2: P2; fork a7; fork a5; quit;</p><p>(para cada aN, executa o respectivo Processo, se for join, sinaliza o contador que está dando join</p><p>, próximo aN)</p><p>a3: P3; fork a6; fork a8; quit;</p><p>a4: P4; join t1, a9; quit;</p><p>a5: P5; join t1, a9; quit;</p><p>a6: P6; join t1, a9; quit;</p><p>a7: P7; join t2, a10; quit;</p><p>a8: P8; join t2, a10; quit;</p><p>a9: P9; join t2, a10; quit;</p><p>a10: P10; quit;</p><p>5. Primeiro, post que pode ajudar a elucidar vários conceitos:</p><p>https://stackoverflow.com/questions/15983872/difference-between-user-level-and-kern</p><p>el-supported-threads</p><p>User threads: gerenciadas por user-level-libraries, sem suporte ao kernel</p><p>Kernel threads: gerenciadas diretamente pelo SO.</p><p>n</p><p>Tipos de mapeamento:</p><p>Vantagens e Desvantagens:</p><p>https://stackoverflow.com/questions/15983872/difference-between-user-level-and-kernel-supported-threads</p><p>https://stackoverflow.com/questions/15983872/difference-between-user-level-and-kernel-supported-threads</p><p>6. São alocados para processos: dados, código, heap e stack;</p><p>Para threads são alocados e dividem com os processos os código e dados, variáveis</p><p>globais, arquivos abertos, diretórios, informações do SO, etc. Além disso elas têm uma</p><p>stack separada, registradores, incluindo stack pointer(SP) e program counter(PC).</p><p>São considerados mais leves que processo pois tem um share de memória, ou seja, o</p><p>chaveamento de contexto acontece muito mais rápido que um processo faria.</p><p>CAIU NA PROVA 2017/1</p><p>7. Como o pid == 0 é referente ao filho, ele acrescenta 5 ao inteiro “value” mas não dá o</p><p>print dele, lembrando que as variáveis são diferentes do pai e do filho, são copiadas.</p><p>Pid > 0 é do processo pai, logo ele vai printar o valor do processo pai que é 5.</p><p>Na linha A portanto vai ser impresso 5.</p><p>wait(NULL) faz com que o pai execute só depois que todos filhos terminarem</p><p>8. C1; C2; C3 executados em sequencia:</p><p>● x = 5</p><p>● y = 2</p><p>Executa C1, C2 e C3 em paralelo</p><p>● X e Y podem assumir valores</p><p>○ Se C2;C1;C3, x = 2, y = -3</p><p>○ Se C2;C3;C1, x = 2, y = -3</p><p>○ Se C1;C2;C3, x = 5, y = 2</p><p>○ Se C1;C3;C2, x = 2, y = -3</p><p>○ Se C3;C2;C1, x = -11, y = -8</p><p>○ Se C3;C1;C2, x = 2, y = -3</p><p>(Espera x > y e executa C1 depois C2) ao mesmo tempo que (executa C3)</p><p>● x nunca será maior que y, somente executando C2 primeiro que isso</p><p>ocorre.</p><p>● Executando C3 primeiro, tornará o valor de x menor ainda.</p><p>Programação concorrente e princípios sobre sincronização</p><p>1. É quando diferentes processos acessam e manipulam dados concorrentemente.</p><p>Resultado depende da ordem que são executados.</p><p>2. É quando um processo ou uma thread está esperando para que alguma condição</p><p>aconteça para continuar executando. Para evitar, temos diversas técnicas como</p><p>at-most-once, funções atômicas, etc.</p><p>3.</p><p>4. Satisfaz pois tem no máximo uma referência(y = x - y) de uma variável(x) em outra etapa</p><p>concorrente.</p><p>Os valores finais podem ser:</p><p>x = 2</p><p>y = 1</p><p>Ou</p><p>x = 2</p><p>y = 0</p><p>5. Não, para ocorrer deadlock, devemos ter alguma dessas quatro situações:</p><p>a. Exclusão Mútua​: um recurso não pode ser usado por mais de um processo;</p><p>b. Pare e espere​: processos que já estão segurando recursos podem requisitar</p><p>novos recursos</p><p>c. Sem preemptividade​: Nenhum recurso pode forçadamente ser retirado de um</p><p>processo que o está segurando, recursos podem ser liberados explicitamente e</p><p>somente pelo processo.</p><p>d. Espera Circular​: 2 ou mais processos formam uma cadeia circular onde cada</p><p>processo espera para um recurso que o outro processo está segurando;</p><p>Logo, para termos deadlocks, temos que ter ou multithreading ou vários</p><p>processos ou os 2.</p><p>6. O caso em que o starvation ocorre é quando um processo está esperando para ser</p><p>atendido, mas sempre chega outro processo que é escolhido pelo escalonador.</p><p>Para resolver o starvation podemos simplesmente criar uma ordem de escalonamento</p><p>de timpressão.</p><p>// Imagino que para solucionar o problema de o processo nunca ser</p><p>escalonado, deveria ser criado uma espécie de prioridade para cada processo</p><p>que aumenta com o tempo</p><p>Pode corrigir usando herança de prioridade</p><p>7. Propriedades primitivas de exclusão mútua:</p><p>a. Exclusão Mútua: garantir que no máximo um processo esteja executando uma</p><p>seção crítica;</p><p>i. Como tem a variável booleana wantsToEnter e mais uma variável turn</p><p>que indica se é a vez do processo em questão, ele nunca vai ter 2</p><p>processos executando a seção crítica.</p><p>b. Progressão: Um processo fora da seção crítica não pode impedir outro de entrar;</p><p>i. Como existem as 2 variáveis explicadas em A, o processo fora da seção</p><p>crítica vai alternar ao final da execução de cada um deles, logo o outro</p><p>também vai ter a sua vez, sem impedimentos.</p><p>c. Espera limitada: Um processo não deve ser proibido indefinidamente de entrar</p><p>em uma seção crítica</p><p>i. Mesmo motivo da B, existe uma alternância entre os processos.</p><p>d. Não deve fazer suposições sobre velocidade relativa do computador, ou</p><p>execução relativa a velocidade dos processos.</p><p>i. Não existem suposições que dependam de velocidade do computador,</p><p>existe um controle de variáveis.</p><p>8. Se por exemplo, P1 é executado, e na região não crítica ele demora muito executar,</p><p>depois de ter alterado o turn, o processo P2 vai executar, ao terminar vai setar uma flag</p><p>contrária a sua execução, então se P1 ainda estiver executando a seção não crítica ele</p><p>vai tentar executar novamente(o P2) e assim ele estaria esperando e sendo bloqueado</p><p>pois P1 não chegou no turn novamente.</p><p>9. Busy-wait num sistema com um único processador implica em tempo perdido de</p><p>execução já que o processo só está ocupando a cpu sem fazer nada. Em sistemas</p><p>multicore isso pode ser aceitável já que outras threads estarão executando em paralelo</p><p>e o fato de não ter troca de contexto do processo em busy wait, pode fazer valer a pena</p><p>ele ficar executando "nada" contando que seja liberado logo.</p><p>10. Porque dá muito poder ao usuário, pode acontecer de um processo ser executado</p><p>infinitamente(loop) e se entrar não irá sair.</p><p>11. Como os 2 estão acessando uma mesma conta, pode acontecer de que ao passar a</p><p>quantia a ser retirada, ele reconheça como a quantia a ser depositada na função de</p><p>depósito. Ou que o marido retire a quantia que a esposa está tentando depositar, enfim,</p><p>conflito de dados.</p><p>Para resolver essa situação exclusão mútua pode ser aplicada, considerando cada</p><p>função como uma seção crítica.</p><p>Saldo: 100</p><p>Deposito: 80</p><p>Saque: 20</p><p>Ambas operações são feitas de forma concorrente</p><p>terminal A: operação deposito, saldo = 100</p><p>Terminal B: operação saque, saldo = 100</p><p>Terminal A: soma 50 ao saldo de 100</p><p>Terminal B: subtrai 80 de 100</p><p>Terminal A: salva saldo 150</p><p>Terminal B: salva saldo de 20</p><p>Depósito foi perdido</p><p>-> implementar seção crítica com mutex ou algo do tipo</p><p>Primitivas de sincronização: mutex, semáforos, monitores</p><p>1. Diferenças e Conceito</p><p>a. Mutex</p><p>i. Mutex deixam somente uma thread por vez entrar na seção crítica e</p><p>somente essa thread pode liberar o mutex.</p><p>No semáforo, pode ser sinalizado de qualquer outra thread ou processo a</p><p>liberação. Por esse motivo semáforos são mais adequados para</p><p>problemas de sincronização como produtor-consumidor.</p><p>O mesmo mutex pode ser compartilhado entre vários processos,</p><p>consequentemente várias threads entre esses processos.</p><p>b. Semáforos</p><p>i. O semáforo faz o mesmo com o mutex com a diferença de que podem</p><p>entrar X processos dentro dessa seção crítica.</p><p>Assim como mutex, podem ser utilizados por vários processo e threads,</p><p>lembrando que os semáforos podem liberar ou alocar recursos de</p><p>qualquer outra thread/processo.</p><p>c. Monitores</p><p>i. Monitores, assim como mutex só deixam uma thread/processo executar</p><p>a seção critica, são feitos para multi-thread dentro de um único processo.</p><p>2.</p><p>a) turn = 2;</p><p>b) p2WantsToEnter = 1 && turn = 2;</p><p>c) turn = 1;</p><p>d) p1WantsToEnter = 1 && turn = 1;</p><p>3. Será violada pois se V pode interferir em P ou o contrário, pode interferir na contagem</p><p>de recursos que o semáforo está controlando no momento. Logo mais de uma thread</p><p>poderia por exemplo usar o mesmo recurso.</p><p>4. Sem arrive1=0,</p><p>arrive2=0;</p><p>Process Worker1 {</p><p>V(arrive1);</p><p>P(arrive2)</p><p>}</p><p>Process Worker2 {</p><p>V(arrive2);</p><p>P(arrive1);</p><p>}</p><p>5. Poderiamos utilizar dois semáforos inicializados em zero, semaforoA e semaforoB.</p><p>threadA: tarefa Y threadB: tarefa X</p><p>semaforoA.V() semaforoB.V()</p><p>semaforoB.P() semaforoA.P()</p><p>Tarefa A tarefa B</p><p>6. Porque caso os semáforos sejam inicializados em zero, vai dar deadlock pois a thread 1</p><p>vai estar esperando o recurso do semaforoB e a thread 2 vai estar esperando o recurso</p><p>do semaforoA. Caso sejam inicializados em 1+, a thread 1 pode executar a tarefa A</p><p>antes da tarefa X ser executada, assim como a B pode executar a tarefa B antes da</p><p>tarefa Y. Nesse caso, os semáforos acabam não tendo sentido.</p><p>7. P = tirar recurso</p><p>V = repor recurso</p><p>Se executarmos começando em 1, 12 operações P’s, ficaremos com -11, ao</p><p>retornarmos recurso com 7 operações V’s, temos -11 + 7 = -4, ​logo temos 4 processos</p><p>aguardando recurso.</p><p>Comunicação Inter-processos</p><p>1. Bind → Associa o socket ao endereço local, isso seria o bind em si, é usado para que o</p><p>cliente possa se conectar no servidor usando o endereço local. É utilizado no Server</p><p>side. É usada tanto em UDP quanto em TCP.</p><p>Connect → É a primitiva que conecta a um endereço remoto(servidor), logo, é utilizado</p><p>pelo Client. É usada somente em TCP, UDP simplWRRWesmente envia por sendto.</p><p>2.</p><p>a. At-most-once(no máximo uma vez)</p><p>b. At-least-once(pelo menos uma vez)</p><p>c. Exactly-once(somente uma vez)</p><p>3. O RMI Registry é um serviço de nomeação, o rmiserver usa o rmiregistry para fazer</p><p>um bind de um objeto remoto em java com os nomes, para que o cliente possa</p><p>tratar diretamente pelo nome registrado no rmiregistry e executar os métodos destes</p><p>objetos.</p><p>RMI cria um proxy remoto para este objeto e envia para os clientes, este objeto de</p><p>proxy, contém a referência para um objeto.</p><p>CAIU NA PROVA 2017/1 (com outros valores)</p><p>4. i) Cada requisição do cliente: 4ms + 1ms (send) + 0,5ms (marshalling) +</p><p>4ms(transmissão do request) + 1ms (receive) + 0,5ms (unmarshalling) = 11ms</p><p>Cada resposta do servidor: 12ms (processar) + 1ms(receive) + 0,5 (unmarshalling) +</p><p>4ms (transmissão da resposta) + 1ms (send) + 0,5ms (marshalling) = 19ms</p><p>Como são duas requisições, 2 * 11 + 2 * 19 = 60</p><p>ii) marshall + send + transmissão + unmarshall + servidor + marshall + transmissão + receive +</p><p>unmarshall + cliente = 24ms, 2*24 = 48</p><p>Se considerar a fluxo da seguinte forma:</p><p>cliente marsh send ----- trans​ ----- ​receive unmarsh servidor marsh send​ ---- ​trans ---- receive unmarsh</p><p>i) soma cada valor individual * numero de requisições</p><p>ii) (soma a parte azul * requisições) + soma parte rosa apenas uma vez*</p><p>* uma pq ta tudo concorrente no cliente</p><p>Provas anteriores</p><p>Prova 2016 (folder P1/2016)</p><p>Questão 1​: Qual é a saída do programa abaixo, impressa na “Linha C” e na “Linha D”?</p><p>Linha C:​ PARENT: value = 20 (value = 17+3 -> valor obtido pela execução da thread)</p><p>Linha D: ​CHILD: value = 3</p><p>(compilei e testei)</p><p>Pthread_create, recebe 4 parâmetros, sendo o 3 e o 4 uma função de inicio e seus</p><p>parâmetros respectivamente.</p><p>Questão 2​: Considere a notação co-oc para especificação de programas concorrentes, e a</p><p>primitiva <await(B) S;>, onde B é uma expressão booleana e S é uma sequência de 0 ou mais</p><p>comandos. Dado o conjunto de comandos abaixo:</p><p>C1: x = x - y²</p><p>C2: y = y + x</p><p>Para cada um dos casos abaixo, assuma x = 3 e y =2 inicialmente. Quais são os valores finais</p><p>para x e y?</p><p>i. C1;C2;</p><p>Único valor possível: x = -1 e y = 1, pois não há concorrência.</p><p>ii. co <C1;> // <C2;> oc</p><p>Duas sequências possíveis de execução:</p><p>C1C2: x = -1 e y = 1</p><p>C2C1: x = -22 e y = 5</p><p>iii. co <await(y >= x) C1;> // <C2;> oc</p><p>Lado esquerdo tranca pois y = 2 < x = 3. Logo, C2 executa antes.</p><p>C2 -> y = 5, x = 3. -> y > x! C1 desbloqueia.</p><p>C1 -> x = -22.</p><p>Valores finais: x = -22, y = 5.</p><p>Questão 3:​ Compare os mecanismos de comunicação Pipes Unix, Sockets UNIX e Sun RPC.</p><p>Compare as características e funcionalidades apresentadas por cada um deles. Em quais</p><p>situações cada um dos mecanismos é apropriado?</p><p>Sockets : ​É local ou remoto, permite comunicação bidirecional, tem suporte a diferentes tipos</p><p>de protocolos, flexibilidade (TCP/UDP)</p><p>Pipes​: ​Fluxo de dados unidirecional, operar processos relacionados, apenas comunicação local</p><p>Sun RPC:​ É implementação de alto nível, semântica at-least-once, binding local, apropriado para</p><p>chamada de procedimento remoto.</p><p>Questão 4​: Qual a finalidade das variáveis tipo lock(mutex), semáforos e monitores? Porque</p><p>existem esses diferentes mecanismos? O que difere um do outro?</p><p>Diferenças e Conceito</p><p>a. Mutex</p><p>i. Mutex deixam somente uma thread por vez entrar na seção crítica e</p><p>somente essa thread pode liberar o mutex.</p><p>No semáforo, pode ser sinalizado de qualquer outra thread ou processo a</p><p>liberação. Por esse motivo semáforos são mais adequados para</p><p>problemas de sincronização como produtor-consumidor.</p><p>O mesmo mutex pode ser compartilhado entre vários processos,</p><p>consequentemente várias threads entre esses processos.</p><p>b. Semáforos</p><p>i. O semáforo faz o mesmo com o mutex com a diferença de que podem</p><p>entrar X processos dentro dessa seção crítica.</p><p>Assim como mutex, podem ser utilizados por vários processo e threads,</p><p>lembrando que os semáforos podem liberar ou alocar recursos de</p><p>qualquer outra thread/processo.</p><p>c. Monitores</p><p>i. Monitores, assim como mutex só deixam uma thread/processo executar</p><p>a seção crítica, são feitos para multi-thread dentro de um único processo.</p><p>CAIU NA PROVA 2017/1 (com outros valores)</p><p>Questão 5​: Uma variável s, do tipo semáforo, é inicializada em 2. Em seguida, onze operações</p><p>P(s) e sete operações V(s) são realizadas por processos distintos. Ao final, qual é a quantidade</p><p>de processos que estão esperando neste semáforo?</p><p>Semáforo iniciado em 2;</p><p>Cada operação P tira 1;</p><p>Cada Operação V soma 1;</p><p>Ao executar 11x a operação P, temos 2 -11 = -9.</p><p>Ao executar em 7x a operação V, temos -9 + 7 = -2.</p><p>Logo temos 2 processos esperando o semáforo.</p><p>CAIU NA PROVA 2017/1</p><p>Questão 6​: Com relação a comunicação inter-processos por troca de mensagens, analise as</p><p>afirmativas</p><p>abaixo:</p><p>i) Comunicação síncrona acontece somente quando ambas as primitivas send e receive</p><p>tem semânticas bloqueantes.</p><p>ii) Sockets fornece um modelo de comunicação com nomeação direta.</p><p>iii) Recebimento bloqueante implica que o processo que faz o receive irá bloquear até</p><p>que a mensagem seja transferida do buffer para o processo, ou retornará NULL caso não haja</p><p>mensagens no buffer.</p><p>a) Apenas I</p><p>b) Apenas I e II</p><p>c) Apenas I e III</p><p>d) Apenas II e III</p><p>e) I, II e III</p><p>CAIU NA PROVA 2017/1</p><p>Questão 7: ​Assinale a alternativa ​INCORRETA​:</p><p>a) Semáforos podem ser usados para sincronização de condição, exclusão mútua e</p><p>alocação de recursos.</p><p>b) Uma aplicação contém uma condição de corrida somente quando o sistema</p><p>operacional que executa esta aplicação tiver mais de um processador.</p><p>c) Um semáforo binário é um tipo especial de semáforo usado para implementar exclusão</p><p>mútua. Para este fim, ele é inicializado em 1 e só pode assumir valores 0 e 1.</p><p>d) Um Monitor é uma construção que oferece duas facilidades: acesso em exclusão mútua</p><p>para dados compartilhados e sincronização de condição entre processos através da</p><p>primitiva wait e signal.</p><p>e) Sincronização de condição permite garantir que processos executarão suas ações em</p><p>uma determinada ordem, independentemente do escalonamento.</p><p>CAIU NA PROVA 2017/1 (IGUAL)</p><p>Questão 8:​ Assuma um processo cliente que faz chamadas remotas de procedimento(RPC) em</p><p>um servidor que está em uma máquina remota. O cliente leva 6 ms para computar os</p><p>argumentos que serão enviados para cada requisição, e o servidor leva 12 ms para processar</p><p>cada requisição. O tempo de processamento do sistema operacional para executar cada send()</p><p>ou receive() é 0,5 ms, e o tempo para transmissão para rede de cada mensagem de requisição</p><p>ou resposta é 3 ms. A execução dos procedimentos marshalling ou unmarshalling leva 1,5 ms</p><p>por mensagem.</p><p>Suponha que tanto o processo cliente quanto o processo servidor estejam executando</p><p>em uma máquina com um único processador, e que o tempo necessário para trocas de</p><p>contexto(context switch) possa ser ignorado. Calcule o tempo levado pelo cliente para gerar e</p><p>receber resultado de duas requisições:</p><p>(i) Se o cliente for implementado com uma única thread.</p><p>(ii) Se o cliente tiver duas threads que possam fazer requisições concorrentemente.</p><p>(i) Resposta:</p><p>Cliente trabalhando(envio):</p><p>Trabalho da requisição do cliente + marshalling + send() + transmissão</p><p>6 + 1,5 + 3 + 0,5 = 11</p><p>Servidor trabalhando(recebimento e envio):</p><p>receive() + unmarshalling + trabalho na requisição recebida do cliente + marshalling + send() +</p><p>transmissão</p><p>0,5 + 1,5 + 12 + 1,5 + 0,5 + 3 = 19</p><p>Cliente trabalhando(recebimento):</p><p>receive() + unmarshalling</p><p>0,5 + 1,5 = 2</p><p>2 + 11 + 19 = 32ms ​x 2 ​= 64ms</p><p>(ii) Resposta:</p><p>Cliente trabalhando(envio total do cliente):</p><p>Trabalho da requisição pelo cliente + marshalling + transmissão + send()</p><p>6 + 1,5 + 3 + 0,5 = 11</p><p>Servidor trabalhando:</p><p>receive() + unmarshalling + trabalho da primeira requisição pelo servidor + marshalling + send()</p><p>0,5 + 1,5 + 12 + 1,5 + 0,5 = 16</p><p>receive() + unmarshalling + trabalho da segunda requisição pelo servidor + marshalling + send()</p><p>+ transmissão</p><p>0,5 + 1,5 + 12 + 1,5 + 0,5 + 3 = 19</p><p>Cliente trabalhando(aqui só contamos o último recebimento pois o primeiro enquanto o</p><p>servidor trabalhava foi feito):</p><p>receive() + unmarshalling</p><p>0,5 + 1,5 = 2</p><p>2 + 16 + 19 + 11 = 48ms</p><p>Questão 9: ​Implemente usando pseudo-linguagem, um monitor que emule a funcionalidade de</p><p>um semáforo. O monitor deve obrigatoriamente implementar os procedimentos SemaphoreP()</p><p>e SemaphoreV(). Assuma existência de um tipo de dado COND, usado para declarar variável de</p><p>condição.</p><p>(tem nos slides de monitor isso)</p><p>monitor Semaphore {</p><p>​int​ s = ​1​; ​# s >= 0</p><p>cond pos; ​# signaled when s > 0</p><p>procedure ​Psem​() {</p><p>​while​ (s == ​0​)</p><p>wait(pos);</p><p>s = s – ​1​;</p><p>}</p><p>procedure ​Vsem​() {</p><p>s = s + ​1​;</p><p>signal(pos);</p><p>}</p><p>}</p><p>Prova 1 - 2014</p><p>CAIU NA PROVA 2017/1</p><p>Questão 1: ​Considerando a implementação de monitores, explique as diferenças entre as</p><p>estratégias de sinalização “signal-and-continue”(SC) e “signal-and-wait”(SW). Em particular,</p><p>explique o que acontece com o processo sinalizador e com o processo sinalizado em cada uma</p><p>das estratégias.</p><p>1) Dentre as duas estratégias de sinalização, existe uma diferença básica em relação ao</p><p>processo sinalizador e sinalizado:</p><p>a) Em SC -> Não-preemptiva -> O processo sinalizador continua sua execução e o sinalizado</p><p>passa para a fila do monitor. Estratégia predominante em Java, ambientes Unix e pthreads.</p><p>b) Em SW -> Preemptiva -> O processo sinalizador vai para a fila da entrada do monitor e o</p><p>processo sinalizado inicia sua execução.</p><p>c) Ainda existe SU (Signal and Urgent Wait) no qual o processo sinalizador vai para a frente da</p><p>fila de entrada do monitor e o sinalizado inicia sua execução.</p><p>Questão 2: ​Repetida de 2016(3)</p><p>CAIU NA PROVA 2017/1</p><p>Questão 3: ​Servidores podem ser construídos de forma a limitar o número de conexões</p><p>abertas. Por exemplo, um servidor pode desejar ter no máximo N conexões sockets abertas em</p><p>um dado momento. Assim que N conexões forem estabelecidas, o servidor não irá aceitar</p><p>qualquer nova conexão até que uma conexão existente seja liberada. Explique como semáforos</p><p>podem ser usados pelo servidor para limitar o número de conexões concorrentes.</p><p>Com um semáforo S inicializado em 100. Realiza uma operação P(S) cada vez que uma</p><p>conexão for aberta e uma operação V(S) toda vez que uma conexão for fechada.</p><p>CAIU NA PROVA 2017/1 (igual)</p><p>Questão 4:​ Em sistema leitores-escritores com preferência para leitores, uma operação de</p><p>leitura consome 3 unidades de tempo e uma operação de escrita consome 5 unidades de</p><p>tempo. No instante ti -1 não há nenhum processo leitor, nem escritor. Um leitor chega no tempo</p><p>ti, e cinco leitores e um escritor chegam no tempo ti+1. Se não chegar mais nenhum processo,</p><p>qual instante de tempo o escritor terminará de escrever?</p><p>a) ti+8</p><p>b) ti+9</p><p>c) ti+18</p><p>d) ti+19</p><p>e) ti+20</p><p>Os leitores têm preferência e operações de escrita não podem ser feitas ao mesmo</p><p>tempo em que alguma outra operação estiver sendo feita.</p><p>Em ​ti​, chega o primeiro leitor, que ficará lendo até ​ti+3. ​No instante seguinte, ​t+1​, cinco</p><p>leitores e um escritor chegam. Como operações de leitura podem ser feitas simultaneamente</p><p>e os leitores têm preferência, eles já iniciam a leitura, e a terminam em ​t+4​. O escritor fica</p><p>aguardando até que não haja algum leitor ou outro escritor executando. Portanto, em ​t+4​ o</p><p>escritor passa a executar, e termina de escrever em ​t+9​.</p><p>CAIU NA PROVA 2017/1 (igual)</p><p>Questão 5: ​Uma variável s, do tipo semáforo, é inicializada em 3. Doze operações P(s) e sete</p><p>operações V(s) são realizadas por processos distintos. Qual é a quantidade de processos que</p><p>estão esperando neste semáforo? (Conferida na prova)</p><p>a) 5</p><p>b) 4</p><p>c) 3</p><p>d) 2</p><p>e) 1</p><p>S = 3.</p><p>Como P = tirar 1;</p><p>E V = colocar 1;</p><p>12x P = -12</p><p>7x V = 7</p><p>3 - 12 + 7 = -2, ​logo 2 processos estão aguardando.</p><p>Questão 6: ​Repetida da prova de 2016(7)</p><p>CAIU NA PROVA 2017/1</p><p>Questão 7:​ Nesta questão, assuma um modelo de falhas que considere APENAS perdas</p><p>ocasionais de mensagens, duplicações de mensagens, e mensagens entregues fora de ordem.</p><p>Assinale a alternativa CORRETA:(Conferida na prova)</p><p>a) Nos modelos Sun RPC e Java RMI, o middleware/runtime implementa um protocolo da</p><p>família request-reply com semântica at-least-once, garantindo assim que o</p><p>procedimento ou método remoto será executado pelo menos uma vez (mas poderá ser</p><p>executado mais vezes).</p><p>b) Em RPC, parâmetros de entrada definidos na IDL podem ser passados por valor ou por</p><p>referência, mas parâmetros de saída somente podem ser passados por valor.</p><p>c) No modelo RMI, o componente dispatcher faz o marshalling dos argumentos de uma</p><p>chamada no lado</p><p>do cliente e despacha a chamada para o servidor remoto.</p><p>d) A implementação do Sun RPC adota uma semântica at-least-once, e assume que as</p><p>operações implementadas pelo servidor são idempotentes.</p><p>e) No modelo RMI, o módulo de referência remota é responsável por traduzir referências</p><p>locais para referências remotas, e por implementar um protocolo da família</p><p>request-reply com uma determinada semântica.</p><p>Questão 8: ​Repetida Prova de 2016(6)</p><p>CAIU NA PROVA 2017/1</p><p>Questão 9:​ Qual é a saída do programa abaixo, impresso na “Linha A”?(Conferida na prova)</p><p>#includes…</p><p>int​ value = ​5​;</p><p>int​ ​main​() {</p><p>pid_t​ pid = fork();</p><p>if​ (pid < ​0​) {</p><p>printf(“Fork failed\n”);</p><p>return​ ​1​;</p><p>}</p><p>else​ ​if​ (pid == ​0​) {</p><p>value +=​15​;</p><p>return​ ​0​;</p><p>}</p><p>else​ {</p><p>wait(pid);</p><p>prinf(“PARENT: value = “%d\n”, value);​ ​/*LINHA A*/</p><p>​return​ ​0​;</p><p>}</p><p>}</p><p>Pid == 0, processo filho.</p><p>Pid > 0, processo pai.</p><p>Logo o value ta sendo acrescido no processo filho e no else, o processo pai é impresso,</p><p>mas como tem a cópia de variáveis, não tem relação os 2 values, é impresso então o</p><p>valor 5, que é o valor inicial da variável value que não foi alterada no processo pai.</p><p>Questão 10: ​Assuma um processo cliente que faz chamadas remotas de procedimento(RPC)</p><p>em um servidor que está em uma máquina remota. O cliente leva 5ms para computar os</p><p>argumentos para cada requisição, e o servidor leva 10ms para processar cada requisição. O</p><p>tempo de processamento do sistema operacional para executar cada send() ou receive() é</p><p>0,5ms, e o tempo para transmissão na rede de cada mensagem de requisição ou resposta é</p><p>3ms. A execução dos procedimentos de marshalling ou unmarshalling leva 0,5ms por</p><p>mensagem.</p><p>Suponha que o tempo necessário para trocas de contexto(context-switch) possa ser</p><p>ignorado. Calcule o tempo levado pelo cliente para gerar e receber o resultado de duas</p><p>requisições.</p><p>(i) se o cliente for implementado com uma única thread.</p><p>(ii) se o cliente tiver duas threads que possam fazer requisições concorrentemente em um</p><p>único processador.</p><p>CAIU NA PROVA 2017/1 (igual)</p><p>Questão 11: ​Considere o programa abaixo, escrito em pseudo-linguagem. O programa deve</p><p>implementar corretamente o acesso a um buffer limitado de 10 posições, utilizando monitores</p><p>e variáveis de condição(cheio e vazio). Complete as lacunas para garantir o acesso</p><p>sincronizado de produtores/consumidores ao buffer compartilhado. Importante considere que</p><p>o monitor implementa a semântica “signal-and-continue”(SC).</p><p>monitor Buffer{</p><p>typeT buf[n];</p><p>int​ inicio = ​0​, fim = ​0​, cont = ​0​, n = ​10​;</p><p>cond cheio,</p><p>vazio;</p><p>procedure ​coloca​(typeT dado) {</p><p>ESPAÇO A</p><p>buf[fim] = dado; fim = (fim+​1​) % n; cont++;</p><p>ESPAÇO B</p><p>}</p><p>procedure ​retira​(typeT &resultado) {</p><p>​ESPAÇO C</p><p>resultado = buf[inicio]; inicio = (inicio+​1​) % n; cont--;</p><p>ESPAÇO D</p><p>}</p><p>}</p><p>ESPAÇO A​ = while(cont == n) wait(cheio);</p><p>ESPAÇO B​ = signal (vazio);</p><p>ESPAÇO C​ = while (cont == 0) wait (vazio);</p><p>ESPAÇO D​ = signal (cheio);</p><p>Prova 1 - 2013</p><p>Questão 1​: Dentre as afirmações abaixo, assinale quais são verdadeiras (V) e quais são falsas</p><p>(F).</p><p>(​ ​F​ ) Toda solução para exclusão mútua necessita de operações Test And Set implementadas</p><p>pelo hardware (processador)</p><p>( ​V​ ) Um grafo de fluxo de processos que não é propriamente aninhado pode ser implementado</p><p>em C sobre um sistema operacional UNIX utilizando as chamadas fork, quit e join</p><p>( ​F​ ) Programação concorrente somente confere maior velocidade ao programa quando se</p><p>utilizam máquinas com múltiplos processadores, ou múltiplos cores</p><p>( ​F​ ​) Um trecho de pseudo-código utilizando semáforos que faz: “while (condição) P();” é um</p><p>exemplo típico de busy waiting, o que é fácil perceber pela construção “while”, que permanece</p><p>continuamente testando a condição</p><p>( ​F​ ) A vantagem de usar threads é que não é necessário empregar mecanismos de</p><p>sincronização de controle e de acesso a dados, já que elas executam dentro de um processo.</p><p>Como um processo só pode ser escalonado em um único processador (ou core), se elimina a</p><p>concorrência.</p><p>( ​F​ ) A inversão de prioridade é caracterizada por uma thread de menor prioridade ser</p><p>escalonada antes de uma thread de maior prioridade quando as duas se encontram no estado</p><p>apto (ready)</p><p>( ​V​ ) A inversão de prioridade é caracterizada por uma thread de menor prioridade deter um</p><p>recurso (lock de uma seção crítica) e assim impedir que uma thread de maior prioridade saia do</p><p>estado bloqueado</p><p>( ​V​ ) Espera ativa (busy waiting) é uma técnica em que um processo (ou thread) verifica</p><p>continuamente uma condição até que ela seja verdadeira.</p><p>( ​F​ ) Com relação a sockets, um programa UDP emprega a primitiva accept, enquanto um</p><p>programa TCP emprega a primitiva connect</p><p>( ​F​ ​) Em monitores, a estratégia de sinalização signal-and-continue implica que o processo</p><p>sinalizado irá continuar sua execução no monitor a partir daquele momento, enquanto que o</p><p>processo sinalizador irá para a fila de entrada.</p><p>Questão 2:​ Repetida questão 4 da lista</p><p>CAIU NA PROVA 2017/1</p><p>Questão 3: ​Com relação a mecanismos de comunicação entre processos, explique as</p><p>diferenças entre os modelos de comunicação com memória compartilhada (shared-memory) e</p><p>troca de mensagens (message passing). Quais são as vantagens e desvantagens de cada um?</p><p>Troca de mensagens:</p><p>Utilizada para pequenas quantidades de dados;</p><p>Utiliza várias vezes chamadas do Kernel;</p><p>Programação simples;</p><p>Pode ser utilizada entre processos não-relacionados;</p><p>Utilizada em programação distribuída</p><p>Memória Compartilhada:</p><p>Utilizada para grandes quantidades de dados;</p><p>Chamadas do Kernel apenas para estabelecer a região da memória;</p><p>Comunicação mais rápida e eficiente;</p><p>Utilizada apenas entre processos relacionados;</p><p>(Programação mais complexa? Tá meio riscado na prova.. Melhor confirmar)</p><p>Questão 4:​ Repetida Prova 2014(4)</p><p>Questão 5​: Utilizando um modelo de falhas que considere perdas ocasionais de mensagens,</p><p>duplicações de mensagens e mensagens entregues fora de ordem, uma semântica no máximo</p><p>uma vez (at-most-once) é caracterizada por:</p><p>a) Garantir que uma tarefa remota foi executada uma única vez retornando um resultado</p><p>válido ou, em caso contrário, retornando um erro.</p><p>b) Garantir que uma tarefa remota foi executada pelo menos uma vez, mas, eventualmente,</p><p>ela pode ter sido realizada várias vezes antes de retornar um resultado válido.</p><p>c) Executar a tarefa remota exatamente uma vez, mesmo na presença de falhas.</p><p>d) Talvez ter sido executada uma vez.</p><p>e) Executar a tarefa remota várias vezes, mas mantendo sempre o mesmo resultado final.</p><p>Questão 6: ​Assinale a alternativa INCORRETA:</p><p>a) Semáforos podem ser usados para sincronização de controle, exclusão mútua e</p><p>alocação de recursos</p><p>b) Uma aplicação contém uma condição de corrida do tipo ​data race​ somente quando o</p><p>sistema computacional que executa esta aplicação tiver mais de um processador (ou</p><p>core).</p><p>c) Um semáforo binário é um tipo especial de semáforo usado para implementar exclusão</p><p>mútua. Para esse fim, ele é inicializado em 1 e só pode assumir um de dois valores, zero</p><p>ou um.</p><p>d) Um monitor é uma construção que oferece duas facilidades: acesso em exclusão mútua</p><p>para dados compartilhados e sincronização de controle entre processos através da</p><p>primitivas wait e signal.</p><p>e) Sincronização de controle é a garantia de que processos executarão suas ações em</p><p>uma determinada ordem, independentemente do escalonamento.</p><p>Questão 7​: Repetida da prova de 2014(7)</p><p>Questão 8​: Repetida da prova de 2016(6)</p><p>Questão 9: ​Igual a questão 2 da parte de primitivas de sincronização da Lista, apenas pede para</p><p>preencher outra parte do código.</p><p>Questão 10: ​Considere o pseudo-código abaixo, que consiste em uma tentativa de resolver o</p><p>problema do jantar dos filósofos. Qual é o problema dessa solução? Apresente duas (2) formas</p><p>de resolver o problema: explique o que deve ser feito e mostre as soluções em pseudo-código.</p><p>N = 5</p><p>Var semaphore forks[N] = {1,1,1,1,1}</p><p>Process Philosopher [int i=0 to N-1] {</p><p>int left = i;</p><p>right = (i+1) % N;</p><p>while (true) {</p><p>Think;</p><p>P(forks[left]);</p><p>P(forks[right]);</p><p>Eat;</p><p>V(forks[left]);</p><p>V(forks[right]);</p><p>}</p><p>}</p><p>O problema é que todos os filósofos podem pegar o garfo à esquerda, e ficar esperando o garfo</p><p>da direita, que nesse caso nunca será liberado. (DEADLOCK)</p><p>Solução 1:</p><p>Um filósofo pega o garfo da direita e depois o da esquerda, e os demais pegam primeiro da</p><p>esquerda e depois o da direita</p><p>…</p><p>while (true) {</p><p>Think;</p><p>if (i == 0){</p><p>P(forks[right]);</p><p>P(forks[left]);</p><p>} else {</p><p>P(forks[left]);</p><p>P(forks[right]);</p><p>}</p><p>Eat;</p><p>V(forks[left]);</p><p>V(forks[right]);</p><p>}</p><p>...</p><p>Solução 2:</p><p>Se no máximo N-1 filósofos tentarem comer, haverá sempre um que terá a chance de pegar</p><p>dois garfos.</p><p>Deve ser feito utilizando um semáforo adicional para representar o número máximo de</p><p>filósofos que terá a chance de pegar dois garfos.</p>