Re: EQP

[Jason Cozens]

Neal H. Walfield wrote:
> Hi Jason,
> 
> It seems like you've put a lot of thought into this and come up with
> some good ideas.  Thanks for sharing them with us!
> 

Thanks for the response. Sorry for any delay in replying but I work for
a bank and during the day I have no way of sending personal emails.

I've made an initial reply to the points you made. The replies may
still be a bit terse but I thought it was better to reply than to spend
a long time adding lots of detail, which hopefully can be filled in
later.

>> A basic assumption of most OS design that processors have to be kept
>> busy is questioned
> 
> Can you clarify what you mean by this?  Assuming there are no adaptive
> applications, a good rule of thumb is, if there is work to do and
> there are available resources, use them.  When there are adaptive
> applications, an adaptation should be executed if its benefit exceeds
> its cost.  (The primary benefits of not using resources are saving
> power and, resource use costs, e.g., for portable devices, network
> costs.)  In your opinion, when should processors not be kept busy?
> 

My main point is that processors should not be kept busy when it leads
to a bad programming model. This bad programming model as I see it is
multiprogramming. I see multiprogramming as bad as any real sense of
time is lost and all the problems of locking and synchronization arise.

A processor can be programmed as a real time device and as such
processors have been used in safety critical applications. Most car
brake systems have at least two microprocessors for example.

I think that the assumption that processors should be kept busy stems
from the early days when processors were really expensive, this lead
to multiprogramming which as I see it has now fed back on itself and
caused processors to become more expensive than they need to be so they
can now support multiprogramming.

>> and instead it is assumed that there is an abundance
>> of very simple processors (1000+) and communication is cheap.
> 
> Commodity systems with 1000+ processors are, I suspect, more than 10
> years off.  Current thinking is that many-core systems will be
> heterogeneous, not homogeneous.  Further, they will look like
> distributed systems for which communication among nodes is not that
> cheap.  Moreover, they will use NUMA architectures--if they have
> shared memory at all.
> 

This relates back to my last point. Processors are overly complex and
therefore overly expensive. My memory might not be very reliable but
when working with processors such as the 68000 the price of these was in
the region of $1.

The sort of thing I'm looking at are things such as the CM-X300. These
are quite expensive at the moment (in small quantities) about 61
dollars but only by two orders of magnitude. See:

http://www.compulab.co.il/all-products/html/products.htm

The systems I'm envisioning would be message based without any shared
memory. I started using Erlang a couple of months ago and this seems to
fit this approach. The only problem here is that the programming model
invades the application. As a first step what I'd like to show is that
programs can be run on a system that automatically runs each new
instance of a program on a new processor.

> Would you please sketch in a bit more detail what class of systems
> your algorithm is targeting.
> 

I'm not targeting any class of systems specifically. What I'm
targeting is the general purpose OS. So can a system be built that has
the versatility of a general purpose OS i.e. it can create unlimited
process architectures but have the reliability of real time safety
critical systems and hopefully be easy to program?

In terms of the Hurd this could possibly mean each translator was
created on its own processor.

>> The versatility of a general purpose operating system often comes at the
>> cost of reliability and predictability largely stemming from the
>> non-deterministic programming model that is a result of its design. The
>> non-determinism arises from the multiprogramming model. The ordering of
>> process execution is controlled by the operating system.
> 
> I'm missing a section describing how your approach enables a
> deterministic programming model.  Also, I'm missing a section on how a
> program is expected to interact with the scheduler.  I feel that I
> need this information before I can provide useful comments on your
> approach.
> 

The sole purpose of an Eager Queue Protocol is to do the scheduling or
resource allocation. Each processor (or resource) has at least one
QCell. If a processor is available to do work it notifies its QCell
which then JOINs an eager queue notifying the Eager Queue that its
processor is available for work. When a processor is working and wants
to REQUEST the use of another processor it also does this through a
QCell. When a processor ACCEPTS a REQUEST it is not longer available
for work.

Processors are also free to leave an eager queue using an EXIT or
DECLINE message.

As an analogy an eager queue is like an employment agency. A processor
can submit its CV to the agency and it can make requests of other
processors through the agency. When a request is made the agency will
give the requesting processor the address of the worker processor and
the requesting processor will negotiate the contract with the worker
outside of the agency. In this way the only purpose of the agency is to
put processors in contact with each other.

Once processors are allocated their unavailability for work is recorded
and it is up to them to join back in for scheduling when they are ready.

In this way when a processor is busy it behaves like a real time device
and is no longer interrupted by the scheduler.

>> The major problem is how to manage the pool of processors. This can be
>> implemented by doing away with the centralised scheduler and letting
>> each processor manage itself. The problem is now really one of resource
>> allocation rather than scheduling.
> 
> What's the difference between scheduling and allocation?
> 

Nothing really, only I try to reserve scheduling for time slicing a
processor whereas resource allocation I try to use more for sharing
out "physical" resources.

Jason.