Skip to content

Instantly share code, notes, and snippets.

@Tahmeed156
Last active January 22, 2022 11:14
Show Gist options
  • Save Tahmeed156/34ef1b949d975d7e8634e8856b0745be to your computer and use it in GitHub Desktop.
Save Tahmeed156/34ef1b949d975d7e8634e8856b0745be to your computer and use it in GitHub Desktop.
Modification of a test file taken from https://www.cs.virginia.edu/~cr4bd/4414/S2021/lottery.html for `xv6` scheduling
#include "types.h"
#include "user.h"
#include "pstat.h"
#undef USE_YIELD
#define MAX_CHILDREN 32
#define LARGE_TICKET_COUNT 100000
#define MAX_YIELDS_FOR_SETUP 100
__attribute__((noreturn))
void yield_forever() {
while (1) {
yield();
}
}
__attribute__((noreturn))
void run_forever() {
while (1) {
__asm__("");
}
}
int spawn(int tickets) {
int pid = fork();
if (pid == 0) {
settickets(tickets);
yield();
#ifdef USE_YIELD
yield_forever();
#else
run_forever();
#endif
} else if (pid != -1) {
return pid;
} else {
printf(2, "error in fork\n");
return -1;
}
}
int find_index_of_pid(int *list, int list_size, int pid) {
for (int i = 0; i < list_size; ++i) {
if (list[i] == pid)
return i;
}
return -1;
}
void wait_for_ticket_counts(int num_children, int *pids, int *tickets) {
for (int yield_count = 0; yield_count < MAX_YIELDS_FOR_SETUP; ++yield_count) {
yield();
int done = 1;
struct pstat info;
getpinfo(&info);
for (int i = 0; i < num_children; ++i) {
int index = find_index_of_pid(info.pid, info.num_processes, pids[i]);
if (info.tickets[index] != tickets[i]) done = 0;
}
if (done)
break;
}
}
int main(int argc, char *argv[])
{
if (argc < 3) {
printf(2, "usage: %s seconds tickets1 tickets2 ... ticketsN\n"
" seconds is the number of time units to run for\n"
" ticketsX is the number of tickets to give to subprocess N\n",
argv[0]);
exit();
}
int tickets_for[MAX_CHILDREN];
int active_pids[MAX_CHILDREN];
int num_seconds = atoi(argv[1]);
int num_children = argc - 2;
if (num_children > MAX_CHILDREN) {
printf(2, "only up to %d supported\n", MAX_CHILDREN);
exit();
}
/* give us a lot of ticket so we don't get starved */
settickets(LARGE_TICKET_COUNT);
for (int i = 0; i < num_children; ++i) {
int tickets = atoi(argv[i + 2]);
tickets_for[i] = tickets;
active_pids[i] = spawn(tickets);
}
wait_for_ticket_counts(num_children, active_pids, tickets_for);
struct pstat before, after;
before.num_processes = after.num_processes = -1;
getpinfo(&before);
sleep(num_seconds);
getpinfo(&after);
for (int i = 0; i < num_children; ++i) {
kill(active_pids[i]);
}
for (int i = 0; i < num_children; ++i) {
wait();
}
if (before.num_processes >= NPROC || after.num_processes >= NPROC) {
printf(2, "getpinfo's num_processes is greater than NPROC before parent slept\n");
return 1;
}
if (before.num_processes < 0 || after.num_processes < 0) {
printf(2, "getpinfo's num_processes is negative -- not changed by syscall?\n");
return 1;
}
printf(1, "TICKETS\tTICKS\n");
for (int i = 0; i < num_children; ++i) {
int before_index = find_index_of_pid(before.pid, before.num_processes, active_pids[i]);
int after_index = find_index_of_pid(after.pid, after.num_processes, active_pids[i]);
if (before_index == -1)
printf(2, "child %d did not exist for getpinfo before parent slept\n", i);
if (after_index == -1)
printf(2, "child %d did not exist for getpinfo after parent slept\n", i);
if (before_index == -1 || after_index == -1) {
printf(1, "%d\t--unknown--\n", tickets_for[i]);
} else {
if (before.tickets[before_index] != tickets_for[i]) {
printf(2, "child %d had wrong number of tickets in getpinfo before parent slept\n", i);
}
if (after.tickets[after_index] != tickets_for[i]) {
printf(2, "child %d had wrong number of tickets in getpinfo after parent slept\n", i);
}
printf(1, "%d\t%d\n", tickets_for[i], after.ticks[after_index] - before.ticks[before_index]);
}
}
exit();
}
  • Add the above file and update Makefile to run fetch as a user program
  • Add a new int num_processes to pstat.h
  • Modify your scheduling algorithm getpinfo syscall to set the num_processes variable to total UNUSED processes number of processes that are in use
  • Add yield as a syscall
void
sys_yield(void)
{
  yield();
}
  • Run the command fetch 1500 100 200 300 400 500
@asifajrof
Copy link

asifajrof commented Jan 22, 2022

modification in the pstat.h file (and modification in getpinfo syscall) can be excluded.

  • add a helper function to get the num_process in fetch.c
Diff-log
diff --git a/fetch.c b/fetch.c
index c9a1886..69d6d0d 100644
--- a/fetch.c
+++ b/fetch.c
@@ -1,5 +1,6 @@
 #include "types.h"
 #include "user.h"
+#include "param.h"
 #include "pstat.h"

 #undef USE_YIELD
@@ -47,6 +48,14 @@ int find_index_of_pid(int *list, int list_size, int pid) {
     return -1;
 }

+int get_num_process(int *inuse){
+       int num_processes = 0;
+       for(int i=0; i<NPROC; ++i){
+               num_processes += inuse[i];
+       }
+       return num_processes;
+}
+
 void wait_for_ticket_counts(int num_children, int *pids, int *tickets) {
     for (int yield_count = 0; yield_count < MAX_YIELDS_FOR_SETUP; ++yield_count) {
         yield();
@@ -54,7 +63,7 @@ void wait_for_ticket_counts(int num_children, int *pids, int *tickets) {
         struct pstat info;
         getpinfo(&info);
         for (int i = 0; i < num_children; ++i) {
-            int index = find_index_of_pid(info.pid, info.num_processes, pids[i]);
+            int index = find_index_of_pid(info.pid, get_num_process(info.inuse), pids[i]);
             if (info.tickets[index] != tickets[i]) done = 0;
         }
         if (done)
@@ -88,28 +97,25 @@ int main(int argc, char *argv[])
     }
     wait_for_ticket_counts(num_children, active_pids, tickets_for);
     struct pstat before, after;
-    before.num_processes = after.num_processes = -1;
     getpinfo(&before);
+       int before_num_processes = get_num_process(before.inuse);
     sleep(num_seconds);
     getpinfo(&after);
+       int after_num_processes = get_num_process(after.inuse);
     for (int i = 0; i < num_children; ++i) {
         kill(active_pids[i]);
     }
     for (int i = 0; i < num_children; ++i) {
         wait();
     }
-    if (before.num_processes >= NPROC || after.num_processes >= NPROC) {
+    if (before_num_processes >= NPROC || after_num_processes >= NPROC) {
         printf(2, "getpinfo's num_processes is greater than NPROC before parent slept\n");
         return 1;
     }
-    if (before.num_processes < 0 || after.num_processes < 0) {
-        printf(2, "getpinfo's num_processes is negative -- not changed by syscall?\n");
-        return 1;
-    }
     printf(1, "TICKETS\tTICKS\n");
     for (int i = 0; i < num_children; ++i) {
-        int before_index = find_index_of_pid(before.pid, before.num_processes, active_pids[i]);
-        int after_index = find_index_of_pid(after.pid, after.num_processes, active_pids[i]);
+        int before_index = find_index_of_pid(before.pid, before_num_processes, active_pids[i]);
+        int after_index = find_index_of_pid(after.pid, after_num_processes, active_pids[i]);
         if (before_index == -1)
             printf(2, "child %d did not exist for getpinfo before parent slept\n", i);
         if (after_index == -1)
@@ -127,4 +133,4 @@ int main(int argc, char *argv[])
         }
     }
     exit();
-}
\ No newline at end of file
+}
`fetch.c`
#include "types.h"
#include "user.h"
#include "param.h"
#include "pstat.h"

#undef USE_YIELD
#define MAX_CHILDREN 32
#define LARGE_TICKET_COUNT 100000
#define MAX_YIELDS_FOR_SETUP 100

__attribute__((noreturn))
void yield_forever() {
    while (1) {
        yield();
    }
}

__attribute__((noreturn))
void run_forever() {
    while (1) {
        __asm__("");
    }
}

int spawn(int tickets) {
    int pid = fork();
    if (pid == 0) {
        settickets(tickets);
        yield();
#ifdef USE_YIELD
        yield_forever();
#else
        run_forever();
#endif
    } else if (pid != -1) {
        return pid;
    } else {
        printf(2, "error in fork\n");
        return -1;
    }
}

int find_index_of_pid(int *list, int list_size, int pid) {
    for (int i = 0; i < list_size; ++i) {
        if (list[i] == pid)
            return i;
    }
    return -1;
}

int get_num_process(int *inuse){
    int num_processes = 0;
    for(int i=0; i<NPROC; ++i){
        num_processes += inuse[i];
    }
    return num_processes;
}

void wait_for_ticket_counts(int num_children, int *pids, int *tickets) {
    for (int yield_count = 0; yield_count < MAX_YIELDS_FOR_SETUP; ++yield_count) {
        yield();
        int done = 1;
        struct pstat info;
        getpinfo(&info);
        for (int i = 0; i < num_children; ++i) {
            int index = find_index_of_pid(info.pid, get_num_process(info.inuse), pids[i]);
            if (info.tickets[index] != tickets[i]) done = 0;
        }
        if (done)
            break;
    }
}

int main(int argc, char *argv[])
{
    if (argc < 3) {
        printf(2, "usage: %s seconds tickets1 tickets2 ... ticketsN\n"
                  "       seconds is the number of time units to run for\n"
                  "       ticketsX is the number of tickets to give to subprocess N\n",
                  argv[0]);
        exit();
    }
    int tickets_for[MAX_CHILDREN];
    int active_pids[MAX_CHILDREN];
    int num_seconds = atoi(argv[1]);
    int num_children = argc - 2;
    if (num_children > MAX_CHILDREN) {
        printf(2, "only up to %d supported\n", MAX_CHILDREN);
        exit();
    }
    /* give us a lot of ticket so we don't get starved */
    settickets(LARGE_TICKET_COUNT);
    for (int i = 0; i < num_children; ++i) {
        int tickets = atoi(argv[i + 2]);
        tickets_for[i] = tickets;
        active_pids[i] = spawn(tickets);
    }
    wait_for_ticket_counts(num_children, active_pids, tickets_for);
    struct pstat before, after;
    getpinfo(&before);
    int before_num_processes = get_num_process(before.inuse);
    sleep(num_seconds);
    getpinfo(&after);
    int after_num_processes = get_num_process(after.inuse);
    for (int i = 0; i < num_children; ++i) {
        kill(active_pids[i]);
    }
    for (int i = 0; i < num_children; ++i) {
        wait();
    }
    if (before_num_processes >= NPROC || after_num_processes >= NPROC) {
        printf(2, "getpinfo's num_processes is greater than NPROC before parent slept\n");
        return 1;
    }
    printf(1, "TICKETS\tTICKS\n");
    for (int i = 0; i < num_children; ++i) {
        int before_index = find_index_of_pid(before.pid, before_num_processes, active_pids[i]);
        int after_index = find_index_of_pid(after.pid, after_num_processes, active_pids[i]);
        if (before_index == -1)
            printf(2, "child %d did not exist for getpinfo before parent slept\n", i);
        if (after_index == -1)
            printf(2, "child %d did not exist for getpinfo after parent slept\n", i);
        if (before_index == -1 || after_index == -1) {
            printf(1, "%d\t--unknown--\n", tickets_for[i]);
        } else {
            if (before.tickets[before_index] != tickets_for[i]) {
                printf(2, "child %d had wrong number of tickets in getpinfo before parent slept\n", i);
            }
            if (after.tickets[after_index] != tickets_for[i]) {
                printf(2, "child %d had wrong number of tickets in getpinfo after parent slept\n", i);
            }
            printf(1, "%d\t%d\n", tickets_for[i], after.ticks[after_index] - before.ticks[before_index]);
        }
    }
    exit();
}

@asifajrof
Copy link

for those who are getting the
child %d had wrong number of tickets in getpinfo before parent slept

  • tweak with the MAX_YIELDS_FOR_SETUP. Increasing it to a certain amount will make the parent process wait necessary times before it calls getpinfo for the before structure.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment