The 410-p2 from cheyuanl

/**

@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.

*/
cheyuanl / 410-p2 Goto Github PK

410-p2's Introduction

410-p2's People

Contributors

Watchers

410-p2's Issues

mutex_init

reverse the order

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent
