Pintos : Series : Part 4 : Final

In this blog post, we will be done with our Pintos Project #1 and this Pintos Series AlhumdullillAllah.

so let's start...

In the previous posts of this series, we have looked at the problem that is of busy waiting. To solve this problem I took help from code written by other people on Github,  so to learn it deeper you can get to look at this code, by Muhammad Zaheer . 

The basic modification is done in two files i.e. timer.c and thread.h; 

     ALARM CLOCK IMPLEMENTAIONS

     ==========================

Changes in timer.c:

  - A global list of sleeping threads is created as:

-static struct list sleep_list;

Changes in thread.h:

  - For keeping track of a sleeping thread when woken up, we declared:

-int64_t sleep_time;

  - When a thread calls timer_sleep(), it gets into the sleep list as:

-struct list_elem sleep_list_elem

---

Algorithms Used

We reimplemented timer_sleep() in devices/timer.c, as it spins in a loop to check the current time and to call thread_yield() which wastes a lot of time, so we needed to avoid busy waiting. Hence we replaced thread_yield() with thread_block() with other functionalities as mentioned below:

In timer_sleep() :

  - First Check ticks <=0, if yes then return

  - Then enable the interrupts

  - Get to the current thread by using thread_current() function

  - Then set its (current thread's) sleep_time equal to the number of 

    ticks it wants to sleep.

  - Then insert the current thread in the global sleep list (i.e. static struct list sleep_list) in (ascending) order

    

In timer_interrupt() :

---

|                 CODE

|                 ====

|

| /* Timer interrupt handler. */

| static void

| timer_interrupt (struct intr_frame *args UNUSED)

| {

|   ticks++;

|   /* Wake up sleeping threads that are eligible

|     i.e. sleep_time <= ticks */

|   wake_sleep();

|   thread_tick(); 

| }

|

| /* Loops over the sleep list and wakes up eligible threads 

|   Terminates if a thread has greater sleep_time than current val of ticks

|   because sleep_list is ordered */

|

| static void

| wake_sleep() 

| {

|     struct list_elem * e;

|

|     for (e = list_begin(&sleep_list); e!=list_end(&sleep_list); e=list_next(e))

|     {

|       struct thread * thread = list_entry(e,struct thread, sleep_list_elem);   

|       if (thread->sleep_time <= timer_ticks())

|       {

| thread->sleep_time = 0;

| thread_unblock(thread);

| list_remove(e);

|

|       }

|       else break;

|     

|     }

|

| }                                           

|

Here it:

•   Increment ticks
•   Then call to wake_sleep() having functionality:
• To Traverse the sleep_list
• For each element, checks if its sleep_time 

               is <= (timer_ticks())

           - If yes, then set its sleep_time = 0, unblock it and

                truncate it from the sleep_list 

           - else break

•     - Then a call to thread_ticks(), to makes sure that current thread yield the CPU if greater priority thread is woken up. [ for Alarm-priority but do not consider this step for this project ]

---

Summary

So , to solve the problem:

•  Initialize ticks in timer.c as: static int64_t ticks;
•  In devices/timer.c edit timer_sleep() function
•  Define wake_threads() function.
•  Edit timer_interrupt().
•  In devices/timer.c define and initialize sleep_list
•  Insert the thread to be slept in sleep_list

This is all about the PintOS Project #1. I hope you have understood the concepts.

Keep Learning :)