MESSAGE
| DATE | 2015-05-08 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
|
From owner-learn-outgoing-at-mrbrklyn.com Fri May 8 19:38:42 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id DF09C16115E; Fri, 8 May 2015 19:38:41 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id B47C2161163; Fri, 8 May 2015 19:38:41 -0400 (EDT)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 382CE16115E;
Fri, 8 May 2015 19:38:15 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 5DEC112914;
Fri, 8 May 2015 19:38:15 -0400 (EDT)
Message-ID: <554D48E6.1060203-at-panix.com>
Date: Fri, 08 May 2015 19:38:14 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: learn-at-nylxs.com, Hangout
Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
References: <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com> <554cb5ea$0$2848$e4fe514c-at-news2.news.xs4all.nl> <20150508090051.901-at-kylheku.com> <87ioc31203.fsf-at-doppelsaurus.mobileactivedefense.com> <20150508085920.634-at-kylheku.com>
In-Reply-To: <20150508085920.634-at-kylheku.com>
X-Forwarded-Message-Id: <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com> <554cb5ea$0$2848$e4fe514c-at-news2.news.xs4all.nl> <20150508090051.901-at-kylheku.com> <87ioc31203.fsf-at-doppelsaurus.mobileactivedefense.com> <20150508085920.634-at-kylheku.com>
Content-Type: multipart/mixed;
boundary="------------040608040403070701090201"
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
This is a multi-part message in MIME format.
--------------040608040403070701090201
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
further in the thread...this is great stuff to read.
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!not-for-mail
From: ruben safir
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
Date: Fri, 08 May 2015 01:57:56 -0400
Organization: PANIX Public Access Internet and UNIX, NYC
Message-ID:
References: <20150422091305.302-at-kylheku.com> <87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com> <20150422110344.469-at-kylheku.com>
NNTP-Posting-Host: www.mrbrklyn.com
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
X-Trace: reader1.panix.com 1431064676 8534 96.57.23.82 (8 May 2015 05:57:56 GMT)
X-Complaints-To: abuse-at-panix.com
NNTP-Posting-Date: Fri, 8 May 2015 05:57:56 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To: <20150422110344.469-at-kylheku.com>
Xref: panix comp.unix.programmer:234577
On 04/22/2015 02:20 PM, Kaz Kylheku wrote:
> By the way, I used mutexes and condition variables in the kernel back in 1998,
> before any such a thing existed in the kernel,
how did they handle problems with concorancy then without mutexes? This
must have been a problem/
Ruben
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!goblin3!goblin.stu.neva.ru!bolzen.all.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Rainer Weikusat
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
Date: Fri, 08 May 2015 13:30:50 +0100
Message-ID: <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
References: <20150422091305.302-at-kylheku.com>
<87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com>
<20150422110344.469-at-kylheku.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: individual.net kzXYMEvXpBoKGKBDaJH+CAtF3QQdbTijEmGYjwMP1wEp2STto=
Cancel-Lock: sha1:0ueExSZFn0NgsBlojTrShb6/jzY= sha1:j+gL4ae40cYU7ceLAMtYJ6MCOhc=
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)
Xref: panix comp.unix.programmer:234579
ruben safir writes:
> On 04/22/2015 02:20 PM, Kaz Kylheku wrote:
>> By the way, I used mutexes and condition variables in the kernel back in 1998,
>> before any such a thing existed in the kernel,
>
> how did they handle problems with concorancy then without mutexes? This
> must have been a problem/
Mostly by avoiding it. A 'traditional' UNIX(*)-kernel would have been
written to run on an uniprocessor and would only preempt processes
executing userspace code. Hence, once a process entered the kernel, it
would run until exiting it again without being troubled by other
processes. Insofar the kernel code executed by this process needed to
work with data structures also used by interrupt handlers, it would
at least disable the corresponding interrupts (possibly more than these)
prior to doing so and re-enable them afterwards. This can be trivially
extended to support multiprocessors by 'preserving the invariants in
software', ie, use a single, global kernel lock every process/ thread
which wants to enter the kernel has to acquire prior to doing anything
else. Linux used to call this 'the BKL' (Big Kernel Lock) and it has
meanwhile been removed but this took years of development.
Another answer (which sort of avoids the question but maybe not): A
mutex is a relatively recent, simple-minded locking primitive. The
traditional way of achieving mutual exclusion would be a somewhat more
general counting semaphore.
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
Date: Fri, 08 May 2015 08:44:12 -0400
Organization: A noiseless patient Spider
Message-ID:
References: <20150422091305.302-at-kylheku.com> <87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com> <20150422110344.469-at-kylheku.com> <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 8 May 2015 12:43:11 +0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="858a9d65d95f4ea4d355bd116aa2cdbf";
logging-data="10373"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX19FeVLE3h8zofFPgEjm4Ico"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To: <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
Cancel-Lock: sha1:fRgvAf7ZVNj+eAJ8Ul4S3PqNqRE=
Xref: panix comp.unix.programmer:234580
On 5/8/2015 8:30 AM, Rainer Weikusat wrote:
> [...] Insofar the kernel code executed by this process needed to
> work with data structures also used by interrupt handlers, it would
> at least disable the corresponding interrupts (possibly more than these)
> prior to doing so and re-enable them afterwards. This can be trivially
> extended to support multiprocessors by 'preserving the invariants in
> software', ie, use a single, global kernel lock every process/ thread
> which wants to enter the kernel has to acquire prior to doing anything
> else. Linux used to call this 'the BKL' (Big Kernel Lock) and it has
> meanwhile been removed but this took years of development.
Solaris went through a similar migration, somewhat earlier. The
dirty secret about Sun's early dual-processor machines was that they
suffered from horrendous Great Big Lock contention within the kernel.
In some situations, you could actually speed up the machine by turning
off one of its CPU's ...
A staggering amount of time and effort went into breaking up that
single Great Big Lock.
--
esosman-at-comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!post.news.xs4all.nl!news.xs4all.nl!not-for-mail
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
References: <20150422091305.302-at-kylheku.com> <87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com> <20150422110344.469-at-kylheku.com> <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
From: Casper H.S. Dik
User-Agent: nn/6.6.2
Date: 08 May 2015 13:11:06 GMT
Message-ID: <554cb5ea$0$2848$e4fe514c-at-news2.news.xs4all.nl>
NNTP-Posting-Host: 31.151.229.227
X-Trace: 1431090666 news2.news.xs4all.nl 2848 casper/31.151.229.227:57381
Xref: panix comp.unix.programmer:234581
Eric Sosman writes:
> Solaris went through a similar migration, somewhat earlier. The
>dirty secret about Sun's early dual-processor machines was that they
>suffered from horrendous Great Big Lock contention within the kernel.
>In some situations, you could actually speed up the machine by turning
>off one of its CPU's ...
Wasn't this mostly true for SunOS 4.x; at that time the first 2-4
CPU systems were being sold and in certain cases, disabling two
CPUs made the system faster as the other two were just spinning.
Depended a lot on what the system was doing.
> A staggering amount of time and effort went into breaking up that
>single Great Big Lock.
It is not a single task with a single final (large) bug fix; it is a
continuous peace of work.
When you add more hardware threads you will run into new bits where
scaling runs into a roadblock; that needs to be fixed, ad inf.
Casper
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!news.linkpendium.com!news.linkpendium.com!news.glorb.com!peer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!post01.iad.highwinds-media.com!fx16.iad.POSTED!not-for-mail
X-Newsreader: xrn 9.03-beta-14-64bit
Sender: scott-at-dragon.sl.home (Scott Lurndal)
From: scott-at-slp53.sl.home (Scott Lurndal)
Reply-To: slp53-at-pacbell.net
Subject: Re: Kernel Scheduler and wiat queues
Newsgroups: comp.unix.programmer
References: <20150422091305.302-at-kylheku.com> <87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com> <20150422110344.469-at-kylheku.com> <87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
Message-ID:
X-Complaints-To: abuse-at-usenetserver.com
NNTP-Posting-Date: Fri, 08 May 2015 13:43:35 UTC
Organization: UsenetServer - www.usenetserver.com
Date: Fri, 08 May 2015 13:43:35 GMT
X-Received-Bytes: 3613
X-Received-Body-CRC: 285018761
Xref: panix comp.unix.programmer:234582
Rainer Weikusat writes:
>ruben safir writes:
>> On 04/22/2015 02:20 PM, Kaz Kylheku wrote:
>>> By the way, I used mutexes and condition variables in the kernel back in 1998,
>>> before any such a thing existed in the kernel,
>>
>> how did they handle problems with concorancy then without mutexes? This
>> must have been a problem/
>
>Mostly by avoiding it. A 'traditional' UNIX(*)-kernel would have been
>written to run on an uniprocessor and would only preempt processes
>executing userspace code.
Yet, by early 90's, multiprocessor versions of UNIX were available
(SVR4/MP based). And prior to that there were proprietary
multiprocessor systems around (starting in the 60's) by Burroughs,
CDC and IBM. The Burroughs systems implemented the lock
primitives in the instruction set.
Concurrency was studied extensively in the 70's, and there
were a number of journal papers describing various methods
including C.A.R Hoare's communicating sequential processes
paper.
http://www.usingcsp.com/cspbook.pdf
Low-level locking is pretty simple:
class c_spinlock {
private:
/**
* The lock value.
* - 1: Lock is available
* - 0: Lock is owned
* - < 0: Lock is contended for
*/
volatile int lockval __attribute__ ((aligned(4)));
public:
void init(void);
void dump(void);
bool is_locked();
void lock(void);
bool lock_noint(void);
void unlock(void);
void unlock_noint(bool);
int trylock(void);
};
/**
* Initialize the spinlock.
*/
inline void
c_spinlock::init(void)
{
lockval = 1;
}
/**
* Obtain the lock, spinning if necessary. See class documentation for
* algorithm details.
*/
inline void
c_spinlock::lock(void)
{
__asm__ __volatile__ (
"\n1:\t"
"lock; decl %0\n\t"
"jz 3f\n"
"2:\n\t"
"rep; nop\n\t"
"cmpl $0, %0\n\t"
"jle 2b\n\t"
"jmp 1b\n\t"
"3:\n\t": "=m" (lockval) : : "memory");
}
/**
* Release the lock. See class documentation for algorithm details.
*/
inline void
c_spinlock::unlock(void)
{
__asm__ __volatile__ ("movl $1, %0": "=m" (lockval): : "memory");
}
The main requirement is having support in the hardware for atomic
access to memory.
>Another answer (which sort of avoids the question but maybe not): A
>mutex is a relatively recent, simple-minded locking primitive. The
>traditional way of achieving mutual exclusion would be a somewhat more
>general counting semaphore.
Mutex as a primitive existed outside of the Unix world as early
as 1965 in the B5500, and later (1981) in the V380. It was also
common in the literature during the 70's.
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!goblin2!goblin.stu.neva.ru!feeder.erje.net!1.eu.feeder.erje.net!news.albasani.net!news.mixmin.net!aioe.org!.POSTED!not-for-mail
From: Kaz Kylheku
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
Date: Fri, 8 May 2015 16:02:46 +0000 (UTC)
Organization: Aioe.org NNTP Server
Message-ID: <20150508090051.901-at-kylheku.com>
References:
<20150422091305.302-at-kylheku.com>
<87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com>
<20150422110344.469-at-kylheku.com>
<87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
NNTP-Posting-Host: OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org
X-Complaints-To: abuse-at-aioe.org
User-Agent: slrn/pre1.0.0-18 (Linux)
X-Notice: Filtered by postfilter v. 0.8.2
Xref: panix comp.unix.programmer:234586
On 2015-05-08, Rainer Weikusat wrote:
> ruben safir writes:
>> On 04/22/2015 02:20 PM, Kaz Kylheku wrote:
>>> By the way, I used mutexes and condition variables in the kernel back in 1998,
>>> before any such a thing existed in the kernel,
>>
>> how did they handle problems with concorancy then without mutexes? This
>> must have been a problem/
>
> Mostly by avoiding it. A 'traditional' UNIX(*)-kernel would have been
> written to run on an uniprocessor and would only preempt processes
> executing userspace code. Hence, once a process entered the kernel, it
> would run until exiting it again without being troubled by other
> processes.
Not Linux in 1998. SMP was already around for a few years; properly written
code used spin_lock and spin_lock_iqrsave. CONFIG_PREEMPT was a few years
away, though.
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!goblin3!goblin.stu.neva.ru!bolzen.all.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Rainer Weikusat
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
Date: Fri, 08 May 2015 17:13:16 +0100
Message-ID: <87ioc31203.fsf-at-doppelsaurus.mobileactivedefense.com>
References: <20150422091305.302-at-kylheku.com>
<87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com>
<20150422110344.469-at-kylheku.com>
<87r3qrz1xh.fsf-at-doppelsaurus.mobileactivedefense.com>
<20150508090051.901-at-kylheku.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: individual.net pTfGfriam0Rpy5FFCnL4Fwyhb/q1XrHon+FwQjI0Q27/8OMJU=
Cancel-Lock: sha1:qonu627GQU3bF/FBAGRPiAfomDk= sha1:H9kX2jzLlY6Hi2CAZOAAAGahXk4=
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)
Xref: panix comp.unix.programmer:234587
Kaz Kylheku writes:
> On 2015-05-08, Rainer Weikusat wrote:
>> ruben safir writes:
>>> On 04/22/2015 02:20 PM, Kaz Kylheku wrote:
>>>> By the way, I used mutexes and condition variables in the kernel back in 1998,
>>>> before any such a thing existed in the kernel,
>>>
>>> how did they handle problems with concorancy then without mutexes? This
>>> must have been a problem/
>>
>> Mostly by avoiding it. A 'traditional' UNIX(*)-kernel would have been
>> written to run on an uniprocessor and would only preempt processes
>> executing userspace code. Hence, once a process entered the kernel, it
>> would run until exiting it again without being troubled by other
>> processes.
>
> Not Linux in 1998. SMP was already around for a few years; properly written
> code used spin_lock and spin_lock_iqrsave. CONFIG_PREEMPT was a few years
> away, though.
1998 was 'Linux 2.0' which relied on BKL-serialization, cf
http://www.tldp.org/HOWTO/SMP-HOWTO-3.html
and before that, it used the traditional model. Linux 2.2 on onwards
supported semaphores for locking in process context, mutexes were added
later,
https://lwn.net/Articles/167034/
--------------040608040403070701090201
Content-Type: message/rfc822;
name="Re: Kernel Scheduler and wiat queues.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Kernel Scheduler and wiat queues.eml"
Path: reader1.panix.com!panix!goblin3!goblin2!goblin.stu.neva.ru!aioe.org!.POSTED!not-for-mail
From: Kaz Kylheku
Newsgroups: comp.unix.programmer
Subject: Re: Kernel Scheduler and wiat queues
Date: Fri, 8 May 2015 16:00:37 +0000 (UTC)
Organization: Aioe.org NNTP Server
Message-ID: <20150508085920.634-at-kylheku.com>
References:
<20150422091305.302-at-kylheku.com>
<87sibsays5.fsf-at-doppelsaurus.mobileactivedefense.com>
<20150422110344.469-at-kylheku.com>
NNTP-Posting-Host: OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org
X-Complaints-To: abuse-at-aioe.org
User-Agent: slrn/pre1.0.0-18 (Linux)
X-Notice: Filtered by postfilter v. 0.8.2
Xref: panix comp.unix.programmer:234585
On 2015-05-08, ruben safir wrote:
> On 04/22/2015 02:20 PM, Kaz Kylheku wrote:
>> By the way, I used mutexes and condition variables in the kernel back in 1998,
>> before any such a thing existed in the kernel,
>
> how did they handle problems with concorancy then without mutexes?
Spinlocks were there, as well as down_sem, up_sem, and wait queues.
You know, the stuff I built the mutexes and conditions out of.
--------------040608040403070701090201--
|
|
