Scribd Logo
Upload

Welcome to Scribd!

  • 639 views

    Operating system: Full name: Trịnh Mạnh Hùng Student id: 1952740

    Uploaded by

    Trịnh Mạnh Hùng
    This document contains code for simulating a CPU scheduler using threads and queues. It includes code for the CPU thread, loader thread, process control blocks (PCBs), and queues. The CPU thread uses a time quantum to limit how long each process runs before being placed back in the ready queue. The loader thread loads processes from an input file into the ready queue over time based on their arrival times.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Operating system: Full name: Trịnh Mạnh Hùng Student id: 1952740

    Uploaded by

    Trịnh Mạnh Hùng
    639 views11 pages
    This document contains code for simulating a CPU scheduler using threads and queues. It includes code for the CPU thread, loader thread, process control blocks (PCBs), and queues. The CPU thread uses a time quantum to limit how long each process runs before being placed back in the ready queue. The loader thread loads processes from an input file into the ready queue over time based on their arrival times.

    Original Description:

    operating system lab 4

    Original Title

    1952740-Lab4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains code for simulating a CPU scheduler using threads and queues. It includes code for the CPU thread, loader thread, process control blocks (PCBs), and queues. The CPU thread uses a time quantum to limit how long each process runs before being placed back in the ready queue. The loader thread loads processes from an input file into the ready queue over time based on their arrival times.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    639 views11 pages

    Operating system: Full name: Trịnh Mạnh Hùng Student id: 1952740

    Uploaded by

    Trịnh Mạnh Hùng
    This document contains code for simulating a CPU scheduler using threads and queues. It includes code for the CPU thread, loader thread, process control blocks (PCBs), and queues. The CPU thread uses a time quantum to limit how long each process runs before being placed back in the ready queue. The loader thread loads processes from an input file into the ready queue over time based on their arrival times.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 11

    Operating system

    Lab 4
    Full name: Trịnh Mạnh Hùng
    Student id: 1952740

    3. Practice (7 PTS):

    Code of sched.c:

    #include "queue.h"
    #include <pthread.h>
    #include <unistd.h>
    #include <stdio.h>
    #include <stdlib.h>

    #define TIME_UNIT 100 // In microsecond

    static struct pqueue_t in_queue; // Queue for incomming processes


    static struct pqueue_t ready_queue; // Queue for ready processes

    static int load_done = 0;

    static int timeslot; // The maximum amount of time a process is allowed


    // to be run on CPU before being swapped out

    // Emulate the CPU


    void * cpu(void * arg) {
    int timestamp = 0;
    /* Keep running until we have loaded all process from the input file
    * and there is no process in ready queue */
    while (!load_done || !empty(&ready_queue)) {
    /* Pickup the first process from the queue */
    struct pcb_t * proc = de_queue(&ready_queue);
    if (proc == NULL) {
    /* If there is no process in the queue then we
    * wait until the next time slice */
    timestamp++;
    usleep(TIME_UNIT);
    }else{
    /* Execute the process */
    int start = timestamp; // Save timestamp
    int id = proc->pid; // and PID for tracking
    /* Decide the amount of time that CPU will spend
    * on the process and write it to 'exec_time'.
    * It should not exeed 'timeslot'.
    */
    int exec_time = 0; // burst time, timslot is quantum time.

    // TODO: Calculate exec_time from process's PCB

    // YOUR CODE HERE


    int timeout;
    if(proc->burst_time >= timeslot) timeout = timeslot;
    else timeout = proc->burst_time;
    //printf("burst: %d, timedo: %d\n", proc->burst_time, timeout);

    exec_time = timeout;
    proc->burst_time -= timeout;
    /* Emulate the execution of the process by using
    * 'usleep()' function */
    usleep(exec_time * TIME_UNIT);

    /* Update the timestamp */


    timestamp += exec_time;

    // TODO: Check if the process has terminated (i.e. its


    // burst time is zero. If so, free its PCB. Otherwise,
    // put its PCB back to the queue.

    // YOUR CODE HERE


    if(proc->burst_time != 0) {
    en_queue(&ready_queue, proc);
    }
    else free(proc);
    /* Track runtime status */
    printf("%2d-%2d: Execute %d\n", start, timestamp, id);
    }
    }
    }

    // Emulate the loader


    void * loader(void * arg) {
    int timestamp = 0;
    /* Keep loading new process until the in_queue is empty*/
    while (!empty(&in_queue)) {
    struct pcb_t * proc = de_queue(&in_queue);
    /* Loader sleeps until the next process available */
    int wastetime = proc->arrival_time - timestamp;
    usleep(wastetime * TIME_UNIT);
    /* Update timestamp and put the new process to ready queue */
    timestamp += wastetime;
    en_queue(&ready_queue, proc);
    }
    /* We have no process to load */
    load_done = 1;
    }

    /* Read the list of process to be executed from stdin */


    void load_task() {
    FILE* fp;
    fp = fopen("input.txt", "r");
    if(fp == NULL) {
    printf("Error! Can not open file\n");
    exit(1);
    }
    int num_proc = 0;
    fscanf(fp, "%d %d\n", &timeslot, &num_proc);
    int i;
    for (i = 0; i < num_proc; i++) {
    struct pcb_t * proc =
    (struct pcb_t *)malloc(sizeof(struct pcb_t));
    fscanf(fp, "%d %d\n", &proc->arrival_time, &proc->burst_time);
    proc->pid = i;
    en_queue(&in_queue, proc);
    }
    }

    int main() {
    pthread_t cpu_id; // CPU ID
    pthread_t loader_id; // LOADER ID

    /* Initialize queues */
    initialize_queue(&in_queue);
    initialize_queue(&ready_queue);

    /* Read a list of jobs to be run */


    load_task();
    /* Start cpu */
    pthread_create(&cpu_id, NULL, cpu, NULL);
    /* Start loader */
    pthread_create(&loader_id, NULL, loader, NULL);

    /* Wait for cpu and loader */


    pthread_join(cpu_id, NULL);
    pthread_join(loader_id, NULL);

    pthread_exit(NULL);

    Code of sched_FCFS.c:

    #include "queue.h"
    #include <pthread.h>
    #include <unistd.h>
    #include <stdio.h>
    #include <stdlib.h>

    #define TIME_UNIT 100 // In microsecond

    static struct pqueue_t in_queue; // Queue for incomming processes


    static struct pqueue_t ready_queue; // Queue for ready processes

    static int load_done = 0;

    static int timeslot; // The maximum amount of time a process is allowed


    // to be run on CPU before being swapped out

    // Emulate the CPU


    void * cpu(void * arg) {
    int timestamp = 0;
    /* Keep running until we have loaded all process from the input file
    * and there is no process in ready queue */
    while (!load_done || !empty(&ready_queue)) {
    /* Pickup the first process from the queue */
    struct pcb_t * proc = de_queue(&ready_queue);
    if (proc == NULL) {
    /* If there is no process in the queue then we
    * wait until the next time slice */
    timestamp++;
    usleep(TIME_UNIT);
    }else{
    /* Execute the process */
    int start = timestamp; // Save timestamp
    int id = proc->pid; // and PID for tracking
    /* Decide the amount of time that CPU will spend
    * on the process and write it to 'exec_time'.
    * It should not exeed 'timeslot'.
    */
    int exec_time = 0; // burst time, timslot is quantum time.

    // TODO: Calculate exec_time from process's PCB

    // YOUR CODE HERE


    int timeout;
    if(proc->burst_time > 0) timeout = proc->burst_time;
    exec_time = timeout;
    proc->burst_time -= timeout;
    /* Emulate the execution of the process by using
    * 'usleep()' function */
    usleep(exec_time * TIME_UNIT);

    /* Update the timestamp */


    timestamp += exec_time;

    // TODO: Check if the process has terminated (i.e. its


    // burst time is zero. If so, free its PCB. Otherwise,
    // put its PCB back to the queue.

    // YOUR CODE HERE


    if(proc->burst_time != 0) {
    en_queue(&ready_queue, proc);
    }
    else free(proc);
    /* Track runtime status */
    printf("%2d-%2d: Execute %d\n", start, timestamp, id);
    }
    }
    }

    // Emulate the loader


    void * loader(void * arg) {
    int timestamp = 0;
    /* Keep loading new process until the in_queue is empty*/
    while (!empty(&in_queue)) {
    struct pcb_t * proc = de_queue(&in_queue);
    /* Loader sleeps until the next process available */
    int wastetime = proc->arrival_time - timestamp;
    usleep(wastetime * TIME_UNIT);
    /* Update timestamp and put the new process to ready queue */
    timestamp += wastetime;
    en_queue(&ready_queue, proc);
    }
    /* We have no process to load */
    load_done = 1;
    }

    /* Read the list of process to be executed from stdin */


    void load_task() {
    FILE* fp;
    fp = fopen("input.txt", "r");
    if(fp == NULL) {
    printf("Error! Can not open file\n");
    exit(1);
    }
    int num_proc = 0;
    fscanf(fp, "%d %d\n", &timeslot, &num_proc);
    int i;
    for (i = 0; i < num_proc; i++) {
    struct pcb_t * proc =
    (struct pcb_t *)malloc(sizeof(struct pcb_t));
    fscanf(fp, "%d %d\n", &proc->arrival_time, &proc->burst_time);
    proc->pid = i;
    en_queue(&in_queue, proc);
    }
    }

    int main() {
    pthread_t cpu_id; // CPU ID
    pthread_t loader_id; // LOADER ID

    /* Initialize queues */
    initialize_queue(&in_queue);
    initialize_queue(&ready_queue);

    /* Read a list of jobs to be run */


    load_task();
    /* Start cpu */
    pthread_create(&cpu_id, NULL, cpu, NULL);
    /* Start loader */
    pthread_create(&loader_id, NULL, loader, NULL);

    /* Wait for cpu and loader */


    pthread_join(cpu_id, NULL);
    pthread_join(loader_id, NULL);

    pthread_exit(NULL);

    Code of queue.c:

    #include <stdlib.h>
    #include "queue.h"
    #include <pthread.h>

    /* Remember to initilize the queue before using it */


    void initialize_queue(struct pqueue_t * q) {
    q->head = q->tail = NULL;
    //pthread_mutex_init(&q->lock, NULL);
    }

    /* Return non-zero if the queue is empty */


    int empty(struct pqueue_t * q) {
    return (q->head == NULL);
    }

    /* Get PCB of a process from the queue (q).


    * Return NULL if the queue is empty */
    struct pcb_t * de_queue(struct pqueue_t * q) {
    struct pcb_t * proc = NULL;
    // TODO: return q->head->data and remember to update the queue's head
    // and tail if necessary. Remember to use 'lock' to avoid race
    // condition

    // YOUR CODE HERE


    struct qitem_t *temp = q->head;
    if(!empty(q))
    if(q->head == q->tail) {
    proc = q->head->data;
    q->head = q->tail = NULL;
    }
    else {
    proc = q->head->data;
    q->head = q->head->next;
    }
    return proc;
    }

    /* Put PCB of a process to the queue. */


    void en_queue(struct pqueue_t * q, struct pcb_t * proc) {
    // TODO: Update q->tail.
    // Remember to use 'lock' to avoid race condition

    // YOUR CODE HERE


    struct qitem_t *temp = (struct qitem_t *)malloc(sizeof(struct qitem_t));;
    temp->data = proc;
    temp->next = NULL;
    if(empty(q)) {
    q->head = q->tail = temp;
    }
    else {
    q->tail->next = temp;
    q->tail = temp;
    if(q->head->next == NULL) {
    q->head->next = q->tail;
    }
    }
    }

    Output when running given test.sh:


    Code of new test.sh:

    #!/bin/bash
    echo "Input file:"
    cat input.txt
    echo "Results_Round Robin"
    gcc sched.c queue.c -o sched -lpthread
    cat input.txt | ./sched
    echo "Results_FCFS"
    gcc sched.c queue.c -o sched_FCFS.s -lpthread
    cat input.txt | ./sched_FCFS

    Output of new test.sh file:


    Result using Make file:
    4. Exercise (3PTS)

    Suppose that the following processes arrive for execution at the times indicated. Each process
    will run for the amount of time listed. In answering the questions, use non-preemptive
    scheduling, and base all decisions on the information you have at the time the decision must be
    made.

    a) What is the average turnaround time for these processes with the FCFS scheduling
    algorithm?
    The average turnaround time for these processes with the FCFS scheduling algorithm is
    (9 − 0) + (14 – 0.6) + (17 − 1)
    = 12.8
    3
    b) What is the average turnaround time for these processes with the SJF scheduling
    algorithm?
    The average turnaround time for these processes with the SJF is
    (9 − 0) + (12 − 1) + (17 − 0.6)
    ≈ 12.13
    3
    c) The SJF algorithm is supposed to improve performance, but notice that we chose to run
    process P1 at time 0 because we did not know that two shorter processes would arrive
    soon. Compute what the average turnaround time will be if the CPU is left idle for the
    first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are
    waiting during this idle time, so their waiting time may increase. This algorithm could be
    called future-knowledge scheduling.

    After CPU is left idle for one unit then the processes are normally run using SJF
    scheduling. It means that after one unit, P3 will run first then P2, P1 run respectively.
    (1+3−1) + (1+3+5−0.6)+(1+3+5+9) 29.4
    The average turnaround time is = = 9.8
    3 3

    You might also like