Scribd Logo
Upload

Welcome to Scribd!

  • 128 views

    Real Time Systems: Assignment - 2 Name: Vithya M BITS ID: 2019HT01605 Session ID: Session1584817886264 (And

    Uploaded by

    vithya
    The document contains the solutions to three questions regarding real-time scheduling algorithms. For question 1, four tasks are scheduled using rate monotonic priority assignment and found to be schedulable under non-preemptive but not preemptive scheduling. Question 2 involves three periodic tasks sharing a resource under priority inheritance protocol, showing priority inheritance occurring at times 7 and 19. Question 3 draws a scheduling diagram for three tasks sharing a resource, identifying priority inversions occurring at times 3, 7, and 17.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Real Time Systems: Assignment - 2 Name: Vithya M BITS ID: 2019HT01605 Session ID: Session1584817886264 (And

    Uploaded by

    vithya
    128 views8 pages
    The document contains the solutions to three questions regarding real-time scheduling algorithms. For question 1, four tasks are scheduled using rate monotonic priority assignment and found to be schedulable under non-preemptive but not preemptive scheduling. Question 2 involves three periodic tasks sharing a resource under priority inheritance protocol, showing priority inheritance occurring at times 7 and 19. Question 3 draws a scheduling diagram for three tasks sharing a resource, identifying priority inversions occurring at times 3, 7, and 17.

    Original Title

    Assignment_2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains the solutions to three questions regarding real-time scheduling algorithms. For question 1, four tasks are scheduled using rate monotonic priority assignment and found to be schedulable under non-preemptive but not preemptive scheduling. Question 2 involves three periodic tasks sharing a resource under priority inheritance protocol, showing priority inheritance occurring at times 7 and 19. Question 3 draws a scheduling diagram for three tasks sharing a resource, identifying priority inversions occurring at times 3, 7, and 17.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    128 views8 pages

    Real Time Systems: Assignment - 2 Name: Vithya M BITS ID: 2019HT01605 Session ID: Session1584817886264 (And

    Uploaded by

    vithya
    The document contains the solutions to three questions regarding real-time scheduling algorithms. For question 1, four tasks are scheduled using rate monotonic priority assignment and found to be schedulable under non-preemptive but not preemptive scheduling. Question 2 involves three periodic tasks sharing a resource under priority inheritance protocol, showing priority inheritance occurring at times 7 and 19. Question 3 draws a scheduling diagram for three tasks sharing a resource, identifying priority inversions occurring at times 3, 7, and 17.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 8

    REAL TIME SYSTEMS

    Assignment -2
    Name: Vithya M
    BITS ID: 2019HT01605
    Session ID: session1584817886264 (and also in personal PC as was getting error session
    Information not found for other 2 times)

    Q1. Schedule the following task according to Rate monotonic algorithm. Implement
    using user defined protocol. Use Cheddar simulator tool for the same.
    T1 (5, 1), T2 (6, 1) T3 (8, 2) T4 (7, 2)
    Rate Monotonic Algorithm: Task with smallest time period will have highest priority
    Task Priority
    T1 1
    T2 2
    T3 4
    T4 3
    Non-Pre-emptive:

    The tasks are schedulable using Non pre-emptive Rate Monotonic Algorithm, but not
    schedulable using Pre-emptive Rate monotonic algorithm.
    Q2. (Use Cheddar simulator)Consider three periodic tasks, synchronous and with
    deadlines on request: tasks T1, T2 and T3. They are defined as follow:

     Task T1 : Period=Deadline=6, Capacity=2, Start time = 0


     Task T2 : Period=Deadline=8, Capacity=2, Start time = 0
     Task T3 : Period=Deadline=12, Capacity=5, Start time = 0

    Assume a pre-emptive fixed priority scheduling policy and apply Rate Monotonic to
    assign priorities. Assume that tasks T1 and T3 share a resource named S. T1 and T3
    access to S in mutual exclusion:

     T3 needs S during all its capacity.


     T1 needs S during the 2nd unit of time of its capacity only.
     First keep the resource protocol as No protocol.

    a)In this time line, find when tasks T1 and T2 lock and unlock S. From this time line,
    can we see priority inversions? Where?

    Priority inversion occurs at time t=7; as T1 wants resource but the resource is already locked
    by T3, So a low priority task is executed with high priority task waiting.

    TASK LOCK UNLOCK


    T1 t=1 t=2
    T2
    T3 t=4 t=12

    At time, t = 6 :T1 is released and executes for 1 unit time, at t=7 T1 requests for resource but
    it is locked with T3 so T1 is pre-empted by T3. High priority job waits for low priority job to
    execute (priority Inversion).
    B) Identify the critical sections for the various tasks.

    Critical section: Time the resource is locked

    JOBS CRITICAL SECTION


    Task 1 [S;1]
    Task 2
    Task 3 [S;5]

    C) Change S protocol by Priority Inheritance Protocol (or PIP), and compute again the
    scheduling simulation. With PIP, find task which blocks another with a higher priority,
    runs its critical section with the blocked task priority. What can we see in this new
    scheduling simulation about the shared resource? Say at which time the priorities of the
    tasks change due to PIP.

    At time t=7, priority inherited

    Time t0: T1 executes

    Time t1: T1 requests for resource and locks resource

    Time t2: T1 completes execution and releases resource. T2 starts execution

    Time t4: T2 completes execution and T3 starts and locks resource S

    Time t6: T1 is released and starts execution

    Time t7: T1 requests for resource and is blocked, so T3 inherits the priority

    Similarly at time t=19 priority is inherited


    Q3. There are 3 tasks J1, J2 and J3 scheduled according to Rate monotonic algorithm.
    The feasible interval of these tasks are (6,10], (2,12], (0, 14] respectively. The critical
    sections [R; 3], [R; 2.5], [R; 2.5] for jobs 1, 2, 3. Execution times of these jobs are 4, 6
    and 5 times slots respectively. Draw the scheduling diagram and find the time instants
    where the priorty inversion occurs. The jobs require resources after 1 time slot after
    start of the execution.

    Rate Monotonic Algorithm: Task with smallest time period will have highest priority
    TASK FEASIBLE EXECUTION PRIORITY CRITICAL
    INTERVAL TIME SECTION
    J1 (6,10] 4 1 [R;3]
    J2 (2,12] 6 2 [R;2.5]
    J3 (0,14] 5 3 [R,2.5]

    Note: Several tasks misses deadline

    T0: J3 is release and starts executing

    T1: J3 requests for resource and locks resource

    T2: J2 is released and starts executing

    T3: J2 requests for resource but as it is locked with J3, J2 gets pre-empted and J3 continues
    execution till completion. (High priority job pre-empted by low priority job – Priority
    Inversion)

    T4.5: J3 completes execution and execution of J2 starts

    T6: J1 is released and starts execution

    T7: J1 requests for resource but gets pre-empted as the resource is locked with J2 (priority
    Inversion Point)

    T8: J1 locks resource and continues execution


    T11: J1 completes execution and now J2 resumes the remaining execution

    T13.5: J2 completes execution and J3 resumes the remaining execution

    T14: J2 is released so J3 is pre-empted by J2

    T15: J2 locks the resource

    T16: J1 is released and starts execution

    T17: J1 requests for resource but locked with J2, so gets pre-empted by J2 (priority
    inversion)

    You might also like