C language ALDS1_3_B Queue

problem

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

The point

** Queue ** or ** Queue ** is one of the basic ** data structures ** of a computer. Data is held in a first-in, first-out list structure. When retrieving data from the queue, the data that was put in first is fetched in order. Putting data in a queue is called enqueue, and taking it out is called dequeue.

In other words, the Tokoroten method

Round robin [^ 1] scheduling can be simulated using queues that store (manage) processes. First, the processes in the initial state are queued in order. Next, until the queue is empty, repeat the process of "taking out the process from the beginning, processing at most Quantum [^ 2], and adding it to the queue again if the required processing (time) still remains". ..

[^ 1]: Round Robin is written in English as Round Robin. It is a word that means that some roles and turns are exchanged in order under certain conditions. It is used in various places such as task management of the OS of a personal computer in a simple but equally eternal way without using a special head.

[^ 2]: The maximum q ms of processes that can be processed by the CPU. The range that can be processed at one time.

Queue operation

Implementation

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

--Unused Quantum will not be carried over. --20 --100 = 0 and the loop progresses. --By performing modulo operation, cues are connected in a ring and loop.

Impressions

--The variable names in the commentary I was looking at were oversimplified, so I supplemented them. ――I couldn't understand it unless I debugged it carefully. ――If you imagine the shape of a ring, the concept of head and tail becomes difficult to understand, so it is better to have an image of a tokoroten and look at it as if you were taking it out, processing it, and storing it.

Time required 180 minutes

【review】

    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);
        }
     }

Recommended Posts

C language ALDS1_3_B Queue
Linked list (list_head / queue) in C language
[C language algorithm] Endianness
[C language algorithm] Block movement
Heapsort made in C language
[C language] readdir () vs readdir_r ()
C language ALDS1_4_A Linear Search
Multi-instance module test in C language
Function pointer and objdump ~ C language ~
Realize interface class in C language
Writing C language with Sympy (metaprogramming)
High energy efficiency programming language C
Introduction to Protobuf-c (C language ⇔ Python)
queue
[C language algorithm] Binary search tree
C language 8 queens problem solving 3 patterns
Segfault with 16 characters in C language
Call c language from python (python.h)
Closure 4 language comparison (Python, JavaScript, Java, C ++)
Socket communication by C language and Python
Generate C language from S-expressions in Python