-
Notifications
You must be signed in to change notification settings - Fork 0
cheyuanl/410-p2
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
/** @mainpage 15-410 Project 2 @author Che-Yuan Liang (cheyuanl) @author Zhipeng Zhao (zzhao1) In this project, we started working on the System-call stub and stack of thread creation together. Then Che-Yuan worked on Thread management calls, Semaphores Readers/writers locks. Zhipeng worked on Mutexes and condition variables, and exception handlers. During the project, the key design decision are all made together, like the stack structure of multi-threaded program, how to do thr_join and how to develop cond_wait and cond_signal pair. The rest of the README details the information of our deliverables. 1. System-call stub routines The system calls can be divided into three types. No inputs, one input and multiple inputs. If there is no input, for example, the "int fork(void)", our stub just call "INT" instruction and return. If there is only one input, for example, the "void set_status(int status)", the input will be passed to system call through %esi. In this case, we first push %esi to save this callee-save register, then mov the parameter to %esi, call the "INT", pop %esi and return in the end. If there are multiple inputs, for example, "int exec(char *execname, char **argvec)", we pass the address of the first paramenter to %esi. 2. A software exception handler which implements automatic stack growth for legacy programs The single-thread legacy program may sometimes need more stack space than allocated initially. The auto-stack growth handler is used to handle the case when the memory access of the stack growth causes pagefault. We first install the handler in "install_autostack()", which will be called before "main()". To install the handler, we need to allocate exception stack that will be used for the handler function. We decided to put the exception stack in Heap, since that would not require space that close to the stack for the legacy program. Such that, the legacy program can grow dynamically until it hits the region of Heap. We used swexn to register the handler. We passed the valid exception stack addr(actually the addr that one word higher than the upper bound of the exception stack), our handler addr to swexn syscall. Since this is registering the handler, we don't need to specify the registers values through ureg. Once the exception happens, the kernel would call our handler. Our handler would check the cause of the exception. The handler only reacts to pagefault due to autostack growth. Since this is in user mode, we don't care about the pagefault in kernel mode. To react, we first double the size of current stack by allocating new pages, then retry the instruction that caused the pagefault. If the pagefault still exist, the handler will double the stack size again until covers the memory access, or hits the memory boundary(overlap with other regions, like Heap). The instruction retry is implemented by passing the ureg to swexn. 3. A software exception handler which handles thread crashes for multi-threaded programs. In a multi-threaded programs, if one thread meets a fatal error, it's likely the whole program would not act correctly. For example, the thread may hold some locks, or other threads are waiting for the results generated by this thread. So it's good to vanish the whole task instead of the single thread. However, the default kernel reaction would only vanish a single thread. In our multi-threaded handler, we generally print out the cause and register values and then vanish the whole task. This handler is installed when a thread is created successfully. This handler will overwrite the autostack growth handler that used for legacy code. In multi-threaded scenario, the autostack growth is not supported any more. 4. Thread management calls. In a multi-threaded program, each thread will have its own stack and registers, while share the same heap. We designed a structure that contains crucial information of a thread, like id, state, lock, etc. We decided to put this structure in each thread's own stack, so that each thread can access its own information. We call this structure "stack header". During thr_init, we get the stack size for the threads to be created, and initialize the locks that to be used in multi-threaded program. In thr_create, we first allocate the stack for child thread and install the "stack header" on the stack. Then we has an assembly code to do the thread fork. After the thr_fork there will be two threads and two copies of registers. These two thread will run independently. However, before the child thread jump to the child function, it should have its id ready in its stack. The child thread would do cond_wait until the parent thread writes the id to child's stack. The parent thread would install the exception handler before leaving thr_create if the child thread is created successfully. And the child thread would install the handler before calling the child function. We have a global lock for create, to ensure the global checking and modification are protected. There is also condition variable between thr_exit and thr_join, since the thr_join needs to wait until the thread calls thr_exit. These condition variable and lock is at thread-level which is stored in each thread's "stack header". The thr_join faces another level of concurrency, which is multiple threads joining one thread. Only one thr_join would succceed, others will fail. We specify a join_flag for each thread. If the join_flag is 1, that means this thread(A) has been registered for joining by another thread(B). Other threads(C,D...) would not be able to join(A) any more. The thread B,C,D... would all go to cond_wait, and A will wake all of them up using cond_broadcast in thr_exit. The one who will re-acquire the lock can enter the critical section to set the join_flag. Other threads will enter later and see if the join_flag is already set, then will directly return -1. We developed some utility functions to manage the linked-list of threads and also check the current "stack header" for the calling thread. 5. Mutexes and condition variables In mutexes data structure, we have two fields, "lock_available" to indicate whether a lock is available or not and "init" to indicate whether the mutex is initialized or not. If the mutex is destroyed, we regard that as not initialized. Mutex is implemented using atomic XCHG instruction. Condition variable(CV) implementation refers to the slides in class. We built the queue using linked-list. We chained the threads together by specifying the "cv_next" in thread "stack header" structure. By using this linked-list, we avoid doing any memory allocation inside the CV calls. A local mutex is used to protect the queue's state in CV's world. The key issue of CV implementation is how to make "atomic unlock and block". Basically, in cond_wait, we need to make sure that after the thread unlock, the thread should go to sleep atomically. We don't want the cond_signal thread sneaks in between of the "unlock and block". However, there is no such atomic instruction. We let the "unlock and block" appears to be atomic by letting the cond_signal do busying waiting on make_runnable. Only after the cond_wait thread actually goes to sleep, the cond_signal thread could proceed to wake up the cond_wait thread. 6. Semaphores For semaphore, we simply build it on top of the conditional variable. Every thread who need to pass through the semaphore need to wait conditioning on the counter variable defined in the semaphore. 7. Reader/writers locks For reader/writer locks, it is also build on top of conditional varaible conditioning on the number of waiting writer, and number of current reader defined in the sem_t. Our lock use the property of the FIFO in our implementation of conditional varaibles. The waiting threads will get the lock in the order of there request. Our lock gives the writer higher prioirty than the user, that is if there is any writer waiting for the lock, the reader should yield, until there is not writer waiting. Note This could couse readers never get a chance to acquire the lock. */
About
No description, website, or topics provided.
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published