{"action":"created","issue":{"url":"https://api.github.com/repos/RIOT-OS/RIOT/issues/7365","repository_url":"https://api.github.com/repos/RIOT-OS/RIOT","labels_url":"https://api.github.com/repos/RIOT-OS/RIOT/issues/7365/labels{/name}","comments_url":"https://api.github.com/repos/RIOT-OS/RIOT/issues/7365/comments","events_url":"https://api.github.com/repos/RIOT-OS/RIOT/issues/7365/events","html_url":"https://github.com/RIOT-OS/RIOT/issues/7365","id":243015997,"number":7365,"title":"scheduler: priority inversion problem","user":{"login":"geith","id":1948747,"avatar_url":"https://avatars0.githubusercontent.com/u/1948747?v=4","gravatar_id":"","url":"https://api.github.com/users/geith","html_url":"https://github.com/geith","followers_url":"https://api.github.com/users/geith/followers","following_url":"https://api.github.com/users/geith/following{/other_user}","gists_url":"https://api.github.com/users/geith/gists{/gist_id}","starred_url":"https://api.github.com/users/geith/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/geith/subscriptions","organizations_url":"https://api.github.com/users/geith/orgs","repos_url":"https://api.github.com/users/geith/repos","events_url":"https://api.github.com/users/geith/events{/privacy}","received_events_url":"https://api.github.com/users/geith/received_events","type":"User","site_admin":false},"labels":[{"id":91234472,"url":"https://api.github.com/repos/RIOT-OS/RIOT/labels/core","name":"core","color":"0052cc","default":false}],"state":"open","locked":false,"assignee":{"login":"gebart","id":317506,"avatar_url":"https://avatars1.githubusercontent.com/u/317506?v=4","gravatar_id":"","url":"https://api.github.com/users/gebart","html_url":"https://github.com/gebart","followers_url":"https://api.github.com/users/gebart/followers","following_url":"https://api.github.com/users/gebart/following{/other_user}","gists_url":"https://api.github.com/users/gebart/gists{/gist_id}","starred_url":"https://api.github.com/users/gebart/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gebart/subscriptions","organizations_url":"https://api.github.com/users/gebart/orgs","repos_url":"https://api.github.com/users/gebart/repos","events_url":"https://api.github.com/users/gebart/events{/privacy}","received_events_url":"https://api.github.com/users/gebart/received_events","type":"User","site_admin":false},"assignees":[{"login":"gebart","id":317506,"avatar_url":"https://avatars1.githubusercontent.com/u/317506?v=4","gravatar_id":"","url":"https://api.github.com/users/gebart","html_url":"https://github.com/gebart","followers_url":"https://api.github.com/users/gebart/followers","following_url":"https://api.github.com/users/gebart/following{/other_user}","gists_url":"https://api.github.com/users/gebart/gists{/gist_id}","starred_url":"https://api.github.com/users/gebart/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gebart/subscriptions","organizations_url":"https://api.github.com/users/gebart/orgs","repos_url":"https://api.github.com/users/gebart/repos","events_url":"https://api.github.com/users/gebart/events{/privacy}","received_events_url":"https://api.github.com/users/gebart/received_events","type":"User","site_admin":false}],"milestone":null,"comments":7,"created_at":"2017-07-14T14:35:53Z","updated_at":"2017-08-04T11:33:25Z","closed_at":null,"body":"The RIOT scheduler seems to have no protection against the [priority inversion problem][priority_inversion] where a task of medium priority can prevent the execution a higher prioritized task when that waits for a resource allocated by a low prioritized task. The attached code example demonstrated this behavior.\r\n\r\nA common solution for this is a for this is [priority inheritance mechanism][priority_inheritance], where owning task temporary inherits the priority of the waiting task. But there might be other solutions too.\r\n\r\nEven though this problem can be mostly avoided in the application design, it would be an feature which can avoid critical complications and simplifies the design of complex applications. \r\nAn famous example for this problem is the [Pathfinder Mission][pathfinder] which got stuck in a reboot loop (triggered by the watchdog timer) and exceeded its energy budget. In that case, that could be fixed by remotely enabling the priority inheritance feature.\r\n\r\n  [priority_inversion]: https://en.wikipedia.org/wiki/Priority_inversion \"Priority Inversion\"\r\n  [priority_inheritance]: https://en.wikipedia.org/wiki/Priority_inheritance\r\n  [pathfinder]: https://en.wikipedia.org/wiki/Mars_Pathfinder#On-board_computer\r\n\r\nIn the example below, the shared resource represented by the mutex _res_mtx_ which is used by a low and a high priority thread. A medium priority thread starts working after 3 s prevents the low priority thread from freeing the mutex and thus, the high priority thread from being scheduled.\r\n\r\n```c\r\n#include <stdio.h>\r\n#include <string.h>\r\n#include <stdint.h>\r\n\r\n#include \"thread.h\"\r\n#include \"mutex.h\"\r\n#include \"xtimer.h\"\r\n\r\nmutex_t res_mtx;\r\n\r\nchar stack_high[THREAD_STACKSIZE_MAIN];\r\nchar stack_mid[THREAD_STACKSIZE_MAIN];\r\nchar stack_low[THREAD_STACKSIZE_MAIN];\r\n\r\nvoid *t_low_handler(void *arg)\r\n{\r\n  /* starting working loop immediately */\r\n  while(1){\r\n    printf(\"t_low: allocating resource...\\n\");\r\n    mutex_lock(&res_mtx);\r\n    printf(\"t_low: got resource.\\n\");\r\n    xtimer_sleep(1);\r\n\r\n    printf(\"t_low: freeing resource...\\n\");\r\n    mutex_unlock(&res_mtx);\r\n    printf(\"t_low: freed resource.\\n\");\r\n    xtimer_sleep(1);\r\n  }\r\n  return NULL;\r\n}\r\n\r\nvoid *t_mid_handler(void *arg)\r\n{\r\n  /* starting working loop after 3s */\r\n  xtimer_sleep(3);\r\n\r\n  printf(\"t_mid: doing some stupid stuff...\\n\");\r\n  while(1){\r\n    thread_yield_higher();\r\n  }\r\n}\r\n\r\nvoid *t_high_handler(void *arg)\r\n{\r\n  /* starting working loop after 500 ms */\r\n  xtimer_usleep(500);\r\n  while(1){\r\n    printf(\"t_high: allocating resource...\\n\");\r\n    mutex_lock(&res_mtx);\r\n    printf(\"t_high: got resource.\\n\");\r\n    xtimer_sleep(1);\r\n\r\n    printf(\"t_high: freeing resource...\\n\");\r\n    mutex_unlock(&res_mtx);\r\n    printf(\"t_high: freed resource.\\n\");\r\n  }\r\n  return NULL;\r\n}\r\n\r\nkernel_pid_t pid_low;\r\nkernel_pid_t pid_mid;\r\nkernel_pid_t pid_high;\r\n\r\nint main(void)\r\n{\r\n  xtimer_init();\r\n  mutex_init(&res_mtx);\r\n  puts(\"This is a scheduling test for Priority Inversion\");\r\n\r\n  pid_low = thread_create(stack_low, sizeof(stack_low),\r\n      THREAD_PRIORITY_MAIN - 1,\r\n      THREAD_CREATE_STACKTEST,\r\n      t_low_handler, NULL,\r\n      \"t_low\");\r\n\r\n  pid_mid = thread_create(stack_mid, sizeof(stack_mid),\r\n      THREAD_PRIORITY_MAIN - 2,\r\n      THREAD_CREATE_STACKTEST,\r\n      t_mid_handler, NULL,\r\n      \"t_mid\");\r\n\r\n  pid_high = thread_create(stack_high, sizeof(stack_high),\r\n      THREAD_PRIORITY_MAIN - 3,\r\n      THREAD_CREATE_STACKTEST,\r\n      t_high_handler, NULL,\r\n      \"t_high\");\r\n\r\n  thread_sleep();\r\n  return 0;\r\n}\r\n```"},"comment":{"url":"https://api.github.com/repos/RIOT-OS/RIOT/issues/comments/320226718","html_url":"https://github.com/RIOT-OS/RIOT/issues/7365#issuecomment-320226718","issue_url":"https://api.github.com/repos/RIOT-OS/RIOT/issues/7365","id":320226718,"user":{"login":"haukepetersen","id":620834,"avatar_url":"https://avatars3.githubusercontent.com/u/620834?v=4","gravatar_id":"","url":"https://api.github.com/users/haukepetersen","html_url":"https://github.com/haukepetersen","followers_url":"https://api.github.com/users/haukepetersen/followers","following_url":"https://api.github.com/users/haukepetersen/following{/other_user}","gists_url":"https://api.github.com/users/haukepetersen/gists{/gist_id}","starred_url":"https://api.github.com/users/haukepetersen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haukepetersen/subscriptions","organizations_url":"https://api.github.com/users/haukepetersen/orgs","repos_url":"https://api.github.com/users/haukepetersen/repos","events_url":"https://api.github.com/users/haukepetersen/events{/privacy}","received_events_url":"https://api.github.com/users/haukepetersen/received_events","type":"User","site_admin":false},"created_at":"2017-08-04T11:33:25Z","updated_at":"2017-08-04T11:33:25Z","body":">  Pathfinder was launched twenty years ago.\r\n\r\nBut that doesn't mean, that programming errors like that are not made anymore... And why not give the developer something to his/her hand to make an application potentially more error proof?!\r\n\r\n> Any solution will not come for free in terms of code size and cycles\r\n\r\nThat's for sure! But adding some priority inversion prevention as an optional module would not hurt, right?!"}}
{"actor":{"display_login":"haukepetersen"}}