Brief Summary
Process and thread management is a key responsibility given to modern operating systems. The operating system is responsible for creating, scheduling, and terminating processes running within a computer. Nearly every computer used today has multiple processors, which are used to run computations in parallel to improve performance. However, it must be stated that programs which use multiple processors must handle issues which arise from concurrency in order to ensure robustness. To achieve software robustness, many multithreaded processes today use shared memory regions, which must be managed to ensure concurrency violations don’t occur.
1 Background Information
In this project, your task is to write a kernel module to calculate the total elapsed time of all the processes that belong to a given user in the system. To demonstrate the efficiency and challenges associated with multithreaded systems, you will model this task as a form of the classic producer-consumer problem.
- The producers and consumers of this project will be kernel threads in your module.
- A producer thread will find processes that belong to a given user and add the process information to a shared buffer.
- Consumers remove process information from the shared buffer, calculate the elapsed time that these processes have run, and output the total elapsed time to the kernel’s log.
- sudo apt update
- sudo apt install git
- git clone -b PTM https://github.com/ASTERISC-Teaching/cse330-public.git
Directory breakdown. The repository contains the following directories:
- process_gen: Contains code which produces processes for project.
- c: Kernel module which will contain the implementation.
- testcase_outputs: Screenshots of expected test case output.
- sample_code: Sample code which offers examples as to how threads/semaphores are used.
- sh: Script that allows you to run a test.
| Important note | |
| • This document only contains high-level instructions for completing this project; they are NOT EXACT step-by-step instructions. You MUST figure out the steps on your own.
• This project requires you to use the kernel (Linux v6.6.9) you compiled in project #1. If you are changing your group, it is okay to get the VM disk from your previous group and use it. • Remember to add debug statements inside the kernel module (e.g., using printk) to see what your code is doing and debug the operations. This applies to all steps of the project. • Using semaphores (explained in section 2) incorrectly in this project can cause your kernel to hang (e.g., due to a deadlock). If it does, simply restart your virtual machine, and find where the kernel module was stuck. • We provide you all testcases but it is your job to understand what these testcases are doing. • The TAs/Instructor will not help you complete the bonus parts. That is totally on you. • If your assignment does not compile or your upload is corrupted, you will get a zero. Always double-check your submission. |
|
2 Prerequisite Knowledge
In this section, we will provide short details regarding three core concepts you will use to build this project: kernel threads, semaphores, and task list. If you are not familiar with using any of these concepts, please refer to the attached reading and lecture slides for further study.
Kernel Threads
To create and start the kernel threads, you can use the kthread_run() function.
| /*
threadfn is the function to run in the thread; data is the data pointer for threadfn; namefmt is the name for the thread. It returns a pointer to the thread’s task_struct if the thread creation is successful or ERR_PTR(-ENOMEM) if it fails.*/ struct task_struct *kthread_run(int (*threadfn)(void *data), void *data, *const char *namefmt, …) |
1
2
3
4
5
6
7
Example code to create a kernel thread:
| #include <linux/kthread.h>
// the function to run in the thead static int kthread_func(void *arg) { // Thread Code } // Create and run a thread that executes “kthread_func” ts1 = kthread_run(kthread_func, NULL, “thread-1”); |
1
2
3
4
5
6
7
8
9
To stop a kernel thread, you need to use kthread_stop. It sets end_flag for thread k to return TRUE. The thread k can check its end_flag using kthread_should_stop and determine if it should stop.
| // stop the kernel thread pointed by task_struct k kthread_stop(struct task_struct *k)
// when kthread_stop() is called, this function will kthread_should_stop(void) |
return | true |
1
2
3
4
5
Semaphores are a type of lock. Recall that locks are used to regulate threads executing within a code region, and synchronize the reading and writing of the shared data.
Use these in areas which contain critical code, such as when threads read and write to the shared buffer.
| Kernel Semaphore | |
| Define | struct semaphore <name>; |
| Initialize | sema_init(&<name>, BUFFER_SIZE); |
| Wait | down(&<name>); |
| Post | up(&<name>); |
Table 1: Functions Related To Kernel Semaphores The following code snippet explains how to use semaphores:
| // Defines a semaphore with a given name struct semaphore name;
// a function to initialize a semaphore static inline void sema_init(struct semaphore *sem, int val) // acquire a lock structure void down(struct semaphore *sem) // release a loc void up(struct semaphore *sem) |
1
2
3
4
5
6
7
8
9 10
11
An example of how to use semaphores and regulate a critical section:
| #include <linux/semaphore.h> // Semaphore Definition struct semaphore empty; // define a semaphore named ’empty’ sema_init(&empty, 5); // init the semaphore as 5
// if the thread works in an infinite loop, this is how it knows when to stop. Check (4) module_exit for more information. while (!kthread_should_stop()) { if (down(&empty)) break; // exit |
1
2
3
4
5
6
7
8
9
| // Beginning Critical section ….
…. // End of Critical Section up(&empty) // signal the semaphore |
10
11
12
13
14
Suggested reading(s)
Please refer to the sample code to see how semaphores work: Semaphore Sample Code Further Reading for using semaphores: Synchronization and Semaphores
Task List
The Linux kernel stores all of the active processes in a circular doubly linked list called “task list”. Each element in the task list is a process descriptor of the struct type task_struct which contains all of the information about a process. The figure below illustrates the task list and its task_struct entries.
The task_struct contains the process’ PID in pid and the process’ user’s UID in cred->uid.val
| struct task_struct *task; task->pid // PID of the process task->cred->uid.val // UID of the user of the | process |
1
2
3
We use the for_each_process macro to iterate through the task list to access each task_struct. The macro goes over all the task_struct in the task list one by one. The following code example calculates the number of processes in the task list using for_each_process.
| #include<linux/sched.h>
#include <linux/sched/signal.h> struct task_struct* p; size_t process_counter = 0; |
1
2
3
4
5
| // On each iteration, p points to the next task in the list.
for_each_process(p) { ++process_counter; } |
6
7
8
9
10
Task #1: Write Producer Thread Code
In your kernel module, the producer thread should search the task list for all the processes that belong to the test_cse330 user (our test scripts will automatically create this user) and add their task_struct to a shared buffer. There will be only one producer in your module, and it should exit after it has iterated through the entire task list.
Task #2: Write Consumer Thread Code
Each consumer thread should read the task_struct of the processes from the shared buffer and calculate the elapsed time for each process and the total elapsed time.
- For each process, you need the pid, start_time, and boot_time to calculate elapsed time.
- The total elapsed time is the sum of elapsed time for all processes of a user.
You will need to synchronize the access of threads from the shared buffer using a semaphore. Also, multiple consumers in the system can work in an infinite loop; remember to check end_flag so they know when to stop.
Task #3: Cleanly Exit The Kernel Module
Your kernel module will not exit cleanly if any threads are waiting for semaphores (e.g., it might hang the VM). Hence, you need to make sure that no threads are waiting for semaphores. To do so, signal all the semaphores; if you expect multiple threads waiting on a semaphore; signal it multiple times.
3 Submission Details
Please place the following in one zip file and submit on canvas.
- The producer_consumer.c file. Please do not submit any binaries/.ko files.
- Output screenshots that show your code is working for each test case.
- A README text file clearly describing the name of the members within your group and any other details you want the TAs to know.
4 Grading Rubric (Regular)
There are 100 points available for this assignment, with 10 points of bonus. To test your assignment, you must run the test.sh script we have provided.
Here is a breakdown of how to use the script:
| ./test.sh <Number of processes> <Buffer Size> <Number of Producers> <Number of
Consumers> <Lines from dmesg> |
1
- Number of Processes: The total number of processes that the script will create.
- Buffer Size: The size of the shared buffer which will be used by the producers and consumers.
- Number of Producers: The number of producer threads to be used.
- Number of Consumers: The number of consumer threads to be used.
- Lines from dmesg: The number of lines which will be printed from the dmesg to the console.
Test Case Scoring
- sudo ./test.sh 10 5 1 0 25: 5 points
- sudo ./test.sh 10 5 0 1 25: 5 points
- sudo ./test.sh 10 50 1 1 25: 10 points
- sudo ./test.sh 100 50 1 1 25: 15 points
- sudo ./test.sh 1000 50 1 1 100: 15 points
- Points Awarded for Code: 50 points
5 Grading Rubric (Bonus)
This bonus test case tests if your code is able to handle multiple consumer threads.
- sudo ./test.sh 100 50 1 2 25: 10 points
- There is no partial grading within individual test cases for the bonus part.
