Operating Systems and Networks Spring2016 Assignment2Due15March2016
1.Scheduling
The following table describes jobs to be scheduled.The table contains the entry times,duration, execution times,and deadlines of jobs.All values are given in milliconds.
Job Entry time Execution time Deadline
103070
202090
3202050
4301040
55030120
Scheduling decisions are performed every10ms.Assume scheduling decisions take no time.The deadlines are absolute.Jobs that enter the system can be scheduled immediately.
morphe
(a)Creating schedules
Create schedules for the different types of policies listed below.Plea visualize your schedules (like in the lecture)and also answer the questions below.If a policy does not clearly specify which job should be scheduled,always schedule the job with the lowest number.
Types of schedules:
i.RR(round robin)
ii.EDF(earliest deadlinefirst)
iii.SRTF(shortest remaining timefirst)
Plea answer the following questions for each of the schedules:
•What is the waiting time for each job?
•What is the average waiting time for all job?
•What is the turnaround time for each job?
•How is the respon time computed for this scheduler?If possible,calculate the respon
time for each job.
(b)General questions
i.What is the problem with the SJF(shortest jobfirst)policy?
ii.What is an advantage of SJF?
iii.What is a benefit of RR?
iv.What is a major conceptual difference between EDF and RR?
v.Why do hard real-time systems often not have dynamic scheduling?
(c)Real-time scheduling
You are designing an HDTV.To keep the production costs low,it has only one CPU which must perform the following tasks:
•Decode video chunks(takes50ms and has to be done at least every200ms)
•Update Screen(takes30ms and has to be done at least every200ms)
•Handle ur input(takes10ms and has to be done at least every250ms)
i.Show that it is possible to schedule all tasks in such a way that all deadlines are met using
rate-monotonic scheduling(RMS).Do not prent a working schedule.
ii.Suppo DRM must be added to your TV.This requires an extra task with a period of300 ms and an execution time of100ms.
α)What is the utilization of the system now?
masffect
β)What is the upper bound according to the theorem ud in(ii).
γ)If you try to construct a working schedule by hand,you will e it is still possible to create one.How can this be explained?
iii.For a general tting show the following:if the number of tasks approaches infinity and the utilization is below69.3%,then all tasks can be scheduled without violating deadlines.
Explain how you derive this result.
2.Process revisited
apocalypCreating new process in Linux(and other Unix-like operating systems)is done using fork().The system call fork()clones an existing process instead of creating a completely new one.
Since fork()clones a process,both the parent and the child execute the same code after the invocation.It is necessary to distinguish to two process,and this can be done by checking the return value of fork().The parent receives the PID of the child process while the child gets0.backorder
(a)Calling fork()multiple times in a row
Write a program which calls fork()multiple times in a hree times.Each forked pro-cess shall print its own level in the process tree and wait for all child process using waitpid().
What process tree do you expect?Note that you can u ps f to verify if your program output matches the actual process tree.
(b)Executing ls-l from your program
Write a program which executes ls-l.Look up the man page of the exec()family of functions using man3exec.(Note that each man page is associated with a ction,and all the ctions are described in the man page of man.Here we must specify ction3to get the correct man page.)
After calling exec()(or one of its variants)in your program,add a printf()statement to show that exec()has completed.
When you run your program,what problem do you obrve?How can it befixed?
(c)Reading the output of ls from a pipe Create a program which opens a pipe.Execute ls
and redirect the output into the pipe.Then read data from the pipe and print it.Your program should print a statement before writing data read from the ,“Output from ls:...”.
3.Process and the kernel
(a)If a process terminates but its parent has not called wait()(or a similar function)or“ignored”
it,the process enters the zombie state.Explain why the process is put in the zombie state instead of being cleaned up in the kernel.
(b)Write a program which calls fork(),and make the parent process terminate while the child
honoluluruns indefinitely.Does the child process get a new parent?If so,which process becomes its parent and is there anything special about the new process?
4.Ur-level threads
qa是什么意思(a)Implementing ur-level threads
In this ction,you should implement a ur-level thread library and a scheduler.To keep it simple,implement a round robin scheduler.
You will need to implement the following functions:
•thread create()
•thread add runqueue()
•thread yield()
•thread exit()
•schedule()
•dispatch()
•thread start threading()
Each thread should be reprented by a TCB(struct thread in the template)which contains at least a function pointer to the thread’s function and an argument of type void*.The thread’s function should take this void*as argument whenever it is executed.This struct should also contain a pointer to the thread’s stack and twofields which store the current stack pointer and ba pointer when it calls yield.
thread create()should take a function pointer and void*arg as arguments.It allocates a TCB and a new stack for the thread and ts default values.It is important that the initial stack pointer(t by this function)is at an address divisible by8.The function returns the initialized structure.
thread add runqueue()adds an initialized TCB to the run queue.Since we implement a round robin scheduler,it is easiest if you maintain a ring of struct thread’s.This can be done by having a linked list where the last node points to thefirst node.
The static variable current thread always points to the currently executing thread.
thread yield()suspends the current thread by saving its context to the TCB and calling the scheduler and the dispatcher.If the process the resumed later,it continues executing from where it stopped.
thread exit()removes the caller from the ring,frees its stack and the TCB,ts current thread to the next thread to be executed,and calls dispatch().It is important to dispatch the next thread right here before returning becau we just removed the current thread.
schedule()decides which thread to run next.This is actually trivial becau it is a round robin scheduler.Simply lect the next thread in the ring.For ,for the dispatcher), it may be helpful to have another static variable which points to the last executed thread. dispatch()actually executes a thread(the thread to run as decided by the scheduler).It has to save the stack pointer and the ba pointer of the last thread to its TCB and restore the stack pointer and ba pointer of the new thread.This involves some asmbly code.In ca the thread has never run before,it may have to do some initialization instead.If the thread’s function returns,the thread has to be removed from the ring and the next one has to be dispatched.The easiest thing to do here is call thread exit()since this function does that already.
thread start threading()initializes the threading by calling schedule()and dispatch(). This function should be called by your main function(after adding thefirst thread to the run queue).It should never return(at least as long as there are threads in your system).
In summary,to create and run a thread,you should follow the steps below:闻鸡起舞是什么意思
static void
thread_function(void*arg)
{squirrel什么意思
//Create threads here and add to the run queue if necessary
while(condition){
otherfaithdo_work();
thread_yield();
if(condition)
thread_exit();
}
}
int
main(int argc,char**argv)
{
struct thread*t=thread_create(f,NULL);
thread_add_runqueue(t);
//Create more threads and add to run queue if necessary
thread_start_threading();
printf("Done\n");
return0;
agp是什么意思}
