实时处理期末总结

1.Real-time system

• A real-time system is a system with explicit time requirement
• The system must be respond to external inputs within a specified period
• Failure to meet the time requirements is as bad as producing the wrong outputs.
• An example of real-time systems: MPEG video and audio encoder(30 frames/s)

2.scheduling algorithm

2.1 clock-driven scheduling approach

1. scheduling decision are made at specific time instants,which are typically chosen a priori.
2. Typically,hardware timer used to provided periodic time instans,at which the schduler wakes up and select the next jobs to execute.
3. The approach is suitable for systems that consist of mostly deterministic and periodic tasks.

2.2 Weighted round-robin scheduling approach

1. jobs are given weights and are placed in FIFO queue
2. Processor’s time is divided into equal time slices.
3. when it is job’s return,it will execute for Wi time before being pre-emptied for the next job in queue.
4. New job execute almost immediately.This approachis suitable incremental producer/consumer jobs.

2.3 Priority-driven scheduling approach

1. At any scheduling decision time,among the eligible jobs,the one with the highest priority is selected for execution.
2. This approach tries to make locally optimal decision and is also known as greedy scheduling.
3. Example are first-in-first-out,shortest-execution-time-first,earliest-deadine-first

3.Priority-Driven scheduling of periodic tasks

3.1Rate-Monotonic (RM)

  Highest priority = Task with the smallest period
  Utilisation = execution / period

U_total =U₁+U₂+U₃+…+U_i
if U_total<= U_RM(i+1)
result: the task set is schedulable
else if U_RM(i+1) < U_total <=1
br if meet the time-demanding
result: the task set is schedulable
else
result: the task set is not schedulable
else
result: the task set is not schedulable

Time demanding

3.2 Earliest-Deadline-First(EDF)

  Higest priority = Task with the earliest absolute deadline
  Utilisation = execution / period

U_total =U₁+U₂+U₃+…+U_i
if u_total<=1
result: the task set is schedulable
else
result: the task set is not schedulable

3.3 Deadline-Monotonic(DM)]

  Highest priority = Task with the smallest realtive deadline
  Utilisation = execution / period

U_total =U₁+U₂+U₃+…+U_i
if u_total<=1
result: the task set is schedulable
else
result: the task set is not schedulable

4.Priority-Driven Scheduling of Non-periodic Tasks

4.1 Scheduling aperiodic jobs

4.1.1 Background Execution

   * Aperiodic jobs are given the lowest priority
   * They are executed in the background,when no periodic or sporadic job is runing

4.1.2 Interrupt-driven Execution

   * Aperiodic jobs are given the highest priority
   * Each new aperiodic job causes an interrupt and preempts the currently executing

4.1.3 Polled Execution

     All aperiodic jobs are placed in a queue
     A periodic task is created to servide the aperiodic queue
     The periodic task is called a server

4.1.3.1 Polling Server

*  when executed,a polling server runs the job at the head of the aperiodic queue until:
    ** the queue is empty or
    ** poller budget is completely used
*  when  the aperiodic queue is empty
    ** the server suspends immediately
    ** the remaining budget is cleared to 0
    ** the budget is recharged to e only in the next Period p

4.1.3.2 Deferrable Server

*  if no aperiodic job is ready,the deferrable server preserves its budget and suspends itself
* when a new aperiodic job arrives and the deferrable server still has budget,the server is actived to run the aperiodic job immediately

R

4.1.3.3 Sporadic Server

 * A sporadic server is T(p,e) treated exactly as a periodic task with period p and execution e
 * Parameter P and e are chosen so that the sporadic server and existing periodic tasks are schedulable

4.2 Scheduling sporadic jobs

4.2.1 Sporadic jobs

  *  A sporadic job has a hard deadline and requires extra handing
  *   Each sporadic job is checked if it can complete on time without affecting the periodic jobs and existing sporadic jobs
  *  In dynamic-priority systems,sporadic jobs are scheduled with periodic jobs using the EDF rule
  *  In static-priority systems,sporadic jobs are serviced using a sporadic server

4.2.2 Accetance Test

     1.EDF
       1-d-(e/(d-r))>=s   is accepted
     2.static-priority
       if i==1
          floor(( Di-Ri)/Ps)*Es>=E1
       else
         floor(( Di-Ri)/Ps)*Es-C>=Ei

5. Multi-processor Scheduling

5.1 Task assignment

5.1.1 First fit(FF)

1. Total Utilisation of each processor must nor exceed a present limit U(U=1)
2. Assign tasks one-by one in an arbitrary order

5.1.2 Rate-monotonic first fit(RMFF)

1. Tasks are allocated in the order of increasing periods.
2. A new task T can be assigned to processor P if u_T+U_p<=U_RM (n+1).
3. Let n be the number of tasks currently assigned to processor.
4. Let U_p be the current utilisation of processor P.
   

5.1.3 Rate-monotonic small tasks(RMST)

1. Tasks set sorted in the increasing order of X
2. For each Task T_i ,a parameter X_i is computed
3. R=max(X)-min(X)
4. U_T+U_p<=max(ln2,1-R*ln2)
   

5.1.4 Rate-monotonic general task

1. Divided the task set into two subsets: Subset "small":task with utilisation<=1/3  ,Subset "large" task: tasks with utilisation > 1/3.
2. Assign subsets "small" according to the RMST algorithm.
3. Assign subsets "large" according to the RMFF algorithm.

5.2 Inter-processor synchronisation

5.2.1 Greedy protocol

1. A job is released as soon as its predecessor is completed
2. Job J_i,k+1,n is released when job J_i,k,_n is completed
   

5.2.2 Phase-modification protocol

1. It enforce periodic release of every subtasks
2. Job j_i,k+1,n is released time: *J_i,k+1,n=SUM_i=1^k(W_i,l)+Q_i+(n-1)p_i

5.2.3 Modified phase-modification protocol

3. Similar to PM protocol except that a job is not released unless its predecessor has been completed
4. Job j_i,k+1,n is released time: max(releasetime of J_i,k,n+W_i,k,completion time of J_i,k,n)

5.2.4 Release guard protocol

1. Job j_i,k+1,n is released time:
2. if busy since J_i,k+1,n-1
   then
   max(r_i,k+1,n-1+P_i,finish of J_i,k,n)
   else
   max(finish of J_i,k,n,processor become free)

5.3 Subtask scheduling

Algorithm	Relative Deadline
Utilmate Deadline	Di,k=Di
Effective Deadline	Di,k=Di -SUMq=k+1K(ei,q)
Proportional Deadline	Di,k=Di *（ei,k/ei）
Normalised Proportional Deadline	Di,k=Di(ei,k(U(Vi,k)/(SUMq=1K(ei,q*U(Vi,q)))))

6 Resource and resource Access Control

6.1 Access control protocol

6.1.1 Non-preemptive critical section protocol(NCS)

 1.when a job requests a resource,it is always granted the resource
 2.when a job holds any resource ,it must not be interrupted
 3.A job is blocked at most once by a lower-priority job
 4.Maximum blocking time of job J<=max(critical sections of lower-priority jobs )
 ![在这里插入图片描述](https://img-blog.****img.cn/20190106193043182.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3NTY2Mw==,size_16,color_FFFFFF,t_70)

6.1.2 Priority-inheritance protocol

1.default priority:given by the scheduling algorithm such as RM or EDF
2.current priority: changed dynamically according to the access control protocol
3.Priority-inherited rules:
         When job J is blocked by job J'(that is ,J' is holding resource R that J requests);
         job J' inherits the current priority of J,and
         Job j' continues running at the inherited priority until it release  R.
         finally,Job J' returns to is priority at time t' when it acquired R

6.1.3 Priority-celling protocol

 1. Each resource R is givenn a priority celling P,which is the highest priority among the job's that need R.
 2. The system is given a priority ceiling P,which is the highest priority among the resource that are currently in use.
 3. Allocation rule:A request for a resource R by job J is granted only if the resource is free and
   J has a priority greater than priority of the system,or
   J holds a resource with priority equal  priority of system

7.Clock-driven Scheduling

7.1 Clock-driven scheduling

1. Scheduling decisions are made at predefined time instans.
2. The schedule is computed off-line and stored as a table for use at run-time.
3. Clock-driven is suitable for system that consist of deterministic and period tasks

7.2 Frame scheduling

4. Scheduling decision are made periodically,rather than at arbitrary time.
5. The hyperperiod is divided into equal time intervals called frames.
6. Three constraints on frame size:
   (1).f>=max(e₁,e₂,e₃,…,e_N)
   (2). H/f must be have an integer
   (3). 2f-gcd(p_i,f)<=D_i, for all i=1,2,3,…,n
   if (1) and (3),can not be satisfied at the same time,priority to meet (3)

7.3 Cyclic executive

1. They cyclic executive is used to execute the schedule table.
2. Only the schedule table for one hyper-period is needed
3. stack stealing :reduce the response times of aperiodic jobs by executing aperiodic jobs ahead of the periodic jobs whenever possible
   (1).no stack stealing:slack time is always at the end of frame.
   (2).Slack stealing 1:putting aperiodic jobs ahead of periodic jobs.
   (3).slack stealing 2:putting aperiodic jobs whenever there is some slack.