Subject: [PATCH 2/2] priority System V Semaphores
Quoted 1 line
From
25aa166505aff2561dd715c927c654d0bbb432baMon Sep 17 00:00:00 2001
From: raz <[email protected]>
Date: Tue, 20 Dec 2011 22:54:56 +0200
Add positioning routine find_pos. find_pos returns the place where to put the sleeper before.
I sort only rt tasks, OTHER policy is pushed back in queue. I do not distinct between SCHED_RR and SCHED_FIFO policies and they are treated as a single policy for the sorting algorithm.
SETPRIO operates only when user issues a single semop operation and not an array of opretions.
SETFIFO is the default for backward compatbility.
--- ipc/sem.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 49 insertions(+), 2 deletions(-)
ipc/sem.c +49 -2
@@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)return error; } +/* +* find the best place to put the task sorted by rt prio +*/ +static struct list_head *find_pos (struct sem *curr,int alter, +struct task_struct *p) +{ +struct sem_queue *q; +struct sem_queue *ret_pos =NULL ; +struct list_head *tasks_queue = &curr->sem_pending; + +if (!alter) +return tasks_queue; + +if (!(curr->flags &PRIO_SEM )) +return tasks_queue; +/* +* make no effort to sort SCHED_OTHER, +* just push task to the back of the queue. +*/ +if (!(p->policy ==SCHED_FIFO || p->policy ==SCHED_RR )) +return tasks_queue; +/* +* make no distinction between SCHED_FIFO +* and SCHED_RR policies. +*/ +list_for_each_entry (q, tasks_queue, simple_list) { +struct task_struct *t; + + t = q->sleeper; +if (current->rt_priority == t->rt_priority) { +/* +* push in a FIFO manner +* tasks in same priority +*/ + ret_pos = q; +continue ; + } +if (current->rt_priority < t->rt_priority) +continue ; +return &q->simple_list; + } +if (ret_pos) +return ret_pos->simple_list.next; +return tasks_queue; +} SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops, unsigned, nsops, const struct timespec __user *, timeout)
@@ -1357,6 +1402,7 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,unsigned long jiffies_left =0 ;struct ipc_namespace *ns;struct list_head tasks; +struct list_head *pending_pos; ns = current->nsproxy->ipc_ns;
@@ -1478,10 +1524,11 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,struct sem *curr; curr = &sma->sem_base[sops->sem_num]; + pending_pos =find_pos (curr, alter, current);if (alter) -list_add_tail (&queue.simple_list, &curr->sem_pending); +list_add_tail (&queue.simple_list, pending_pos);else -list_add (&queue.simple_list, &curr->sem_pending); +list_add (&queue.simple_list, pending_pos); }else {INIT_LIST_HEAD (&queue.simple_list); sma->complex_count++;
Signature · 1 line
1.7.5.4
Hi raz,
Quoted 12 lines · raz ben yehuda
Quoted 1 line
From
25aa166505aff2561dd715c927c654d0bbb432baMon Sep 17 00:00:00 2001From: raz<[email protected]>
Date: Tue, 20 Dec 2011 22:54:56 +0200Add positioning routine
find_pos.find_posreturns the place where to put the sleeper before.
I sort only rt tasks, OTHER policy is pushed back in queue. I do not distinct betweenSCHED_RRandSCHED_FIFOpolicies and they are treated as a single policy for the sorting algorithm.
Quoted 2 lines
SETPRIO operates only when user issues a single semop operation and not an array of opretions.
As far as I can see, the advantages of sysvsem are backward compatibility and the ability to use complex ops. You propose to add a new feature that doesn't work on complex ops.
Are there any apps that use SETPRIO?
What is the use case?
Quoted 18 lines
SETFIFO is the default for backward compatbility.
Signed-off-by raz<[email protected]>--- ipc/sem.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 49 insertions(+), 2 deletions(-)ipc/sem.c +3
-0@@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)return error; } +/* +* find the best place to put the task sorted by rt prio +*/
ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1358
Quoted 10 lines
ipc/sem.c +10
-0+static struct list_head *find_pos (struct sem *curr,int alter, +struct task_struct *p) +{ +struct sem_queue *q; +struct sem_queue *ret_pos =NULL ; +struct list_head *tasks_queue =&curr->sem_pending; + +if (!alter) +return tasks_queue; +
Tasks that do not alter anything end up first - IMHO correct.
Quoted 18 lines
ipc/sem.c +18
-0+if (!(curr->flags&PRIO_SEM )) +return tasks_queue; +/* +* make no effort to sort SCHED_OTHER, +* just push task to the back of the queue. +*/ +if (!(p->policy ==SCHED_FIFO || p->policy ==SCHED_RR )) +return tasks_queue; +/* +* make no distinction between SCHED_FIFO +* and SCHED_RR policies. +*/ +list_for_each_entry (q, tasks_queue, simple_list) { +struct task_struct *t; + + t = q->sleeper; +if (current->rt_priority == t->rt_priority) { +/*
ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1386
Quoted 10 lines
ipc/sem.c +10
-0+* push in a FIFO manner +* tasks in same priority +*/ + ret_pos = q; +continue ; + } +if (current->rt_priority< t->rt_priority) +continue ; +return &q->simple_list; + }
Here in the loop, non-alter tasks are evaluated as well. I think that's wrong, it could starve non-alter tasks.
e.g. queue:
- high prio non-alter
- low prio non-alter.
Now a medium prio alter task is added.
I think it will end up in the wrong position (before the low-prio non-alter task), correct?
--
Manfred
Quoted 16 lines · Manfred Spraul
Hi raz,
Quoted 12 lines · raz ben yehuda
Quoted 1 line
From
25aa166505aff2561dd715c927c654d0bbb432baMon Sep 17 00:00:00 2001From: raz<[email protected]>
Date: Tue, 20 Dec 2011 22:54:56 +0200Add positioning routine
find_pos.find_posreturns the place where to put the sleeper before.
I sort only rt tasks, OTHER policy is pushed back in queue. I do not distinct betweenSCHED_RRandSCHED_FIFOpolicies and they are treated as a single policy for the sorting algorithm.
Quoted 8 lines
Quoted 2 lines
SETPRIO operates only when user issues a single semop operation and not an array of opretions.
As far as I can see, the advantages of sysvsem are backward compatibility and the ability to use complex ops.
You propose to add a new feature that doesn't work on complex ops.Are there any apps that use SETPRIO?
What is the use case?
Vxworks is the use case. And there are plenty of companies with vxWorks software and in i believe they will migrate sooner or later to PreemptRT. My current company uses old wrapper software that implements vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority feature which is widely used.
I will probably change it some time in the future to posix semaphores , but posix semaphores are implemented in glibc with futexes and atomic ops and i rather mess with kernel and not glibc. funny , but true. glibc is harder.
Quoted 64 lines
Quoted 18 lines
SETFIFO is the default for backward compatbility.
Signed-off-by raz<[email protected]>--- ipc/sem.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 49 insertions(+), 2 deletions(-)e
ipc/sem.c +3
-0@@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)return error; } +/* +* find the best place to put the task sorted by rt prio +*/ ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1358
Quoted 10 lines
ipc/sem.c +10
-0+static struct list_head *find_pos (struct sem *curr,int alter, +struct task_struct *p) +{ +struct sem_queue *q; +struct sem_queue *ret_pos =NULL ; +struct list_head *tasks_queue =&curr->sem_pending; + +if (!alter) +return tasks_queue; +Tasks that do not alter anything end up first - IMHO correct.
Quoted 18 lines
ipc/sem.c +18
-0+if (!(curr->flags&PRIO_SEM )) +return tasks_queue; +/* +* make no effort to sort SCHED_OTHER, +* just push task to the back of the queue. +*/ +if (!(p->policy ==SCHED_FIFO || p->policy ==SCHED_RR )) +return tasks_queue; +/* +* make no distinction between SCHED_FIFO +* and SCHED_RR policies. +*/ +list_for_each_entry (q, tasks_queue, simple_list) { +struct task_struct *t; + + t = q->sleeper; +if (current->rt_priority == t->rt_priority) { +/* ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1386
Quoted 10 lines
ipc/sem.c +10
-0+* push in a FIFO manner +* tasks in same priority +*/ + ret_pos = q; +continue ; + } +if (current->rt_priority< t->rt_priority) +continue ; +return &q->simple_list; + }Here in the loop, non-alter tasks are evaluated as well. I think that's wrong, it could starve non-alter tasks. e.g. queue:
- high prio non-alter
- low prio non-alter.
Quoted 3 lines
Now a medium prio alter task is added.
I think it will end up in the wrong position (before the low-prio non-alter task), correct?
hammm.. correct. thanks. I did not check non-alter tasks at all. The entire queue might be a total mess. I will sort non alter tasks as well.
Also, this patch is missing scenario where a task priority is changed whilst it is waiting. I fixed that already.
Who maintains this code ?
Quoted 2 lines
--
Manfred
Quoted 101 lines · raz ben yehuda
Quoted 16 lines · Manfred Spraul
Hi raz,
Quoted 12 lines · raz ben yehuda
Quoted 1 line
From
25aa166505aff2561dd715c927c654d0bbb432baMon Sep 17 00:00:00 2001From: raz<[email protected]>
Date: Tue, 20 Dec 2011 22:54:56 +0200Add positioning routine
find_pos.find_posreturns the place where to put the sleeper before.
I sort only rt tasks, OTHER policy is pushed back in queue. I do not distinct betweenSCHED_RRandSCHED_FIFOpolicies and they are treated as a single policy for the sorting algorithm.Quoted 8 lines
Quoted 2 lines
SETPRIO operates only when user issues a single semop operation and not an array of opretions.
As far as I can see, the advantages of sysvsem are backward compatibility and the ability to use complex ops.
You propose to add a new feature that doesn't work on complex ops.Are there any apps that use SETPRIO?
What is the use case?Vxworks is the use case. And there are plenty of companies with vxWorks software and in i believe they will migrate sooner or later to PreemptRT. My current company uses old wrapper software that implements vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority feature which is widely used.
I will probably change it some time in the future to posix semaphores , but posix semaphores are implemented in glibc with futexes and atomic ops and i rather mess with kernel and not glibc. funny , but true. glibc is harder.Quoted 64 lines
Quoted 18 lines
SETFIFO is the default for backward compatbility.
Signed-off-by raz<[email protected]>--- ipc/sem.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 49 insertions(+), 2 deletions(-)e
ipc/sem.c +3
-0@@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)return error; } +/* +* find the best place to put the task sorted by rt prio +*/ ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1358
Quoted 10 lines
ipc/sem.c +10
-0+static struct list_head *find_pos (struct sem *curr,int alter, +struct task_struct *p) +{ +struct sem_queue *q; +struct sem_queue *ret_pos =NULL ; +struct list_head *tasks_queue =&curr->sem_pending; + +if (!alter) +return tasks_queue; +Tasks that do not alter anything end up first - IMHO correct.
Quoted 18 lines
ipc/sem.c +18
-0+if (!(curr->flags&PRIO_SEM )) +return tasks_queue; +/* +* make no effort to sort SCHED_OTHER, +* just push task to the back of the queue. +*/ +if (!(p->policy ==SCHED_FIFO || p->policy ==SCHED_RR )) +return tasks_queue; +/* +* make no distinction between SCHED_FIFO +* and SCHED_RR policies. +*/ +list_for_each_entry (q, tasks_queue, simple_list) { +struct task_struct *t; + + t = q->sleeper; +if (current->rt_priority == t->rt_priority) { +/* ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1386
Quoted 10 lines
ipc/sem.c +10
-0+* push in a FIFO manner +* tasks in same priority +*/ + ret_pos = q; +continue ; + } +if (current->rt_priority< t->rt_priority) +continue ; +return &q->simple_list; + }Here in the loop, non-alter tasks are evaluated as well. I think that's wrong, it could starve non-alter tasks. e.g. queue:
- high prio non-alter
- low prio non-alter.Quoted 3 lines
Now a medium prio alter task is added.
I think it will end up in the wrong position (before the low-prio non-alter task), correct?
Quoted 7 lines
hammm.. correct. thanks. I did not check non-alter tasks at all. The entire queue might be a total mess. I will sort non alter tasks as well.
Also, this patch is missing scenario where a task priority is changed whilst it is waiting. I fixed that already.Who maintains this code ?
It's mainly core kernel code and only changes when true changes are made. An update could be done to extend its use as long as it doesn't break any tools in the process. IOW, it must stay backward compatible.
-- Steve
Quoted 8 lines · raz ben yehuda
Vxworks is the use case. And there are plenty of companies with vxWorks software and in i believe they will migrate sooner or later to PreemptRT. My current company uses old wrapper software that implements vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority feature which is widely used.
I will probably change it some time in the future to posix semaphores , but posix semaphores are implemented in glibc with futexes and atomic ops and i rather mess with kernel and not glibc. funny , but true. glibc is harder.
Semaphores are a fscking trainwreck for real-time programming. Don't use them, full stop. If you do, you're doing it wrong, it's really that simple.
Use PI mutexes, which are already fully supported in glibc, no extra patching needed.
Full NAK for any and all priority fudging for any semaphore implementation.
Quoted 14 lines · Peter Zijlstra
Quoted 8 lines · raz ben yehuda
Vxworks is the use case. And there are plenty of companies with vxWorks software and in i believe they will migrate sooner or later to PreemptRT. My current company uses old wrapper software that implements vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority feature which is widely used.
I will probably change it some time in the future to posix semaphores , but posix semaphores are implemented in glibc with futexes and atomic ops and i rather mess with kernel and not glibc. funny , but true. glibc is harder.Semaphores are a fscking trainwreck for real-time programming. Don't use them, full stop. If you do, you're doing it wrong, it's really that simple.
Quoted 5 lines
Use PI mutexes, which are already fully supported in glibc, no extra patching needed.
Full NAK for any and all priority fudging for any semaphore implementation.
please correct me if am wrong, " posix semaphores
are implemented with pi mutex. ..?" I need a counting semaphore. vxWorks priority/fifo semaphores are different from posix semaphores in that the behaviour is defined on the semaphore and not the thread.
Q: what happens if I want one posix semahore to be FIFO and another posix semaphore to be PRIO while both are used by the same thread.should i to change policies each time ?
--
To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 2 lines · Raz
please correct me if am wrong, " posix semaphores
are implemented with pi mutex. ..?"
Probably not, that would be pointless. They might be implemented using a mutex, but I've already looked at glibc this month and my eyes can't handle more.
Quoted 3 lines
I need a counting semaphore.
vxWorks priority/fifo semaphores are different from posix semaphores in that the behaviour is defined on the semaphore and not the thread.
That doesn't make them sane locking primitives.
Quoted 3 lines
Q: what happens if I want one posix semahore to be FIFO and another posix semaphore to be PRIO while both are used by the same thread.should i to change policies each time ?
If you need a counting semaphore your program is very likely not a correct real-time application. So who cares what order things are woken up in.
Semaphores don't have lock owners, therefore priority inheritance and related schemes don't work, therefore you suffer from priority inversion and thus your program is invalid.
Seriously, forget semaphores exist, they're a hysterical accident.