Programming language:C;

Programming environment: minix 3(Linux like system);

Thx!

Modify the scheduler such that all processes use fair-share scheduling. Group mem- bership is determined by the process group identification (field mp procgrp of struct mproc), file /usr/src/minix/servers/pm/mproc.h.

With fair-share scheduling, the CPU is shared by a set of processes according to the group to which they belong. For example, if there are three groups G1, G2 and G3. Each group should get one third of the CPU time with fair-share scheduling. Let us suppose that there is one process in G1, three processes in G2, and six processes in G3. The process in group G1 should get 33% of the CPU time, each process in G2 should get 11% of the CPU time and each process in G3 should get 5.5% of the CPU time.

I have implement a new system call with signature: int getdpids(pid t top, pid t dpids[], int len); It finds process IDs (PIDs) of descendant processes of a given process, in breath first search order. The system call takes three arguments: the PID of the top process (top), a array to store the PIDs (dpids[]) and an integer that indicates the size of the array (len), in PIDs.

Now I need to Modify the scheduler such that all processes use fair-share scheduling.

Use the following two test programs:

/* File: tester1.c *

* A CPU-bound process (no children).

*/ #include #include #include int main(int argc, char *argv[]) { int i, j; i = 1; while (1) { i = j; j = i; } } /* File: tester2.c * * A CPU-bound process with one child. */ #include 1 #include #include int main(int argc, char *argv[]) { int i, j; fork(); i = 1; while (1) { i = j; j = i; } } Start each program in different terminals using ./tester1 & and ./tester2 &. The command ps can be used to confirm that processes are created in two different groups: minix# ps -o pid,ppid,pgid,command PID PPID PGID COMMAND 667 666 667 -sh 750 667 667 ./tester2 751 750 667 ./tester2 678 677 678 -sh 749 678 678 ./tester1 The field pgid stands for process group ID.

Extra INFO:

Open three terminals, call the following sequence of commands: 1. date;uname -v;more tester1.c;./tester1 2. date;uname -v;more tester2.c;./tester2 3. top

In original MINIX, the command top shows that each of the CPU-bound process gets approximately one third of the CPU time up 0+81:14:50 19:59:13 load averages: 3.80, 3.00, 2.34; 52 processes: 4 runnable, 48 sleeping CPU states: 100% user, 0.0% nice, 0.0% system, 0.0% kernel, 0.0% idle Memory: 1823M Total, 954M Free, 953M Contig, 46M Cached PID USERNAME PRI NICE SIZE RES STATE 749 root 751 root 750 root 15 0 1224K 728K RUN 14 1224K 728K RUN 14 0 1224K 728K RUN TIME WCPU CPU COMMAND 3: 23 33. 79% 33. 79% tester! 3 : 00 32 . 28% 32 . 28% tester2 2: 56 30 , 52% 38. 52% tester2 The process associated with testerl is one group. When started in a different ter- minal, the two processes associated with tester2 is another group. In MINIX together with your implementation of fair-share scheduling, the command top should show that each of the group gets approximately one half of the CPU time, while each of the two processes in the second group should get approximately of fourth of the CPU time minix# ps -o pid,ppid,pgid , command PID PPID PGID COMMAND 687 631 631 ./tester2 688 687 631 ./tester2 686 682 682 ./tester1 In original MINIX, the command top shows that each of the CPU-bound process gets approximately one third of the CPU time up 0+81:14:50 19:59:13 load averages: 3.80, 3.00, 2.34; 52 processes: 4 runnable, 48 sleeping CPU states: 100% user, 0.0% nice, 0.0% system, 0.0% kernel, 0.0% idle Memory: 1823M Total, 954M Free, 953M Contig, 46M Cached PID USERNAME PRI NICE SIZE RES STATE 749 root 751 root 750 root 15 0 1224K 728K RUN 14 1224K 728K RUN 14 0 1224K 728K RUN TIME WCPU CPU COMMAND 3: 23 33. 79% 33. 79% tester! 3 : 00 32 . 28% 32 . 28% tester2 2: 56 30 , 52% 38. 52% tester2 The process associated with testerl is one group. When started in a different ter- minal, the two processes associated with tester2 is another group. In MINIX together with your implementation of fair-share scheduling, the command top should show that each of the group gets approximately one half of the CPU time, while each of the two processes in the second group should get approximately of fourth of the CPU time minix# ps -o pid,ppid,pgid , command PID PPID PGID COMMAND 687 631 631 ./tester2 688 687 631 ./tester2 686 682 682 ./tester1