Description
CSCI4730/6730 Project #1: Multi-process and IPC
In this project, you will design and implement a multi-process word counting
program. The single-process version1 is provided and you will convert it into the
multi-process architectures.
Multi-process Word Counting Program (50%)
The main problem of a single-process program is the scalability. It cannot scale large
number of words.
To address the problem, you will convert the word counting program into the multiprocess model. The main process creates multiple child processes and effectively
divides work between child processes. The child process sends the result to the main
process via Inter-process communication channel. We will use pipe in this project.
The main process waits children processes and reads the result via IPC channel, and
prints out the total on the screen.
• You will modify “wc.c” to a multi-process model.
• The program receives the number of child processes and an input file name
through the command-line argument.
o 1st argument: target file
o 2nd argument: # of child processes (default is 0)
o 3rd argument: crash rate (default is 0%)
o Example: ./wc ./large.txt 4
• Explain your program structure and IPC in README.pdf file. Only “pdf”
format will be accepted.
1 It is slightly modified from the code in http://www.opentechguides.com/howto/article/c/72/c-file-counts.html
Crash-handling (50%)
If one or more child processes crash before they complete the job (before sending the
result through pipe), the final output will be incorrect. In this project, we will
monitor the exit status of each child. If there is one or more child processes crashed,
we will create new child processes to complete the job.
The parent process should “wait” for all child processes and monitor their exit status
(hint: use waitpid()). If an exit status of a child process is “abnormal termination” by
a signal, the parent process creates a new child process to re-do the incomplete job.
• You can use 3rd command-line arguments (integer between 1 and 50) to
trigger crash. 50 means each child process has 50% chance to be killed
abnormally by signal. 0 means 0% chance to crash.
• Explain how your program handles crash in README.pdf file.
Submission
Submit a tarball file using the following command
%tar czvf p1.tar.gz README.pdf Makefile wc_multi.c
1. README.pdf file with:
a. Your name
b. Explain your design of multi-process structure and IPC.
c. Explain how your program handles crash.
2. Submit a tarball through ELC.
CSCI4730/6730 Project #2: Multi-threaded Web Server
In this project, you will design and implement a multi-threaded web server. The code of the
single-threaded version1 is provided, and you will convert it into a multi-threaded
architecture.
Note that you do not need to write or modify any code that deals with sockets or the HTTP
protocols. They are already implemented in “net.c” file and you don’t need to modify it.
Your job is to modify “webserver.c” file to make it to multi-threaded structure.
Part 1. Thread Pool – 60%
The main problem of a single-threaded web server is the poor scalability. It cannot scale up
to large numbers of clients. To address the problem, you will convert the web server into
the multi-threaded model. The multi-threaded model has a much better performance to
handle multiple clients simultaneously.
One way to implement this is to create a child thread for each request. However, it causes
unnecessary thread creation and termination overhead. To minimize such overheads, you
will design and implement a thread-pool model.
1 It is slightly modified from the code in http://www.jbox.dk/sanos/webserver.htm
Thread-pool: When the server launches, we create [N+1] child threads: [N] worker
threads, and one listener thread. The main thread only monitors the child threads.
We will use producer-consumer solution in this problem. The synchronizations will include
two semaphores (sem_full, sem_empty), and one mutex lock (mutex).
1. Listener thread keeps listening for client connections. When a request arrives (i.e.,
new item), accepts it and puts the request information (file descriptor) into the shared
buffer, and starts to listen for a new request again. If the buffer is full, the listener
should wait.
2. Each worker thread initially waits for the signal from the listener thread because the
buffer is initially empty. When the listener inserts a new request into the buffer, any
available child thread pulls a request information from the buffer and handles it (call
process() function). You will need to carefully use semaphores and lock methods to
avoid concurrency problems such as race conditions or deadlocks.
• You will modify “webserver.c” to build a multi-threaded server.
• The number of worker thread(N) is given by the user via command-line argument. Your
program will accept 2 command line arguments, “port number” and “number of
threads”.
o ./webserver 4000 10 // port 4000, create 10 child threads
• You can use client2 (html client) to test of your server program.
o ./client [host_ip or dns] [port] <# of threads>
o ex) ./client 127.0.0.1 4001 10
o <# of threads> is optional. The default is 10.
• Partial credit will be given to correct but not efficient solutions (e.g., busy-waiting).
Part 2. Crash Handling – 40%
If one or more child threads crash, we need to create new child threads to keep the same
number of threads in the thread pool. Like the first programming project, you will use the
command-line argument to simulate the thread crash. However, you do not need to repeat
the failed request in the server side. The client re-sends the request when it detects the
failure.
2 http://coding.debuntu.org/c-linux-socket-programming-tcp-simple-http-client
• You can use 3rd command-line arguments (integer between 1 and 50) to trigger a crash.
50 means each child thread has 50% chance to be killed abnormally by calling
“pthread_exit(NULL)”. 1 means 1% chance to crash.
o ./webserver 4000 10 50 // port 4000, create 10 child threads, each thread has 50%
chance to crash
• Hint: You can use “pthread_tryjoin_np()” to perform a non-blocking join.
o Details can be found in the man page: “$man pthread_tryjoin_np”
Submission
Submit a tarball file that includes the following files through eLC
1. README file with:
a. Your name
b. List what you have done and how did you test them. So that you can be sure to
receive credit for the parts you’ve done.
c. Explain your design of shared data structure and synchronization (and show that
your solution does not have any concurrency problems). Also, you need to explain how
you tested and verified your program against race conditions and deadlocks.
2. All source files needed to compile, run and test your code
a. Makefile
b. All source files
c. Do not submit object or executable files
Note: Your code should be compiled and run correctly in odin machine.
a. No credit will be given if your code failed to compile with “make” in odin (we
will use your makefile).
CSCI4730/6730 – Operating Systems Project #3
In this project, you will implement a virtual memory simulator in order to understand the
behavior of a page table and the page replacement algorithms. Virtual memory allows the
execution of processes that are not completely in memory. This is achieved by page table and
page replacement techniques. A page table stores the mapping information between virtual
addresses and physical addresses. A page fault mechanism by which the memory
management unit (MMU) can ask the operating system (OS) to bring in a page from the swap
disk. The system we are simulating is 16-bit machine (8 bits for index and 8 bits for offset).
Part 1: Page Table – (50%)
The page table structure that we will implement is a linear page table. Each page table entry
contains a physical frame number (PFN), a valid bit, and a dirty bit. The size of main memory
(# of physical memory frames) is configurable via command-line arguments. The size of
virtual memory (# of virtual pages), and the number of process are specified in the input file.
The machine we are simulating supports up to 256 pages, 256 frames, and 8 processes.
Initially, all physical frames are free. Our page allocation policy simply hands out the free
physical frame until the free-frame list becomes empty. When the free-frame list is empty,
you should find a victim page using page replacement policy.
We also simulate the placement of virtual pages on the swap disk. We keep track of the
number of swap disk read and write operations that are needed to handle the page faults.
We maintain “dirty” bit on the page table and swap out the dirty page when it is replaced.
In this project, you will need to handle two types of requests. The request format is the
following:
[pid] [R or W] [Virtual Address] [Byte (if W)]
1. Read req: It reads 1 byte of the memory.
2. Write req: It writes 1 byte to the memory. For simplicity, we use a single character to
fill-out the entire page. For example, if the request is “1 W 0x03D2 H”, it will fill out the
entire page from 0x0300 to 0x03FF (256 bytes) with “H”. We assume that the entire
process memory is initialized with “A”.
In this project, you do not need to directly access data structure for “page table”, “inverted
page table”, or “swap disk”. Instead, you can simply use APIs to access them. All APIs are
defined in “API.h” header file.
1. To access the page table (convert virtual page number (VPN) to physical frame
number (PFN))
A. PTE read_PTE (int pid, int VPN);
B. void write_PTE(int pid, int VPN, PTE pte);
2. To access the inverted page table (convert physical frame number (PFN) to virtual
page number (VPN) and process id (pid)):
A. IPTE read_IPTE (int PFN);
B. void write_IPTE (int PFN, IPTE ipte);
3. To access the swap disk:
A. void swap_in(int pid, int VPN, int PFN); // read swap disk: swap space ->
physical memory
B. void swap_out(int pid, int VPN, int PFN); // write swap disk: physical
memory -> swap space
The following is details of data structure:
• Data structure for the page table is defined in vm.h
o PTE is a page table entry. It contains virtual to physical mapping information
for each virtual pages including [physical frame number], [valid bit], and [dirty
bit].
o Each process has own page table.
• Invert page table is necessary to identify process id and virtual page number for each
physical frame. You need this information during swapping procedure.
Implementation guidelines:
1. You will need to implement the following two functions in “pagetable.c” file.
A. int is_page_hit(int pid, int VPN, char type)
i. This function checks the page table. If the requested page is available
and valid, return PFN. If the page is not valid, return -1.
B. int pagefault_handler(int pid, int VPN, char type)
i. This function handles the page fault. If a free frame is available, simply
use it to load a request page to physical memory. Note that,
“get_freeframe()” function to get free frame is provided and you don’t
need to implement it. If no free frame is available, call
“find_replacement” function to find a victim frame from the physical
memory.
ii. To read a page from swap disk, use “swap_in” function. To write a page
from the memory to swap disk (when it is dirty), use “swap_out”
function.
2. Currently, ZERO replacement algorithm is available that always replaces the frame 0
for the page fault. You will be implementing FIFO, LRU, and CLOCK in the next part.
Part 2: Page Replacement Algorithm– (50%, FIFO: 15%, LRU: 15%,
CLOCK: 20%)
The current simulator only supports ZERO page replacement algorithm that always replace
the frame 0.
In this part, you will implement three page replacement algorithms, First-in-first-out (FIFO)
and Least-recently-used (LRU) algorithms, and second chance algorithm (CLOCK).
• All replacement functions are declared in pagetable.c file, but they are empty now.
• The simulator requires a command-line argument to specify a replacement policy.
o 0: ZERO
o 1 : FIFO
o 2 : LRU
o 3 : CLOCK
• You can use “double linked list” to maintain LRU list. “list.c” and “list.h” are double
linked list implementation. If you want, feel free to use your own or favorite linked
list implementations.
o Define head node with “struct Node”. This should be initialized as NULL.
o “list_insert_head()” to insert a new item into the head of the list.
o “list_insert_tail()” to insert an item into the tail of the list.
o “list_remove()” to remove an item.
o “list_print()” to print the list.
o list_test.c is a test implementation for the list.
Command-Line Arguments
Our virtual memory simulator requires three command line arguments.
1. Number of frames in the physical memory (between 1 and 256)
2. Page replacement policy (0 – ZERO, 1 – FIFO, 2 – LRU, 3 – CLOCK)
3. Input file that contains
A. The number of processes and virtual pages
B. reference string
4. ex) ./vm 4 0 ./example_inputs/belady_input.txt
Input Generator
The input format for your simulator will be in the following format:
[pid] [R or W] [Virtual Address] [Byte (if W)]
You can find example inputs, including the belady sequence and reference string, in
“example_input” folder.
The first line of the input file indicates “# of pages” and “# of processes”
You may use a provided input generation tool “input_gen” to generate random inputs.
o $./input_gen [# of page] [# of process] [# of requests]
Output Format
The output of your simulation should be the result of each memory request:
“[PID, R/W] original_request –> physical_address: byte [hit/miss]”.
For the process termination, the output should be:
“[PID, T] # of freed physical frame”
At the end of a request sequence, the total number of requests, the total numbers of hit and
miss in page table, and the total numbers of swap disk read and write should be printed. A
code for the output is already implemented, and you will just need to use provided APIs to
update “hit”, “miss”, “swap read”, and “swap write” count. You do not need any additional
implementation for that.
Example of output (belady input with 6 virtual pages, 3 physical frames, FIFO):
$ ./vm 3 1 ./example_inputs/belady_input.txt
# PAGES: 6, # FRAMES: 3, # PROCS: 1, Replacement Policy: 1 – FIFO
[pid 0, W] 0x0100 –> 0x0000: a [miss]
[pid 0, W] 0x0200 –> 0x0100: b [miss]
[pid 0, W] 0x0300 –> 0x0200: c [miss]
[pid 0, W] 0x0400 –> 0x0000: d [miss]
[pid 0, R] 0x0100 –> 0x0100: a [miss]
[pid 0, R] 0x0200 –> 0x0200: b [miss]
[pid 0, W] 0x0500 –> 0x0000: e [miss]
[pid 0, R] 0x0100 –> 0x0100: a [hit]
[pid 0, R] 0x0200 –> 0x0200: b [hit]
[pid 0, R] 0x0300 –> 0x0100: c [miss]
[pid 0, R] 0x0400 –> 0x0200: d [miss]
[pid 0, R] 0x0500 –> 0x0000: e [hit]
=====================================
Request: 12
Page Hit: 3 (25.00%)
Page Miss: 9 (75.00%)
Swap Read: 9
Swap Write: 4
Important! You should remove all debugging messages before the submission. TA will use
“diff” to compare your output with the solution output. You could have a penalty if your
code emits anything other than the defined output.
Tip! You can use “debug(..)” instead of “printf(..)” to print out your debugging messages. It
will print out the messages in the screen if you comment out “#define NDEBUG” in vm.h
file. You can simply enable “#define NDEBUG” before the submission to remove the
debugging messages.
Testing
You may use “vm_reference” executable to generate reference output and compare it with
yours. Note that it is not yet fully tested and could have bugs and can crash.
$./vm_reference 3 1 ./example_inputs/belady_input.txt
Submission
Submit a tarball file to include all source code and a README file:
1. README file with:
a. Your name
b. List what you have done and how you tested them. So that you can be sure to
receive credit for the parts you’ve done.
c. Explain your design of data structures.
d. README should be PDF format. Only PDF will get points.
2. Your code should be compiled in odin machine. Any compilation error on odin
will lead to 0 point. Make sure to use Makefile and command “make” to compile the
project on Odin. If you have any special compilation needs, make sure to modify
Makefile accordingly.
3. Submit a tarball through eLC.
CSCI4730/6730 – Operating Systems Project #4
In this project, you will implement a simple EXT-like file system simulator to understand the hierarchical directory and inode structures. You will be able to (1) browse the disk information, file and directory list, (2) create and delete files and directories, (3) read files. The functionality of the file system is similar to EXT file systems, but it does not include perprocess open file table, permission and user management. Figure 1 shows the file system structure of the simulator. A disk block size is 512 byte and the disk has 4096 blocks. Superblock, inode map, block map, and inode blocks are loaded into the memory at file system mount time. A size of inode entry is 128 byte, and 4 inode entries are stored in a single disk block. You can start the simulator with the following command: $./fs_sim It has one command-line argument, to specify the file name that stores our file system. If is not exist, the simulator creates a new file system and mounts it. If is already exist, the simulator mounts it. After the simulator mounts the file system, it waits for the commands from the user. It supports commands to access files and directories, and “quit” or “exit” to unmount the file system. You can also feed commands directly from the input file as follows: $./fs_sim test.disk < testfile.input You may use “fs_sim_reference” executable to generate reference output and compare it with yours. Note that it is not yet fully tested and could have bugs and can crash. Part 1: File – 50% In this file system, the super block is stored in the disk block 0. It contains the number of available inode and data blocks, and root directory information. Super block is defined in “fs.h” as follows: In this project, each inode uses 15 direct blocks and 1 single-indirect block to support files up to 73,216 (7,680 +65,536) bytes. Specifically, 15 direct blocks support 7,680 bytes (15 * 512 bytes) and 1 indirect block supports 73,216 bytes (128 * 512 bytes). Each file in a file system has an identification number, called inode number, which is unique in a file system. Inode structure (Inode) is defined in “fs.h” file as follows: The file system will support the following functionalities (The current file system already supports “df”, “create”, and “stat”. You will need to implement “cat”, “rm”, “ln”, and “cp”) . Command Arguments Description df Show the file system information: number of free blocks / number of free inodes. stat Show the status of the file or directory with name . It displays the inode information; whether it is a file or directory; size of the file/directory; number of blocks allocated; other information stored about this file/directory. create Create a file with as a name in the current directory, and fill it with amount of random characters. cat Print out the content of the file. cp Copy file to . Both and are in the current directory. rm Delete file in the current directory. ln Create a hard link. Both and are in the current directory. You will need to modify “file.c” file to implement Part 1. You can use pre-defined APIs to access inode, inode map, block map, and disk blocks. All APIs are declared in “API.h” file. Part 2: Directory – 50% In this part, you will implement hierarchical, tree-structured directory. In our simulator, each directory has up to 25 entries (files and sub-directories). The first entry is always a current directory (“.”) and the second entry is a parent directory(“..”). The root directory does not have a parent directory. You will need to implement the following functionalities (you will need to implement “mkdir”, “rmdir”, and “chdir”): Command Arguments Description ls Show the content of the current directory mkdir Create a sub-directory under the current directory. rmdir Remove the sub-directory . It only removes an empty directory. “.” and “..” cannot be deleted. cd Change the current directory to A directory structure (Dentry) is 512 bytes, and it is stored in a single disk block. Directory structure is defined in “fs.h” file as follows: To create a new directory, you will need one inode and one data block to store the directory structure (Dentry). The filesystem always maintains “curDir” that contains the directory structure of the current directory. When the user changes the current directory using “cd”, you need to properly change “curDir”. You will need to modify “directory.c” file to implement Part 2. Submission Submit a tarball file through eLC with all project files include: 1. README file with: a. Your name b. List what you have done and how to test them. So that you can be sure to receive credit for the parts you’ve done. c. Explain your design. 2. file.c and directory.c files. If you made further modification, make sure to include all modified files. a. Makefile b. All modified source and header files c. Do not submit object or executable files 3. Your code should be compiled in odin machine. Any compilation error on Odin will lead to 0 point. Make sure to use Makefile and command “make” to compile the project on Odin. If you have any special compilation needs, make sure to modify Makefile accordingly. 4. Submit a tarball through ELC.