Lottery scheduler

We will implement lottery scheduler in xv6
The basic idea is simple: Assign each running process a slice of the processor proportional to the number of tickets it has "The more tickets a process has, the more it runs ", The algorithm draws a random ticket to select the next process.

Specifically, in this project we are required to do the following:

We have to change the scheduler algorithm to work as lottery scheduler instead of round-roubin.
We have to define a new system call to set number of tickets settickets().
We have to define a new system call to get all processes information getpinfo().
We have to Make sure a child process inherits the same number of tickets as its parents.

1. Modify the scheduler algorithm

1. Adding number of tickets , ticks

In proc.h:

We have to add int tickets; , int ticks; in proc struct.

In proc.c:

In function allocproc() add the follwing after found label:

 found : 
   // code 
   p->tickets=1;
   p->ticks=0;

2. Pre-processing functions

Add a new function tickets_sum(void):

This function calculates the total number of tickets for all runnable processes.

 int
 tickets_sum(void){
 	struct proc *p;
 	int ticketsTotal=0;

 	//loop over process table and increment total tickets if a runnable process is found 
 	for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
 	{
 		if(p->state==RUNNABLE){
 			ticketsTotal+=p->tickets;
 		}
 	}
 	return ticketsTotal;  // returning total number of tickets for runnable processes
 }

Add random_at_most(int max) function:

We have to
- Add #include "rand.h" in proc.c
- Add the following in Makefile:
```
 OBJS = \
 	rand.o\
```

3. Modify the scheduler function `scheduler()`

Prepare all needed variables

long counter = 0 , winner = 0;

And in the for loop add the following:

winner = random_at_most( tickets_sum() );

winner equals to a random variable generated by this function random_at_most() from 0 to total tickets.

We will count the total number of tickets for each runnable process, when the counter becomes greater than the rondom number the winner process will run.

for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->state != RUNNABLE)
        continue;
	     //change start
      counter += p->tickets; 

      if (counter < winner) { 
            continue;
      }
      p->ticks += 1; //increment number of times process work
      
       break;
      //change end
 }
 //rest of the code

2. Implementing `setticket()`

We will add a wrapper function in sysproc.c to make sure the user has provided the right number and type of arguments before forwarding the arguments to the actual system call.

int
sys_settickets(void) {
  int n;
  if(argint(0, &n) < 0)
      return -1;
 
  return settickets(n);
}

Now we will implement the settickets() system call in proc.c

int 
settickets(int tickets)
{

  if(tickets < 1)
    return -1;
    
  struct proc *proc = myproc();
  
  acquire(&ptable.lock);
  ptable.proc[proc-ptable.proc].tickets = tickets;
  release(&ptable.lock);
  
  return 0;
}

Now that we have the implementation of the set tickets system call, we need to glue it in to the rest of the operating system. To do this we will need to make changes to the following five files:

syscall.h: Add a new system call number to the end of the #define list.

#define SYS_settickets 22
syscall.c: Add an extern definition for the new system call and add an entry to the table of system calls.
```
extern int sys_settickets(void);

[SYS_settickets] sys_settickets,
```
usys.S: Add an entry for clone.

SYSCALL(settickets)
user.h: Add a function prototype for the system call.

int settickets(int);
defs.h: Add a function prototype for the system call.

int settickets(int);

3. Implementing `getpinfo()`

We will add a wrapper function in sysproc.c to make sure the user has provided the right number and type of arguments before forwarding the arguments to the actual system call.

int
sys_getpinfo(void)
{
    struct pstat *d;
  if (argptr(0, (char **)&d, sizeof(struct pstat)) < 0)
      return -1;
  
  return getpinfo(d);
}

Also we need to add #include pstate.h in sysproc.c to be able to use the pstate structure

Now we will implement the getpinfo() system call in proc.c

int
getpinfo(struct pstat* ps) {
  int i = 0;
  struct proc *p;
  acquire(&ptable.lock);
  for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
    ps->pid[i] = p->pid;
    ps->inuse[i] = (p->state != UNUSED);
    ps->tickets[i] = p->tickets;
    ps->ticks[i] = p->ticks;
    i++;
  }
  release(&ptable.lock);
  return 0;
}

Aslo we need to add #include pstate.h in proc.c to be able to use the pstate structure

Now that we have the implementation of the clone system call, we need to glue it in to the rest of the operating system.

4- Child process inherits tickets from its parent

In proc.c specifically in fork() function:

We need to make sure any child inherits the same tickets as its parent, to do that we added:

np->tickets = curproc->tickets;

Testing

lottery_test :We can set diffrent ticketss for many processes and trace the change of its ticks.

To run lottery_test.c just type $ lottery_test with any number of tickets as you want.

forktickets.c: here we make sure that child's tickets equal to parent's tickets.

Graph

We have made a program graher.c to print the ticks of three processes for 50 iterations.
After copying these values into excel we can generate a graph representing the relation between the three processes

You can notice here that the ratio is 1:2:3 because Process A has 10 tickets, Process B has 20 tickets and Process C has 30 tickets.

Null-pointer Dereference

In XV6 if you dereference a null pointer such like that:

  int *p = NULL;   
 printf(1, "null pointer address : %x null pointer value : %x\n", p, *p);

You will not see an exception (as you might expect); rather, you will see whatever code is the first bit of code in the program that is running.

When the user try to dereference a null pointer, the xv6 OS go to virtual address zero (first page at the page table of the process) and access the memory using it.

To fix this problem:

When null dereference occurs XV6 shouldn't find virtual address zero (first page at page table of the process), we can achieve thisi by doing the following:

1. Making process itself to be loaded starting from address 4096 (`page number 2`).

In `exec.c`

modify line: sz = 0 to sz = PGSIZE. // PGSIZE = 4096

2. Making modification to not transfer the first page from the parent to the child when `fork()` is used .

In `vm.c` inside `pde_t* copyuvm(pde_t *pgdir, uint sz)` function:

Modify line: for(i = 0; i < sz; i += PGSIZE) to for(i = PGSIZE; i < sz; i += PGSIZE) .

3. Making XV6 load the program into the memory not from the address 0 but from the next page which is in fact address (4096) that is 0x1000.

In `Makefile`

Replace line:

$(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $@ $^

With:

$(LD) $(LDFLAGS) -N -e main -Ttext 0x1000  -o $@ $^

4. Understanding `traps.h` to know the needed types of traps, focusing on `T_PGFLT --> page fault`.

5. Adding some code at `trap.c` inside `void tvinit(void)` function that is required to initialize the IDT (Interrupt Descriptor Table).

case T_PGFLT :
    cprintf("pid %d %s: trap %d err %d on cpu %d "
    "eip 0x%x addr 0x%x--kill proc\n",
     myproc()->pid, myproc()->name, tf->trapno,
     tf->err, cpuid(), tf->eip, rcr2());
     cprintf("This trap cause null pointer execption\n");
      myproc()->killed = 1;
      break;

Testing

Add nullpointer.c In Makefile.

Our test file nullpointer.c include two function to test :

Null pointer dereference.

Copying parent memory to child memory from second page.

Read-only Code

In XV6, code is marked as read-write but In most operating systems, code is marked read-only instead of read-write, so no program can overwrite its code.

To convert XV6 to be read-only or return it to be read-write again we have to change the protection bits of some parts of the page table to be read-only, thus preventing such over-writes, and also be able to change them back.

In page table entry (PTE) the writable bit is responsible for changing code to be read-only or read-write.

To reset writable bit (read-only) we wrote a system call: `int mprotect(void *addr, int len)`

which changes the protection bits of the page range starting at addr and of len pages to be read only. Thus, the program could still read the pages in this range after mprotect() finishes, but a write to this region should cause a trap (and thus kill the process).

To set writable bit (read-write) we wrote a system call: `int munprotect(void *addr, int len)`

Which does the opposite operation of `int mprotect(void *addr, int len)`, it sets the region back to both readable and writeable.

All the steps required to implement `mprotect` system call are identical to `munprotect` system call except for few differeneces, our main focus will be at `proc.c`:

In `proc.c`

Added int mprotect(void *addr, int len) as shown below :

int
mprotect(void *addr, int len){      ///mprotect(start, 1) ; 
  struct proc *curproc = myproc();
  
  //Check if addr points to a region that is not currently a part of the address space
  if(len <= 0 || (int)addr+len*PGSIZE > curproc->sz){ 
    cprintf("\nwrong len\n");
    return -1;
  }

  //Check if addr is not page aligned
  if((int)(((int) addr) % PGSIZE )  != 0){
    cprintf("\nwrong addr %p\n", addr);
    return -1;
  }
 
  //loop for each page
  pte_t *pte;
  int i;
  for (i = (int) addr; i < ((int) addr + (len) *PGSIZE); i+= PGSIZE){ //  from start to end=(start+lenght)
    // Getting the address of the PTE in the current process's page table (pgdir)
    // that corresponds to virtual address (i)
    pte = walkpgdir(curproc->pgdir,(void*) i, 0);
    if(pte && ((*pte & PTE_U) != 0) && ((*pte & PTE_P) != 0) ){// check it's present and user 
      *pte = (*pte) & (~PTE_W) ; //Clearing the write bit 
      cprintf("\nPTE : 0x%p\n", pte);
    } else {
      return -1;
    }
  }
  //Reloading the Control register 3 with the address of page directory 
  lcr3(V2P(curproc->pgdir));
   /* after changing a page-table entry, you need to make sure the hardware knows of the change.
    On 32-bit x86, this is readily accomplished by updating the CR3 register (what we generically call the page-table 
    base register in class). When the hardware sees that you overwrote CR3 (even with the same value), 
    it guarantees that your PTE updates will be used upon subsequent accesses.
   */
return 0;
}

`munprotect` Same like `mprotect` but:

replace line

             				xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx    ---> pte
    //Clearing the write bit				                         &
    *pte = (*pte) & (~PTE_W) ;		1111 1111 1111 1111 1111 1111 1111 1101    ---> (~ PTE_W)
					---------------------------------------
					xxxx xxxx xxxx xxxx xxxx xxxx xxxx xx0x    ---> pte

with

             				xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx    ---> pte
    //set the write bit				                                  |
    *pte = (*pte) | (PTE_W) ;		0000 0000 0000 0000 0000 0000 0000 0010    ---> (PTE_W)
					---------------------------------------
					xxxx xxxx xxxx xxxx xxxx xxxx xxxx xx1x    ---> pte

Important information :

In `mmu.h`

Clarify how to get Page Directory ,Page Table Index and Offset within Page from Virtual address

// A virtual address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |      Index     |                     |
// +----------------+----------------+---------------------+
//  \--- PDX(va) --/ \--- PTX(va) --/

// page directory index
#define PDX(va)         (((uint)(va) >> PDXSHIFT) & 0x3FF)

// page table index
#define PTX(va)         (((uint)(va) >> PTXSHIFT) & 0x3FF)


// Address in page table or page directory entry
#define PTE_ADDR(pte)   ((uint)(pte) & ~0xFFF)
#define PTE_FLAGS(pte)  ((uint)(pte) &  0xFFF)

// Page table/directory entry flags.
#define PTE_P           0x001   // Present
#define PTE_W           0x002   // Writeable
#define PTE_U           0x004   // User
#define PTE_PS          0x080   // Page Size( 0 =4KB ^^^^ 1 = 4MB )

Testing

Add read_only.c In Makefile.

Add protect.c In Makefile.

protect.c test if the size belong to the address space and if the page aligned or not

Kernel Threads

In this project, we'll be adding real kernel threads to xv6.

Specifically, in this project we are required to do the following:

We have to define a new system call to create a kernel thread, called clone().
We have to define a new system call to wait for a thread called join().
We have to implement a simple ticket lock and three routines initlock_t(), acquire_t() and release_t() which initialize, acquire and release the ticketlock.
Then, we'll use clone(), join(), initlock_t(), acquire_t() and release_t() to build a little thread library, with a thread_create() thread_join() calls and lock_init(), lock_acquire() and lock_release() functions.

The clone() and join() system calls are necessary for introducing the notion of a thread in the xv6 kernel. The ticket lock mechanism is used to synchronize across multiple threads.

1. Implementing `clone()`

We will add a wrapper function in sysproc.c to make sure the user has provided the right number and type of arguments before forwarding the arguments to the actual system call.

int
sys_clone(void) 
{
  void *fcn, *arg1, *arg2, *stack;
  
  //check if arguments is valid before calling clone syscall
  if (argptr(0, (void *)&fcn, sizeof(void *)) < 0)	return -1;
  if (argptr(1, (void *)&arg1, sizeof(void *)) < 0)	return -1;
  if (argptr(2, (void *)&arg2, sizeof(void *)) < 0)	return -1;
  if (argptr(3, (void *)&stack, sizeof(void *)) < 0)	return -1;

  return clone(fcn, arg1, arg2, stack);
}

Now we will implement the clone() system call in proc.c by copying the body of the fork() system call into the body of our new clone() function and modify it.

The full signature of the function is: int clone(void(*fcn)(void *, void *), void *arg1, void *arg2, void *stack).

The clone() system call creates a new thread-like process. It is very similar to fork() in that it creates a child process from the current process, but there are a few key differences:
- The child process should share the address space of the original process (fork() creates a whole new copy of the address space).
- clone() takes a pointer to a function (void(*fcn)(void *, void *)) and two arguments (void *arg1, void *arg2), and runs the function as soon as the child process starts (fork() starts the child at the same place in code as the parent).
- The child process's stack (void *stack) should be in the address space of the original process (fork() creates a separate stack for the child process).
Now that we have the implementation of the clone system call, we need to glue it in to the rest of the operating system.

2. Implementing `join()`

We will add a wrapper function in sysproc.c to make sure the user has provided the right number and type of arguments before forwarding the arguments to the actual system call.
```
int
sys_join(void)
{
  int stackArg;
  void **stack;
  
  stackArg = argint(0, &stackArg);
  stack = (void**) stackArg;

  return join(stack);
}
```
Now we will implement the join() system call in proc.c by copying the body of the wait() system call into the body of our new join() function and modify it.

The full signature of the function is: int join(void** stack).

The join() system call waits for a child thread that shares the address space with the calling process to exit. It returns the PID of waited-for child or -1 if none. The location of the child's user stack is copied into the argument stack (which can then be freed). It is very similar to wait() (which does the same thing, but for processes), but there are a fey key differences:
- The thread to be joined shares the address space of its parent (a child thread will have the same pgdir attribute as its parent), so join() shouldn't touch the thread virtual memory because freeing it would break the parent process (wait() frees the virtual memory of the child process).
- join() have to check if a process is a child thread of the current process by checking if its parent equal to the current process and have the same pgdir (wait() just needs to find a process whose parent is equal to the current process).
Now that we have the implementation of the join() system call, we need to glue it in to the rest of the operating system.

3. Implementing ticket lock

With clone and join we have the ability to create and join threads, but we lack a way to protect data from being accessed by multiple threads simultaneously. To provide support for synchronization we will add a spinning ticketlock to xv6.

A ticketlock is one way to implement a mutex, but adds a little bit of complexity in order to improve fairness. Normal mutexes can have starvation issues, where one thread manages to acquire the lock before other threads almost all the time, preventing other threads from getting access. A ticketlock has a turn and a ticket. When a thread wants to acquire the lock, it receives a ticket number. It then waits for the lock's turn to equal its ticket. Meanwhile, the lock increments the turn each time a thread releases the lock. This creates a simple FIFO queue system.

To implement the ticket lock, we have to do the following:

Define the ticketlock structure, which user programs can use to declare and use ticketlocks.

 struct ticketlock
 {
     int next_ticket; // next ticket number to be given
     int current_turn; // current ticket number being served
     struct proc *proc; // process currently holding the lock
 };

Then we will implement three system calls initlock_t(), acquire_t() and release_t() which initialize, acquire and release the ticketlock.

We will add a wrapper function for each system call in sysproc.c.

int sys_initlock_t(void)
{
  struct ticketlock *tl;
  if (argptr(0, (char**)&tl, sizeof(struct ticketlock*)) < 0) return -1;

  initlock_t(tl);
  return 0;
}

int sys_acquire_t(void)
{
  struct ticketlock *tl;
  if (argptr(0, (char**)&tl, sizeof(struct ticketlock*)) < 0) return -1;

  acquire_t(tl);
  return 0;
}

int sys_release_t(void)
{
  struct ticketlock *tl;
  if (argptr(0, (char**)&tl, sizeof(struct ticketlock*)) < 0) return -1;
   
  release_t(tl);
  return 0;
}

We will implement each system call in proc.c.

void initlock_t(struct ticketlock *lk)
{
    lk->next_ticket = 0;
    lk->current_turn = 0;
}

void acquire_t(struct ticketlock *lk)
{
    cli(); //clear inturrupt flag (IF) Disable inturrupts
    int myTicket = fetch_and_add(&lk->next_ticket, 1);

    while (lk->current_turn != myTicket)
    ticket_sleep(lk); // to prevent busy waiting.
}

void release_t(struct ticketlock *lk)
{
    fetch_and_add(&lk->current_turn, 1);
    wakeup(lk); // wakup on release and reacquire lock.
    sti(); //set inturrupt flag (IF) Enable inturrupts
}

// ticket_sleep is a helper function used in acquire_t() to prevent busy waiting.
void ticket_sleep(void *chan)
{
   struct proc *p = myproc();

   if (p == 0)
       panic("sleep");

   acquire(&ptable.lock);

   p->chan = chan;
   p->state = SLEEPING;
   sched();
   p->chan = 0;

   release(&ptable.lock);
 }

And Voila! now we have a fully working ticket lock that we can use to protect data from being accessed by multiple threads simultaneously.

4. Adding Thread Library

Now we can say that we are ready to use clone(), join(), initlock_t(), acquire_t() and release_t() to build a little thread library, with a thread_create() thread_join() calls and lock_init(), lock_acquire() and lock_release() functions.

To make the thread library, we have to do the following:

Create 5 functions in ulib.c that call the five system calls we made previously.

int thread_create(void (*start_routine)(void*, void*), void *arg1, void *arg2)
{
    void *stack = sbrk(PGSIZE);
    return clone(start_routine, arg1, arg2, stack);
}

int thread_join()
{
    void *stack;
    int result = join(&stack);	
    return result;
}

void lock_init(struct ticketlock *lock)
{
    initlock_t(lock);
}

void lock_acquire(struct ticketlock *lock)
{
    acquire_t(lock);
}

void lock_release(struct ticketlock *lock)
{
    release_t(lock);
}

Add a function prototype in user.h for the five functions.

int thread_create(void(*fcn)(void*, void*), void *arg1, void *arg2);
int thread_join();
void lock_init(struct ticketlock *lock);
void lock_acquire(struct ticketlock *lock);
void lock_release(struct ticketlock *lock);

Now we can use this thread library to make multithreading programs in xv6.

Testing

Now we can make multithreading programs that contain two or more parts that can run concurrently.

To test Kernel Threads we have made a program that uses the thread library (threadtest.c), the program contains the following two tests:

Single thread test.
Multi threads test.

To run threadtest.c just type $ threadtest in qemu.

You can notice the fairness of ticketlock in the multi threads test (threads take turns in execution).

Team Members:

Omar Gamal : @O-Gamal

Mariam Gad : @Mariamgad

Mostafa Amin : @M0stafaAmin

Mostafa Ayman : @MostafaAE

Mostafa Saad : @MostafaSaad7

Files

README.md

Latest commit

History

README.md

File metadata and controls

Table of contents

Lottery scheduler

1. Modify the scheduler algorithm

1. Adding number of tickets , ticks

2. Pre-processing functions

3. Modify the scheduler function scheduler()

Prepare all needed variables

2. Implementing setticket()

3. Implementing getpinfo()

4- Child process inherits tickets from its parent

Testing

Graph

Null-pointer Dereference

To fix this problem:

When null dereference occurs XV6 shouldn't find virtual address zero (first page at page table of the process), we can achieve thisi by doing the following:

1. Making process itself to be loaded starting from address 4096 (page number 2).

In exec.c

2. Making modification to not transfer the first page from the parent to the child when fork() is used .

In vm.c inside pde_t* copyuvm(pde_t *pgdir, uint sz) function:

3. Making XV6 load the program into the memory not from the address 0 but from the next page which is in fact address (4096) that is 0x1000.

In Makefile

4. Understanding traps.h to know the needed types of traps, focusing on T_PGFLT --> page fault.

5. Adding some code at trap.c inside void tvinit(void) function that is required to initialize the IDT (Interrupt Descriptor Table).

Testing

Read-only Code

In page table entry (PTE) the writable bit is responsible for changing code to be read-only or read-write.

To reset writable bit (read-only) we wrote a system call: int mprotect(void *addr, int len)

To set writable bit (read-write) we wrote a system call: int munprotect(void *addr, int len)

Which does the opposite operation of int mprotect(void *addr, int len), it sets the region back to both readable and writeable.

All the steps required to implement mprotect system call are identical to munprotect system call except for few differeneces, our main focus will be at proc.c:

In proc.c

munprotect Same like mprotect but:

Important information :

In mmu.h

Testing

Kernel Threads

1. Implementing clone()

2. Implementing join()

3. Implementing ticket lock

To implement the ticket lock, we have to do the following:

And Voila! now we have a fully working ticket lock that we can use to protect data from being accessed by multiple threads simultaneously.

4. Adding Thread Library

To make the thread library, we have to do the following:

Now we can use this thread library to make multithreading programs in xv6.

Testing

Team Members:

3. Modify the scheduler function `scheduler()`

2. Implementing `setticket()`

3. Implementing `getpinfo()`

1. Making process itself to be loaded starting from address 4096 (`page number 2`).

In `exec.c`

2. Making modification to not transfer the first page from the parent to the child when `fork()` is used .

In `vm.c` inside `pde_t* copyuvm(pde_t *pgdir, uint sz)` function:

In `Makefile`

4. Understanding `traps.h` to know the needed types of traps, focusing on `T_PGFLT --> page fault`.

5. Adding some code at `trap.c` inside `void tvinit(void)` function that is required to initialize the IDT (Interrupt Descriptor Table).

To reset writable bit (read-only) we wrote a system call: `int mprotect(void *addr, int len)`

To set writable bit (read-write) we wrote a system call: `int munprotect(void *addr, int len)`

Which does the opposite operation of `int mprotect(void *addr, int len)`, it sets the region back to both readable and writeable.

All the steps required to implement `mprotect` system call are identical to `munprotect` system call except for few differeneces, our main focus will be at `proc.c`:

In `proc.c`

`munprotect` Same like `mprotect` but:

In `mmu.h`

1. Implementing `clone()`

2. Implementing `join()`