I need to create the user level thread library called threadlib . The library sh
ID: 3681743 • Letter: I
Question
I need to create the user level thread library called threadlib. The library should create user level threads, map the user level threads to a kernel thread following the many to one mapping model, schedule the mapping based on the user-level thread priority numbers (i.e., when the kernel thread becomes available, the user thread with highest priority should be mapped to it; when there are multiple highest priority user threads, the thread at the head of the priority ready queue should be selected for mapping), and support inter thread message passing.
/************** Here are the function requirment for this threadlib ********************/
thread_set_init()
/* functions can be called. It initializes the uthread system. */
int thread_create(void (* func)( ), int priority)
/* The calling thread requests the thread library to create a new user level thread that runs the function func(), which is specified as the first argument of this function. A context of this new user thread should be properly created and stored on the priority ready queue, based on the thread priority number, which is specified as the second argument of this function.The ready queue should be a priority queue that sorts all ready threads based on their priorities. The smaller is a priority number, the higher is the priority. */
void thread_yield()
/* The calling thread requests to yield the kernel thread to another user level thread with the same or higher priority. If each ready thread has lower priority than this calling thread, the calling thread will continue itsrunning; otherwise, the kernel thread is yielded to a ready thread with the highest priority. */
void uthread_exit()
/* This function is called when the calling user level thread terminates its execution. In respond to this call, if no ready user thread in the system, the whole process terminates; otherwise, a ready user thread with the highest priority should be mapped to the kernel thread to run. */
int thread_send(int tid, void *content, int size)
/* The calling thread requests to send a message pointed to by argument content to the thread with ID tid. The third argument, size, specifies the size of the message. If there is no user thread with ID tid, the function returns 1; otherwise 0 is returned. Note that, this sending operation is non-blocking. */
int thread_recv(int tid, void **content)
/* The calling thread requests to retrieve a message sent by a thread of IDtid. If there is no message from tid available, the calling thread is blocked (i.e., it should be put into a waiting queue to wait to be moved back to the ready queue until the thread with ID tid sends a message to it) When returning from this function, the starting address of the retrieved message should be saved in *content, which is a variable of type void*,and the function returns an integer which is the size of the retrieved message. In the case of failure, the function returns 1. Note that, once a message has been retrieved, it is consumed and cannot be retrieved again. */
/*********************** Here are the Test Code ***********************************/
#include <threadlib.h>
void th0 (){
int i;
for(i=0;i<3;i++){
printf("This is thread 0. ");
sleep(1);
uthread_yield();
}
printf("Thread 0 exit. ");
uthread_exit();
}
void th1 (){
int i;
for(i=0;i<3;i++){
printf("This is thread 1. ");
sleep(1);
uthread_yield();
}
printf("Thread 1 exit. ");
uthread_exit();
}
void th2 (){
int i;
for(i=0;i<3;i++){
printf("This is thread 2. ");
sleep(1);
uthread_yield();
}
printf("Thread 2 exit. ");
uthread_exit();
}
int main(){
uthread_init();
uthread_create(th0,1);
uthread_create(th1,2);
uthread_create(th2,1);
uthread_exit(); }
/*********************** Here is what the output should look like ***********************************/
This is thread 0
This is thread 2
This is thread 0
This is thread 2
This is thread 0
This is thread 2
Thread 0 exits
Thread 2 exits
This is thread 1
This is thread 1
This is thread 1
Thread 1 exits
/*********************** Here are the send and recv message test code ***********************************/
#include <threadlib.h>
void th0 () {
int i;
for(i=0;i<3;i++){
if(i==0) continue;
printf("This is thread 0. ");
char msg[256];
sprintf(msg, "greeting from %d to %d", 0, i);
uthread_send(i,msg,256);
printf("Thread %d has sent to Thread %d: %s ", 0, i, msg);
char *rcv_msg;
uthread_recv(i,(void **)&rcv_msg);
printf("Thread %d receives from Thread %d: %s ", 0, i, rcv_msg);
}
printf("Thread 0 exit. ");
uthread_exit();
}
void th1 () {
int i;
for(i=0;i<3;i++){
if(i==0) continue;
printf("This is thread 1. ");
char msg[256];
sprintf(msg, "greeting from %d to %d", 1, i);
uthread_send(i,msg,256);
printf("Thread %d has sent to Thread %d: %s ", 1, i, msg);
char *rcv_msg;
uthread_recv(i,(void **)&rcv_msg);
printf("Thread %d receives from Thread %d: %s ", 1, i, rcv_msg);
}
printf("Thread 1 exit. ");
uthread_exit();
}
void th2 () {
int i;
for(i=0;i<3;i++){
if(i==0) continue;
printf("This is thread 2. ");
char msg[256];
sprintf(msg, "greeting from %d to %d", 2, i);
uthread_send(i,msg,256);
printf("Thread %d has sent to Thread %d: %s ", 2, i, msg);
char *rcv_msg;
uthread_recv(i,(void **)&rcv_msg);
printf("Thread %d receives from Thread %d: %s ", 2, i, rcv_msg);
}
printf("Thread 2 exit. ");
uthread_exit();
}
int main(){
uthread_init();
uthread_create(th0,1);
uthread_create(th1,1);
uthread_create(th2,1);
uthread_exit();
}
/*********************** Here is what the output should look like ***********************************/
This is thread 0.
Thread 0 has sent to Thread 1: greeting from 0 to 1
This is thread1.
Thread 1 has sent to Thread 0: greeting from 1 to 0
Thread 1 receives from Thread 0: greeting from 0 to 1
This is thread 1.
Thread 1 has sent to Thread 2: greeting from 1 to 2
This is thread 2.
Thread 2 has sent to Thread 0: greeting from 2 to 0
Thread 0 receives from Thread 1: greeting from 1 to 0
This is thread 0.
Thread 0 has sent to Thread 2: greeting from 0 to 2
Thread 0 receives from Thread 2: greeting from 2 to 0
Thread 0 exit.
Thread 2 receives from Thread 0: greeting from 0 to 2
This is thread 2.
Thread 2 has sent to Thread 1: greeting from 2 to 1
Thread 2 receives from Thread 1: greeting from 1 to 2
Thread 2 exit.
Thread 1 receives from Thread 2: greeting from 2 to 1
Thread 1 exit.
Explanation / Answer
main.c
#include <stdio.h>
#include "uthread.h"
void th0() {
int i;
for (i = 0; i < 3; i++) {
if (i == 0) {
continue;
}
printf("This is thread 0. ");
char msg[256];
sprintf(msg, "greeting from %d to %d", 0, i);
uthread_send(i, msg, 256);
printf("Thread %d has sent to Thread %d: %s ", 0, i, msg);
char *rcv_msg;
uthread_recv(i, (void **) &rcv_msg);
printf("Thread %d receives from Thread %d: %s ", 0, i, rcv_msg);
}
printf("Thread 0 exit. ");
uthread_exit();
}
void th1() {
int i;
for (i = 0; i < 3; i++) {
if (i == 1) {
continue;
}
printf("This is thread 1. ");
char msg[256];
sprintf(msg, "greeting from %d to %d", 1, i);
uthread_send(i, msg, 256);
printf("Thread %d has sent to Thread %d: %s ", 1, i, msg);
char *rcv_msg;
uthread_recv(i, (void **) &rcv_msg);
printf("Thread %d receives from Thread %d: %s ", 1, i, rcv_msg);
}
printf("Thread 1 exit. ");
uthread_exit();
}
void th2() {
int i;
for (i = 0; i < 3; i++) {
if (i == 2) {
continue;
}
printf("This is thread 2. ");
char msg[256];
sprintf(msg, "greeting from %d to %d", 2, i);
uthread_send(i, msg, 256);
printf("Thread %d has sent to Thread %d: %s ", 2, i, msg);
char *rcv_msg;
uthread_recv(i, (void **) &rcv_msg);
printf("Thread %d receives from Thread %d: %s ", 2, i, rcv_msg);
}
printf("Thread 2 exit. ");
uthread_exit();
}
int main() {
uthread_init();
uthread_create(th0, 1);
uthread_create(th1, 1);
uthread_create(th2, 1);
uthread_exit();
}
uthread.c
#include <sched.h>
#include <stdlib.h>
#include <ucontext.h>
#include <string.h>
#include "uthread.h"
// define a queue of user thread records
typedef struct thread_info_s {
ucontext_t *context;
struct thread_info_s *next;
int priority;
int tid;
} thread_info;
thread_info *head, *current_thread;
thread_info *tid_assigned[100];
// get the next tid to be assigned
// returns -1 if all 100 spots are used up
int next_tid() {
int i;
for (i = 0; i < 100; i++) {
if (tid_assigned[i] == NULL) {
return i;
}
}
return -1;
}
void enqueue(thread_info *thread) {
thread_info *cur_thread = head;
thread_info *last_thread = NULL;
while (cur_thread != NULL && thread->priority <= cur_thread->priority) {
last_thread = cur_thread;
cur_thread = cur_thread->next;
}
if (last_thread != NULL) {
last_thread->next = thread;
} else {
head = thread;
}
}
thread_info *dequeue() {
thread_info *to_return = head;
if (head != NULL && head->next != NULL) {
head = head->next;
}
return to_return;
}
// return the tid of the new thread, or -1 if uthread is a capacity
int uthread_create(void (*func)(), int priority) {
// check if we can run another thread
int tid = next_tid();
if (tid == -1) {
return tid;
}
//construct a thread record
thread_info *thread;
thread = (thread_info *) malloc(sizeof(thread_info));
thread->tid = tid;
//initialize the context structure
thread->context = (ucontext_t *) malloc(sizeof(ucontext_t));
getcontext(thread->context);
thread->context->uc_stack.ss_sp = malloc(16384);
thread->context->uc_stack.ss_size = 16384;
thread->next = NULL;
thread->priority = priority;
//make the context for a thread running func
makecontext(thread->context, func, 0);
// save the thread record and add it to the queue
tid_assigned[tid] = thread;
enqueue(thread);
return tid;
}
void uthread_exit() {
if (head == NULL) {
//all threads are finished, so we can completely exit
exit(0);
}
// free up the thread's tid
if (current_thread != NULL) {
tid_assigned[current_thread->tid] = NULL;
}
// get the next thread and run
current_thread = dequeue();
setcontext(current_thread->context);
}
void uthread_yield() {
if (head == NULL) {
// no other threads to yield to; resume execution
return;
}
// save the current thread's information
thread_info *old_thread = (thread_info *) malloc(sizeof(thread_info));
old_thread->context = (ucontext_t *) malloc(sizeof(ucontext_t));
enqueue(old_thread);
// fetch and run the thread at the front of the ready queue
current_thread = dequeue();
swapcontext(old_thread->context, current_thread->context);
}
typedef struct message_s {
void *content;
int content_size;
struct message_s *next;
} message;
message *messages [100][100];
void save_message(int sender, int destination, void *content, int size) {
// make a copy of the message content
void *content_copy = malloc(size);
memcpy(content_copy, content, size);
// initialize the message struct
message *new_message = (message*) malloc(sizeof (message));
new_message->content = content_copy;
new_message->content_size = size;
new_message->next = NULL;
message *cur_message = messages[destination][sender];
if (cur_message == NULL) {
// if there are no current messages for this recipient, start the
// linked list with this message
messages[destination][sender] = new_message;
return;
}
// otherwise, iterate to the end of the list, then add our new message
while (cur_message->next != NULL) {
cur_message = cur_message->next;
}
cur_message->next = new_message;
}
int uthread_send(int tid, void *content, int size) {
// check if tid is currently assigned to a thread
if (tid_assigned[tid] == NULL) {
return -1;
}
save_message(current_thread->tid, tid, content, size);
return 0;
}
int uthread_recv(int tid, void **content) {
return 0;
}
void uthread_init() {
head = NULL;
current_thread = NULL;
int i, j;
for (i = 0; i < 100; i++) {
for (j = 0; j < 100; j++) {
messages[i][j] = NULL;
}
}
for (i = 0; i < 100; i++) {
tid_assigned[i] = NULL;
}
}
uthread.h
#ifndef UTHREAD_H_
#define UTHREAD_H_
void uthread_init();
int uthread_create(void (* func)( ), int priority);
void uthread_exit();
void uthread_yield();
int uthread_send(int tid, void *content, int size);
int uthread_recv(int tid, void **content);
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.