This is user level thread library I have created, a kernel thread following many
ID: 3680776 • Letter: T
Question
This is user level thread library I have created, a kernel thread following many to one mapping, schedule the mapping based on the user level thread priority number.
/* Here is user level thread library*/
#include <stdio.h>
#include <stdlib.h>
#include <ucontext.h>
#define STACK_SIZE 16384
typedef struct {
int priority;
void *data;
} node_t;
typedef struct {
node_t *nodes;
int len;
int size;
} heap_t;
void push (heap_t *h, int priority, void *data) {
if (h->len + 1 >= h->size) {
h->size = h->size ? h->size * 2 : 4;
h->nodes = (node_t *) malloc( h->size * sizeof(node_t));
}
int i = h->len + 1;
int j = i / 2;
while (i > 1 && h->nodes[j].priority > priority) {
h->nodes[i] = h->nodes[j];
i = j;
j = j / 2;
}
h->nodes[i].priority = priority;
h->nodes[i].data = data;
h->len++;
}
void *pop (heap_t *h) {
int i, j, k;
if (!h->len) {
return NULL;
}
void *data = h->nodes[1].data;
h->nodes[1] = h->nodes[h->len];
h->len--;
i = 1;
while (1) {
k = i;
j = 2 * i;
if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) {
k = j;
}
if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) {
k = j + 1;
}
if (k == i) {
break;
}
h->nodes[i] = h->nodes[k];
i = k;
}
h->nodes[i] = h->nodes[h->len + 1];
return data;
}
ucontext_t *current = NULL;
heap_t *h = NULL;
void system_init() {
h = calloc(1, sizeof (heap_t));
current = (ucontext_t *) malloc(sizeof(ucontext_t));
if (current == NULL) return;
getcontext(current);
}
int uthread_create(void (*func)(void), int priority) {
ucontext_t *context;
context = (ucontext_t *) malloc(sizeof(ucontext_t));
if (context == NULL) return -1;
getcontext(context);
/* Create our stack for the context */
context->uc_stack.ss_sp = (char *) malloc(sizeof(char) * STACK_SIZE);
context->uc_stack.ss_size = STACK_SIZE;
makecontext(context, func, 0);
push(h, priority, context);
return 0;
}
int uthread_yield() {
ucontext_t *previous;
/* Error checking */
if (h == NULL) return -1;
if (h->size <= 0) return 0;
/* Dequeue before we add the next one to it */
previous = current;
current = pop(h);
push(h, 1, previous);
return swapcontext(previous, current);
}
void uthread_exit() {
ucontext_t *previous;
if (h == NULL) return;
/* Get the next context and swap it */
previous = current;
current = pop(h);
swapcontext(previous, current);
}
//Here is what I don't know how to do ??
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.
/* Testing*/
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
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.