Multitasking theory question

Multitasking theory question

[Kai Schuelke]

Hello,

during my programming course we learned about tasks, too. One qustion that
couldn't be answered was:

Is an Ada-Task a process of the operating system or is it a kind of process
inside the whole program?

I tend to agree with the second opinion, based on what I have seen during
some personal "experiments". But it seems to depend on how the compiler
handles the tasks.
The example consisted of two tasks. In one case, using DOS and an old Ada83
compiler the second task never could do anything, because all resources
(CPU-Time) where blocked by Task #1. The same code run in a WinNT DOS-Box
and compiled with the actual Aonix compiler switched between the task with
intervals of about 1 second.

Under DOS tasks ran cooperative, under Win preemtive. Why this difference?
Is it because of the OS, the compiler or the change from Ada83 to Ada95?

Thanks a lot

Kai Schuelke

Re: Multitasking theory question

[Stephen Leake]

"Kai Schuelke" <kai.schuelke@gmx.net> writes:

> Hello,
> 
> during my programming course we learned about tasks, too. One qustion that
> couldn't be answered was:
> 
> Is an Ada-Task a process of the operating system or is it a kind of process
> inside the whole program?

This is not defined by the language. It is up to the implementation,
and both approaches have been taken.

Most Ada 95 compilers use OS threads for Ada tasks, if the OS supports
threads. This is simple, because threads within a process share an
address space, as Ada tasks do.

> I tend to agree with the second opinion, based on what I have seen
> during some personal "experiments". But it seems to depend on how
> the compiler handles the tasks. The example consisted of two tasks.
> In one case, using DOS and an old Ada83 compiler the second task
> never could do anything, because all resources (CPU-Time) where
> blocked by Task #1. The same code run in a WinNT DOS-Box and
> compiled with the actual Aonix compiler switched between the task
> with intervals of about 1 second.

This is addressing a different question; whether the runtime supports
preemption. Since DOS is neither multi-processing nor multi-threaded,
this is not surprising.

> Under DOS tasks ran cooperative, under Win preemtive. Why this
> difference? Is it because of the OS, the compiler or the change from
> Ada83 to Ada95?

The OS.

-- 
-- Stephe

Re: Multitasking theory question

[Ted Dennison]

Kai Schuelke wrote:
> during my programming course we learned about tasks, too. One qustion that
> couldn't be answered was:
> 
> Is an Ada-Task a process of the operating system or is it a kind of process
> inside the whole program?

How tasks are implemented is up to the compiler. If the OS has support 
for lightweight processes (processes that share a global memory space 
with each other, aka "threads"), then the compiler usually implements 
tasks using those. If not, then typically it will simulate them within 
the program's process.

I've even seen one compiler that implemented tasks using heavyweight 
processes and a shared memory section (this system broke down if you 
ever called a non-Ada routine that allocated memory).


> Under DOS tasks ran cooperative, under Win preemtive. Why this difference?
> Is it because of the OS, the compiler or the change from Ada83 to Ada95?

DOS has no process support of any kind, Win32 supports threads.

Re: Multitasking theory question

[AG]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:3D128BA9.8090707@telepath.com...
> Kai Schuelke wrote:

> How tasks are implemented is up to the compiler.
<<...>>
> DOS has no process support of any kind, Win32 supports threads.

What does it have to do with DOS or any OS for that matter?
Surely, a run-time system can implement whatever scheduling
it wants to (within hardware capabilities that is). After all, what
is an OS but a glorified run-time system...

Re: Multitasking theory question

[tmoran]

> What does it have to do with DOS or any OS for that matter?
> Surely, a run-time system can implement whatever scheduling
  IIRC there was an outfit in Iceland (Artek?) that was working
on Ada 83 on DOS with preemptive scheduling.  Did they ever get
anywhere?

Re: Multitasking theory question

[AG]

<tmoran@acm.org> wrote in message
news:10xR8.245$Gc5.62814264@newssvr14.news.prodigy.com...
> > What does it have to do with DOS or any OS for that matter?
> > Surely, a run-time system can implement whatever scheduling
>   IIRC there was an outfit in Iceland (Artek?) that was working
> on Ada 83 on DOS with preemptive scheduling.  Did they ever get
> anywhere?

Not sure about that one. The only Ada compiler on DOS that
I ever saw was a [very] old Meridian version. Since it was limited
[all the usual disclaimers here] to just a few tasks if I remember
correctly, and that DOS probably wasn't *the* problem, well...
It looks like it wasn't the question of what does OS support - if
you can do 15 tasks you can as wel do 255 at least :)

Re: Multitasking theory question

[Dale Stanbrough]

In article <A8xR8.23$zt.1911@news.xtra.co.nz>, "AG" <ang@xtra.co.nz> 
wrote:

> Not sure about that one. The only Ada compiler on DOS that
> I ever saw was a [very] old Meridian version. Since it was limited
> [all the usual disclaimers here] to just a few tasks if I remember
> correctly, and that DOS probably wasn't *the* problem, well...
> It looks like it wasn't the question of what does OS support - if
> you can do 15 tasks you can as wel do 255 at least :)

The Meridian Ada compiler was quite a nice compiler (i've since
thrown out my documentation) but as far as I know there was no
restriction on the number of tasks (at least not down to the level
of "a few").

dale

Re: Multitasking theory question

[AG]

"Dale Stanbrough" <dale@cs.rmit.edu.au> wrote in message
news:dale-368E8F.17334724062002@its-aw-news.its.rmit.edu.au...
> In article <A8xR8.23$zt.1911@news.xtra.co.nz>, "AG" <ang@xtra.co.nz>
> wrote:
>
> > Not sure about that one. The only Ada compiler on DOS that
> > I ever saw was a [very] old Meridian version. Since it was limited
> > [all the usual disclaimers here] to just a few tasks if I remember
> > correctly, and that DOS probably wasn't *the* problem, well...
> > It looks like it wasn't the question of what does OS support - if
> > you can do 15 tasks you can as wel do 255 at least :)
>
> The Meridian Ada compiler was quite a nice compiler

Yep. And anyways - it was the only one I could get my hands on
at the time.

> (i've since
> thrown out my documentation) but as far as I know there was no
> restriction on the number of tasks (at least not down to the level
> of "a few").

We may be talking different versions perhaps? The one I had, I tried
to implement a simple, model, elevator-control setup for students to
play with and work on basic asynch logic. (The sort of thing when
random events happen and need to be handled on the first-come
last-served :) basis).  Unfortunatly, the system was limited to just 15
concurrent tasks. While still useful, it was not exactly enough.

Don't get me wrong - it was still great for the time but, really, if you
go for the trouble of writing a tasking implementation for DOS (of
all things) why limit it to 15 tasks only? Surely, 255 shouldn't be much
harder? Or 64k?

Re: Multitasking theory question

[tmoran]

> [Meridian Ada for DOS]  Unfortunatly, the system was limited to just 15
> concurrent tasks.
  I'm confused here.  Did Meridian do 15 or whatever tasks preemptively,
or non-preemptively?
  As to DOS, IIRC there were system calls explicitly to allow you to
run while a system call was blocking its caller.  And device drivers
were written with an interrupt driven part and a part callable from
the app, so there was at least a nod toward multitasking.

Re: Multitasking theory question

[AG]

<tmoran@acm.org> wrote in message
news:WCSR8.355$Ye2.71695719@newssvr13.news.prodigy.com...
> > [Meridian Ada for DOS]  Unfortunatly, the system was limited to just 15
> > concurrent tasks.
>   I'm confused here.  Did Meridian do 15 or whatever tasks preemptively,
> or non-preemptively?

Well, to the best of my recollection, the run-time just closed down and
displayed
an error saying that it can't start another task. Always happened at 16th
instantiation.
Wasn't a question of pre-emptive or not but just a matter of starting it up.
I also seem to
recall that there was some documentation saying as much.

Re: Multitasking theory question

[Darren New]

tmoran@acm.org wrote:
>   As to DOS, IIRC there were system calls explicitly to allow you to
> run while a system call was blocking its caller.  

No. There was a system call to tell you whether the interrupt routine had
been entered while DOS was already active. If you called DOS again while
this was set, you scragged the stack frame and crashed the machine. DOS
switched to its own stack area when you called it, and switched back when
you returned, and this prevented *anything* from being reentrant in DOS.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.

Re: Multitasking theory question

[AG]

"Darren New" <dnew@san.rr.com> wrote in message
news:3D17FCEE.B24B69D8@san.rr.com...
> tmoran@acm.org wrote:

BTW, quite regardless of our differences on the subject, note how successful
the troll was:)
My news screen is covered with replies, not that it's a bad thing, but the
guy should be given
the "Troll of the week" award:)

Re: Multitasking theory question

[Mark Biggar]

AG wrote:
> 
> "Ted Dennison" <dennison@telepath.com> wrote in message
> news:3D128BA9.8090707@telepath.com...
> > Kai Schuelke wrote:
> 
> > How tasks are implemented is up to the compiler.
> <<...>>
> > DOS has no process support of any kind, Win32 supports threads.
> 
> What does it have to do with DOS or any OS for that matter?
> Surely, a run-time system can implement whatever scheduling
> it wants to (within hardware capabilities that is). After all, what
> is an OS but a glorified run-time system...

The OS can greatly effect how things work.  For example if your
run-time system implements its own threads inside a OS process
then things like the OS blocking the process on IO and other
services can interfere with the run-times internal threading.

--
Mark Biggar
mark.a.biggar@attbi.com

Re: Multitasking theory question

[AG]

"Mark Biggar" <mark.a.biggar@attbi.com> wrote in message
news:3D16B14B.2A5D8261@attbi.com...
> AG wrote:
> >
> > "Ted Dennison" <dennison@telepath.com> wrote in message
> > news:3D128BA9.8090707@telepath.com...
> > > Kai Schuelke wrote:
> >
> > > How tasks are implemented is up to the compiler.
> > <<...>>
> > > DOS has no process support of any kind, Win32 supports threads.
> >
> > What does it have to do with DOS or any OS for that matter?
> > Surely, a run-time system can implement whatever scheduling
> > it wants to (within hardware capabilities that is). After all, what
> > is an OS but a glorified run-time system...
>
> The OS can greatly effect how things work.  For example if your
> run-time system implements its own threads inside a OS process
> then things like the OS blocking the process on IO and other
> services can interfere with the run-times internal threading.

Well, yes, of course - if you take an axe and make sure
that chips are exactly that, no arguing with that sort of thing ...

However, what I was driving at is a sort of a virtual machine:
- *assuming* it runs at all, and lets you do some basic things
like Turing machine, where does an OS come into it? Sure, it
may take ages for anything to happen if the computer is sufficiently
slow but you still can implement whatever scheduling you like.

Re: Multitasking theory question

[Darren New]

AG wrote:
> However, what I was driving at is a sort of a virtual machine:
> - *assuming* it runs at all, and lets you do some basic things
> like Turing machine, where does an OS come into it?

The places where a machine isn't a turing machine. I.e., Input/Output.

> Sure, it
> may take ages for anything to happen if the computer is sufficiently
> slow but you still can implement whatever scheduling you like.

Uh, no. If you have a 3rd party device driver that blocks, then you can't do
non-blocking I/O to that device, regardless of what cleverness you set up in
your part of the program.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.

Re: Multitasking theory question

[Larry Kilgallen]

In article <3D173788.8758A005@san.rr.com>, Darren New <dnew@san.rr.com> writes:
> AG wrote:
>> However, what I was driving at is a sort of a virtual machine:
>> - *assuming* it runs at all, and lets you do some basic things
>> like Turing machine, where does an OS come into it?
> 
> The places where a machine isn't a turing machine. I.e., Input/Output.
> 
>> Sure, it
>> may take ages for anything to happen if the computer is sufficiently
>> slow but you still can implement whatever scheduling you like.
> 
> Uh, no. If you have a 3rd party device driver that blocks, then you can't do
> non-blocking I/O to that device, regardless of what cleverness you set up in
> your part of the program.

In that case, you should switch to an operating system that does not
allow device drivers to block.

Re: Multitasking theory question

[AG]

"Darren New" <dnew@san.rr.com> wrote in message
news:3D173788.8758A005@san.rr.com...
> AG wrote:

> > Sure, it
> > may take ages for anything to happen if the computer is sufficiently
> > slow but you still can implement whatever scheduling you like.
>
> Uh, no. If you have a 3rd party device driver that blocks, then you can't
do
> non-blocking I/O to that device, regardless of what cleverness you set up
in
> your part of the program.

Well, let's take a step back and regard it as a theoretical question:
If you use something like "inc ax" - how do you know if it's blocking
or not? And how does it matter? Assuming the operation completes
*at all*, I still can write whatever scheduling I like and it will work
(albeit slowly). Basically, if you would allow some minimum set of
properties (like "inc ax" terminating in a finite time) then OS has
nothing to do with it. [Again, I agree that it may and, probably, would
be impracticable, but that doesn't mean it's impossible]

On the other hand, if you mean that scheduling can't be trusted because
of external mechanical faults which are non-deterministic - well, yes true.
You can also pull the cord from the plug and see what happens.

[Guess I'd better not cross-post *THAT* comment to VMS group:) ]

Re: Multitasking theory question

[Darren New]

AG wrote:
> Well, let's take a step back and regard it as a theoretical question:
> If you use something like "inc ax" - how do you know if it's blocking
> or not? 

Um... It's not. I'm assuming the normal use of the word "blocking" here:

   "To delay or sit idle while waiting for something."

You know an increment instruction isn't "blocking" because you're not
sitting idle during its execution. You know this because you read the
instruction manual for the CPU. Similarly, you know that the MS-DOS call to
wait for a key from the keyboard is indeed a blocking call, because of
similar types of documentation.

But surely this isn't what you were asking?

> And how does it matter? Assuming the operation completes
> *at all*,

Well, now, there's the rub, isn't it? How do you know it'll complete? If
it's waiting for the user, and the user is waiting for the other thread to
progress before typing, you just deadlocked. (Assuming you're talking about
a blocking call, that is, and not [inc ax])

Again, if you have two threads, and one calls an OS routine that loops
indefinitely, and the OS isn't supporting threads, then your second thread
won't progress. Sure, you can be sophistic about it and simply define away
the problem by saying "as long as the program ends before the end of the
universe...", but then you're just Humpty Dumptying. 

If the question is "where does the OS enter into it if I do all my
scheduling myself", the answer is "when you call the OS with one thread and
the OS prevents all the other threads from running." Some OSes do, some
don't. If your OS doesn't support threads and your OS doesn't support
non-blocking I/O, then you're definitely going to get different behavior
than if neither of these are true. If you don't think this is an actual
concern, then you simply haven't tried to write multitasking programs under
a single-tasking OS. :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.

Re: Multitasking theory question

[AG]

"Darren New" <dnew@san.rr.com> wrote in message
news:3D17E1E2.AED28873@san.rr.com...
> AG wrote:
> > Well, let's take a step back and regard it as a theoretical question:
> > If you use something like "inc ax" - how do you know if it's blocking
> > or not?
>
> Um... It's not. I'm assuming the normal use of the word "blocking" here:
>
>    "To delay or sit idle while waiting for something."
>
> You know an increment instruction isn't "blocking" because you're not
> sitting idle during its execution. You know this because you read the
> instruction manual for the CPU. Similarly, you know that the MS-DOS call
to
> wait for a key from the keyboard is indeed a blocking call, because of
> similar types of documentation.

Really? If I remember correctly, even the 3.something DOS could print
while it waited for the key-press. Also, increment instruction can be
blocking
if it tries to access controlled memory (think optimistic locking for
example).

>
> But surely this isn't what you were asking?
>
> > And how does it matter? Assuming the operation completes
> > *at all*,
>
> Well, now, there's the rub, isn't it? How do you know it'll complete? If
> it's waiting for the user, and the user is waiting for the other thread to
> progress before typing, you just deadlocked.

No, you are only deadlocked if there is a circular dependance. That is -
the user must be waiting on a thread that is waiting on you. If that's the
case - tough, no amount of scheduling would help (including OS).

> Again, if you have two threads, and one calls an OS routine that loops
> indefinitely, and the OS isn't supporting threads

And suppose I call an OS routine that allows me to pull the cord from
the plug but can't handle the results? Looping indefinetely isn't what I
would
call a reasonable behaviour. It is well-defined of course, but you might
just
as well have a "full-stop" as a result of any execution.

> If the question is "where does the OS enter into it if I do all my
> scheduling myself", the answer is "when you call the OS with one thread
and
> the OS prevents all the other threads from running."

OK, I'll have to agree with that - if you really have an OS that can prevent
you
from executing arbitrary code regardless of permissions/access rightts etc
etc
that you have - then "no can do" I guess - the thing is simply broken. In
fact,
it's just not functional.

> If you don't think this is an actual
> concern, then you simply haven't tried to write multitasking programs
under
> a single-tasking OS. :-)

Will a car-engine control program written under DOS on x86 machine qualify?
:)
It probably wasn't as hard real-time as some other things around but it
certainly
was heavily multi-tasking. And I hope you wouldn't call DOS non-single
tasking.

Re: Multitasking theory question

[Darren New]

AG wrote:
 
> Really? If I remember correctly, even the 3.something DOS could print
> while it waited for the key-press.

Depends on the system call, yes. There were definitely "read a key" calls
that didn't return until a key had been pressed. There were some that did.
The ones that did aren't the ones I'm talking about, naturally.

> > If the question is "where does the OS enter into it if I do all my
> > scheduling myself", the answer is "when you call the OS with one thread
> and
> > the OS prevents all the other threads from running."
> 
> OK, I'll have to agree with that - if you really have an OS that can prevent
> you
> from executing arbitrary code regardless of permissions/access rightts etc
> etc
> that you have - then "no can do" I guess - the thing is simply broken. In
> fact,
> it's just not functional.

Err, well, no. I think you're still missing the point. Say you're trying to
write (say) a web server. The only I/O the OS supports is blocking I/O.
There's no way to say "I have three sockets open, wait for whichever one is
readable first."  The only way to make this work is either rewrite the
blocking device drivers yourself, or have threads that don't run "properly".
There doesn't need to be a deadlock, but you don't want one dropped
connection to take 5 minutes to time out before you service the next visitor
either.

> Will a car-engine control program written under DOS on x86 machine qualify?

Dunno. Were you calling anyone else's code? Or did you write all the device
drivers yourself? Of course if you don't use any blocking calls in the OS
then you can write your own scheduler.

Is it me, or do many of these discussions degenerate into "well, in spite of
the fact that what you're trying to say is obvious, here's one possible way
to read your words such that you'd be mistaken in a small number of special
cases"? If there are OS services you rely on that might possibly take an
unacceptably long time to return to the control of the user program, no
amount of user-level coding in the run-time system is going to let you
schedule another thread to run during that time. That just seems obvious
(almost tautological) to me, but it's possible I'm mistaken. 

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.

Re: Multitasking theory question

[AG]

"Darren New" <dnew@san.rr.com> wrote in message
news:3D17EF7D.40F88B17@san.rr.com...

> Err, well, no. I think you're still missing the point. Say you're trying
to
> write (say) a web server. The only I/O the OS supports is blocking I/O.
> There's no way to say "I have three sockets open, wait for whichever one
is
> readable first."

Do you have access to the timer interrupt? Can you switch into the Kernel
mode? (Hose the thing in the process perhaps, but can you?) Can you
intercept
PowerChute interrupts? If yes to all of the above, then what's the problem?
If not, ask your system administrator I guess.

>  The only way to make this work is either rewrite the
> blocking device drivers yourself

Yep, and we're back to where we started - you *can* re-write them if you
want to...

> Of course if you don't use any blocking calls in the OS
> then you can write your own scheduler.

Just where I joined this thread, thanks for confirming.

>
> Is it me, or do many of these discussions degenerate into "well, in spite
of
> the fact that what you're trying to say is obvious, here's one possible
way
> to read your words such that you'd be mistaken in a small number of
special
> cases"?

From another side of the fence, I fully agree - they do ;)

> If there are OS services you rely on that might possibly take an
> unacceptably long time to return to the control of the user program

For example, who's talking about "returning control"? Even in blocking calls
it is not really neccessary for a call to "return". Use an asynch trap and
just
abort it.

> amount of user-level coding in the run-time system is going to let you
> schedule another thread to run during that time.

Sorry? Did you just say "user-level coding in the run-time system"?
Guess I rest my case.

Re: Multitasking theory question

[Darren New]

AG wrote:
> 
> "Darren New" <dnew@san.rr.com> wrote in message
> news:3D17EF7D.40F88B17@san.rr.com...
> 
> > Err, well, no. I think you're still missing the point. Say you're trying
> to
> > write (say) a web server. The only I/O the OS supports is blocking I/O.
> > There's no way to say "I have three sockets open, wait for whichever one
> is
> > readable first."
> 
> Do you have access to the timer interrupt? Can you switch into the Kernel
> mode? (Hose the thing in the process perhaps, but can you?) Can you
> intercept
> PowerChute interrupts? If yes to all of the above, then what's the problem?
> If not, ask your system administrator I guess.




> 
> >  The only way to make this work is either rewrite the
> > blocking device drivers yourself
> 
> Yep, and we're back to where we started - you *can* re-write them if you
> want to...

As I said once...

"If there are OS services you rely on that might possibly take an
unacceptably long time to return to the control of the user program, no
amount of user-level coding in the run-time system is going to let you
schedule another thread to run during that time."

That's my position. Your position seems to be

"It's possible to write a non-blocking OS for any collection of hardware."

You see how these two statements are not in conflict?

Sure, it's possible to rewrite the blocking device drivers, given enough
time and programming competence. It also fails spectacularly when the user
unplugs the 10baseT connection and plugs in the new USB-based wireless
networking device released five years after you sold him your program.

> > amount of user-level coding in the run-time system is going to let you
> > schedule another thread to run during that time.
> 
> Sorry? Did you just say "user-level coding in the run-time system"?
> Guess I rest my case.

Err, we were talking about Ada run-time systems doing multi-tasking under a
non-tasking and potentially non-reentrant OS, weren't we? I have no idea
what 'case' you think you're resting. I also think I don't care, since I
figured out that what you're talking about and what I'm talking about are
two different situations.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.