File d'attente ALDS1_3

problème

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=ja

Le point

** Queue ** ou ** Queue ** est l'une des ** structures de données ** de base d'un ordinateur. Il contient les données dans une structure de liste premier entré, premier sorti. Lors de la récupération des données de la file d'attente, les données qui ont été insérées en premier sont récupérées dans l'ordre. Mettre des données dans une file d'attente est appelé encu, et le retirer s'appelle décuition.

En d'autres termes, la méthode Tokoten

La planification circulaire [^ 1] peut être simulée à l'aide de files d'attente qui stockent (gèrent) les processus. Tout d'abord, les processus à l'état initial sont mis en file d'attente dans l'ordre. Ensuite, jusqu'à ce que la file d'attente soit vide, répétez le processus consistant à "retirer le processus depuis le début, traiter au maximum Quantum [^ 2], et l'ajouter à nouveau à la file d'attente si le traitement requis (temps) reste". ..

[^ 1]: Round Robin est écrit en anglais comme Round Robin. C'est un mot qui signifie que certains rôles et tours sont échangés dans l'ordre sous certaines conditions. Il est utilisé dans divers endroits tels que la gestion des tâches du système d'exploitation d'un ordinateur personnel d'une manière simple mais également permanente sans utiliser de tête particulière.

[^ 2]: q ms maximum de processus que le CPU peut traiter. La plage qui peut être traitée en une seule fois.

Fonctionnement de la file d'attente

enqueue(x) --Ajoutez l'élément x à la fin de la file d'attente.
dequeue() --Récupérez un élément du début de la file d'attente.
isEmpty() --Vérifiez si la file d'attente est vide.
isFull() --Vérifiez si la file d'attente est pleine.

la mise en oeuvre

Q
Tableau unidimensionnel de type entier pour stocker des données
head
Variable de type entier qui est le premier pointeur
tail
Une variable de type entier qui est un pointeur de queue
enqueue(x) --Une fonction qui ajoute un élément à une file d'attente
dequeue() --Une fonction qui récupère les éléments depuis le début de la file d'attente

code

#include <stdio.h>
#include <string.h>
#define LEN 100000

typedef struct
{
    char name[100];
    int time;
} Process;

/* global variable */
static Process Q[LEN];
static int head, tail, n;

/* enqueue */
void enqueue(Process process_obj)
{
    Q[tail] = process_obj;
    tail = (tail + 1) % LEN;
}

/* dequeue */
Process dequeue()
{
    Process process_obj;

    process_obj = Q[head];
    head = (head + 1) % LEN;

    return process_obj;
}

int min(int a, int b) { return a < b ? a : b; }

int main(void)
{
    int elapse_time = 0;
    int time_ms;
    int qms;
    Process process_obj;

    /* input */
    scanf("%d %d", &n, &qms);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].time);
    }

    /* initialize */
    head = 1;
    tail = n + 1;

    while (head != tail)
    {
        process_obj = dequeue();
        time_ms = min(qms, process_obj.time);
        process_obj.time -= time_ms;
        elapse_time += time_ms;

        if (process_obj.time > 0)
            enqueue(process_obj);
        else
            printf("%s %d\n", process_obj.name, elapse_time);
    }
    return 0;
}

point

Le Quantum inutilisé ne sera pas reporté. --20 --100 = 0 et la boucle progresse.
En effectuant une opération modulaire, la file d'attente est connectée en anneau et en boucle.

Impressions

Les noms des variables dans l'explication que je regardais étaient trop simplifiés, alors je les ai complétés. ―― Je ne pourrais pas le comprendre sans un débogage minutieux. ――Si vous imaginez la forme d'un anneau, il sera difficile de comprendre le concept de tête et de queue, il est donc préférable d'avoir une image d'une joue ironique et de la regarder comme si elle avait été retirée, traitée et stockée.

Temps requis 180 minutes

【la revue】

2020/04/05 «Quand je l'ai écrit moi-même, c'est devenu la manière suivante d'écrire. Celui-ci semble être meilleur. --Manipuler la tête et la queue au lieu de manipuler toute la file d'attente ――J'ai oublié l'idée d'utiliser tout en vidant la file d'attente avec le calcul modulaire
Non mis en œuvre
Temps requis: 80 minutes

    while (head != tail)
    {
        process_obj = dequeue();
        if(process_obj.time > qms){
            process_obj.time -= qms;
            elapse_time += qms;
            enqueue(process_obj);
        } else {
            elapse_time += process_obj.time;
            printf("%s %d\n", process_obj.name, elapse_time);
        }
     }

File d'attente ALDS1_3_B langage C