Me dan un tamaño total máximo de unsigned int = 100000000 y tenemos que ingresar el tamaño de cada procesador, pero no sabemos la cantidad de matriz que habrá ... La mayoría de las personas que vi en línea ya tienen un tamaño de matriz definido , así que me preguntaba si hay alguna otra forma de hacer el mejor algoritmo de ajuste sin el tamaño de la matriz. Parece que no puedo encontrar una buena manera de crear este algoritmo. También probé la lista doblemente vinculada y estoy teniendo problemas

int MaxMem = 20000000;

struct PCB
{
    int ProcessID;
    unsigned int ProcessorSize;
    unsigned int Begin;
    unsigned int End;
    int sumOfMemory = 0;
    PCB ()
    {
        ProcessID = NULL;
        ProcessorSize = NULL;
        priority = NULL;
    }

    bool operator < (const PCB &c)
    {
        return priority < c.priority;
    }
    bool operator > (const PCB &c)
    {
        return priority > c.priority;
    }

    void rem(PCB &a)
    {
        a.ProcessID = NULL;
        a.ProcessorSize = NULL;
        a.priority = NULL;
        sumOfMemory -= a.ProcessorSize;
    }
};
 static int start = NULL;
 static int temp;

void best_fit(PCB a,vector<int> &memory)
{
    int bestfit = -1;
    unsigned int endMem = MaxMem;
    unsigned int tempMem = MaxMem;
       if((start == NULL) && (bestfit = -1))
        {
            temp = start;
            memory.push_back(a.ProcessorSize);
            bestfit = a.ProcessID;
            start = a.ProcessorSize;
            tempMem -= a.ProcessorSize;
            cout << "pushed" << endl;
        }
        else if((start != NULL)&& (bestfit = -1) && (a.ProcessorSize < memorySize) && (a.sumOfMemory < tempMem) )
        {
            memory.push_back(a.ProcessorSize);
            bestfit = a.ProcessID;
            tempMem -= a.ProcessorSize;
            temp = start;
            start += a.ProcessorSize;
            cout << "pushed!" << endl;
        }
        else
        {
             cout << "No space" << endl;
        }

}
int main()
{
    PCB pcb;
    while(true)
    {
        vector<int> mem;
        cout << "process ID?" << endl;
        cin >> pcb.ProcessID;
        cout << "enter processor size?" << endl;
        cin >> pcb.ProcessorSize;
        bestfit(pcb,mem);
    }
-2
darkflames363 13 dic. 2016 a las 23:24
Falta una cláusula else final. ¿Qué sucede si ambas declaraciones if son falsas?
 – 
Thomas Matthews
13 dic. 2016 a las 23:30
Parece que falta un bucle for en su código. ¿Dónde se define la variable i?
 – 
Jvinniec
13 dic. 2016 a las 23:30
Necesitaríamos la definición de PCB para poder brindarle información.
 – 
Thomas Matthews
13 dic. 2016 a las 23:32
¿Está asignando (asociando) memoria con un procesador o asignando bloques de memoria?
 – 
Thomas Matthews
13 dic. 2016 a las 23:33
¿Dónde está definido start? Cual es su tipo? Edita tu publicación con la respuesta.
 – 
Thomas Matthews
13 dic. 2016 a las 23:34

1 respuesta

La mejor respuesta

Parece que lo que quieres es un asignador de bloques básico. Mencionas que a tu maestro no le importa cómo se implementa, siempre que funcione. Si bien eso puede no ser muy útil en cuanto a la dirección, nos da mucho margen de maniobra en nuestra implementación.

La estrategia de mejor ajuste es simplemente seleccionar el bloque más pequeño disponible que satisfaga la solicitud. Si la lista disponible está ordenada por tamaño de bloque, el bloque que mejor se ajusta es el límite inferior, lo que hace que el contenedor std::multimap sea perfectamente adecuado para esta tarea.

Normalmente, podría considerarse una mala práctica usar un contenedor como este en un asignador de memoria (mejor reutilizar la tienda gratuita), pero nuevamente, dado que a Teach no le importa, también podríamos facilitar las cosas.

Aquí cada bloque reserva espacio para un encabezado. Esto solo almacena el tamaño del bloque, pero se pueden agregar campos adicionales. Inicialmente, la lista disponible contiene un bloque grande. Si el bloque encontrado es mayor que la solicitud por algún umbral, el bloque se divide en dos y el resto se coloca nuevamente en la lista disponible.

// memory block header size in words.
#define HEADER_SIZE static_cast<word_type>(1)

// extract block size from block header.
#define BLOCK_SIZE(location) \
    (heap[(location) - HEADER_SIZE])

// heap types/members.
typedef unsigned int word_type;
constexpr  word_type heap_size = 1000000;
word_type  heap[heap_size];

// key: block size; data: block location.
std::multimap<word_type, word_type> free_list;

void heap_initialize()
{
    word_type next = HEADER_SIZE;
    BLOCK_SIZE(next) = heap_size;
    release(next);
}

void release(word_type p)
{
    if (p != 0)
        free_list.insert(std::make_pair(BLOCK_SIZE(p), p));
}

word_type acquire(word_type request)
{
    if (request == 0)
        return 0;

    // threshold minimum is (header + 1*data word).
    word_type threshold = 8;
    request = (request + HEADER_SIZE + (threshold-1))
            / threshold * threshold;

    // locate best-fit.
    auto best_iter = free_list.lower_bound(request);

    // no suitable block found.
    if (best_iter == free_list.end())
        throw std::bad_alloc();

    // extract index; update free list.
    word_type best = best_iter->second;
    free_list.erase(best_iter);

    // split block.
    if (BLOCK_SIZE(best) > request + threshold) {
        word_type  next  = best + request;
        BLOCK_SIZE(next) = BLOCK_SIZE(best) - request;
        BLOCK_SIZE(best) = request;
        release(next);
    }
    return best;
}

La prueba de este código con salida se puede ver aquí. Una implementación alternativa que utiliza una lista doblemente enlazada y la unión de bloques es aquí.

Espero que esto ayude. Buena suerte.

0
John Q. 17 dic. 2016 a las 15:57