Tasks for the Problem Session on RTSD 13.04.2004
1. Build Gantt diagram for 1-processor SPT schedule, calculate throughput
Let’s assume that we have L=5 tasks with execution times of (2,3,5,4,2) which enter uni-processor at moment t=0. SPT algorithm orders tasks in the ascending of execution time order: this sequence of tasks numbers is (1,5,2,4,3), and tasks are assigned for execution in such order:
In the figure above time axis corresponding to processor’s behavior is represented as a stripe, time units are boxes of this stripe, inside each box is shown number of the task which is executed by processor in corresponding period of time. So, task 1 will terminate at moment 2, task 5 – at moment 4, task 2 – at moment 7, task 4 – at moment 11, task 3 – at moment 16. Average time of staying of tasks in the system will be sum of these times divided by 5:
ATS=(2+4+7+11+16)/5=40/5=8 units_of_time per task, this reflects mean time required for the task to leave the system. Throughput is average number of tasks leaving system per time unit, and may be calculated as 1/ATS=1/8 task will exit system per unit of time. SPT schedule provides optimal value of ATS, and respectively, of throughput.
2. Build Gantt diagram for 1-processor round-robin schedule, calculate throughput
Let’s consider the same conditions as in the previous exercise 1, but now we are to use round-robin discipline to assign tasks. This corresponds to allowance of interruption of execution of the current task after expiration of time quantum. We assume that time quantum is equal to time unit. Tasks are assigned one by one in circular manner:
We see that after getting 1st 2 quanta of time 1st and 5th task terminated at moments 6 and 10 respectively, task 2 terminated at moment 11, task 4 terminated at moment 15, and task 5 terminated at moment 16. We see that tasks with less execution time left system earlier than larger tasks, this corresponds to SPT idea but as far as exact times are not used for making decisions while scheduling, results are worse than in SPT schedule:
ATS=(6+10+11+15+16)/5=58/5=11.6 time units per task
Throughput=1/ATS=1/11.6 tasks leave system per time unit
In priority preemptive systems tasks of higher priority interrupt lower priority tasks. System with 2 priority levels – high, low is a foreground-background system, in which foreground tasks preempt background tasks.
3. Consider priority preemptive system with 3 tasks – t1, t2, t3, having execution times 40, 20, 30 and priorities – 3,1,2 respectively (priority of level 1 is highest). They arrive in moments 1,2,3 respectively. What is the time to complete task 1,2,3? (Laplante, p. 167, ex. 13)
Task 1 will run in time [1,2], then it will be preempted by task 2 of priority 1, this task will run for 20 units without preemptions as of highest priority in interval [2,22], then will start execution of task 3, which entered the system at moment 3 and waited for execution together with interrupted task 1. Task 3 will be executed in interval [22,52]. Task 1 will be resumed at moment 52 and will run for its rest 39 time units until moment 91. So, task 1 will require to complete 90 time units, task 2 – 20, task 3 – 49 (time from entering till exiting of the system).
4. Should a task be allowed to interrupt itself? (Laplante, p. 167, Ex. 14)
Why not? If we assume, that tasks of the previous exercise are interruption handlers, we see that while handling one interruption signal there may come again interruption signal of other, as in exercise 3, level of priority and from the other source, or of the same level of priority, and from the same source. This situation corresponds to possible bursts of requests for serving. They may be queued on the level of controller, or by allowing of interrupting itself we shall have in memory stack sequence of interrupted calls. Of course, if such bursts will be for long period, stack may be overflowed and this may cause failure of the system. So, self interrupting may be allowed, but run-time stack size is to be designed taking into account maximal possible depth of interruptions, and size of stack required for each context switch.
Better, is not to allow self-interruptions. In such an approach, size of stack is better predictable.
5. What criteria are needed to determine the size of the run-time stack in a multiple-interrupt system? What safety precautions are necessary? (Laplante, p. 167, Ex. 15)
This is a question, connected with a previous exercise. For designing run-time stack we are to multiply maximal possible depth of interruptions by size of context for switching saved in stack each time of interruption occurs. For safety precautions, this figure is to be increased by size of one or two more interruptions.
6. What is the worst response time for the background process in a foreground-background system in which the background requires 100 milliseconds to complete, foreground task executes every 50 milliseconds and requires 25 milliseconds to complete, and context switching requires no more than 100 microseconds (recall that background task may be preempted) (Laplante, p. 167, Ex. 16)
The worst case for execution of the background process is when it will try to start simultaneously with next start of foreground task. Let’s assume that at moment 0 was issued request for background (B) task.
In the figure above F time axis shows time usage by F task, B time axis is for B task, Switch time line shows time necessary for context switch. Task B starts at moment 0, it is assumed that 0.1 ms were to switch context to it from operating system mode; just at this moment foreground (F) task request was issued. So, 0.1 ms will be required for context switching, 25 ms F task will run, 0.1 ms are to switch again to B task. So, next start time of serving of B now is 25.3 ms, and next request for F task will occur at moment 50.1 ms, up to this moment B task will work really for 50.1-25.3 = 24.8 ms. So, each 50 ms period of time B task will get 24.8 ms of processor time. To get 100 ms of processor time it will be necessary to wait for (100 div 24.8)=4 full 50 ms periods, and the last 5th period for getting rest 0.8 ms will be also needed, but not full. So, in 4 full periods B task will work for 99.2 ms. In the 5th period it will wait for 25.2 ms for context switching to F, execution of F, switching back to B, then it will terminate in 0.8 ms. So, total time to complete B task will be:
0.1+4*50+25.2+0.8=226.1 ms
7. Implement counting semaphore with a help of binary
If assume MaxSem to be maximal value of CountSem, BinSem – binary semaphore initiated by 1, shared by multiple processes, then
Const
GuardSem:TBinSem=1;//global binary semaphore, initialized by 1, guards counter
CountSem:TBinSem=1;//global binary semaphore to simulate counting semaphore
R:integer=MaxSem;//global integer, representing current value of counting
//semaphore; negative values give number of suspended processes
P(R:integer){//counter P operation
P(GuardSem); //lock counter
R:=R-1; //decrement semaphore value
If (R<0){//none available?
V(GuardSem);//release counter
P(CountSem);//wait for free resource
}
V(GuardSem);//release counter
}
V(R:integer){//counter V operation
P(GuardSem);//lock counter
If (R<MaxSem) R:=R+1;//free resource, if possible
If (R<=0) //any task waiting for free resource
V(CountSem);//give that task to go ahead
Else V(GuardSem);//release counter
}
For V operation, releasing of GuardSem in the case of R<=0 is made by activated process (last V(GuardSem) in P operation).
8. (Laplante, p. 187, Ex. 3). Why it is not wise to disable interruptions before the while loop in the following implementation of P-operation on binary semaphore S:
Procedure P(var S:Boolean);
Begin
While s=false do;
S:=false
End;
Procedure V(var s:Boolean);
Begin
S:=true
End;
If to disable interruptions before while loop:
Procedure P(var S:Boolean);
Begin
Asm
Cli
End;
While s=false do;
S:=false
End; //It is a Pascal code
then in the case of false value of s it couldn’t be set to 1 because control yielding will not be allowed, and deadlock could happen. From the other hand, if to disable interrupts after while loop and before assignment, it is not reasonable if assume assignment implemented by 1 machine instruction. In general case, several commands are required to implement assignment. But after cycle while and before disabling of interruptions control may be yielded to another process and it will also watch s=true. So, disable interruptions after while is useless. But without such disabling we can get several processes watching the same not-modified yet value of s. What to do? Solution follows:
Procedure P(var S:Boolean);
Begin
While true do begin //infinite loop
While s=false do;//wait for true value of s
//this loop is made with enabled interrupts!
Asm //disable interruptions
Cli
End;
If s then begin //again check for true value
S:=false; //reset if s was true
Asm
Sti //enable interruptions
End;
Break //exit infinite loop
End //end of then branch
Asm
Sti //enable interruptions
End; //here we come if s became false in between while loop and interrupt
//disabling
End //end of infinite loop
End;//end of P
Simpler solution, but requiring more interruption switches:
Procedure P(var s:boolean);
Var
Temp:Boolean;
Begin
Repeat
Disable interrupts;//cli
Temp:=s;
S:=false;
Enable interrupts;//sti
Until temp=true;
End;
Procedure V(var s:boolean);//for both cases above of P operation
Begin
S:=true
End;
9. Implement a pipe mechanism of inter-processes communications using circular buffer and semaphores. Consider non-blocking interactions (Similar to Laplante, p. 188, Ex. 15)
CircularBuffer will be of N places of information portions (bytes, sectors, blocks, etc.). We shall have 2 pointers associated with CircularBuffer: Head, Tail. Head will point to position where next portion of information is to be written, Tail will point to position from which next portion of information is to be read. After reading, we assume this portion of information not available any more for other requests, and place in which it was may be reused after read operation terminated. Circular means that after write into 1st position we shall write into 2nd and so on, after write in the last N-th position we shall try to write in the 1st position; similar for reading. Places for next write and read will be indicated by Tail and Head respectively. For circulating we shall use (x mod N) operation (remainder after integer division by N).
Simultaneous reading and writing are prohibited, for this sake we shall use binary semaphore BufferSem, initialized by 1.
Pascal code follows:
Const
N=20; //buffer will be on 20 places
Head:integer=1;
Tail:integer=1;//Head and Tail at first show to the same position, that corresponds to
//empty buffer state
Type
Buffer=array[1..N] of Elements;//type of buffer
Var
BufferSem: BinSemaphore;//global semaphore variable shared by several processes
CircularBuffer:Buffer;
function WriteBuff( Info:element):integer;//return -1 if no place to write
begin
P(BufferSem);
If Tail mod N+1<>Head then begin //there is space for next write
CircularBuffer[Tail]:=info; //write into tail position
Tail:=Tail mod N+1;//shift tail pointer
WriteBuf:=0;//successfully wrote
End
Else
WriteBuff:=-1;//no space in buffer
V(BufferSem);
End;
function ReadBuff( var Info:element):integer;//return -1 if buffer is empty
begin
P(BufferSem);
If Head<>Tail then begin //buffer is not empty
Info:=CircularBuffer[Head];//read from head
Head:= Head mod N+1;//shift head pointer
ReadBuf:=0;//successfully read
End
Else
ReadBuff:=-1;//empty buffer
V(BufferSem);
End;
Producer will use
If WriteBuff(information)=0 then begin
Work in the case of successful write operation
End
Else begin
Work in the case of not writing successfully
End
Similarly, Consumer will not be blocked in the case of absence information in the buffer.
10. Consider Bakery algorithm
shared Boolean taking[n]=false; //used to show time of taking next ticket by each
//process
shared int ticket[n]=0; //ticket number for each process
shared int max=0;//current number of ticket
It is assumed that
(a,b) < (c,d), if a < c or if a == c & b < d
Process Pi :
while (some condition) {/*entry protocol*/
taking[i] = true;//wants to take ticket
ticket[i] =++max;// max(ticket[0], ...,ticket[n-1]) + 1;
taking[i] = false;//already took
for(j = 0; j < n; j++){
while(taking[j]); //if j-th process is now taking - wait
while(ticket[j] != 0 && (ticket[j],j) < (ticket[i],i));
} /*end of entry protocol*/
critical section
ticket[i] = 0; //exit protocol
remainder section
}
11. Consider execution of set of priority processes without priority inheritance, using OCPP, ICPP.