Difference between revisions of "Problema da fragmentação de memória"
From AdonaiMedrado.Pro.Br
(→Entrada) |
(→Dificuldade Única) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
Garantias e considerações: | Garantias e considerações: | ||
| − | *Caso as requisições ultrapassem o tamanho da memória só serão atendidas as requisições possíveis, considerando a linha do tempo. Assim caso o tamanho da memória for 200 e as requisições forem {50, 50, 90, 30, 10, 5} a requisição 3 por 30 bytes não será atendida, mas a 4 de 10 bytes será enchendo a memória o que impedirá que a solicitação 5 por 5 bytes seja atendida. | + | *Caso as requisições ultrapassem o tamanho da memória só serão atendidas as requisições possíveis, considerando a linha do tempo. Assim caso o tamanho da memória for 200 e as requisições forem {50, 50, 90, 30, 10, 5} a requisição 3 por 30 bytes não será atendida, mas a 4 de 10 bytes será, enchendo a memória, o que impedirá que a solicitação 5 por 5 bytes seja atendida. |
| − | *O valor máximo da memória será de 2048. | + | *O valor máximo da memória será de 2048 bytes. |
*O número de elementos do vetor de requisição de alocação e do vetor de requisição de liberação pode variar de 0 a 200. | *O número de elementos do vetor de requisição de alocação e do vetor de requisição de liberação pode variar de 0 a 200. | ||
| + | *Devem ser processadas todas as alocações possíveis para só então processar as liberações. | ||
=== Exemplo 1 === | === Exemplo 1 === | ||
| Line 55: | Line 56: | ||
==== Saída ==== | ==== Saída ==== | ||
| − | 80 | + | 80 |
=== Exemplo 4 === | === Exemplo 4 === | ||
Latest revision as of 14:50, 1 October 2008
Contents
Dificuldade Única
Considere um conjunto hipotético de processador, memória e sistema operacional. Neste sistema a memória é alocada em blocos não fragmentados e sempre começa-se a pesquisa por espaço livre do primeiro endereço da memória.
Faça um programa capaz de identificar, após uma série de alocações e liberações, qual o tamanho do maior bloco disponível para alocação.
Para o cálculo o programa receberá os dados abaixo um em cada linha:
- Tamanho da memória.
- Quantidade de requisições de alocação.
- Vetor de alocação (um elemento por linha) onde a posição (baseada em zero) corresponde ao número da requisição e o valor armazenado na posição à quantidade de memória requisitada. Assim, por exemplo, no vetor {30, 40, 60, 85} temos que na requisição 0 foram solicitados 30 bytes, na 1 40 bytes, na 2 60 bytes e na 3 85 bytes. O vetor está ordenado de acordo com a linha do tempo, assim no exemplo, 30 foi a primeira solicitação, 85 a última.
- Quantidade de requisições de liberações.
- Vetor (um elemento por linha) onde cada elemento corresponde ao número da requisição cuja memória deve ser liberada.
Garantias e considerações:
- Caso as requisições ultrapassem o tamanho da memória só serão atendidas as requisições possíveis, considerando a linha do tempo. Assim caso o tamanho da memória for 200 e as requisições forem {50, 50, 90, 30, 10, 5} a requisição 3 por 30 bytes não será atendida, mas a 4 de 10 bytes será, enchendo a memória, o que impedirá que a solicitação 5 por 5 bytes seja atendida.
- O valor máximo da memória será de 2048 bytes.
- O número de elementos do vetor de requisição de alocação e do vetor de requisição de liberação pode variar de 0 a 200.
- Devem ser processadas todas as alocações possíveis para só então processar as liberações.
Exemplo 1
Entrada
200 3 50 100 50 1 1
Saída
100
Exemplo 2
Entrada
200 4 30 40 60 85 1 1
Saída
70
Exemplo 3
Entrada
300 5 50 20 30 100 20 0
Saída
80
Exemplo 4
Entrada
300 9 1 10 40 3 150 50 150 1 44 4 0 2 5 8
Saída
50
