ECSE 427程序代做、代写Systems编程设计、c/c++语言编程调试

日期：2020-11-01 11:23

ECSE 427/COMP 310 – Operating Systems Assignment 02 – Simple Thread Scheduler

Fall 2020 (version 2) Page 1 10/18/2020

Simple User-Level Thread Scheduler

Check My Courses for Due Date

High-Level Description

In this project, you will develop a simple many-to-many user-level threading library with a simple

first-come-first-serve (FCFS) thread scheduler. The threading library will have two executors –

these are kernel-level threads that run the user-level threads. One executor is dedicated to running

compute tasks and the other executor is dedicated for input-output tasks.

The user-level threads are responsible for running tasks. The tasks are C functions. Your threading

library is expected to at least run the tasks we provide as part of this assignment. A task is run by

the scheduler until it completes or yields. The tasks we provide here do not complete (i.e., they

have while (true) in their bodies). The only way a task can stop running once it is started is by

yielding the execution. A task calls sut_yield() for yielding (i.e., pausing) its execution. A task

that is yielding is put back in the task ready queue (at the end of the queue). Once the running task

is put back in the ready queue, the task at the front of the queue is selected to run next by the

scheduler.

A newly created task is added to the end of the task ready queue. To create a task we use the

sut_create() function, which takes a C function as its sole argument. When the task gets to run

on the executor, the user supplied C function is executed.

All tasks execute in a single process. Therefore, the tasks share the process’ memory. In this simple

user-level threading system, variables follow the C scoping rules in the tasks. You can make

variables local to a task by declaring them in the C function that forms the “main” of the task. The

global variables are accessible from all tasks.

The sut_yield() pauses the execution of a thread until it is selected again by the scheduler. With

a FCFS scheduler the task being paused is put at the back of the queue. That means the task would

be picked again after running all other tasks that are ahead of it in the queue. We also have a way

of terminating a task’s execution by calling sut_exit(), which stops the execution of the current

task like sut_yield() but does not put it back into the task ready queue for further execution.

So far, we described what happens with the compute tasks. The threading library has two executors

(i.e., kernel-level threads). One is dedicated for compute tasks and is responsible for carrying out

all that is described above. The other executor is dedicated for input-output (I/O). For instance, a

task would want to send a message to outside processes or receive data from outside processes.

This is problematic because input-output can be blocking. We have a problem when a user-level

thread blocks – the whole program would stall. To prevent this problem, we use a dedicated

executor for I/O. The idea is to offload the input and output operations to the I/O executor such

that the compute executor would not block.

For instance, sut_read() would read data from an external process much like the read() you

would do on a socket. The sut_read() can stall (delay) the task until the data arrives. With userlevel

threading, stalling the task is not a good idea. We want to receive the data without stalling

the executor with the following approach. When a task issues sut_read() we send the request to

a request queue and the task itself is put in a wait queue. When the response arrives, the task is

ECSE 427/COMP 310 – Operating Systems Assignment 02 – Simple Thread Scheduler

Fall 2020 (version 2) Page 2 10/18/2020

moved from the wait queue to the task ready queue and it would get to run in a future time. We

have sut_write() to write data to the remote process. However, the write is non-blocking. To

simplify the problem, we don’t even wait for an acknowledgement of the sent data. We copy the

data to be sent to local buffer and expect the I/O executor to reliably send it to the destination.

Same way we also have sut_open() and expect the I/O executor to make the connection to the

remote process without error. Error conditions such as remote process not found is not willing to

accept connections are not handled. We assume all is good regarding the remote process and just

open the connection and move to the next statement.

Overall Architecture of the SUT Library

The simple user-level threading (SUT) library that you are developing in this assignment has the

following major components.

It has two kernel-level threads known as the executors. One of them is the compute executor (CEXEC)

and the other is the I/O executor (I-EXEC). The C-EXEC is responsible for most the

activities in the SUT library. The I-EXEC is only taking care of the I/O operations. Creating the

two kernel-level threads to run C-EXEC and I-EXEC is the first action performed while initializing

the SUT library.

The C-EXEC is directly responsible for creating tasks and launching them. Creating a task means

we need to create a task structure with the given C task-main function, stack, and the appropriate

values filled into the task structure. Once the task structure is created, it is inserted into the task

ready queue. The C-EXEC pulls the first task in the task ready queue and starts executing it. The

executing task can take three actions:

1. Execute sut_yield(): this causes the C-EXEC to take over the control. That is the user

task’s context is saved in a task control block (TCB) and we load the context of C-EXEC

and start it. We also put the task in the back of the task ready queue.

2. Execute sut_exit(): this causes the C-EXEC to take over the control like the above case.

The major difference is that TCB is not updated or the task inserted back into the task

ready queue.

3. Execute sut_read(): this causes the C-EXEC to take over the control. We save the user

task’s context in a task control block (TCB) and we load the context of C-EXEC and start

it. We put the task in the back of the wait queue.

When a task executes sut_open(), it sends a message to the I-EXEC by enqueuing the message

in the To-IO queue. The message will instruct the I-EXEC to open a connection to the specified

destination. In a subsequent statement, the task would issue sut_write() to write the data to the

destination process. We would not wait for confirmation from open or write as a way of

simplifying their implementations. The destination process we open for I/O is used by

sut_read() as well. Because we assume a single active remote process there is no need to pass a

connection handle like a file descriptor for the sut_read() or sut_write() call. We will have

a sut_close() terminate the connection we have established with the remote process.

After the SUT library is done with the initializations, it will start creating the tasks and pushing

them into the task ready queue. Once the tasks are created, the SUT will pick a task from the task

ready queue and launch it. Some tasks can be launched at runtime by user tasks by calling the

sut_create() function. The task scheduler, which is a very simple scheme – just pick the task

ECSE 427/COMP 310 – Operating Systems Assignment 02 – Simple Thread Scheduler

Fall 2020 (version 2) Page 3 10/18/2020

at the front of the queue, might find that there are no tasks to run in the task ready queue. For

instance, the only task in the task ready queue could issue a read and go into the wait queue. To

reduce the CPU utilization the C-EXEC will go take a short sleep using the nanosleep command

in Linux (a sleep of 100 microseconds is appropriate). After the sleep, the C-EXEC will check the

task ready queue again.

The I-EXEC is primarily responsible for reading the To-IO message queue and executing the

appropriate command. For instance, I-EXEC needs to open a connection to the remote process in

response to the sut_open() call. Similarly, it needs to process the sut_write() call as well.

With the sut_read() call, I-EXEC get the data and needs to put the data in the From-IO message

queue and transfer the task from the wait queue to the task ready queue. This transfer is done by

I-EXEC because the task does not need to wait any more. The data the task wanting to read has

arrived.

The sut_shutdown() call is responsible for cleanly shutting down the thread library. We need to

keep the main thread waiting for the C-EXEC and I-EXEC threads and it one of the important

functions of sut_shutdown(). In addition, you can put any termination related actions into this

function and cleanly terminate the threading library.

The SUT Library API and Usage

The SUT library will have the following API. You need to follow the given API so that testing can

be easy.

void sut_init();

bool sut_create(sut_task_f fn);

void sut_yield();

void sut_exit();

void sut_open(char *dest, int port);

void sut_write(char *buf, int size);

void sut_close();

Executor (C-EXEC)

Executor (I-EXE

C)

Task Ready

Queue

Wait

Queue

ECSE 427/COMP 310 – Operating Systems Assignment 02 – Simple Thread Scheduler

Fall 2020 (version 2) Page 4 10/18/2020

char *sut_read();

void sut_shutdown();

Context Switching and Tasks

You can use the makecontext() and swapcontext() to manage the user-level thread creation,

switching, etc. The sample code provided in the YAUThreads package illustrates the use of the

user-level context management in Linux.

Important Assumptions

Here are some important assumptions you can make in this assignment. If you want to make

additional assumptions, check with the TA-in-charge (Jason) or the professor.

• The read and write tasks are launched by the application. We assume that there is only one

outstanding read/write at any given time. With the read API provided in SUT, we can have

multiple outstanding read calls. However, processing multiple outstanding read calls can

be complicated. Therefore, we assume only one read or write call could be pending at any

given time. That also means that the wait queue for I/O can have only one task at any given

time (do we actually need a queue?).

• There are no interrupts in the user-level thread management to be implemented in this

assignment. A task that starts running only stops for the three reasons given in Section 2.

• You can use libraries for creating queues and other data structures – you don’t need to

implement them yourself! We have already given you some libraries for implementing data

structures.

Grading

Your assignment will be evaluated in stages.

1. Only simple computing tasks. We spawn several simple tasks that just print messages and

yield. You need to get this working to demonstrate that you can create tasks and they can

cooperatively switch among them.

2. Tasks that spawn other tasks. In this case, we have some tasks that spawn more tasks. In

total a bounded (not more than 15 tasks) will be created. You need to demonstrate that you

can have tasks creating other tasks at runtime.

3. Tasks that have I/O in them. We have some tasks write to a remote server. We don’t mix

write and read, just one type – write from the tasks to an external server.

4. Tasks that have I/O again. This time the tasks have read in them.