Thread: How do you design scheduler ?

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    80

    How do you design scheduler ?

    I am working on embedded system. I want to write a c program to make simple real time scheduler. System can do multiple task's. scheduler decides which task can run at a given time.

    I am trying to figure out how to design small and simple scheduler before to start coding.

    Task states In typical designs, a task has three states:
    1. Ready (ready to be executed);
    2. Running (executing on the CPU);
    3. Waiting (for an event):


    I assume I have three task's

    1. Task 1
    2. Task 2
    3. Task 3


    I think I have to decide time for each task How long it should be run on system.

    I assume I have three task's

    1. Task 1 --> Run every 15ms
    2. Task 2 --> Run every 30 ms
    3. Task 3 --> Run every 50 ms


    system tick 10ms

    so all the time period are just considered i don't know if this is most suitable for what I am trying to design. if it's not suitable then you can also consider the time period of your choice

    My primary goal is to understand how to design the real time scheduler

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,738
    Are the tasks independent, or do they share resources which are guarded with mutexes?

    With a tick rate of 10mS, your 15mS task is going to have very poor timings.

    With 15mS and 30mS rates, task1 and task2 are going to become ready at the same time.
    Do you need to have task priorities to ensure the right one runs first?
    Do you need to have some fairness algorithm to ensure one task doesn't starve?

    Every 150mS, all three tasks will become ready at the same time.
    How long is it going to take to run all 3 tasks?

    If task3 takes 40mS, what impact does that have on T1 and T2?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2019
    Posts
    80
    Quote Originally Posted by Salem View Post
    Are the tasks independent, or do they share resources which are guarded with mutexes?

    With a tick rate of 10mS, your 15mS task is going to have very poor timings.

    With 15mS and 30mS rates, task1 and task2 are going to become ready at the same time.
    Do you need to have task priorities to ensure the right one runs first?
    Do you need to have some fairness algorithm to ensure one task doesn't starve?

    Every 150mS, all three tasks will become ready at the same time.
    How long is it going to take to run all 3 tasks?

    If task3 takes 40mS, what impact does that have on T1 and T2?
    I am trying to understand the concept of Real Time Scheduling System. I tried my best to understand the basics. I have read chapters of many books, also saw many tutorial, watched videos but I still don't understand it completely.

    In a real time context certain tasks must be run within certain time periods. Tasks share the processor's resources. yes it is necessary to set task priority as i want always important task to be executed first.

    I don't know if the information below will make sense, but I'll show you something new again to show you that I am trying to hard to understand


    System tick 1ms

    Task 1 needs to run for 8ms. It run 1 time in 40 ms. Priority 2
    Task 2 needs to run for 5ms. It run 2 times in 40 ms. Priority 1
    Task 3 needs to run for 10ms. It run 2 times in 40 ms. Priority 3

    I would appreciate any help

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,738
    On a machine with infinite CPUs, each task can be scheduled and executed at the correct time.
    +---+...............+---+............... ; T2 @ P1
    +------+................................ ; T1 @ P2
    +--------+..........+--------+.......... ; T3 @ P3


    On a single CPU, the tasks would be executed like this.
    TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT..
    22222111111113333333222223333333333333..


    Notes
    - The first run of T1 is delayed because T2 has higher priority.
    - The first run of T3 is delayed because T2 and T1 are higher priority.
    - The first run of T3 is interrupted by T2 before it has finished (after 7mS of it's 10mS run).
    - T3 ends up running back to back.
    - There is a 2mS dead time before the whole thing repeats.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Nov 2019
    Posts
    80
    Quote Originally Posted by Salem View Post
    On a single CPU, the tasks would be executed like this.
    TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT..
    22222111111113333333222223333333333333..


    Notes
    - The first run of T1 is delayed because T2 has higher priority.
    - The first run of T3 is delayed because T2 and T1 are higher priority.
    - The first run of T3 is interrupted by T2 before it has finished (after 7mS of it's 10mS run).
    - T3 ends up running back to back.
    - There is a 2mS dead time before the whole thing repeats.
    Thank you Salem for saving me from big trouble. I understand completely now

    There are many type of scheduling. Is it type of preemptive scheduling? I think yes

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. co operative scheduler design
    By abhi143 in forum C Programming
    Replies: 2
    Last Post: 05-07-2021, 12:04 PM
  2. brainstorming with a scheduler.
    By seemaxie in forum C Programming
    Replies: 2
    Last Post: 12-05-2012, 10:36 AM
  3. problem with the scheduler
    By ushacy in forum C Programming
    Replies: 3
    Last Post: 09-20-2011, 05:52 AM
  4. scheduler in linux
    By anjana in forum Linux Programming
    Replies: 6
    Last Post: 05-29-2007, 12:59 AM
  5. new scheduler in linux
    By anjana in forum Linux Programming
    Replies: 1
    Last Post: 05-28-2007, 02:55 AM

Tags for this Thread