linux-kernel - RE: sched

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 20 Oct 2008 18:04:23 -0700
From:	"David Schwartz" <davids@...master.com>
To:	"David@...g. Hm" <david@...g.hm>
Cc:	"linux-kernel" <linux-kernel@...r.kernel.org>
Subject: RE: sched_yield() options

> in the case I'm looking at there are two (or more) threads running with
> one message queue in the center.
>
> 'input threads' are grabbing the lock to add messages to the queue
>
> 'output threads' are grabbing the lock to remove messages from the queue
>
> the programmer is doing a pthread_yield() after each message is processed
> in an attempt to help fairness (he initially added it in when he started
> seeing starvation on single-core systems)

Yuck. That forces the worst possible scenario, which is nearly strict
alternation.

There is no reason he should ever be seeing starvation. Each thread should
either:

1) Use out its timeslice. In which case, a thread can at most be starved for
the number of threads multiplied by the size of the timeslice. If this is
too long, then you have too many threads or your timeslice is too big. You
can't fix it with ugly hacks.

2) Get blocked because it needs another thread to help it make forward
progress. In this case, there should be no starvation, since each thread
can't continue until other threads continue.

> what should he be doing instead?

Simply set a limit on the maximum number of messages that can go in the
queue when output threads are CPU limited. Output threads can't starve input
threads because they have to block if the queue is empty (assuming you never
let the queue get too ridiculously full). Input threads can't starve output
threads if there's a reasonable limit on the queue size.

> the link above talks about other cases more, but really doesn't say what
> the right thing to do is for this case.
>
> David Lang

Implement a sensible queue.

DS

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/