Due: Monday, October 28th, 2024, at 11:59pm
This project aims to provide a comprehensive understanding of system calls, kernel programming, concurrency, synchronization, and elevator scheduling algorithms. It consists of multiple parts that build upon each other to deepen your knowledge and skills in these areas.
In Part 1, you start by working with system calls. By adding system calls to a C/Rust program and verifying their correctness using the "strace" tool, you gain hands-on experience with system call integration and learn about the available system calls for your machine. This part lays the foundation for understanding how system calls interact with the kernel.
Part 2 takes you further into kernel programming. You will develop a kernel module called "my_timer" that retrieves and stores the current time using the "ktime_get_real_ts64()" function. This module creates a proc entry and allows you to read the current time and elapsed time since the last call. This part helps you understand how kernel modules work, how to interact with kernel functions, and how to use proc interfaces for communication.
Part 3 focuses on a more complex task: implementing a scheduling algorithm for a dorm elevator. You create a kernel module representing the elevator, supporting operations like starting, stopping, and issuing requests. The module also provides a "/proc/elevator" entry to display important elevator information. This part challenges you to manage concurrency, synchronization, and efficient scheduling within the kernel environment.
Each part of the project builds upon the knowledge and skills gained in the previous parts. Part 1 introduces you to system calls and their integration, which forms the basis for kernel programming in Part 2. Part 2 expands your understanding of kernel modules and communication through proc interfaces, setting the stage for the more advanced concepts explored in Part 3.
By completing this project, you acquire practical experience in system calls, kernel programming, concurrency, synchronization, and scheduling algorithms. These are essential skills for developing efficient and robust software systems, particularly in operating systems and low-level programming domains. Understanding system calls and kernel programming enables you to interact with and extend the functionality of the operating system, while concurrency, synchronization, and scheduling concepts are crucial for efficient resource management and multitasking in complex systems.
Submit your division of labor document on Canvas by 11:59 PM, 10/07/24.
You can find the example code in Module.
Please follow the instructions below to complete Part 1 of the task:
To minimize the length of the output from strace, try to minimize the use of other function calls (e.g., stdlib.h) in your program.
Note: Running strace on an empty C program will generate a number of system calls. Therefore, when using strace on your Part 1 code, it should produce four more system calls than the empty program.
Please submit the following files:
In Unix-like operating systems, the time is often represented as the number of seconds since the Unix Epoch (January 1st, 1970). The task requires creating a kernel module named "my_timer" that utilizes the function ktime_get_real_ts64() to retrieve the time value, which includes seconds and nanoseconds since the Epoch.
To insert a kernel module:
$ sudo insmod my_timer.ko
To remove a kernel module:
$ sudo rmmod my_timer.ko
To check for your kernel module:
$ lsmod | grep my_timer
Example Usage:
$ cat /proc/timer
current time: 1518647111.760933999
$ sleep 1
$ cat /proc/timer
current time: 1518647112.768429998
elapsed time: 1.007495999
$ sleep 3
$ cat /proc/timer
current time: 1518647115.774925999
elapsed time: 3.006496001
$ sleep 5
$ cat /proc/timer
current time: 1518647120.780421999
elapsed time: 5.005496000
Your task is to implement a scheduling algorithm for a dorm elevator. You will create a kernel module elevator to implement this.
Download the latest stable linux-kernel-6.10.x and follow the provided slides in compiling your kernel. You can download from the following link:
Download KernelYou should move the kernel to your /usr/src/ directory and create a soft link to it as so:
$ sudo ln -s /usr/src/[kernel_version] ~/[kernel_version]
$ cd ~/[kernel_version]
This will make it easier to modify from elsewhere instead of having to edit it in a restricted area.
Modify the kernel by adding three system calls to control the elevator and create passengers. Assign the following numbers to the system calls:
The respective function prototypes are as followed:
int start_elevator(void)
The start_elevator() system call activates the elevator for service. From this point forward, the elevator exists and will begin to service requests. It returns 1 if the elevator is already active, 0 for a successful start, and -ERRORNUM if initialization fails or -ENOMEM if it couldn't allocate memory. The elevator is initialized with the following values:
State: IDLE
Current floor: 1
Number of passengers: 0
int issue_request(int start_floor, int destination_floor, int type)
The issue_request() system call creates a request for a passenger, specifying the start floor, destination floor, and type of passenger (0 for freshmen, 1 for sophomore, 2 for junior, 3 for senior). It returns 1 if the request is invalid (e.g., out of range or invalid type) and 0 otherwise.
int stop_elevator(void)
The stop_elevator() system call deactivates the elevator. It stops processing new requests (passengers waiting on floors), but it must offload all current passengers before complete deactivation. Only when the elevator is empty can it be deactivated (state = OFFLINE). The system call returns 1 if the elevator is already in the process of deactivating and 0 otherwise.
You will need to make these files to add the system calls:
You will need to modify the following files to add te system calls:
You will need to disable certain certificates when adding system calls, follow the slides.
Compile the kernel with the new system calls. The kernel should be compiled with the following options:
$ make menuconfig
$ make -j$(nproc)
$ sudo make modules_install
$ sudo make install
$ sudo reboot
Check that you installed your kernel by typing this into the terminal:
$ uname -r
Note: Making kernel is a long process! Make sure to do this part early!
You should test if you successfully added the system called to your installed kernel with the provided tests in the example code in the directory p2-example-code/system-calls-test/
Read README.md and run the following commands:
$ make
$ sudo insmod syscheck.ko
$ make run
You should get a message that tells you if you have the system calls installed or not.
Then, remove the module, rmmod syscheck.ko, since it is used only for testing system calls.
Implement the elevator kernel module. The module should be named "elevator" and should be loaded using insmod. The module should be unloaded using rmmod.
Recall that these are the details:
The module must provide a proc entry named /proc/elevator. The following information should be printed (labeled appropriately):
For each floor of the building, the following should be printed:
Example Proc File:
Elevator state: LOADING
Current floor: 4
Current load: 650 lbs
Elevator status: O5 F2 S4 S1
[ ] Floor 6: 1 S3
[ ] Floor 5: 0
[*] Floor 4: 2 F1 J2
[ ] Floor 3: 2 J4 J5
[ ] Floor 2: 0
[ ] Floor 1: 0
Number of passengers: 4
Number of passengers waiting: 5
Number of passengers serviced: 61
F is for freshmen, O is for sophomore, J is for junior, S is for seniors.
Interact with two provided user-space applications that enable communication with the kernel module:
You can use the following command to see your elevator in action:
$ watch -n [snds] cat [proc_file]
You can find producer.c and consumer.c programs in p2-example-code/part3-test-case/syscall-tests.
You will be required to give a 15-minute demo of your elevator kernel module to demonstrate your understanding of the project. A week before the project is due, registration for the demonstration will open. The presentations will take place between 10/28/24 and 11/11/24. You will present your project, and then demonstrate the functionality of your elevator. Your presentation will involve a brief overview of your elevator, a discussion regarding your implementation, and then a demonstration of your elevator. You will be required to demonstrate:
The number of passengers that your elevator is able to transport in a span of 3 minutes (without cheating) will receive bonus points. Only groups that have submitted the project before the deadline are elligible for competition. The point distribution amongst ranks is as follows:
If there is a tie at any rank, all groups involved in the tie will receive the points associated with that position, and the next position(s) will be skipped to avoid double-counting. Example: If two participants are tied for 2nd place, they both receive 3 points, but the next group ranks 4th (as the 3rd place is skipped).
Additionally, a leaderboard will be posted of the top 5 finishers and the number of passengers that they were able to transport in three minutes.
If you score onto the leaderboard, your score will be posted, but your group number remain anonymous.
You can assume that the proc file will only be 10000 characters long.
You can assume that students will not leave from the same floor they entered from.
The demo will run off your chosen machine with your chosen kernel module.
All code ran during the demo will be pulled off your GitHub Classroom repository.
You are only allowed to use C or Rust.
The list of passengers waiting at each floor and the list of passengers on the elevator must be stored in a linked list, using your own implementaton or linux/list.h.
The passengers must be allocated dynamically using kmalloc.
The elevator activity must be controlled within a kthread.
The elevator must use locking around shared data, using mutex.
The elevator is not circular. For example, you cannot go from floor 6 to floor 1 or from floor 1 to floor 6 in one move.
The elevator may not cheat, you will lose points and be disqualified from extra credit.
A program with compilation errors will get 0 points (you must demonstrate your project in front of us).
Please refer to the standard project syllabus.
Total points: 105
You should have the following files/directories in your Git repository:
For this project, you only need to organize your source code and header files into the src/ folder.
If you are using Rust, the standard Rust project structure (in rubric) will suffice.
Do not include your final executable(s) in your repository, doing so will result in a deduction!
For part 2 and part 3, your makefile should produce a kernel module, my_timer.ko and elevator.ko respectively.
Program submissions will be done through GitHub Classroom.
Except for changes that substantially affect the implementation of the evaluation (grading) statement, this syllabus is a guide for the course and is subject to change with advance notice.