DOC PREVIEW
UB CSE 321 - SchedSept28

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Realtime System Fundamentals : Scheduling and Priority-based schedulingRealtime schedulingMotivating ProblemTask State DiagramDeadline driven schedulingDeadline Scheduling (periodic tasks)PowerPoint PresentationAperiodic Task setRate-monotonic schedulingCritical sections and SemaphoresResources & Critical ResourcesPthread and mutexPriority InversionPriority inversion (Priority: t1>t2>t3)Problem: Priority inversion Solution1: Priority InheritanceSolution2:Priority Ceiling ProtocolB. RAMAMURTHY01/13/19Realtime System Fundamentals : Scheduling and Priority-based schedulingPage 1Realtime scheduling01/13/19We will realtime system scheduling as in:Earliest deadline scheduling (EDS)Starting deadline Completion deadlineDynamic priority scheduling Rate monotonic scheduling (RMS) Periodic tasks are prioritized by the frequency of repetition (high priority to tasks with shorter periods)Preemptive schedulingFixed priority schedulingSchedulability according to RMS Σ(Ci/Ti) <= n(21/n-1)Cyclic executives (pre-scheduled) Concepts of cycle, slot and frame Repeated executiontimesPage 2Motivating ProblemYou are building a realtime system PLTO to send on a mission to Pluto and beyond. Consider three periodic tasks t1, t2, and t3 with {cpu time, period} as {40, 100}, {75, 300} and {50, 200} respectively. Examine the schedulability of these tasks on a processor in the system PLTO. (This problem may be equally applicable to a system in a modern automobile.)01/13/19Page 301/13/19Task State DiagramReadyBlockedNewRunTask admittedResources allocatedDispatched; cpu allocatedWaiting for eventEvent occurredTask exitPage 4Deadline driven scheduling01/13/19Parameters: ready time, starting deadline, completion deadline, processing time, resource requirement, priority, preemptive or non-preemptivePage 5Deadline Scheduling (periodic tasks)01/13/19Process Arrival Time Execution Time Ending DeadlineA(1) 0 10 20A(2) 20 10 40A(3) 40 10 60A(4) 60 10 80A(5) 80 10 100• • • •• • • •• • • •B(1) 0 25 50B(2) 50 25 100• • • •• • • •• • • •Page 601/13/19Page 7deadlineA1 B1 A2 B1 A3 B2 A4 B2 A5 B2A1 A2 B1 A3 A4 A5, B2(missed)A1(missed)A2 A3 A4(missed)A5, B2B1 A2 A3 B2 A5A1 A2 B1 A3 A4 A5, B2A1 B1 A2 B1 A3 B2 A4 B2 A5Fixed-priority scheduling;A has priorityFixed-priority scheduling;B has priorityEarliest-deadline schedulingusing completion deadlinesB1Aperiodic Task set01/13/19Page 8Arrival Time Execution Time Starting DeadlineA 10 20 110B 20 20 20C 40 20 50D 50 20 90E 60 20 70Use earliest deadline with unforced idle timeRate-monotonic scheduling01/13/19Page 9First proposed by Liu.For RMS, the highest-priority task is the one with the shortest period, thesecond highest-priority task is the one with the second shortest period, and so on.Schedulability according to RMS Σ(Ci/Ti) <= n(21/n-1)Critical sections and Semaphores01/13/19When multiples tasks are executing there may be sections where only one task could execute at a given time: critical region or critical sectionThere may be resources which can be accessed only be one of the processes: critical resourceSemaphores can be used to ensure mutual exclusion to critical sections and critical resourcesPage 10Resources & Critical Resources 01/13/19Shared resources: need mutual exclusionTasks cooperating to complete a jobTasks contending to access a resourceTasks synchronizing Critical resources and critical regionA important synchronization and mutual exclusion primitive / resource is “semaphore”Page 11Pthread and mutex1. #include <pthread.h>2. Declare mutex variable global to the threads, functions pthread_mutex_t mtx; // declare3. pthread_mutex_init(&mtx, NULL); //initialize4. Identify critical section within thread; use mutex to realize mutual exclusion pthread_mutex_lock(&mtx); // code for critical section pthread_mutex_unlock(&mtx);5. Destroy mutex before exiting the program; pthread_mutex_destroy(&mtx);01/13/19Page 12Priority Inversion01/13/19When we allow concurrent task to execute and with semaphore and mailboxes and other synchronization primitives, it is possible that a low priority task may come to block a high priority task. This situation is known as priority inversion.What happened on Mars?Page 13Priority inversion (Priority: t1>t2>t3)01/13/19task3task2Critical sectiontask1time0 1 2 3 4 5 6 7 8 9 10blockedPage 14Problem: Priority inversion Solution1: Priority Inheritance01/13/19task3task2Critical sectiontask1time0 1 2 3 4 5 6 7 8 9 10blockedPriority of t1 inheritedTask 2 delayedPriority revertedTo t3Page 15Solution2:Priority Ceiling ProtocolCS Used byPriority CeilingS1 t1,t2 P(t1)S2 t1,t2,t3 P(t1)S3 t3 P(t3)01/13/19Critical sectiontask1time0 1 2 3 4 5 6 7 8 9 10task2task3Acquire S2Attempt to Acquire S1Acquire S1Acquire S1 Acquire S2Release S1Release S2No wayPage


View Full Document

UB CSE 321 - SchedSept28

Documents in this Course
Anomaly1

Anomaly1

48 pages

ProcSept9

ProcSept9

17 pages

LecSept2

LecSept2

30 pages

CRCNov23

CRCNov23

14 pages

Load more
Download SchedSept28
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view SchedSept28 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SchedSept28 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?