{"id":61456,"date":"2022-05-16T01:35:10","date_gmt":"2022-05-16T01:35:10","guid":{"rendered":"https:\/\/assignmenttutors.net\/blog\/os-scheduling-2-computer-science-homework-help\/"},"modified":"2022-05-16T01:35:10","modified_gmt":"2022-05-16T01:35:10","slug":"os-scheduling-2-computer-science-homework-help","status":"publish","type":"post","link":"https:\/\/assignmenttutors.net\/blog\/os-scheduling-2-computer-science-homework-help\/","title":{"rendered":"Os scheduling 2 | Computer Science homework help"},"content":{"rendered":"
\n

SMP4: Thread Scheduler<\/p>\n

======================<\/p>\n

INSTRUCTIONS<\/p>\n

============<\/p>\n

1. OVERVIEW<\/p>\n

===========<\/p>\n

In this MP, you will write a user-mode thread scheduler. \u00a0The basic purpose<\/p>\n

of a scheduler is to multiplex use of the computer across several threads<\/p>\n

of execution. \u00a0This MP deals with two different scheduling policies: FIFO<\/p>\n

and Round Robin. \u00a0You will implement both, for use in a simple cooperative<\/p>\n

multi-threading system. \u00a0Along the way, you’ll also learn about implementing<\/p>\n

object-oriented constructs in low-level procedural languages like C.<\/p>\n

This assignment consists of implementing the core functionality of the<\/p>\n

scheduler (Step 4) and answering 10 questions (Step 5). \u00a0Code for<\/p>\n

Step 4 goes in sched_impl.c and sched_impl.h.<\/p>\n

2. THEORY OF OPERATION<\/p>\n

======================<\/p>\n

The given code in the MP defines the skeleton of a scheduler together with a<\/p>\n

parameterized dummy workload. \u00a0The idea is when you run the MP, you specify<\/p>\n

a scheduling policy, scheduler queue size, some number of worker threads to<\/p>\n

create, and, optionally, the number of iterations for which the worker<\/p>\n

threads should run. \u00a0The basic code that parses command line arguments and<\/p>\n

creates these worker threads is provided in the MP, but you must implement<\/p>\n

the core synchronization and scheduling operations.<\/p>\n

As provided, the MP only includes the “dummy” scheduling algorithm, which<\/p>\n

doesn’t even try to do anything. \u00a0You can run it like this:<\/p>\n

\u00a0\u00a0make<\/p>\n

\u00a0\u00a0.\/scheduler -dummy 0 N \u00a0\u00a0# where N is some number of worker threads<\/p>\n

All threads run right away regardless of the queue size (even zero!), and<\/p>\n

are scheduled by the operating system. \u00a0The goal of this MP is to create<\/p>\n

scheduler implementations which are a bit more controlled and predictable.<\/p>\n

For example, once you have completed the MP, the following should work:<\/p>\n

\u00a0\u00a0.\/scheduler -fifo 1 2 3<\/p>\n

\u00a0\u00a0Main: running 2 workers on 1 queue_size for 3 iterations<\/p>\n

\u00a0\u00a0Main: detaching worker thread 3075984304<\/p>\n

\u00a0\u00a0Main: detaching worker thread 3065494448<\/p>\n

\u00a0\u00a0Main: waiting for scheduler 3086474160<\/p>\n

\u00a0\u00a0Thread 3075984304: in scheduler queue<\/p>\n

\u00a0\u00a0Thread 3075984304: loop 0<\/p>\n

\u00a0\u00a0Thread 3075984304: loop 1<\/p>\n

\u00a0\u00a0Thread 3075984304: loop 2<\/p>\n

\u00a0\u00a0Thread 3075984304: exiting<\/p>\n

\u00a0\u00a0Thread 3065494448: in scheduler queue<\/p>\n

\u00a0\u00a0Thread 3065494448: loop 0<\/p>\n

\u00a0\u00a0Thread 3065494448: loop 1<\/p>\n

\u00a0\u00a0Thread 3065494448: loop 2<\/p>\n

\u00a0\u00a0Thread 3065494448: exiting<\/p>\n

\u00a0\u00a0Scheduler: done!<\/p>\n

The command line options used above specify:<\/p>\n

\u00a0\u00a0-fifo Use FIFO scheduling policy<\/p>\n

\u00a0\u00a01 One thread can be in the scheduler queue at a time<\/p>\n

\u00a0\u00a02 Create 2 worker threads<\/p>\n

\u00a0\u00a03 Each thread runs for 3 time slices<\/p>\n

Here’s another example:<\/p>\n

\u00a0\u00a0.\/scheduler -rr 10 2 3<\/p>\n

\u00a0\u00a0Main: running 2 workers on 10 queue_size for 3 iterations<\/p>\n

\u00a0\u00a0Main: detaching worker thread 3075828656<\/p>\n

\u00a0\u00a0Main: detaching worker thread 3065338800<\/p>\n

\u00a0\u00a0Main: waiting for scheduler 3086318512<\/p>\n

\u00a0\u00a0Thread 3075828656: in scheduler queue<\/p>\n

\u00a0\u00a0Thread 3065338800: in scheduler queue<\/p>\n

\u00a0\u00a0Thread 3075828656: loop 0<\/p>\n

\u00a0\u00a0Thread 3065338800: loop 0<\/p>\n

\u00a0\u00a0Thread 3075828656: loop 1<\/p>\n

\u00a0\u00a0Thread 3065338800: loop 1<\/p>\n

\u00a0\u00a0Thread 3075828656: loop 2<\/p>\n

\u00a0\u00a0Thread 3065338800: loop 2<\/p>\n

\u00a0\u00a0Thread 3075828656: exiting<\/p>\n

\u00a0\u00a0Thread 3065338800: exiting<\/p>\n

\u00a0\u00a0Scheduler: done!<\/p>\n

The command line options used above specify:<\/p>\n

\u00a0\u00a0-rr Use Round Robin scheduling policy<\/p>\n

\u00a0\u00a010 \u00a0Ten threads can be in the scheduler queue at a time<\/p>\n

\u00a0\u00a02 Create 2 worker threads<\/p>\n

\u00a0\u00a03 Each thread runs for 3 time slices<\/p>\n

Things to observe:<\/p>\n

In both examples, the worker threads are created at the beginning of<\/p>\n

execution. \u00a0But in the case with queue size 1, one of the threads has to<\/p>\n

wait until the other thread exits before it can enter the scheduler queue<\/p>\n

(the “in scheduler queue” messages). \u00a0Whereas in the case with queue size<\/p>\n

10, both threads enter the scheduler queue immediately.<\/p>\n

The FIFO policy would actually have basically the same behavior even with a<\/p>\n

larger queue size; the waiting worker threads would simply be admitted to<\/p>\n

the queue earlier.<\/p>\n

The Round Robin scheduling policy alternates between executing the two<\/p>\n

available threads, until they run out of work to do.<\/p>\n

3. FILE LAYOUT<\/p>\n

==============<\/p>\n

The MP distribution consists of the following source files:<\/p>\n

scheduler.c<\/p>\n

\u00a0\u00a0Includes the skeleton of a scheduler (sched_proc()) and a<\/p>\n

\u00a0\u00a0parameterized dummy workload (worker_proc()). \u00a0The main() function<\/p>\n

\u00a0\u00a0accepts several parameters specifying the test workload (see<\/p>\n

\u00a0\u00a0description below). \u00a0The scheduler relies on a scheduler<\/p>\n

\u00a0\u00a0implementation (sched_impl_t) to implement the specifics of its<\/p>\n

\u00a0\u00a0scheduling policy (to be provided by you in sched_impl.[hc])<\/p>\n

scheduler.h<\/p>\n

\u00a0\u00a0Describes the interface to which your scheduler implementation must<\/p>\n

\u00a0\u00a0adhere. \u00a0The structures containing function pointers are similar to<\/p>\n

\u00a0\u00a0Java interfaces or C++ pure virtual base classes. \u00a0This file<\/p>\n

\u00a0\u00a0declares that you must define two sched_impl_t structures,<\/p>\n

\u00a0\u00a0sched_fifo and sched_rr in another file (sched_impl.c).<\/p>\n

dummy_impl.c<\/p>\n

\u00a0\u00a0Implements the dummy scheduling algorithm, which just lets the OS<\/p>\n

\u00a0\u00a0schedule all threads, regardless of queue size.<\/p>\n

sched_impl.h \u00a0(define your data structures here)<\/p>\n

\u00a0\u00a0This is where you will define the data structures stored per<\/p>\n

\u00a0\u00a0scheduler instance (struct sched_queue) and per worker thread<\/p>\n

\u00a0\u00a0(struct thread_info). \u00a0This will likely include synchronization<\/p>\n

\u00a0\u00a0constructs like semaphores and mutexes, and a list of threads<\/p>\n

\u00a0\u00a0available to be scheduled.<\/p>\n

sched_impl.c \u00a0(implement your code here)<\/p>\n

\u00a0\u00a0This is where you will define the functions implementing the core<\/p>\n

\u00a0\u00a0behavior of the scheduler, including the FIFO and Round Robin<\/p>\n

\u00a0\u00a0scheduling policies. \u00a0The only way functions defined in this file<\/p>\n

\u00a0\u00a0are made available to the main program (scheduler.c) is by placing<\/p>\n

\u00a0\u00a0function pointers in the sched_impl_t structures sched_fifo and<\/p>\n

\u00a0\u00a0sched_rr.<\/p>\n

list.h<\/p>\n

\u00a0\u00a0Defines the basic operations on a bidirectional linked list data<\/p>\n

\u00a0\u00a0structure. \u00a0The elements of the list, of type list_elem_t, include<\/p>\n

\u00a0\u00a0a void *datum where you can store pointers to whatever kind of<\/p>\n

\u00a0\u00a0data you like. \u00a0You don’t have to use this linked list library,<\/p>\n

\u00a0\u00a0but it will probably come in handy.<\/p>\n

list.c<\/p>\n

\u00a0\u00a0Implements the linked list operations.<\/p>\n

smp4_tests.c<\/p>\n

testrunner.c<\/p>\n

testrunner.h<\/p>\n

\u00a0\u00a0Test harness, defines test cases for checking your MP solution.<\/p>\n

Please take a look at the source files and familiarize yourself with how<\/p>\n

they work. \u00a0Think about how structures containing function pointers compare<\/p>\n

to classes and virtual methods in C++. \u00a0If you’d like to learn more, read<\/p>\n

about the virtual function table in C++. \u00a0The struct containing function<\/p>\n

pointers technique employed in this MP is also used by C GUI libraries like<\/p>\n

GTK+ and to define the operations of loadable modules, such as file systems,<\/p>\n

within the Linux kernel.<\/p>\n

4. PROGRAMMING<\/p>\n

==============<\/p>\n

Now you’re ready to implement the core of the scheduler, including the FIFO<\/p>\n

and Round Robin scheduling algorithms. \u00a0For this purpose, you should only<\/p>\n

modify sched_impl.h and sched_impl.c. \u00a0Please see scheduler.h for the<\/p>\n

descriptions of what functions you must implement. \u00a0You are free to put<\/p>\n

whatever you want in the thread_info and sched_queue structures. \u00a0Note that<\/p>\n

the only way that the functions you implement are made available to the main<\/p>\n

program is through the sched_impl_t structures sched_fifo and sched_rr. \u00a0See<\/p>\n

dummy_impl.c for a completed example of how to fill in a sched_impl_t.<\/p>\n

Suggested approach:<\/p>\n

4.1 Create stub versions of all of the functions you will need to implement<\/p>\n

\u00a0\u00a0\u00a0\u00a0in sched_impl.c, and statically initialize sched_fifo and sched_rr.<\/p>\n

4.2 Figure out how you will implement the scheduler queue, add the<\/p>\n

\u00a0\u00a0\u00a0\u00a0appropriate fields to struct sched_queue, and fill in the appropriate<\/p>\n

\u00a0\u00a0\u00a0\u00a0queue-related operations in the functions you created in (4.1).<\/p>\n

\u00a0\u00a0\u00a0\u00a0Remember that we provide a doubly-linked list in list.[hc].<\/p>\n

4.3 Implement scheduler queue admission control, so that only the requested<\/p>\n

\u00a0\u00a0\u00a0\u00a0number of threads can be in the scheduler queue at once. \u00a0Create the<\/p>\n

\u00a0\u00a0\u00a0\u00a0appropriate synchronization constructs to prevent threads not in the<\/p>\n

\u00a0\u00a0\u00a0\u00a0queue from executing (look at the implementation of worker threads in<\/p>\n

\u00a0\u00a0\u00a0\u00a0scheduler.c:worker_proc()).<\/p>\n

4.4 Implement the queue operations for selecting the next thread to execute.<\/p>\n

\u00a0\u00a0\u00a0\u00a0This will be different for FIFO vs. Round Robin scheduling.<\/p>\n

4.5 Add in synchronization constructs to make sure only the selected thread<\/p>\n

\u00a0\u00a0\u00a0\u00a0executes at any given time.<\/p>\n

4.6 Fill in any gaps that might remain.<\/p>\n

When you think you’re done, you can test your program using the command<\/p>\n

“make test”. \u00a0For more thorough testing, the fifo_var and rr_var tests<\/p>\n

accept queue_size, num_workers, and num_iterations arguments just like the<\/p>\n

main program (but <num_iterations> is mandatory for the test case):<\/p>\n

\u00a0\u00a0.\/scheduler -test fifo_var <queue_size> <num_workers> <num_iterations><\/p>\n

\u00a0\u00a0.\/scheduler -test rr_var \u00a0\u00a0<queue_size> <num_workers> <num_iterations><\/p>\n

5. QUESTIONS<\/p>\n

============<\/p>\n

Q 1 \u00a0What are some pros and cons of using the struct of function pointers<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0approach as we did in the MP to link different modules? \u00a0Does it<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0significantly affect performance? \u00a0Give some examples of when you would<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0and wouldn’t use this approach, and why.<\/p>\n

\t\u00a0<\/p>\n

\t The pros and cons are roughly the same. We get some overhead in calling\u00a0<\/p>\n

\t function pointers, but it can open the door to polymorphic classes.<\/p>\n

\t No it does not significantly affect the performance. We will use it\u00a0<\/p>\n

\t when we are interested in polymarphic classes, otherwise we don’t want to use it.<\/p>\n

Q 2 \u00a0Briefly describe the synchronization constructs you needed to implement<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0this MP–i.e., how you mediated admission of threads to the scheduler<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0queue and how you made sure only the scheduled thread would run at any<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0given time.<\/p>\n

\t\u00a0<\/p>\n

\t I used synchronous threading to make sure that everythread is executing at its given time.<\/p>\n

Q 3 \u00a0Why is the dummy scheduling implementation provided potentially<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0unsafe (i.e. could result in invalid memory references)? \u00a0How does<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0your implementation avoid this problem?<\/p>\n

\t\u00a0<\/p>\n

\t Yes, it is resulting in invalid memory references. My implementation\u00a0<\/p>\n

\t is totally dynamic and allocating memories according to the command line arguments<\/p>\n

\t so there is no chance of invalid references.<\/p>\n

Q 4 \u00a0When using the FIFO or Round Robin scheduling algorithm, can<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0sched_proc() ever “miss” any threads and exit early before all threads<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0have been scheduled and run to completion? \u00a0If yes, give an example; if<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0no, explain why not.<\/p>\n

\t\u00a0<\/p>\n

\t No, it won’t exit without completing all threads. Because all threads are joined\u00a0<\/p>\n

\t and program will execute all the threads before exiting.<\/p>\n

Q 5 \u00a0Why are the three variables in scheduler.h declared ‘extern’? \u00a0What<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0would happen if they were not declared ‘extern’? \u00a0What would happen<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0if they were not declared without the ‘extern’ in any file?<\/p>\n

\t Because we want to retain their values for complete execution,\u00a0<\/p>\n

\t and we want to access those variables\u00a0<\/p>\n

\t anywhere in the program with the same value everywhere.<\/p>\n

\t\u00a0<\/p>\n

Q 6 \u00a0Describe the behavior of exit_error() function in scheduler.c. \u00a0Why<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0does exit_error() not use errno?<\/p>\n

\t\u00a0<\/p>\n

\t It will just print the error statement along with error_num passed as\u00a0<\/p>\n

\t parameter and exits the program.<\/p>\n

Q 7 \u00a0Does it matter whether the call to sched_ops->wait_for_queue(queue) in<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0sched_proc() actually does anything? \u00a0How would it affect correctness<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0if it just returned right away? \u00a0How about performance?<\/p>\n

\t\u00a0<\/p>\n

\t yes, it matters. If it returns right away, then it will be conflicting with\u00a0<\/p>\n

\t some other thread, so it will harm the correctness.<\/p>\n

Q 8 \u00a0Explain how worker_proc() is able to call the appropriate<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0implementation of wait_for_cpu() corresponding to the scheduling policy<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0selected by the user on the command line. \u00a0Start from main() and<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0briefly explain each step along the way.<\/p>\n

\t\u00a0<\/p>\n

\t The main will call the method create_workers along with the information in the command line arguments.<\/p>\n

\t create_workers will set the values for worker_args_t object and call the\u00a0<\/p>\n

\t method worker_proc in threads along with the object parameter of worker_args_t which we just set.<\/p>\n

\t worker_proc will the call the wait_for_cpu() along with the information of thread in worker_args_t.<\/p>\n

\t\u00a0<\/p>\n

\t\u00a0<\/p>\n

Q 9 \u00a0Is it possible that a worker thread would never proceed past the call to<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0wa->ops->wait_for_cpu(&wa->info) when using one of the scheduling<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0policies implemented in this MP?<\/p>\n

\t\u00a0<\/p>\n

\t yes, it is possible. For example if all the processes are of 1 unit time\u00a0<\/p>\n

\t and number of maximum processes at one time are less than or equal to the\u00a0<\/p>\n

\t number of threads then they will be finished right away.<\/p>\n

Q 10 Explain how you would alter the program to demonstrate the “convoy”<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0effect, when a large compute bound job that never yields to another<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0thread slows down all other jobs in a FIFO scheduled system? See Page<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0402, Stallings, the paragraph starting “Another difficulty with FCFS is<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0that it tends to favor processor-bound processes over I\/O bound<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0processes”. \u00a0Why is it difficult to show the benefits of Round Robin<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0scheduling in this case using the current implementation in the machine<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0problem?<\/p>\n

\t\u00a0<\/p>\n

\t We can do this by altering the concept of FIFO a little. Like we can have<\/p>\n

\t a threshold that a process can maximum stay n time units for the execution,\u00a0<\/p>\n

\t after that the process must wait again for its turn.<\/p>\n

SMP5: Scheduler with Signals<\/p>\n

============================<\/p>\n

This MP is a variation of SMP4.<\/p>\n

In the last MP, we built a simulated OS process scheduler. The scheduler can<\/p>\n

hold only a certain number of processes (workers) at one time. Once the process<\/p>\n

has been accepted into the scheduler, the scheduler decides in what order the<\/p>\n

processes execute. We implemented two scheduling algorithms: FIFO and Round<\/p>\n

Robin.<\/p>\n

In this MP, we are to simulate a time-sharing system by using signals and<\/p>\n

timers. We will only implement the Round Robin algorithm. Instead of using<\/p>\n

iterations to model the concept of “time slices” (as in the last MP), we use<\/p>\n

interval timers. \u00a0The scheduler is installed with an interval timer. The timer<\/p>\n

starts ticking when the scheduler picks a thread to use the CPU which in turn<\/p>\n

signals the thread when its time slice is finished thus allowing the scheduler<\/p>\n

to pick another thread and so on. When a thread has completely finished its work<\/p>\n

it leaves the scheduler to allow a waiting thread to enter. Please note that in<\/p>\n

this MP, only the timer and scheduler send signals. The threads passively handle<\/p>\n

the signals without signaling back to the scheduler.<\/p>\n

The program takes a number of arguments. Arg1 determines the number of jobs<\/p>\n

(threads in our implementation) created; arg2 specifies the queue size of the<\/p>\n

scheduler. Arg3 through argN gives the duration (the required time slices to<\/p>\n

complete a job) of each job. Hence if we create 2 jobs, we should supply arg3<\/p>\n

and arg4 for the required duration. You can assume that the autograder will<\/p>\n

always supply the correct number of arguments and hence you do not have to<\/p>\n

detect invalid input.<\/p>\n

Here is an example of program output, once the program is complete:<\/p>\n

% scheduler 3 2 3 2 3<\/p>\n

Main: running 3 workers with queue size 2 for quanta:<\/p>\n

\u00a03 2 3<\/p>\n

Main: detaching worker thread 3075926960.<\/p>\n

Main: detaching worker thread 3065437104.<\/p>\n

Main: detaching worker thread 3054947248.<\/p>\n

Main: waiting for scheduler 3086416816.<\/p>\n

Scheduler: waiting for workers.<\/p>\n

Thread 3075926960: in scheduler queue.<\/p>\n

Thread 3075926960: suspending.<\/p>\n

Thread 3065437104: in scheduler queue.<\/p>\n

Thread 3065437104: suspending.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3075926960.<\/p>\n

Thread 3075926960: resuming.<\/p>\n

Scheduler: suspending 3075926960.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3065437104.<\/p>\n

Thread 3065437104: resuming.<\/p>\n

Thread 3075926960: suspending.<\/p>\n

Scheduler: suspending 3065437104.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3075926960.<\/p>\n

Thread 3075926960: resuming.<\/p>\n

Thread 3065437104: suspending.<\/p>\n

Scheduler: suspending 3075926960.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3065437104.<\/p>\n

Thread 3065437104: resuming.<\/p>\n

Thread 3075926960: suspending.<\/p>\n

Scheduler: suspending 3065437104.<\/p>\n

Thread 3065437104: leaving scheduler queue.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3075926960.<\/p>\n

Thread 3075926960: resuming.<\/p>\n

Thread 3065437104: terminating.<\/p>\n

Thread 3054947248: in scheduler queue.<\/p>\n

Thread 3054947248: suspending.<\/p>\n

Scheduler: suspending 3075926960.<\/p>\n

Thread 3075926960: leaving scheduler queue.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3054947248.<\/p>\n

Thread 3054947248: resuming.<\/p>\n

Thread 3075926960: terminating.<\/p>\n

Scheduler: suspending 3054947248.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3054947248.<\/p>\n

Thread 3054947248: suspending.<\/p>\n

Thread 3054947248: resuming.<\/p>\n

Scheduler: suspending 3054947248.<\/p>\n

Scheduler: scheduling.<\/p>\n

Scheduler: resuming 3054947248.<\/p>\n

Thread 3054947248: suspending.<\/p>\n

Thread 3054947248: resuming.<\/p>\n

Scheduler: suspending 3054947248.<\/p>\n

Thread 3054947248: leaving scheduler queue.<\/p>\n

Thread 3054947248: terminating.<\/p>\n

The total wait time is 12.062254 seconds.<\/p>\n

The total run time is 7.958618 seconds.<\/p>\n

The average wait time is 4.020751 seconds.<\/p>\n

The average run time is 2.652873 seconds.<\/p>\n

The goal of this MP is to help you understand (1) how signals and timers work,<\/p>\n

and (2) how to evaluate the performance of your program. You will first<\/p>\n

implement the time-sharing system using timers and signals. Then, you will<\/p>\n

evaluate the overall performance of your program by keeping track of how long<\/p>\n

each thread is idle, running, etc.<\/p>\n

The program will use these four signals:<\/p>\n

SIGALRM: sent by the timer to the scheduler, to indicate another time<\/p>\n

\u00a0\u00a0quantum has passed.<\/p>\n

SIGUSR1: sent by the scheduler to a worker, to tell it to suspend.<\/p>\n

SIGUSR2: sent by the scheduler to a suspended worker, to tell it to resume.<\/p>\n

SIGTERM: sent by the scheduler to a worker, to tell it to cancel.<\/p>\n

You will need to set up the appropriate handlers and masks for these signals.<\/p>\n

You will use these functions:<\/p>\n

\u00a0\u00a0clock_gettime<\/p>\n

\u00a0\u00a0pthread_sigmask<\/p>\n

\u00a0\u00a0pthread_kill<\/p>\n

\u00a0\u00a0sigaction<\/p>\n

\u00a0\u00a0sigaddset<\/p>\n

\u00a0\u00a0sigemptyset<\/p>\n

\u00a0\u00a0sigwait<\/p>\n

\u00a0\u00a0timer_settime<\/p>\n

\u00a0\u00a0timer_create<\/p>\n

Also, make sure you understand how the POSIX:TMR interval timer works.<\/p>\n

There are two ways you can test your code. \u00a0You can run the built-in grading<\/p>\n

tests by running “scheduler -test -f0 rr”. \u00a0This runs 5 tests, each of which can<\/p>\n

be run individually. \u00a0You can also test you program with specific parameters by<\/p>\n

running “scheduler -test gen …” where the ellipsis contains the parameters you<\/p>\n

would pass to scheduler.<\/p>\n

Programming<\/p>\n

===========<\/p>\n

Part I: Modify the scheduler code (scheduler.c)<\/p>\n

———————————————–<\/p>\n

We use the scheduler thread to setup the timer and handle the scheduling for the<\/p>\n

system. \u00a0The scheduler handles the SIGALRM events that come from the timer, and<\/p>\n

sends out signals to the worker threads.<\/p>\n

Step 1.<\/p>\n

Modify the code in init_sched_queue() function in scheduler.c to initialize the<\/p>\n

scheduler with a POSIX:TMR interval timer. Use CLOCK_REALTIME in timer_create().<\/p>\n

The timer will be stored in the global variable “timer”, which will be started<\/p>\n

in scheduler_run() (see Step 4 below).<\/p>\n

Step 2.<\/p>\n

Implement setup_sig_handlers(). \u00a0Use sigaction() to install signal handlers for<\/p>\n

SIGALRM, SIGUSR1, and SIGTERM. \u00a0SIGALRM should trigger timer_handler(), SIGUSR1<\/p>\n

should trigger suspend_thread(), and SIGTERM should trigger cancel_thread().<\/p>\n

Notice no handler is installed for SIGUSR2; this signal will be handled<\/p>\n

differently, in step 8.<\/p>\n

Step 3.<\/p>\n

In the scheduler_run() function, start the timer. \u00a0Use timer_settime(). \u00a0The<\/p>\n

time quantum (1 second) is given in scheduler.h. \u00a0The timer should go off<\/p>\n

repeatedly at regular intervals defined by the timer quantum.<\/p>\n

In Round-Robin, whenever the timer goes off, the scheduler suspends the<\/p>\n

currently running thread, and tells the next thread to resume its operations<\/p>\n

using signals. These steps are listed in timer_handler(), which is called every<\/p>\n

time the timer goes off. \u00a0In this implementation, the timer handler makes use of<\/p>\n

suspend_worker() and resume_worker() to accomplush these steps.<\/p>\n

Step 4.<\/p>\n

Complete the suspend_worker() function. \u00a0First, update the info->quanta value.<\/p>\n

This is the number of quanta that remain for this thread to execute. \u00a0It is<\/p>\n

initialized to the value passed on the command line, and decreases as the thread<\/p>\n

executes. \u00a0If there is any more work for this worker to do, send it a signal to<\/p>\n

suspend, and update the scheduler queue. \u00a0Otherwise, cancel the thread.<\/p>\n

Step 5.<\/p>\n

Complete the cancel_worker() function by sending the appropriate signal to the<\/p>\n

thread, telling it to kill itself.<\/p>\n

Step 6.<\/p>\n

Complete the resume_worker() function by sending the appropriate signal to the<\/p>\n

thread, telling it to resume execution.<\/p>\n

Part II: Modify the worker code (worker.c)<\/p>\n

——————————————<\/p>\n

In this section, you will modify the worker code to correctly handle the signals<\/p>\n

from the scheduler that you implemented in the previous section.<\/p>\n

You need to modify the thread functions so that it immediately suspends the<\/p>\n

thread, waiting for a resume signal from the scheduler. You will need to use<\/p>\n

sigwait() to force the thread to suspend itself and wait for a resume signal.<\/p>\n

You need also to implement a signal handler in worker.c to catch and handle the<\/p>\n

suspend signals.<\/p>\n

Step 7.<\/p>\n

Modify start_worker() to (1) block SIGUSR2 and SIGALRM, and (2) unblock SIGUSR1<\/p>\n

and SIGTERM.<\/p>\n

Step 8.<\/p>\n

Implement suspend_thread(), the handler for the SIGUSR1 signal. \u00a0The<\/p>\n

thread should block until it receives a resume (SIGUSR2) signal.<\/p>\n

Part III: Modify the evaluation code (scheduler.c)<\/p>\n

————————————————–<\/p>\n

This program keeps track of run time, and wait time. \u00a0Each thread saves these<\/p>\n

two values regarding its own execution in its thread_info_t. \u00a0Tracking these<\/p>\n

values requires also knowing the last time the thread suspended or resumed.<\/p>\n

Therefore, these two values are also kept in thread_info_t. \u00a0See scheduler.h.<\/p>\n

In this section, you will implement the functions that calculate run time and<\/p>\n

wait time. \u00a0All code that does this will be in scheduler.c. \u00a0When the program<\/p>\n

is done, it will collect all these values, and print out the total and average<\/p>\n

wait time and run time. \u00a0For your convenience, you are given a function<\/p>\n

time_difference() to compute the difference between two times in microseconds.<\/p>\n

Step 9.<\/p>\n

Modify create_workers() to initialize the various time variables.<\/p>\n

Step 10.<\/p>\n

Implement update_run_time(). \u00a0This is called by suspend_worker().<\/p>\n

Step 11.<\/p>\n

Implement update_wait_time(). \u00a0This is called by resume_worker().<\/p>\n

Questions<\/p>\n

==========<\/p>\n

Question 1.<\/p>\n

Why do we block SIGUSR2 and SIGALRM in worker.c? \u00a0Why do we unblock SIGUSR1 and<\/p>\n

SIGTERM in worker.c?<\/p>\n

Because we want just one process to be executing at a time.<\/p>\n

Question 2.<\/p>\n

We use sigwait() and sigaction() in our code. Explain the difference between the<\/p>\n

two. (Please explain from the aspect of thread behavior rather than syntax).<\/p>\n

sigaction() is used to allow other code to run until a process is pending,\u00a0<\/p>\n

whereas sigwait() suspends execution of the thread until a process is pending but blocked<\/p>\n

Question 3.<\/p>\n

When we use POSIX:TMR interval timer, we are using relative time. What is the<\/p>\n

alternative? Explain the difference between the two.<\/p>\n

Its alternative is POSIX:XSI interval timer.\u00a0<\/p>\n

In POSIX:TMR interval timer has small number of clocks, such as CLOCK_REALTIME ,\u00a0<\/p>\n

and a process can create many independent timers for each clock<\/p>\n

In POSIX:XSI interval timer each process has a small fixed number of timers,\u00a0<\/p>\n

one of each of the types ITIMER_REAL , ITIMER_VIRTUAL , ITIMER_PROF and so on.<\/p>\n

Question 4.<\/p>\n

Look at start_worker() in worker.c, a worker thread is executing within an<\/p>\n

infinite loop at the end. When does a worker thread terminate?<\/p>\n

It will terminate when the thread time expires.<\/p>\n

Question 5.<\/p>\n

When does the scheduler finish? \u00a0Why does it not exit when the scheduler queue<\/p>\n

is empty?<\/p>\n

The scheduler will finish after completing its time. It won’t finish when the\u00a0<\/p>\n

queue is empty because it will wait for the new tasks<\/p>\n

Question 6.<\/p>\n

After a thread is scheduled to run, is it still in the sched_queue? When is it<\/p>\n

removed from the head of the queue? When is it removed from the queue completely?<\/p>\n

Yes. It will still in the queue. It will be completely removed once the thread is completely done.<\/p>\n

Question 7.<\/p>\n

We’ve removed all other condition variables in SMP4, and replaced them with a<\/p>\n

timer and signals. Why do we still use the semaphore queue_sem?<\/p>\n

Question 8.<\/p>\n

What’s the purpose of the global variable “completed” in scheduler.c? Why do we<\/p>\n

compare “completed” with thread_count before we wait_for_queue() in<\/p>\n

next_worker()?<\/p>\n

It is keeping track of the threads that got completed. We are comparing because\u00a0<\/p>\n

if completed becomes equal to or greater than the thread_count, then it means we\u00a0<\/p>\n

are done. We don’t have any more threads. So we can’t return any thread.<\/p>\n

Question 9.<\/p>\n

We only implemented Round Robin in this SMP. If we want to implement a FIFO<\/p>\n

scheduling algorithm and keep the modification as minimum, which function in<\/p>\n

scheduler.c is the one that you should modify? Briefly describe how you would<\/p>\n

modify this function.<\/p>\n

We will modify timer_handler. Here we are shifting the jobs in round robin. So if\u00a0<\/p>\n

we just shift each job when its completed then it will become fifo.<\/p>\n

Question 10.<\/p>\n

In this implementation, the scheduler only changes threads when the time quantum<\/p>\n

expires. \u00a0Briefly explain how you would use an additional signal to allow the<\/p>\n

scheduler to change threads in the middle of a time quantum. \u00a0In what situations<\/p>\n

would this be useful?<\/p>\n

we can make the time slices short enough that we don’t need to wait long after\u00a0<\/p>\n

a signal completes.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

SMP4: Thread Scheduler ====================== INSTRUCTIONS ============ 1. OVERVIEW =========== In this MP, you will write a user-mode thread scheduler. \u00a0The basic purpose of a scheduler is to multiplex use of the computer across several threads of execution. \u00a0This MP deals with two different scheduling policies: FIFO and Round Robin. \u00a0You will implement both, for use […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16],"tags":[],"class_list":["post-61456","post","type-post","status-publish","format-standard","hentry","category-education"],"_links":{"self":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts\/61456","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/comments?post=61456"}],"version-history":[{"count":0,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/posts\/61456\/revisions"}],"wp:attachment":[{"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/media?parent=61456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/categories?post=61456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/assignmenttutors.net\/blog\/wp-json\/wp\/v2\/tags?post=61456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}