keos_project4/
lib.rs

1//! # Project 4: Synchronization and Multithreading
2//!
3//! In Project 4, you will expand KeOS's process abstraction to support
4//! **multithreading**. You will implement basic **synchronization primitives**
5//! such as **mutexes**, **condition variables**, and **semaphores** to
6//! synchronize resources between threads.
7//!
8//! Synchronization primitives will be used to support correct multithreaded
9//! behavior. For example, **thread join** functionality will be built using
10//! semaphores, which themselves are implemented using a combination of mutexes
11//! and condition variables.
12//!
13//! Finally, you will improve the scheduler by implementing a **round-robin**
14//! scheduling algorithm. Unlike previous projects where the unit of scheduling
15//! was the **entire process**, starting from this project, the unit of
16//! scheduling becomes an individual **thread**.
17//!
18//! ## Getting Started
19//!
20//! To get started, navigate to the `keos-project4/grader` directory and run:
21//!
22//! ```bash
23//! $ cargo run
24//! ```
25//!
26//! ## Modifiable Files
27//! In this project, you can modify the following five files:
28//! - `sync/mutex.rs`
29//! - `sync/condition_variable.rs`
30//! - `sync/semaphore.rs`
31//! - `process.rs`
32//! - `round_robin.rs`
33//!
34//! ## Project Outline
35//!
36//! - [`Synchronization Primitives`]:
37//!   - **Mutex**: Provide mutual exclusion.
38//!   - **Condition Variable**: Enable waiting for conditions.
39//!   - **Semaphore**: Implement higher-level synchronization using mutex and
40//!     condition variables.
41//!
42//! - [`MultiThreading`]: Implement thread creation, termination, and and join
43//!   mechanisms.
44//!
45//! - [`Round Robin Scheduler`]: Implement a round-robin scheduler that switches
46//!   between threads fairly, using time slices.
47//!
48//!
49//! [`Synchronization Primitives`]: sync
50//! [`MultiThreading`]: process
51//! [`Round Robin Scheduler`]: round_robin
52
53#![no_std]
54#![no_main]
55#![feature(negative_impls)]
56#![deny(rustdoc::broken_intra_doc_links)]
57
58extern crate alloc;
59#[allow(unused_imports)]
60#[macro_use]
61extern crate keos;
62
63pub mod process;
64pub mod round_robin;
65pub mod sync;
66
67use alloc::boxed::Box;
68use core::ops::Range;
69use keos::{
70    KernelError,
71    addressing::{Pa, Va},
72    syscall::Registers,
73    task::PFErrorCode,
74    task::Task,
75    thread::{ThreadBuilder, with_current},
76};
77use keos_project1::syscall::SyscallAbi;
78use keos_project2::mm_struct::MmStruct;
79use keos_project3::{fork::fork, get_phys::get_phys, lazy_pager::PageFaultReason};
80pub use process::Thread;
81
82/// Represents system call numbers used in project4.
83///
84/// Each variant corresponds to a specific system call that can be invoked
85/// using the system call interface. The numeric values align with the
86/// syscall table in the operating system.
87#[repr(usize)]
88pub enum SyscallNumber {
89    /// Terminates the calling thread.
90    Exit = 0,
91    /// Opens a file and returns a file descriptor.
92    Open = 1,
93    /// Reads data from a file descriptor.
94    Read = 2,
95    /// Writes data to a file descriptor.
96    Write = 3,
97    /// Moves the file offset of an open file.
98    Seek = 4,
99    /// Retrieves the current file offset.
100    Tell = 5,
101    /// Closes an open file descriptor.
102    Close = 6,
103    /// Create an interprocess communication channel.
104    Pipe = 7,
105    /// Map the memory.
106    Mmap = 8,
107    /// Unmap the memory.
108    Munmap = 9,
109    /// Fork the process.
110    Fork = 10,
111    /// Create a thread.
112    ThreadCreate = 11,
113    /// Join a Thread.
114    ThreadJoin = 12,
115    /// Terminates the process, by terminating all threads.
116    ExitGroup = 13,
117    /// Get Physical Address of Page (for grading purposes only)
118    GetPhys = 0x81,
119}
120
121impl TryFrom<usize> for SyscallNumber {
122    type Error = KernelError;
123    fn try_from(no: usize) -> Result<SyscallNumber, Self::Error> {
124        match no {
125            0 => Ok(SyscallNumber::Exit),
126            1 => Ok(SyscallNumber::Open),
127            2 => Ok(SyscallNumber::Read),
128            3 => Ok(SyscallNumber::Write),
129            4 => Ok(SyscallNumber::Seek),
130            5 => Ok(SyscallNumber::Tell),
131            6 => Ok(SyscallNumber::Close),
132            7 => Ok(SyscallNumber::Pipe),
133            8 => Ok(SyscallNumber::Mmap),
134            9 => Ok(SyscallNumber::Munmap),
135            10 => Ok(SyscallNumber::Fork),
136            11 => Ok(SyscallNumber::ThreadCreate),
137            12 => Ok(SyscallNumber::ThreadJoin),
138            13 => Ok(SyscallNumber::ExitGroup),
139            0x81 => Ok(SyscallNumber::GetPhys),
140            _ => Err(KernelError::NoSuchSyscall),
141        }
142    }
143}
144
145impl Task for Thread {
146    /// Handles a system call request from a user program.
147    fn syscall(&mut self, regs: &mut Registers) {
148        let abi = SyscallAbi::from_registers(regs); // Extract ABI from the registers.
149        // Lookup the system call handler function based on the system call number.
150        let return_val = SyscallNumber::try_from(abi.sysno).and_then(|no| match no {
151            SyscallNumber::Exit => self.exit(&abi),
152            SyscallNumber::Open => self.with_file_struct_mut(|fs, abi| fs.open(abi), &abi),
153            SyscallNumber::Read => self.with_file_struct_mut(|fs, abi| fs.read(abi), &abi),
154            SyscallNumber::Write => self.with_file_struct_mut(|fs, abi| fs.write(abi), &abi),
155            SyscallNumber::Seek => self.with_file_struct_mut(|fs, abi| fs.seek(abi), &abi),
156            SyscallNumber::Tell => self.with_file_struct_mut(|fs, abi| fs.tell(abi), &abi),
157            SyscallNumber::Close => self.with_file_struct_mut(|fs, abi| fs.close(abi), &abi),
158            SyscallNumber::Pipe => self.with_file_struct_mut(|fs, abi| fs.pipe(abi), &abi),
159            SyscallNumber::Mmap => {
160                self.with_file_mm_struct_mut(|fs, mm, abi| mm.mmap(fs, abi), &abi)
161            }
162            SyscallNumber::Munmap => self.with_mm_struct_mut(|mm, abi| mm.munmap(abi), &abi),
163            SyscallNumber::Fork => self.with_file_mm_struct_mut(
164                |fs, mm, abi| {
165                    fork(fs, mm, abi, |file_struct, mm_struct| {
166                        with_current(|th| {
167                            let builder = ThreadBuilder::new(&th.name);
168                            let tid = builder.get_tid();
169                            builder.attach_task(Box::new(Thread::from_file_mm_struct(
170                                file_struct,
171                                mm_struct,
172                                tid,
173                            )))
174                        })
175                    })
176                },
177                &abi,
178            ),
179            SyscallNumber::ThreadCreate => self.thread_create(&abi),
180            SyscallNumber::ThreadJoin => self.thread_join(&abi),
181            SyscallNumber::ExitGroup => self.exit_group(&abi),
182            SyscallNumber::GetPhys => {
183                self.with_file_mm_struct_mut(|fs, mm, abi| get_phys(mm, fs, abi), &abi)
184            }
185        });
186        // Set the return value of the system call (success or error) back into the
187        // registers.
188        abi.set_return_value(return_val);
189    }
190
191    /// Validates whether the given memory range is accessible for the process.
192    fn access_ok(&self, addr: Range<Va>, is_write: bool) -> bool {
193        self.with_mm_struct_mut(
194            |mm_struct, (addr, is_write)| mm_struct.access_ok(addr, is_write),
195            (addr, is_write),
196        )
197    }
198
199    /// Handles a page fault.
200    fn page_fault(&mut self, ec: PFErrorCode, cr2: Va) {
201        if !self.with_mm_struct_mut(
202            |mm_struct, (ec, cr2)| {
203                let reason = PageFaultReason::new(ec, cr2);
204                // Acquire a lock on the thread's memory state (`mm_state`) to ensure safe
205                // access.
206
207                // Delegate the fault handling to [`LazyPager::handle_page_fault`],
208                // which will update the page table and allocate a physical page if necessary.
209                let MmStruct { page_table, pager } = mm_struct;
210                pager.handle_page_fault(page_table, &reason).is_ok()
211            },
212            (ec, cr2),
213        ) {
214            // If the fault is real fault, exit the process.
215            let _ = self.exit_group(&SyscallAbi {
216                sysno: SyscallNumber::ExitGroup as usize,
217                arg1: -1isize as usize,
218                arg2: 0,
219                arg3: 0,
220                arg4: 0,
221                arg5: 0,
222                arg6: 0,
223                regs: &mut Registers::default(),
224            });
225            unreachable!()
226        }
227    }
228
229    /// Runs a given closure with physical address of page table.
230    fn with_page_table_pa(&self, f: &fn(Pa)) {
231        f(self.page_table_pa)
232    }
233}
keos_project4/lib.rs

keos_project4/
lib.rs
