Develop a user level thread library called uthread . The thread library should c
ID: 3680530 • Letter: D
Question
Develop a user level thread library called uthread. The thread 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.
User level thread library that we develop should provide the following function
uthread_init()
//functions can be called. It initializes the uthread system.
int uthread_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 uthread_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 uthread_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 uthread_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.
2. Testing
#include
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(); }
Output:
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
3. Testing
#include
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(); }
output:
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
Answer:
file uthread.h:
#ifndef THREADS_H_INCLUDED
#define THREADS_H_INCLUDED
#include <ucontext.h>
void uthread_init();
int uthread_create(void (*func)(int), int val, int pri);
void uthread_yield();
void uthread_exit();
#endif //THREADS_H_INCLUDED
file uthread.c:
#include <ucontext.h>
#include <stdio.h>
#include <stdlib.h>
#include "uthread.h"
#include "linked.h"
#include "queue.h"
#include "util.h"
#ifndef STACK_SIZE
#define STACK_SIZE 1048576
#endif
static volatile int iD = 0;
static queue_t *queue;
static queue_t *deleted;
void make_stack(ucontext_t* context)
{
char* stack = malloc(STACK_SIZE);
CHECK_PTR(stack);
CHECK_ARG(context);
context->uc_stack.ss_flags = 0;
context->uc_stack.ss_sp = stack;
context->uc_stack.ss_size = sizeof stack;
}
ucontext_t *acquire_context()
{
ucontext_t* context = malloc(sizeof(ucontext_t));
CHECK_PTR(context);
make_stack(context);
if(getcontext(context)==-1){
die("failed to getcontext in acquire_context()");
}
context->uc_link = NULL;
if(context == NULL)
{
die("Failed to acquire context.");
}
return context;
}
int uthread_create(void (*func)(int), int val, int priority)
{
ucontext_t* oldcontext = acquire_context();
//make_stack(oldcontext);
ucontext_t* link = queue->current->context;
oldcontext->uc_link = link;
makecontext(oldcontext, (void (*)(void)) func, priority, val);
queue_push_context(queue, oldcontext);
return iD++;
}
ucontext_t* deleter_context;
linked_t* swap_node = NULL;
void delete_func()
{
while(true)
{
if (!queue_is_empty(deleted))
{
linked_t* delnode = queue_pop(deleted);
//printf("We are deleting (%d) from (%d) ", delnode->id, swap_node->id);
if (delnode->context == NULL)
{
die("null context ");
}
//delnode->context->uc_stack.ss_sp;
//free(delnode->context->uc_stack.ss_sp);
free(delnode->context);
free(delnode);
}
swapcontext(deleter_context, swap_node->context);
}
}
void create_deleter()
{
deleter_context = acquire_context();
makecontext(deleter_context, &delete_func, 0);
}
void uthread_init()
{
queue = queue_create();
deleted = queue_create();
ucontext_t *rootContext = acquire_context();
queue_push_context(queue, rootContext);
create_deleter();
}
void uthread_yield()
{
if(queue_is_empty(queue))
{
die("Yielded from nonexistent thread.");
}
linked_t *rmHead = queue_pop(queue);
queue_insert(queue, rmHead);
linked_t *newHead = queue->current;
if(newHead->context == NULL)
{
die("Yielded from null context ", newHead->id);
}
swapcontext(rmHead->context, newHead->context);
}
void uthread_exit()
{
if(queue_is_empty(queue)==true)
{
die("Thread exited when no running thread remained. ");
}
linked_t *rmHead = queue_pop(queue);
swap_node = rmHead;
swapcontext(rmHead->context, deleter_context);
queue_insert(deleted, rmHead);
linked_t* next = queue->current;
rmHead->context->uc_link = next->context;
if(queue_is_empty(queue)==true)
{
exit(0);
}
/*linked_t *peeker = queue->current;
//setcontext(peeker->context);
swapcontext(rmHead->context, peeker->context);
//die("setcontext failure in uthread_exit");
//peeker->context->uc_link = rmHead->context;
return;*/
}
file util.h:
#ifndef UTIL_H_INCLUDED
#define UTIL_H_INCLUDED
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/*
Removes trailing newlines from strings
*/
void chomp(char* string);
// Tells the compiler that this function never returns
void die(const char* msg, ...) __attribute__ ((noreturn));
#ifdef DEBUG
#define CHECK_PTR(X)
do {
if ((X) == NULL)
{
perror("malloc");
exit(1);
}
} while(0)
#else
#define CHECK_PTR(X) ;
#endif
#define CHECK_ARGS
#ifdef CHECK_ARGS
#define CHECK_ARG(X)
do {
if ((X) == NULL)
{
die("Argument "%s" to function "%s" was NULL ", #X, __FUNCTION__);
}
} while(0)
#else
#define CHECK_ARG(X) ;
#endif
#endif //UTIL_H_INCLUDED
file util.c:
#include "util.h"
/*
Removes trailing newlines from strings
*/
void chomp(char* string)
{
int len = strlen(string);
int i;
for (i = len-1; i >= 0; i -= 1)
{
if (string[i] == ' ' || string[i] == ' ')
{
string[i] = '';
}
else
{
return;
}
}
}
// Tells the compiler that this function never returns
void die(const char* msg, ...) __attribute__ ((noreturn));
void die(const char* msg, ...)
{
va_list args;
va_start(args, msg);
vfprintf(stderr, msg, args);
va_end(args);
exit(1);
}
file queue.h:
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "util.h"
#include "linked.h"
typedef struct {
linked_t* sentinel;
linked_t* current;
} queue_t;
#define SENTINEL (-1)
queue_t* queue_create();
void queue_insert(queue_t* queue, linked_t *new);
linked_t* queue_pop(queue_t* queue);
void queue_rev_print(queue_t* queue);
void queue_print(queue_t* queue);
bool queue_is_empty(queue_t* queue);
void queue_push_context(queue_t* queue, ucontext_t* context);
#endif //QUEUE_H_INCLUDED
file queue.c:
#include "queue.h"
queue_t* queue_create()
{
queue_t* result = malloc(sizeof(queue_t));
result->sentinel = malloc(sizeof(linked_t));
result->sentinel->next = result->sentinel;
result->sentinel->prev = result->sentinel;
result->sentinel->context = NULL;
result->sentinel->id = SENTINEL;
result->current = result->sentinel;
return result;
}
void queue_insert(queue_t* queue, linked_t *new)
{
CHECK_ARG(queue);
CHECK_ARG(new);
linked_t* node = queue->current->prev;
if (!node->id == SENTINEL)
{
//printf("invalid node ");
}
if (queue->current->id == SENTINEL)
{
new->next = queue->sentinel;
new->prev = queue->sentinel;
queue->sentinel->next = new;
queue->sentinel->prev = new;
queue->current = new;
}
else
{
linked_t* next = queue->sentinel->next;
next->prev = new;
new->next = next;
queue->sentinel->next = new;
new->prev = queue->sentinel;
}
}
void queue_push_context(queue_t* queue, ucontext_t* context)
{
linked_t* new = linked_create(context);
queue_insert(queue, new);
}
linked_t* queue_pop(queue_t* queue)
{
linked_t* result = queue->current;
if (result->id == SENTINEL)
{
fprintf(stderr, "Removed from empty queue ");
exit(1);
}
linked_t* prev = result->prev;
queue->current = prev;
prev->next = queue->sentinel;
return result;
}
void queue_rev_print(queue_t* queue)
{
linked_t* current = queue->sentinel;
printf("(Reverse) Sentinel -> ");
fflush(stdout);
current = current->prev;
while(current->id != SENTINEL)
{
printf("(%d) -> ", current->id);
fflush(stdout);
current = current->prev;
}
printf(" ");
}
void queue_print(queue_t* queue)
{
linked_t* current = queue->sentinel;
printf("Sentinel -> ");
fflush(stdout);
current = current->next;
while(current->id != SENTINEL)
{
printf("(%d) -> ", current->id);
fflush(stdout);
current = current->next;
}
printf(" ");
}
bool queue_is_empty(queue_t* queue)
{
return queue->current->id == SENTINEL;
}
file linked.h:
#ifndef LINKED_H_INCLUDED
#define LINKED_H_INCLUDED
#include <stdlib.h>
#include <stdbool.h>
#include <ucontext.h>
#include "util.h"
typedef struct linked {
struct linked* next;
struct linked* prev;
ucontext_t* context;
int id;
} linked_t;
linked_t* linked_create(ucontext_t* context);
#endif //LINKED_H_INCLUDED
file linked.c:
#include "linked.h"
static int glob_id = 0;
linked_t* linked_create(ucontext_t* context)
{
linked_t* list = malloc(sizeof(linked_t));
CHECK_PTR(list);
CHECK_ARG(context);
list->context = context;
list->next = NULL;
list->prev = NULL;
list->id = glob_id;
glob_id+=1;
return list;
}
file empty main.c:
#include "uthread.h"
#include "linked.h"
#include "queue.h"
#include <stdlib.h>
#include <stdio.h>
int main(){
return 0;
}
2. Testing:
file main.c:
#include "uthread.h"
#include "linked.h"
#include "queue.h"
#include <stdlib.h>
#include <stdio.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,10,1);
uthread_create(th1,20,2);
uthread_create(th2,15,1);
uthread_exit();
return 0;
}
Output:
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
Note: based on h t t p : // t e st -p roj ect-ho mew ork.go og lecod e.c o m /sv n/trun k/lab 3/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.