PintOS, created by Ben Pfaff, is a UNIX-like “instruction operating system”, meaning that its functionalities are limited and its source code is available. The implementation of many modules and functionalities is either very simple or totally absent, which is made intentionally for educational purposes to allow students create their own custom modifications.
This repository contains my own implementation of the modules listed below:
Changed files: src/threads/thread.h, src/devices/timer.c.
The implementation of thread and timer modules is changed so that the caller thread is blocked and unblocked instead of having it busy-wait wasting the CPU cycles. Blocking the thread removes it from the list of ready threads, so to keep track of the sleeping threads, a new container is implemented.
Changed files: src/threads/thread.c.
The implementation of thread yielding and unblocking is modified to allow the threads to be added into the ready queue in the order of their priority. Additionally, when a new thread is created, if its priority is larger than that of the parent thread, the parent thread yields the CPU. Multilevel Feedback Queue Scheduling is implemented using dynamically updated priorities based on recent_cpu and load_average values.
Changed files: src/userprog/syscall.c.
The list of implemented system calls and their description is as follows:
-
bool create (const char *file, unsigned initial_size)
Creates a new file called file initially initial_size bytes in size. Returns true if successful, false otherwise. Creating a new file does not open it: opening the new file is a separate operation which would require the open() system call.
-
bool remove (const char *file)
Deletes the file called file. Returns true if successful, false otherwise. A file may be removed regardless of whether it is open or closed, and removing an open file does not close it.
-
int open (const char *file)
Open the file called file. Returns the file descriptor (fd), or -1 if the file could not be opened.
-
int filesize (int fd)
Returns the size, in bytes, of the file open as fd.
-
int read (int fd, void *buffer, unsigned size)
Reads size bytes from the file open as fd into buffer. Returns the number of bytes actually read (0 at end of file), or -1 if the file could not be read (due to a condition other than end of file). Fd 0 reads from the keyboard using input_getc().
-
int write (int fd, const void *buffer, unsigned size)
Writes size bytes from buffer to the open file fd. Returns the number of bytes actually written, which may be less than size if some bytes could not be written.
-
void seek (int fd, unsigned position)
Changes the next byte to be read or written in open file fd to position, expressed in bytes from the beginning of the file. (Thus, a position of 0 is the file's start.)
-
unsigned tell (int fd)
Returns the position of the next byte to be read or written in open file fd, expressed in bytes from the beginning of the file.
-
void close (int fd)
Closes file descriptor fd. Exiting or terminating a process implicitly closes all its open file descriptors, as if by calling this function for each one.
Changed files: src/userprog/exception.c, src/vm/frame.h, src/vm/frame.c, src/vm/page.h, src/vm/page.c, src/vm/swap.h, src/vm/swap.c.
Valid memory addressing is ensured by checking whether the faulting address is the NULL or kernel address, and if either is true, an invalid memory access is flagged, and the program is returned with an error code.
The faulting address can be resolved in one of the two ways:
- Loading a page from disk or swap
- Growing the stack by one page
Either way, the page table entry associated with the faulting address must be fetched.
The clock-version of the second chance eviction policy is implemented by iterating over the frame table starting from the clock hand and continuously iterating over every entry until a frame with no second chance is found, which is removed. Importantly, if the page is dirty, before being removed, it should be written to swap.
Changed files: src/filesys/cache.c, src/filesys/inode.c.
The OS can cache recently accessed blocks in main memory and ensure that subsequence accesses go through the cache first to avoid unnecessary and slow I/Os.
After receiving a disk sector number, we need to find the index of the corresponding cache entry, or return -1 if the sector is not in the cache. If there are no free slots when a request for a free entry is made, a cache slot is evicted per the clock policy and the index of the evicted slot is returned. Finally, when the cache entry is accessed, if it is a write operation, the entry should be marked as dirty.
Instead of a single extent file allocation scheme, we implemented a scheme allowing us to store the file in multiple locations on disk and keep track of which sectors a file was written to. Theinode_grow function that governs this process is responsible for calculating the number of extra sectors needed to store a file, implementing direct allocation of the first 4 memory blocks, implementing indirect allocation of the next 9 memory blocks, and implementing doubly indirect allocation of the next and last memory blocks.