Difference between revisions of "Problema da fragmentação de memória"

Latest revision as of 14:50, 1 October 2008

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:

1. Tamanho da memória.
2. Quantidade de requisições de alocação.
3. 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.
4. Quantidade de requisições de liberações.
5. 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