CS414 Section 1Project 1: MinithreadsOwen [email protected] slides stolen.What are minithreads? User-level thread package for WindowsNT/2000/XP Windows only comes with kernel-levelthreads, but user-level threads are better insome cases because of its low overhead Real motivation? We want you to learn how threading andscheduling worksWhat do I have to do? Implement minithreads of course! Requires the following parts: FIFO Queue O(1) enqueue and dequeue Non-preemptive threads and FCFS scheduler Semaphore Threads not very useful if they can’t work together Simple application – “Food services” problem Optional: Add preemption, not covered today Optional material not gradedWhat do we give you? Interfaces for the queue, minithread, andsemaphore Machine specific parts i.e. context switching, stack initialization Simple test applications Not exhaustive tests! Write you own test programs to verify thecorrectness of your code.Minithreads structuremachineprimitives_x86.cmachineprimitives.hmachineprimitives.cminithread.hminithread.csynch.hsynch.cqueue.hqueue.cinterrupts.hinterrupts.cQueues Singly or doubly linked list are both fine and can satisfy the O(1)requirements Queue must be able to hold arbitrary data Take any_t as queue_append and queue_prepend argument any_t really just a void* Note that queue_dequeue takes any_t* as its second argument Why? Remember that C is call by value If you want the any_t variable in your calling function to point towhere the item you just dequeued points to, you must pass theaddress of your any_t pointer to the queue_dequeue function. Your queue_dequeue function must dereference the any_t*argument before assigning it the value it just dequeued.headtailExample of using queue_dequeue In the calling function:any_t datum = NULL;queue_dequeue(run_queue, &datum);/* You should check the return value in your code */ In queue_dequeue function:int queue_dequeue(queue_t queue, any_t* item) {…*item = ((struct my_queue*)queue)->head->datum;…}Minithread structure Need to create a Thread Control Block(TCB) for each thread Things that must be in a TCB: Stack top pointer Stack base pointer i.e. where the stack start in memory Thread identifier Anything else you think might be usefulMinithread operations to implementminithread_t minithread_fork(proc, arg)create thread and make it runnableminithread_t minithread_create(proc, arg)create a thread but don’t make it runnablevoid minithread_yield()Let another thread in the run queue run(make the scheduling decisions here)void minithread_start(minithread_t t)void minithread_stop()start another thread, stop yourselfMinithread Creation Two methods to choose from minithread_create(proc, arg) minithread_fork(proc, arg) proc is a proc_t (a function pointer) typedef int (*proc_t)(arg_t) e.g. int run_this_proc(int* x) arg_t is actually an int*, but you cancast any pointer to it.Minithread Creation For each thread, you must allocate a stack forit and initialize the stack minithread_allocate_stack(stackbase,stacktop) minithread_initialize_stack(stacktop,body_proc, body_arg, final_proc,final_arg) The implementation of allocate and initializestack are given to you.Minithread Creationroot_proc addrfinal_argfinal_proc addrbody_argbody_proc addrstack_topstack_baseminithread_initialize_stackinitializes the stack withroot_proc (minithread_root),which is a wrapper that callsbody_proc(body_arg), followedby final_proc(final_arg).Sets up your stack to look asthough a minithread_switchhas been called (which we’llsee in a little bit).Minithread Creation What’s final_proc for? Thread cleanup You will want to free up resources such as TCB and stackallocation after your thread terminates (or else yourprogram will run out of memory like certain OS-es….) But can a thread cleanup after itself? No, not directly, not safe for a thread to free it’s own stack. Solution? Dedicated cleanup thread Should only run if there are threads to clean up though,otherwise, otherwise it should be blocked.Context switching Swap execution contexts with a thread from the runqueue (a queue that holds all your ready to runprocesses) Registers Program counter Stack pointer minithread_switch(old_thread_sp_ptr,new_thread_sp_ptr)is provided How does context switching work?Before context switch startsold_thread_sp_ptr new_thread_sp_ptrESP?new thread’s registersold thread TCB new thread TCBPush on old contextold_thread_sp_ptr new_thread_sp_ptrESP?old thread’s registersnew thread’s registersold thread TCB new thread TCBChange stack pointersold_thread_sp_ptr new_thread_sp_ptrESPold thread’s registersnew thread’s registersold thread TCB new thread TCBPop off new contextold_thread_sp_ptr new_thread_sp_ptrESPold thread’s registersold thread TCB new thread TCBYielding a thread Because our threads are non-preemptive, we need a user level way ofinitiating a switch between threads Thus: minithread_yield Use minithread_switch toimplement minithread_yield Where does a yielding thread go? Into the run queue, so it can be re-scheduled laterInitializing the system minithreads_system_initialize(proc_t mainproc,arg_t mainarg) Starts up the system First user thread runsmainproc(mainarg) Should probably create any additional threads(idle, cleanup, etc.), queues, and any otherglobal structures at this pointWhat about the Windows thread? Windows gives me an initial (kernel) threadand stack to work with, can I re-use that forone of my threads? Yes, and you should as you don’t really want tothrow away memory for no reason. But be careful, make sure this thread never exits orgets cleaned up. Remember, your threaded program neverreally exits, as the idle thread will always keeprunning. May want to re-use the initial Windows thread asthe idle thread because of this property.Semaphores semaphore_t semaphore_create(); Creates a semaphore (allocating resources for it) void semaphore_destroy(semaphore_t sem); destroys a semaphore (freeing resources for it) void semaphore_initialize(semaphore_t sem, int cnt); Initializes semaphore to an initial value i.e. Determines how many more semaphore_P functions canbe called than semaphore_V before a semaphore_P will block void semaphore_P(semaphore_t sem); Decrements on semaphore,