Tech Insider					     Technology and Trends

			      USENET Archives

Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!umd5!uvaarpa!mcnc!
From: jo...@rtmvax.UUCP (John Connin)
Newsgroups: comp.os.minix
Subject: Minix Scheduler
Message-ID: <1002@rtmvax.UUCP>
Date: 9 Mar 88 22:09:59 GMT
Organization: AFS Inc. REMOTE Site -rtmvax- Orlando,FL
Lines: 13
Keywords: minix, scheduler, multitasking

It appears to me that the Minix scheduling policy, although facilitating
a simple implementation, does not adequately support smooth operation
of concurrent applications.  Additionally, based on various comp.os.minix
messages it appears that others have make (in one form or another) similar

Before I possibly go off the deepend, I would be appreciative of others
(a) sharing any definitive work done in this area, and lacking such (b)
the sharing of ideas as to how the Minix scheduler should be changed,
both respect to policy and implementation.

     johnc!rtmvax!alxfin!codas          John Connin

Path: utzoo!mnetor!uunet!munnari!otc!metro!ipso!runx!brucee
From: bru...@runx.ips.oz (Bruce Evans)
Newsgroups: comp.os.minix
Subject: Re: Minix Scheduler (and tty performance)
Message-ID: <1432@runx.ips.oz>
Date: 16 Mar 88 16:30:40 GMT
References: <1002@rtmvax.UUCP>
Reply-To: bru...@runx.OZ (Bruce Evans)
Organization: RUNX  Un*x Timeshare. Sydney, Australia.
Lines: 97

In the referenced article jo...@rtmvax.UUCP (John Connin) writes:

> It appears to me that the Minix scheduling policy, although facilitating
> simple implementation, does not adequately support smooth operation
> of concurrent applications.  ...

I am doing a major rewrite of the scheduler in order to get better performance
from the new tty driver. Already performance has been improved from something
below 1200 baud to over 4800 baud on a 5 MHz PC. Some handshaking is still
necessary at this speed, but the interrupt handler and task switching is no
longer a major bottleneck. Zmodem runs on Minix and gives no errors at 4800
baud with a block size of 1024 over a cable linked to an Xenix machine.
Actual throughput is only 2400 baud.

This was mostly just a re-implementation, without major design changes. I'm
quite happy with the design of the scheduler. As Andy says, the complications
are mainly in the device drivers. The scheduler just has to be fast to handle
the heavy message traffic, and anything more complicated is likely to just
slow the system down.

I think the main problem is that fs is not really multi-tasking. While a
device driver is busy, fs is held busy and no tasks other than the one that
called fs can do I/O. They tend to do a little calculation, then line up on
a long queue waiting for fs. The drivers themselves are also a bit slow.
For instance, I have a floppy driver for another machine which reads 14 of 16
sectors per cylinder every revolution (after the seek). The Minix ones
seem to read 2 of 9 (1 block). They must be doing too much calculation for
the inter-sector gap (more likely, fs is). I have less experience with hard
disk drivers, but no doubt similar improvements are possible. DOS already
has them :-(. (On my new 386, Minix runs and the hard disk is about as fast
as for DOS :-). The disk has become the bottleneck.)

Summary of changes to speed up ttys (semi-chronological order)
(1) Modified clock handler to avoid unnecessary message passing and even
    save/restore. This alone gave a system-wide improvement of 14%.
(2) Eliminated unecessary locks and restores. Only the task switching runs
    with interrupts off (plus a few critical regions). This didn't make
    much difference.
(3) Re-coded tty interrupt handlers. The ttys started to work properly on
    input at 1200 baud.
(4) Changed system calls and interrupts to save the state on the user stacks
    instead of in the process table.  (The stack pointers alone are put in
    the table). mpx88.s was completely rewritten. It's much cleaner and a
    bit shorter now, and keeps the stack pointer valid at all times so the
    switch can be single-stepped by a debugger.
    fork() and exec() in mm had to be changed. The modularity of the system
    just got in the way.
(5) Introduced a new message structure for interrupt messages. It's only 10
    bytes instead of 24 and can be copied by structure assignment instead
    of cp_mess(). Made interrupt messages mostly read-only so they could be
    initialised at compile time. Achieved 2400 baud.
(6) Re-wrote interrupt() with subroutine calls to mini_send(), ready(),
    and pick_proc() in-line. It's not much longer because the subroutines
    collapsed into 3 or 4 C instructions each, but is less maintainable.
    Improved the subroutines as well. This didn't help the tty drivers
    but gave a few percent on another benchmark.
(7) Replaced the 1-deep message pointer queues in interrupt() by proper
    queues built in a small pool of interrupt messages. This was to fix
    a bug. The keyboard interrupt and tty input and output interrupts all
    used to compete for the same tty task. That's up to 3 messages when
    only 2 could be handled (it's worse with multiple ttys).
(8) Put in official mods to avoid deadlocks. No obvious problems.
(9) Moved flushing of the new interrupt message queue out of interrupt()
    into mini_rec(). It became much simpler, just 5 lines or so with
    much the same logic as reception of ordinary queued messages. At last!
    4800 baud. The flushing in interrupt() depended on repeated interrupts
    from the clock to keep it going. This gave 16 msec latency for some
    interrupts by was probably not the problem here. It was probably just
    the overhead.

Interrupt processing time for the tty input interrupt is now 170 machine
instructions.  This is before the high-level tty driver does *anything*. At
4800 baud, this consumes about 40% of the power a 5 MHz PC and leaves enough
time for the high level driver (and not much else). Zmodem only works
(at a reduced throughput) because the tty driver's buffers are larger than
zmodem's block size, so zmodem's handshaking takes effect.

To be done
(1) Improve high-level tty driver.
(2) Make handshaking work (both XON/XOFF and RTS/CTS/DTR). Now there is some
    handshaking in the low level driver, but it doesn't mesh with the high
    level one. I like to run all local terminals at the same baud rate
    (9600 now), even if handshaking throttles it way down. It saves on stty's.
(3) Consider allowing interrupts while kernel is switching tasks. This
    could reduce latency to well under 100 instructions but requires more
(4) Accumulate several characters in the low level tty driver before calling
    interrupt(). This requires some sort of timer interrupt to flush the
    queue (busy-waiting is no good).
(5) Convince the manufacturer to do (4) in hardware :-).

Bruce Evans
Internet:    UUCP: uunet!!brucee

Path: utzoo!mnetor!uunet!husc6!purdue!umd5!mimsy!chris
From: ch...@mimsy.UUCP (Chris Torek)
Newsgroups: comp.os.minix
Subject: Re: Minix Scheduler (and tty performance)
Message-ID: <10721@mimsy.UUCP>
Date: 19 Mar 88 18:22:08 GMT
References: <1002@rtmvax.UUCP> <1432@runx.ips.oz>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 15

In article <1...@runx.ips.oz> bru...@runx.ips.oz (Bruce Evans) writes:
>(4) Changed system calls and interrupts to save the state on the user stacks
>    instead of in the process table.

Saving syscall state in the user stack is arguably correct (although
4BSD Unix, at least, leaves it in a per-process kernel stack).  Saving
interrupt state on the user stack, however, is `wrong'.  coroutines
(among others) may want to leave stack stuff undisturbed at times.

One reason not to use user stacks for syscalls is the old `what if you
run out of space' argument.  I have no idea whether Minix tries to
handle this, but it is something worth considering.
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	Path:	uunet!mimsy!chris

			        About USENET

USENET (Users’ Network) was a bulletin board shared among many computer
systems around the world. USENET was a logical network, sitting on top
of several physical networks, among them UUCP, BLICN, BERKNET, X.25, and
the ARPANET. Sites on USENET included many universities, private companies
and research organizations. See USENET Archives.

		       SCO Files Lawsuit Against IBM

March 7, 2003 - The SCO Group filed legal action against IBM in the State 
Court of Utah for trade secrets misappropriation, tortious interference, 
unfair competition and breach of contract. The complaint alleges that IBM 
made concentrated efforts to improperly destroy the economic value of 
UNIX, particularly UNIX on Intel, to benefit IBM's Linux services 
business. See SCO v IBM.

The materials and information included in this website may only be used
for purposes such as criticism, review, private study, scholarship, or

Electronic mail:			       WorldWideWeb: