This operating systems programming project in C consists of three parts: The first part is about system call tracing an empty C program with only 4 system calls. The second is to implement a timer kernel module. The third is to implement a
producer/consumer analogy of an elevator scheduler. Once the
implementation of all three parts is completed, a demonstration is also
necessary to be delivered, as it is outlined in the Project
Specifications document. A Project Guidelines document has been
provided, along with the sample and testing codes that accompany it.
Please take the time to go over them.
Project Specifications Project : Kernel Module Programming Purpose This project introduces you to the nuts and bolts of system calls, kernel programming, concurrency, and synchronization in the kernel. It is divided into three parts. Part 1: System-call Tracing Write an empty C program, empty.c. Then, create a copy of this program called part1.c and add exactly four system calls to the program. You will not receive points if the program contains more or fewer than four. The system calls available to your machine can be found within /usr/include/unistd.h. Further, you can use the command line tool, strace, to intercept and record the system calls called by a process. To confirm you have added the correct number of system calls, execute the following commands: $ gcc -o empty.x empty.c $ strace -o empty.trace ./empty.x $ gcc -o part1.x part1.c $ strace -o part1.trace ./part1.x To reduce the length of the output from strace, try to minimize the use of other function calls (e.g., stdlib.h) in your program. Note: Using strace on an empty C program will produce several system calls, so when using strace on your Part 1 code, it should produce 4 more system calls than that. Submit empty.c, emtpy.trace, part1.c, and part1.trace. Part 2: Kernel Module In Unix-like operating systems, time is sometimes specified to be the seconds since the Unix Epoch (January 1st, 1970). You will create a kernel module called my_timer that calls void ktime_get_ts64(timespec64 *ts) and stores the time value; struct timespec64 holds the number of seconds and nanoseconds since the Epoch. When my_timer is loaded (using insmod), it should create a proc entry called /proc/timer. When my_timer is unloaded (using rmmod), /proc/timer should be removed. On each read you will use the proc interface to both print the current time as well as the amount of time that's passed since the last call or the first time the file was opened (if valid). 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 Part 3: Elevator Scheduler Your task is to implement a scheduling algorithm for a pet elevator. The pet elevator can only hold a maximum of 10 passengers and cannot exceed a maximum weight of 100 lbs. Each pet is either a cat, a dog, or a lizard (randomly chosen, equally likely). Pets will appear on a floor of their choosing and always know where they wish to go. For optimization purposes, you can assume most passengers that do not start on the first floor are going to the lobby (first floor). Pets board the elevator in FIFO order, each passenger (cat, dog, or lizard) will have an assumed weight based on the type of passenger. Each cat will weigh 15 lbs., each dog 45 lbs., and each lizard 5 lbs. Once a pet boards the elevator, they may only get off when the elevator arrives at the destination. Pets will wait on floors to be serviced indefinitely. Step 1: Kernel Module with an Elevator Develop a representation of an elevator. In this project, you will be required to support having a maximum of 10 occupants and a maximum weight of 100lbs (these limits can never be exceeded by the elevator). The elevator must wait for 2.0 seconds when moving between floors, and it must wait for 1.0 second while loading/unloading passengers. The building has floor 1 as the minimum floor number (lobby) and floor 10 being the maximum floor number. New pets can arrive at any time and each floor needs to support an arbitrary number of them. Step 2: Add System Calls Once you have a kernel module, you must modify the kernel by adding three system calls. These calls will be used by a user-space application to control your elevator and create passengers. You need to assign the system calls the next set of free system call numbers. For example: • 335 for start_elevator() • 336 for issue_request() • 337 for stop_elevator() int start_elevator(void) Activates the elevator for service. From that point onward, the elevator exists and will begin to service requests. This system call will return 1 if the elevator is already active, 0 for a successful elevator start, and -ERRORNUM if it could not initialize (e.g. -ENOMEM if it couldn’t allocate memory). Initialize an elevator as follows: • State: IDLE • Current floor: 1 • Current load: 0 passengers int issue_request(int start_floor, int destination_floor, int type) Creates a request for a passenger at start_floor that wishes to go to destination_floor. type is an indicator variable where 0 represents a cat, 1 represents a dog, and 2 represents a lizard. This function returns 1 if the request is not valid (one of the variables is out of range or invalid type), and 0 otherwise. int stop_elevator(void) Deactivates the elevator. At this point, the elevator will process no more new requests (that is,passengers waiting on floors). However, before an elevator completely stops, it must offload all its current passengers. Only after the elevator is empty may it be deactivated (state = OFFLINE). This function returns 1 if the elevator is already in the process of deactivating, and 0 otherwise. Step 3: /Proc The module must provide a proc entry named /proc/elevator. Here, you will need to print the following (each labeled appropriately): • The elevator's movement state: ◦ OFFLINE: when the module is installed but the elevator isn’t running (initial state) ◦ IDLE: elevator is stopped on a floor because there are no more passengers to service ◦ LOADING: elevator is stopped on a floor to load and unload passengers ◦ UP: elevator is moving from a lower floor to a higher floor ◦ DOWN: elevator is moving from a higher floor to a lower floor • The current floor the elevator is on • The elevator's current load (weight) • The number of passengers of each type • The total number of passengers waiting • The total number of passengers serviced You will also need to print the following for each floor of the building: • An indicator for whether the elevator is on the floor • The count of the waiting passengers • For each waiting passenger, a character indicating the passenger type sample_proc.txt Output: Elevator state: UP Current floor: 4 Current weight: 85 Elevator status: 2 C, 1 D, 2 L Number of passengers: 5 Number of passengers waiting: 10 Number passengers serviced: 61 [ ] Floor 10: 3 D D L [ ] Floor 9: 0 [ ] Floor 8: 2 C D [ ] Floor 7: 0 [ ] Floor 6: 1 L [ ] Floor 5: 0 [*] Floor 4: 2 C L [ ] Floor 3: 2 D D [ ] Floor 2: 0 [ ] Floor 1: 0 (C cats, D dogs, L lizards) Step 4: Test Once you've implemented your system calls, you must interact with two provided user-space applications that will allow communication with your kernel module. producer.c: This program will issue N random requests, specified by input. consumer.c: This program expects one flag: • If the flag is --start, then the program must start the elevator • If the flag is --stop, then the program must stop the elevator The testing files producer.c , consumer.c , wrappers.h are provided to you. This is what you will use during your demonstration of the project. Do not modify these files in any way. Implementation Requirements • 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 implementation 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. • Linux kernel version 5.15 or newer must be used for the implementation of this project. • Ubuntu 22.04 is not required but highly recommended for the implementation of this project. • Variable/functions names should indicate purpose with appropriate comments, have indentation, white space, and a max column-width < 100="" chars.="" •="" c="" only="" project="" deliverables="" part="" 1:="" ◦="" empty.c="" ◦="" part1.c="" ◦="" empty.trace="" ◦="" part1.trace="" ◦="" readme="" ◦="" makefile="" part="" 2:="" ◦="" my_timer.c="" ◦="" makefile="" ◦="" readme="" •="" part="" 3:="" ◦="" elevator.c="" ◦="" sys_call.c="" ◦="" makefile="" ◦="" readme="" if="" you="" split="" your="" code="" into="" multiple="" header/c="" files,="" those="" must="" also="" be="" included="" in="" your="" deliverables.="" in="" addition="" to="" the="" deliverables,="" you="" are="" required="" to="" completely="" demonstrate="" the="" project="" on="" your="" screen="" showing="" the:="" •="" project="" source="" files="" ◦="" system="" calls,="" module="" sources,="" user-space="" sources,="" makefiles="" •="" successful="" installation="" of="" part="" 1="" •="" successful="" installation="" of="" part="" 2="" •="" properly="" display="" my_timer="" proc/timer="" •="" successful="" remove="" of="" part="" 2="" •="" successful="" installation="" of="" part="" 3="" •="" execution="" of="" an="" arbitrary="" number="" of="" consumers="" and="" producers="" for="" 5="" minutes="" •="" information="" stored="" in="" proc/elevator="" once="" per="" second="" •="" successful="" removal="" of="" part="" 3="" be="" sure="" that="" to="" include="" how="" you="" install="" and="" remove="" all="" kernel="" modules="" before="" in="" the="" demonstration="" your="" makefile="" should="" have="" some="" description,="" proper="" gnu/c99="" flags="" to="" compile,="" and="" clean.="" your="" readme="" file="" will="" need="" to="" contain="" the="" following="" in="" a="" nicely="" formatted="" text="" file.="" ●="" the="" contents="" of="" your="" source="" code="" and="" a="" brief="" description="" of="" each="" file="" ●="" instructions="" on="" how="" to="" compile="" your="" executables="" using="" your="" makefile="" ●="" list="" of="" all="" known="" bugs="" and="" unfinished="" portions="" of="" the="" project.="" for="" each="" bug,="" include="" a="" brief="" description="" of="" when="" it="" is="" occurring="" (compile,="" link,="" or="" runtime),="" when="" the="" bug="" first="" showed="" up,="" the="" symptoms="" the="" bug="" is="" giving="" off,="" and="" how="" you="" attempted="" to="" fix="" it.="" if="" there="" are="" no="" bugs,="" then="" there="" is="" no="" need.="" project="" guidelines="" project="" guidelines="" and="" hints="" kernel="" module="" ●="" portion="" of="" kernel="" that="" can="" be="" dynamically="" loaded="" and="" unloaded="" ●="" examples="" ○="" usb="" drivers="" ○="" file="" system="" drivers="" ○="" disk="" drivers="" ○="" cryptographic="" libraries="" why="" modules?="" ●="" not="" every="" machine="" needs="" the="" same="" modules="" ○="" different="" machines="" use="" different="" drivers="" ●="" load="" only="" the="" components="" you="" need="" ○="" smaller="" system="" footprint="" ○="" quicker="" boot="" time="" ●="" dynamically="" load="" modules="" for="" new="" devices="" ○="" new="" usb,="" camera,="" printer,="" graphics="" card,="" motherboard,="" etc.="" kernel="" logistics="" ●="" source="" code="" is="" stored="" in="" usr/src/="" ●="" kernel="" image="" gets="" installed="" to="" boot/vmlinux-="">
Kernel Programming ● Kernel modules are event-driven ○ Register functions ○ Wait for requests from user-space and service them ○ Server/client module ● No standard C library → Kernel libraries instead ● No floating point support ● Crashes/deadlocks in a module can crash the entire kernel ○ Requires system-wide reboot Kernel Headers #include - Module stuff #include - Module stuff #include - Locks Kernel