Advanced Systems Programming Assignment

Contributors:

• Alex Rogers - 22018703
• Jevhan Seechurn - 21038410

Table of Contents

1. Introduction
2. Task 1 - Part 1
3. Task 1 - Part 2
4. Task 2 - Part 1
5. Task 2 - Part 2
6. Task 2 - Part 3
7. Task 3
8. Task Extra

1. Introduction

1.1 About the Assignment

In this assignment, we are given the task of the implementing a simple runtime that will support cooperative tasks running within a single thread in c++.

1.2 What is a Fiber ?

Provide an explanation on fibers

1.2 What is a Thread ?

Provide an explanation on threads

2. Task 1 - Fiber Class design and implementation (Part 1)

2.1 Explanation

The first part of task 1 explores the basics and implementation of context switching, which focuses on saving and restoring the program's execution state. We implement a simple mechanicsm in order to pause and continue execution by using a context library.

2.2 Implementation

2.2.1 Context Library Interface

This is the Context Library that was provided by the lectuere and will be the used throughout the following tasks. This will provide the necessary functions for context switching and can handld saving and restoring execution states.

#pragma once

struct Context {
  void *rip, *rsp;
  void *rbx, *rbp, *r12, *r13, *r14, *r15;
};

extern "C" int get_context(Context *c);
extern "C" void set_context(Context *c);
extern "C" void swap_context(Context *out, Context *in);

2.2.2 Variable declaration

This code snippet shows x declared as a volatile. This is to prevent the compiler from optimising it as ideally, we want the program to function as intended with the consideration to x in the context switching scenario.

volatile int x = 0;

2.2.3 Retrieve Context

This code snippet saves the current state of the execution as well as the instructions pointer, stack pointer and registers into c.

   Context c;
   get_context(&c);

2.2.4 Ouput

This code snippet prints a message to the screen before the context switching happens.

   std::cout << "a message" << std::endl;

2.2.5 Conditional Check and Context Switch

This code snippet shows the conditional and cetext switch where, if x is 0, it gets incremented, and then the execution state is restored with the use of set_context(&c). In addition, set_context will jump back to where get_context was called, but instead will execute after the if statement and x will now be 1.

   if (x == 0) {
       x = x + 1;
       set_context(&c);
   }

2.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Make to move to the task 1 directory using the command cd Task\ 1

• Run the following command within the terminal in order to compile the classes:

  g++ -o task1.1 task1.1.cpp ../context/context.s -std=c++0

• Once compiled, we run the next command: ./task1.1

2.3.1 Screenshot 1 (Task 1 Part 1 Output)

As shown in the screenshot, the program works as intended.

3. Task 1 - Fiber Class design and implementation (Part 2)

3.1 Explanation

Part 2 of Task 1 expands the concept of context switching by implemented two fibers, foo and goo, each containing their own stack and context. Memory is allocated for the stacks then the stack pointers are set with proper alingment and the context for fibers are initialized.

3.2 Implementation

3.2.1 Implementing the Fibers

This snippet shows the functions for both Fibers foo and goo. When the foo function is exectued, it will print a message to the console "You called foo". After that, it will call the set_context() in order to switch to the goo fiber. When goo function is executed, it will print "you caled goo". After that, it will call exit(1) in order to exit the program, which will stop the program and simulte the termination of the fiber.

   void foo() {
       std::cout << "You called foo" << std::endl;
       set_context(&goo_context);
   }


   void goo() {
       std::cout << "You called goo" << std::endl;
       exit(1);
   }

3.2.2 Allocating Stack memory

In this code snippet the memory is aollcated for the stack of both fibers foo and `goo. As shown, both fiber will recieve a stack size of 4096 bytes each.

   int main() {
       char foo_stack[4096];
       char goo_stack[4096];
   }

3.2.3 Setting Stack Pointers

In this snippet, the stack pointers are set up for both fibers. The base address of each stack is casted to a uniptr_t and is adjusted to point to the top of the stack. This will make sure that each fiber will execute with their own task.

   uintptr_t sp_foo;
   uintptr_t sp_goo;


   sp_foo = reinterpret_cast<uintptr_t>(foo_stack) + sizeof(foo_stack);
   sp_goo = reinterpret_cast<uintptr_t>(goo_stack) + sizeof(goo_stack);

3.2.4 Initializing the Fiber Context

In this code snippet, the execution context for both fibers are initialized (foo_context and goo_context). Next, the instruction pointer is set to the functions address and stack pointer to the respective stack pointer for each fiber. This will ensure that each fiber will starts at its own repsective function and use its own stack for execution.

   foo_context.rip = reinterpret_cast<void*>(foo);
   foo_context.rsp = reinterpret_cast<void*>(sp_foo); 


   goo_context.rip = reinterpret_cast<void*>(goo);
   goo_context.rsp = reinterpret_cast<void*>(sp_goo); 

3.2.5 Outputting a message before context Switching

In this code snippet, the main functions will print a messsage in order to indicate that it will now switch control to foo and goo fibers before starting the execution.

   std::cout << "Main function, calling foo and goo" << std::endl;

3.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Make to move to the task 1 directory using the command cd Task\ 1

• Run the following command within the terminal in order to compile the classes:

  g++ -o task1.2 task1.2.cpp ../context/context.s -std=c++0

• Once compiled, we run the next command: ./task1.2

2.3.1 Screenshot 2 (Task 1 Part 2 Output)

As shown in the screenshot, the program works as intended.

3. Task 2 - Implementing a Scheduler for Fiber Execution (Part 1)

3.1 Explanation

Part 1 of task 2 will be focusing on the implemetation of the fiber scheduler for fiber executionby designing a fiber data structure in order to hold fiber state and context. The aim will be to create and run the fibers by testing if they can yield and resume as needed, which will allow them to run until the objective is completed.

3.2 Implementation

3.2.1 Defining the Fiber class

The Fiber class simply contains the fibers state, as well as its context (Stack Pointer and Instruction pointer ) and memory (stack). In addtion the Constructor will allocate the stack mempory and set up the fibers context, include the function that will be executed. The destrcutor will free the stack memory once the fiber is no longer needed. Finally, the getContext() will return a poter to the context_ in order to set or retrieve the fibers state.

class Fiber {
private:
    Context context_{}; 
    char *stack_bottom; 
    char *stack_top; 

public:
    Fiber(void (*function)()) {
        stack_bottom = new char[4096];
        stack_top = stack_bottom + 4096;

        uintptr_t sp = reinterpret_cast<uintptr_t>(stack_top);
        sp = (sp & -16L) - 128; 

        context_.rsp = reinterpret_cast<void *>(sp);
        context_.rip = reinterpret_cast<void *>(function);
    }

    ~Fiber() {
        delete[] stack_bottom;
    }

    Context *getContext() { return &context_; }
};

3.2.2 Fiber Function

In this snippet, this function is what will be executed by the fiber. Will simply print a message and calls the exit(1) in order to remove the program, thus simulating the end of the fiber.

void foo() {
   std::cout << "You called foo" << std::endl;
   exit(1);
}

3.2.3 Main Function and Fiber Execution

In this code snippet, the main function will create a fiber that will execute the foo() function, where it calls the set_context() function in order to switch control to the fiber. This means that the execution will jump to the foo() function and run it within the fibers context.

int main() {
    std::cout << "Main function, calling foo and goo" << std::endl;

    Fiber foo_fiber(foo);
    set_context(foo_fiber.getContext());

    return 0;
}

3.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Make to move to the task 2 directory using the command cd Task\ 2

• Run the following command within the terminal in order to compile the classes:

  g++ -o task2.1 task2.1.cpp ../context/context.s -std=c++11

• Once compiled, we run the next command: ./task2.1

3.3.1 Screenshot 1 (Task 2 Part 1 Output)

As shown in the screenshot, the fiber scheduler works successfully, transferring control to the fiber function foo

4. Task 2 - Implementing a Scheduler for Fiber Execution (Part 2)

4.1 Explanation

Task 2 part 2 will be expanding from the previous task by implementing a fiber scheduler, which will be used to handle the execution of fibers. This will be used to perform actions such as context switching, restoring and saving the state of fibers, and handling the creating and termination of fibers. The objective is to run multiple finers simultaneouly

4.2 Implementation

4.2.1 Defining the Scheduler Class

This code snippet manages a queue of fibers and controls their execution. This is done by by the spawn function adding fibers to the queue as the do_it function executes the fibers by switching to each fibers context. The fiber_exit functions allows a fiber yield control back to the scheduler, allowing for other fibers to run.

class Scheduler {
private:
    std::deque<Fiber *> fibers_; 
    Context context_; 

public:
    Scheduler() {}

    ~Scheduler() {}

    void spawn(Fiber *fiber) {
        fibers_.push_back(fiber); 
    }

    void do_it() {
        get_context(&context_);
        while (!fibers_.empty()) {
            Fiber *current_ = fibers_.front();
            fibers_.pop_front();

            set_context(current_->getContext());
        }
    }

    void fiber_exit() {
        set_context(&context_);
    }
};

4.2.2 Fiber Functions

This code snippet shows multiple functions that are executed as fibers, with each fiber function printing as message and then yielding control back to the scheduler. In addition, the parent_function will show a fiber creating and spawning a child fiber, showing the handling of nested fibers being created and scheduled.

void func1() {
    std::cout << "fiber 1\n";
    scheduler.fiber_exit();
}

void func2() {
    std::cout << "fiber 2\n";
    scheduler.fiber_exit();
}

void func3() {
    std::cout << "fiber 3\n";
    scheduler.fiber_exit();
}

void func4() {
    std::cout << "fiber 4\n";
    scheduler.fiber_exit();
}

void child_function() {
    std::cout << "Child fiber\n";
    scheduler.fiber_exit();
}

void parent_function() {
    std::cout << "Parent fiber\n";
    // Create a child fiber inside the child function
    Fiber *child_fiber = new Fiber(child_function);

    // Spawn the parent fiber
    scheduler.spawn(child_fiber);

    scheduler.fiber_exit();
}

4.2.3 Testing Funtions for the Scheduler

These are testing functions to run differnt scenarios:

• testSchedulerBasic executes two fibers
• testSchedulerMultipleFibers executes multiple fibers
• testParentWithChildFiber will test fiber creation within a parent fiber
• testSchedulerEmptyQueue if there are no fibers that are scheduled, the program will just do nothing

void testSchedulerBasic() {
    std::cout << "Running Basic Test: Scheduler with 2 fibers\n";
    
    Fiber f1(func1);
    Fiber f2(func2);

    scheduler.spawn(&f1);
    scheduler.spawn(&f2);

    scheduler.do_it(); // Run all fibers
}

void testSchedulerMultipleFibers() {
    std::cout << "Running Multiple Fibers Test\n";
    
    Fiber f1(func1);
    Fiber f2(func2);
    Fiber f3(func3);
    Fiber f4(func4);

    scheduler.spawn(&f1);
    scheduler.spawn(&f2);
    scheduler.spawn(&f3);
    scheduler.spawn(&f4);

    scheduler.do_it(); // Run all fibers
}

void testParentWithChildFiber() {
    std::cout << "Running Parent-Child Fiber Test\n";
    
    Fiber f1(parent_function);

    scheduler.spawn(&f1);

    scheduler.do_it(); // Run all fibers, including the child fiber created inside the parent
}

void testSchedulerEmptyQueue() {
    std::cout << "Running Empty Queue Test\n";

    // Nothing to execute, so the program should not output anything
    scheduler.do_it();
}

4.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Make to move to the task 2 directory using the command cd Task\ 2

• Run the following command within the terminal in order to compile the classes:

  g++ -o task2.2 task2.2.cpp ../context/context.s -std=c++0

• Once compiled, we run the next command: ./task2.2

3.3.1 Screenshot 2 (Task 2 Part 2 Output)

As shown in the screenshot, the fiber scheduler ran successfully

5. Task 2 - Implementing a Scheduler for Fiber Execution (Part 3)

5.1 Explanation

This task further expands the Fiber Class system by adding data management. By building up from part2 , the Fiber scheduler now contain fibers that can carry and modify its own data during the execution. This will allow fibers to maintain state and process actual data. The objective of this part is to show how fibers can share and modify data between execution whilst maintaining memory management.

5.2 Implementation

5.2.1 Fiber Class Updated

The code snippet shows the updated version of the Fiber class to fit within the requirements of Task 2, part 3. The new class now uses a dedicated Fiber class that will handle the context, stack and data. In addition, the Fiber Class now uses dynamic memory allocation for the fibers stack. Finally, we have the getContext() and getData() functions to gain access to the fibers state.

class Fiber {
private:
    Context context_{}; 
    void *data_; 
    char *stack_bottom; 
    char *stack_top; 

public:
    Fiber(void (*function)(), void *data = nullptr){
        data_ = data;
        stack_bottom = new char[4096];
        stack_top = stack_bottom + 4096;

        uintptr_t sp = reinterpret_cast<uintptr_t>(stack_top);
        sp = (sp & -16L) - 128; 

        context_.rsp = reinterpret_cast<void *>(sp);
        context_.rip = reinterpret_cast<void *>(function);
    }

    ~Fiber() {
        delete[] stack_bottom;
    }

    Context *getContext() { return &context_; }

    void *getData() const { return data_; }
};

5.2.2 Retreiving Fiber Data

This code snippet shows a functions that can allow fibers to retrieve their data whilst running.

void *getCurrentFiberData() {
    if (current_fiber_) {
        return current_fiber_->getData();
    }
    return nullptr;
}

5.2.3 Fiber Functions

This code snippet shows the new fiber functions added which can retreive data as well as modifying and printing the values.

void func1() {
    void *dp = scheduler.getCurrentFiberData();
    if (dp) {
        std::cout << "fiber 1: " << *reinterpret_cast<int *>(dp) << std::endl;
        *reinterpret_cast<int *>(dp) += 1;  
    }
    scheduler.fiber_exit();
}

void func2() {
    void *dp = scheduler.getCurrentFiberData();
    if (dp) {
        std::cout << "fiber 2: " << *reinterpret_cast<int *>(dp) << std::endl;
    }
    scheduler.fiber_exit();
}

5.2.4 Main Funtion Updated

int main() {
    int d = 10;
    void *dp = &d; 

    Fiber f1(func1, dp);  
    Fiber f2(func2, dp);  

    scheduler.spawn(&f1);
    scheduler.spawn(&f2);

    scheduler.do_it();

    return 0;
}

5.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Make to move to the task 2 directory using the command cd Task\ 2

• Run the following command within the terminal in order to compile the classes:

  g++ -o task2.3 task2.3.cpp ../context/context.s -std=c++0

• Once compiled, we run the next command: ./task2.3

3.3.1 Screenshot 1 (Task 2 Part 3 Output)

As shown in the screen shot the system was able to work successfully.

6. Task 3 - Fiber Yielding and Cooperative Multitasking

6.1 Explanation

Task 3 will be focusing on implementing yield functionality in order to halt their execution temporarily and continue it later, rather than running until it is completed like in previous tasks. A yield function will be implemeted to save a fibers current state and return controls to the scheduler allowing for cooperative multitasking where Fibers can freely give up their execution time.

6.2 Implementation

6.2.1 Current Fiber Tracker

This code snippet shows the Sheduler class with the addition of a pointer that will be used to track which fiber is currently running. This will allow the schedule to know which fiber needs to be re-queded when the yield has been called.

class Scheduler {
private:
    std::deque<Fiber *> fibers_; 
    Context context_; 
    Fiber *current_fiber_;  
}

6.2.2 Yield Method Implementation

This code snippet shows the yield method which allows the Fibers tp pause their execution. When called, it will check if there is a Fiber currently running, it will add that current Fiber to the end of the queue, and switch execution context back to the scheduler.

void Scheduler::yield() {
    if (current_fiber_) {
        fibers_.push_back(current_fiber_);  
        swap_context(current_fiber_->getContext(), &context_);  
    }
}

6.2.3 Test Funtion

This code snippet shows the test function that will demonstrate both cooperative multi tasking and data sharing between Fibers. This will be done by assessing, displaying and checking shared data values before and after yielding control to other Fibers.

void func1() {
    void *dp = scheduler.getData();
    if (dp) {
        std::cout << "fiber 1: " << *reinterpret_cast<int *>(dp) << std::endl;
        scheduler.yield();  
        std::cout << "fiber 1 after yield: " << *reinterpret_cast<int *>(dp) << std::endl;
    }
    scheduler.fiber_exit();
}

6.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Make to move to the task 3 directory using the command cd Task\ 3

• Run the following command within the terminal in order to compile the classes:

  g++ Fibers/Fibers.cpp Scheduler/Scheduler.cpp Test.cpp Context/context.o -o test_program

• Once compiled, we run the next command: ./test_program

3.3.1 Screenshot 1 (Task 3 Output)

As shown in the screen shot the system was able to work successfully.

7. Extra Features Implementation

7.1 Explanation

In order to meet the requirements to break beyond 72 marks, additional features will need to be added that has not been covered in the spcification. Here are the extra features that have been added to further extend the fiber system:

(Ideas subject to change)

7.1.1 Fiber Priority System

7.1.2 Fiber State Tracking Monitor

7.2 Implementation

7.2.1

7.3 Testing & Results

In order to run the program there are few a pre-requisites.

• Move to the task 4 directory using the command cd Task\ 4

• Run the following command within the terminal in order to compile the classes:

  g++ Fibers/Fibers.cpp Scheduler/Scheduler.cpp Test.cpp Context/context.o -o test_program

• Once compiled, we run the next command: ./test_program

7.3.1 Screenshot 1 (Task 3 Output)

As shown in the screen shot the system was able to work successfully.

8. Conclusion