Computer Science 475 Spring 1994 - Assignment 1 Design Document Due Date: 3 February 1994 Assignment Due Date: 10 February 1994 The first assignment will require a design and implementation of the following: * thread scheduler * thread synchronization functions(semaphores) * buffer management functions In order to do this you will need to use the thread functions and libraries available in the Sun workstation cluster on the second floor of the IACC. Development is possible on other platforms such as Linux, FreeBSD, SunOS 4.03D(Plains), NeXTstep (and any other system supporting threads but it is important to understand that the final product must function properly on the Solaris platform. Man pages are available in section 3 of the manual. It is also not required (although highly recommended and encouraged) that this assignment be written in C. In reality any language available on the Solaris platform supporting the C calling convention should allow you to get the job done. If you wish to use another language please inform me ASAP so that I can brush up on whatever language you have chosen. (hint: don't ponder this idea too long - C is by far the best choice - trust me :-)) In your system you will need a master thread which will act as a parent thread for all the other threads. This thread will be responsible for the management (creation, destruction, readying, etc.) of the various user thread groups used in testing this assignment. These thread groups will include any test suites which you design (strongly recommended and encouraged) as well as the ones provided sometime on the Saturday prior to the due date of this assignment. The provided thread groups will be in object form and you will not be allowed access to the source code. Consequently it is of fundamental importance that you stick to the specification of this assignment closely with respect to calls to start these thread groups as well as any specified function as these groups will obviously need to call the specified functions in order to test them. A large portion of the result of your efforts will depend on whether the provided thread groups run correctly in your OS. Scheduler The thread scheduler will be a high priority thread that uses a ready list and a blocked list of threads to implement a round-robin policy. You will also need five additional functions, t_create(), t_destroy(), t_block(), t_myid, and t_ready(). Their definitions are as follows(in C): TID t_create(void *f) - returns the TID of a new, blocked thread which runs the function f, and -1 on failure int t_destroy(void) - destroys the current thread, returning 0 on success and -1 on failure int t_block(void) - blocks the current thread, returning 0 on success and -1 on failure int t_ready(TID t) - makes the thread with tid t ready, returning 0 on success and -1 on failure TID t_myid(void) - returns the tid of the calling thread and -1 on failure The type TID should be an integer ("man typedef" for those of you who are not sure what I am talking about). The entry point for the scheduler thread will be a function which should be called something like scheduler(). The time quantum you decide on for the scheduler should be small enough so that it doesn't deteriorate to a FCFS scheduling algorithm, and should be large enough so that threads run for a time greater than the decision time necessary for scheduling threads. You are free to implement this scheduler with whatever methods you decide are best. However, YOU MUST HAVE COMPLETE CONTROL OVER WHAT IS HAPPENING!! Do not rely on the system to manage your threads for you. It is nearly guaranteed that such an approach will result in a runaway train effect. This train will crash during grading :-) You must also explain and justify your approach thoroughly in the design document. Synchronization For the synchronization functions you well need s_create(), s_destroy(), s_open(), s_close(), s_signal(), and s_wait(). Their definitions are as follows (in C): int s_create(int sem_name, int initial_value) - an atomic operation which creates a semaphore with name sem_name and count initial_value, returning 0 on success and -1 on failure int s_destroy(int sem_name) - an atomic operation which destroys the semaphore with the name sem_name and returns 0 on success and -1 on failure SID s_open(int sem_name) - an atomic operation which opens the semaphore with the name sem_name, and returns the SID which identifies the semaphore, thus binding the SID to the semaphore name, -1 should be returned on failure. int s_close(SID sem_ID) - an atomic operation which closes the semaphore with SID sem_ID, returns 0 on success and -1 on failure int s_signal(SID sem_ID) - an atomic operation which signals the semaphore with SID sem_ID, releasing a waiting thread, if any exist. Returns 0 on success and -1 on failure (UP operation) int s_wait(SID sem_ID) - an atomic operation that waits on a semaphore with SID sem_ID and returns 0 on success and -1 on failure (DOWN operation) SID is an integer indentifier that your synchronization functions use to identify the semaphore (see typedef again). Duplicate semaphore names are not allowed but you are free to handle this situation as you best see fit. At the time a semaphore is created it will not be in use by any thread. Be careful not to use s_destroy to destroy a semaphore that is in use. You are allowed (but discouraged) to use the built in system semaphores and monitors to implement critical sections but you must handle your OS' user semaphores in your implementation. Buffer Management The buffer management functions are the primitive pieces of the Inter-Thread Communication functions in the next assignment. There are two required functions, b_get() and b_release. BUFFER *b_get(void) - returns a pointer to a fully usable 64 byte buffer if available, will block and wait for a buffer to become available if no buffers are available at the time of its call int b_release(BUFFER *buffer) - releases the buffer back to the buffer pool thus making it available to other threads, returns 0 on success and -1 on failure The buffer type should be a pointer to a buffer so the user thread groups can use them, and the pointer should point to memory that is fully usable by the caller. These two functions are intended to manage a fixed size pool of buffers available to any thread. No more than 20 buffers should be needed in the buffer pool. Utility Function char my_malloc(size_t s) - this function accepts one parameter, s, that is the size of the memory request. It returns a pointer to a fully useable block of memory that can be used as necessary. This is an atomic function. This is the only function in which it will be permissible to make calls to malloc. It is also recommended that you do your own garbage collection upon shutdown of your OS so that Solaris does not have to do it for you.