A Lei de Moore deixou de ser uma verdade há alguns anos. Durante um tempo, a indústria de processadores se apegou ao Escalonamento de Dennard para aumentar o desempenho de cada core, aumentando a velocidade de clock. Em paralelo, incentivados pela regra de Amdahl’s, a quantidade de cores em um chip cresceu consideravelmente na última década (o primeiro processador comercial com mais de um core foi lançado em 2005). Mais recentemente, a tendência parece levar às Arquiteturas Específicas de Domínio para extrair ainda mais desempenho. O exemplo mais notável são as placas aceleradoras de aprendizado de máquina lançadas pela Google. Mas isso é spoiler de uma outra disciplina.

Neste contexto, o Homem-Morcego, Cavaleiro das Trevas, Cruzado Encapuzado, Maior Detetive do Mundo, primeiro de seu nome, mas também conhecido como Batman, precisa de sua ajuda para construir um novo bat-computador para combater o crime em Gothan City. Você, como grande fã do trabalho do vigilante noturno, se colocou à disposição para implementar as funções de gerenciamento da bat-memória.

Implemente um programa batcomputador que simula algumas operações da bat-memória. Para isso, você precisará de um vetor dinâmico de inteiros para representar os dados armazenados na memória. Tome cuidado com as restrições do nosso herói, às vezes ele é meio exigente.

Operações

Em todos os testes, a bat-memória irá começar com 8 inteiros e crescer de acordo com a necessidade. A primeira linha da entrada contém um inteiro, que representa o número de operações a serem analisadas. Cada uma das linhas seguintes corresponde a uma operação de memória.

Bat-alloc

A operação de bat-alloc guarda uma lista de inteiros na bat-memória virtual do seu bat-computador e imprime a posição de início. Batman pediu que todo vetor de inteiros seja armazenado de forma contínua, ou seja, um vetor de 4 inteiros não pode ter seus inteiros colocados espalhados pela bat-memória.

Além disso, Batman pediu para você sempre colocar o vetor no primeiro espaço de memória disponível em que ele cabe, seguindo a ordem dos índices. Assim, se um vetor couber começando na posição 5 ou na posição 40, você sempre irá escolher a posição 5.

Operações como esta serão lidas na forma:

bat-alloc N LISTA

Essa operação armazena uma lista de N inteiros na memória virtual. A linha seguinte contém um exemplo de operação para armazenar 5 inteiros na memória.

bat-alloc 5 10 12 16 18 42

Após realizada a operação, você deve imprimir o local da memória onde o vetor foi armazenado. Há um detalhe importante: a primeira posição do espaço armazenado deve conter o tamanho do vetor. Assim, na bat-memória, teríamos algo como na figura:

Para este exemplo, a saída seria:

31

Caso não haja nenhum espaço contínuo para alocar o vetor, você deve duplicar a capacidade do vetor de bat-memória virtual. Você pode fazer isso criando um novo vetor e copiando (nos mesmos locais de memória) o vetor antigo. Assim, o vetor acima, depois de uma expansão, sempre permanecerá na posição 31, até que seja bat-liberado. Sempre será possível alocar após a expansão.

Bat-free

A operação de bat-free libera a memória correspondente a um vetor. Ela aparecerá no formato:

bat-free ENDEREÇO

Assim, seguindo o exemplo anterior, se o Batman te pedir para dar bat-free no endereço 31, você poderá usar as posições 31 a 36 (inclusive) livremente para alocar outras coisas depois. Perceba que isso irá deixar lacunas vazias na sua memória, mas no bat-computador isso não é um problema.

Depois da realização da operação de bat-free, pode ser que uma grande parte contígua do vetor fique livre. Para evitar desperdício, enquanto não houver bat-memória utilizada depois do primeiro quarto do vetor, ele deve ser reduzido pela metade. Por exemplo, se a memória tiver 128 inteiros e não houver nenhuma memória utilizada entre as posições 32 a 127 (inclusive), o vetor deve ser reduzido a 64 inteiros.

Atenção: a memória nunca deve ser reduzida a menos que 8 inteiros. Além disso, Batman, como grande programador que é, nunca erra os endereços passados para você. Assim, todo bat-free possui um alvo válido (que foi alocado e ainda não liberado).

Depois desta operação, não é necessário imprimir nada.

Bat-print

A operação de bat-print imprime a lista de inteiros indicada pelo seu início. Ela aparecerá no formato:

bat-print ENDEREÇO

Os inteiros são impressos separados por espaço e apenas os inteiros correspondentes ao vetor alocado naquela posição devem ser impressos. Lembre-se de que a posição apontada pelo endereço contém o tamanho do vetor.

Exemplo de saída:

10 12 16 18 42

Bat-uso

A operação de bat-uso imprime uma linha com dois inteiros: a quantidade de inteiros da memória que estão sendo usados (seja pela alocação ou por representarem o tamanho do vetor) e o tamanho total da bat-memória. A operação corresponde a uma linha sozinha, sem parâmetros:

bat-uso

Uma saída possível é:

321 de 512

Exemplo 1

Entrada

6
bat-alloc 5 1 2 3 4 5
bat-print 0
bat-alloc 3 9 8 7
bat-print 6
bat-free 0
bat-uso

Saída

0
1 2 3 4 5
6
9 8 7
4 de 16

Exemplo 2

Entrada

8
bat-alloc 7 52 57 63 25 33 40 37
bat-alloc 6 69 35 62 49 44 44
bat-free 0
bat-alloc 4 36 45 59 66
bat-uso
bat-alloc 3 24 34 51
bat-print 0
bat-uso

Saída

0
8
0
12 de 16
15
36 45 59 66
16 de 32

Dicas

Um aviso do Alfred: enquanto Bruce Wayne é despreocupado e irresponsável, Batman é frio, determinado e implacável. Não seja como Bruce Wayne! Antes de começar a programar, tome um tempo para pensar nas estruturas de dados utilizadas e nos algoritmos necessários para cada operação. Se começar a escrever código antes disso, pode ser que você gaste muito mais tempo do que necessário.

Em cada momento da execução do bat-computador, a memória conterá posições livres e posições ocupadas, então o vetor dinâmico corresponderá a uma sequência de blocos contíguos de posições livres ou ocupadas. Faça um desenho de um vetor de exemplo e se pergunte de que maneira ele seria representado em seu programa. Pode ser útil também criar uma função que liste e mostre os blocos atuais do vetor. Mesmo que ela não seja chamada na versão final do programa, funções como essa servem para inspecionar a estrutura de dados depois de cada operação e são convenientes durante o desenvolvimento.

Critérios

Você deve representar a memória virtual utilizando um vetor dinâmico de inteiros que crescem e diminuem de acordo com as regras acima. Para alocar e liberar memória você deverá usar malloc e free, mas outras operações sobre ao vetor devem ser implementadas diretamente. Assim, não serão permitidas outras funções para manipular memória, como realloc, memcpy, etc.

← Anterior Voltar Próximo →