6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Mon Nov 11, 2024 1:52 pm

All times are UTC




Post new topic Reply to topic  [ 52 posts ]  Go to page Previous  1, 2, 3, 4  Next
Author Message
 Post subject: Re: Multi tasking?
PostPosted: Wed Oct 02, 2013 2:03 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1949
Location: Sacramento, CA, USA
That sounds to me like the best general-purpose solution, BigEd. Now we just need to figure out how to shoe-horn
everything we want to do into 64KB ... man, I can still remember a time when 64K sounded like a generous amount!

Mike


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Oct 02, 2013 6:45 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8481
Location: Midwestern USA
barrym95838 wrote:
... man, I can still remember a time when 64K sounded like a generous amount!

It still is—if you know how to write tight code. :)

BTW, the PDP-11 machine that Ken Thompson and Dennis Ritchie used to rewrite UNIX into C only allocated 64KB per user. Most of that space came from lots of swapping...
--------
Edit: I had typed 8KB. I was thinking about the PDP-7.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Last edited by BigDumbDinosaur on Wed Dec 18, 2013 6:09 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Oct 02, 2013 6:53 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8481
Location: Midwestern USA
BigEd wrote:
As a counterpoint to trying to use the small stack to pass parameters: the BBC OS convention is to pass a pointer to a parameter block, in X and Y. (There's often also an operation code in A, so you don't need a different call address for each function in a class of functions.) That parameter block may contain data or pointers to data or both. I think this approach allows for arbitrary call graphs - concurrency, recursion - at the possible cost of the caller needing a tactic for memory allocation and deallocation.#

Cheers
Ed

I used to use that technique quite often back in my days of writing code for the C-128. One of my "library" functions was input, which was a programmable keyboard input routine that had keypress filtration, input limiting, defaults, etc. I seem to recall a total of 12 parameters were required to "program" the function, which I passed through a parameter table:

Code:
          ldx #<parmtab
          ldy #>parmtab
          jsr input
          bcs error

Theoretically, you can pass any number of parameters this way, limited only by RAM. I have to say I've gotten spoiled by the 65C816's 16-bit stack and the associated stack addressing instructions. I keep looking at creating a 65C02 version of my 65C816 machine language monitor but shudder at the thought of "regressing" the code to work with the 'C02's smaller instruction set and more limited stack. Maybe some day... :)

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Sat Nov 16, 2013 2:16 pm 
Offline

Joined: Tue Jul 05, 2005 7:08 pm
Posts: 1042
Location: near Heidelberg, Germany
You could even extend that parameter table idea to the mulititasking idea.

In my GeckOS operating system, I have to pointers in zeropage:
- the first one is unique within a process
- the second one is unique within a thread
The operating system switches them on thread switches.

This effectively gives local variables even in a shared memory environment. I use it for the lib6502 functionality.
It adds to the interrupt latency though.

BTW: Ed and I have recently written a small summary on multitasking on the 6502 on out google+ page: https://plus.google.com/108984290462000 ... nNiRUCTudq

André

(Edit: g+ link has a new video demo of my GeckOS multitasking OS )

_________________
Author of the GeckOS multitasking operating system, the usb65 stack, designer of the Micro-PET and many more 6502 content: http://6502.org/users/andre/


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Sat Nov 16, 2013 9:45 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8481
Location: Midwestern USA
fachat wrote:
(Edit: g+ link has a new video demo of my GeckOS multitasking OS )

Watched the video. Pretty cool!

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Nov 27, 2013 7:16 pm 
Offline

Joined: Fri Sep 28, 2012 12:27 pm
Posts: 25
Location: Boulogne Billancourt, France
Hi,

Related to "multi tasking", there is an Applesoft extension I designed which offers a concurrent coroutine behavior with a round robin strategy to switch from routine to routine.
It is not a "true" multi tasking monitor as:
a) it is not based on some hardware interrupt signals and thus can run on every Apple 2 model with Applesoft in ROM;
b) it does not have to save the *whole stack* content upon every context switch; only a tiny part of it and a bunch of page zero locations (Applesoft context description like text pointers, line numbers, error handling settings, ...)
c) it plays with the interpreter eval loop within Applesoft: the switching occurs as the count of Applesoft instructions processed by current co routine since it was entered reaches a threshold value; however a "protection" mechanism exists which forbids such switch while a "critical" section of Applesoft code is run for instance;
d) As the co routines do not have to be designed to release the CPU at multiple points in time, the mechanism could be considered as "preemptive mutli tasking";
e) As Applesoft is a flavour of MS Basic, it can be easily ported to other MS BASIC versions whether written for 6502 archictectures or not. Briefly stated, the way it works is illustrated by the sample screen dumps below (as you can see it provides other enhancements like variable default typing according to name's 1st character, but I disgress :wink: ).

g) The mechanism described here is going to be developed further in the months to come (given my contingencies) in order to implement further abilities within the engine (like resource allocation such as the keyboard or the disk drive or part of the screen or any peripheral card).
h.1) The URL to download from is this one: http://bgilon.free.fr/apple2
h.2) The files are: "D34Peersoftv15.do" for the executable and "D34Merlin - Peersoftv15.do" for the assembly source files (Merlin format) and "ShrinkIt_1.5.2.2mg" for the hard disk image to be used with CiderPress and finally a CFFA board (compact flash interface) in a real Apple2 hardware.

HTHATS (HopeThisHelpsAsTheySay)
Benoît


Attachments:
Screen1.4.8.png
Screen1.4.8.png [ 9.33 KiB | Viewed 2080 times ]
Screen1.4.7.png
Screen1.4.7.png [ 13.12 KiB | Viewed 2080 times ]
Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Dec 18, 2013 9:41 am 
Offline

Joined: Sun May 08, 2011 7:39 am
Posts: 104
TMorita wrote:
jonb wrote:
Hi everyone!

I was thinking just now... can I implement a preemptive multitasking OS on the Micro UK101? Presumably I'd need a few extra bits (RTC? Better I/O?), but I fancy it might make an interesting challenge. Start with a simple round robin scheduler (I guess this is what you'd call "co-operative multitasking") then introduce a timed interrupt (and so on).
...


No, this is not cooperative multitasking.

Cooperative multitasking is a multitasking system where the threads voluntarily give up control of the processor. Basically, each thread must call the equivalent of a sleep() function periodically so other threads can execute.

I wrote a cooperative multitasking system for the 65816 which was used on a few SNES games, including Zombies Ate My Neighbors, Big Sky Trooper, Ghoul Patrol, etc.

Cooperative multitasking works better on the 65816 rather than the 6502 IMHO because on the 65816, each thread can have its own direct page, whereas the 6502 has a fixed zero page.

Toshi


The round-robin scheduler is co-operative insofar as there is no (timed) interrupt to take control away from the currently executing task. Therefore the task must voluntarily give up control. Once you introduce a timed interrupt you have a pre-emptive multitasking scheduler.

Well, I knew what I meant, anyway! :D


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Dec 18, 2013 6:21 pm 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8481
Location: Midwestern USA
jonb wrote:
The round-robin scheduler is co-operative insofar as there is no (timed) interrupt to take control away from the currently executing task. Therefore the task must voluntarily give up control. Once you introduce a timed interrupt you have a pre-emptive multitasking scheduler.

Potentially preemptive.

Unless the jiffy interrupt service routine actually has the ability to suspend one process and restart another the system remains cooperative. In UNIX, task switching may occur any time a process returns from kernel mode to user mode. That could happen following a routine kernel call (e.g., opening a file) or could occur as an interrupt service routine (any ISR, not just the jiffy ISR) finishes up and is ready to resume foreground processing.

In practice, task switching is often occurs within the foreground part of the kernel, not in the ISR. For example, if a process calls open() there may be some delay in terms of wall clock time while the disk seeks to the block containing the inode. The process is suspended for the duration (put to sleep), at which time the kernel will start some other process that is in the ready-to-run state but is not awaiting disk I/O. Later on when the inode of the file that is to be opened is accessed, the suspended process will be restarted. The goal, of course, is to maximize MPU utilization at all times.

It's not a particularly simple procedure.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Mon Jan 27, 2014 3:48 pm 
Offline

Joined: Sun May 08, 2011 7:39 am
Posts: 104
Hmm, yes I see.. :)


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Tue Feb 11, 2014 10:47 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8539
Location: Southern California
Arlet wrote:
There's a crucial difference, though, between a list of tasks called in some fashion, and a (preemptive) multitasking OS. The difference is in the stacks. A real multitasking OS has a stack per task, while your task list has one common stack.

This difference implies a difference in usage. When you have a stack per task, it can hold implicit state information. This means you can do something like:
Code:
print string( "what is your first name?" )
input string in buffer 1
print string( "what is your last name?" )
input string in buffer 2

While waiting for keystrokes in the first 'input string' call, the OS can switch to another task. When a key is pressed, the OS switches back and ends up in the correct place, with all the state preserved on the stack.

When you have a single stack, you can't wait in the middle of a task. You first need to record the state explicitly in some data structure, and return to the main loop. When data is available, you need to retrieve the state, and figure out where you were, and what you were doing.

For some problems, solving the problem in the form of a state machine is easy, for others, it becomes really messy, so there are advantages and disadvantages to either method.

I'm doing essentially this with a cyclic executive now, and came across this topic again when looking for something else, so I thought I'd comment.

  • There's a string-editing subroutine STR_EDIT_TASK that's called from MAIN_LOOP, along with other tasks. If the edit flag variable EDIT_FLAG is clear (meaning editing is not supposed to be in progress), it just exits immediately without doing anything. Next it checks NEW_KEY_FLAG for any new keypress, and exits if there's none. So usually it will be out in a total of 4 or 6 instructions including the subroutine call and return.

  • If there is a keypress, it handles it (including cursor keys, INS/DEL, etc.) and exits. Enter and Esc do the same thing (turning off EDIT_FLAG) but the routine that wanted the string entry/edit sees which key was last and determines whether the user wanted it to accept the string as edited, or abort and go back to what was there before, discarding the edits. A half-dozen variables are used, plus the string variable itself. These include the current cursor position in the LCD, and type (insert or replace), minimun and maximum cursor positions (so the user can't type over parts of the display that they shouldn't), what the last keypress was, and whether or not it has been handled yet.

  • The keys routine KEY_TASK is separate, and handles the scanning, debouncing, shift key (which other routines don't see, as it basically only modifies other keys' output), delay before auto repeat, repeat rate, and which keys are allowed to repeat. Timings for these are not affected by other things going on.

It's really not a very complex routine, especially with program structures, and doesn't need to operate like a state machine. Audio signals continue to be produced, uninterrupted, at a 39kHz sampling rate, based on timer interrupts. There are no stack gymnastics other than a couple of levels of subroutine-return addresses on the hardware stack.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Tue Feb 11, 2014 1:28 pm 
Offline
User avatar

Joined: Mon Apr 23, 2012 12:28 am
Posts: 760
Location: Huntsville, AL
Miro Samek and Robert Ward wrote an interesting article in Embedded Systems on the subject of single stack multi-tasking in 2006. The article can be found here.

Their multi-tasking concept is not universally applicable in the sense that processor utilizing Harvard architectures may have some problems implementing the concept as presented in the article. However, a von Neumann processor like the 6502 should be able to implement the concept with little difficulty.

The basis for their multitasking concept is the use of a task that Runs To Completion (RTC). The RTC concept relies on the fact that if a task runs to completion, it may exit back to the executive/kernel using RTS or RTI. Tasks preempted by a scheduler function, are held on the common stack, and the new task is scheduled by a simple JSR.

The RTC model achieves its use of a single stack because it exits to the executive/kernel whenever it blocks. Thus, it simply does not require its stack to maintain state information. A task in a traditional multitasking environment never completes. These tasks are generally implemented as infinite loops using a while(1) {...}; construction. Because the task never completes, signalling that it no longer requires any information contained in its stack, a traditional multitasking executive must generally provide each task its own private stack.

There are some issues with the RTC model. I find that you have to be committed to building your tasks as state machines. Each task requires a static variable that defines its state. Each task requires its own dispatcher that redirects each call/restart from the executive to the appropriate subroutine, which must complete and return to the executive. Thus, state transitions are implemented within the task or the executive. If implemented within the task, the completion of a state transition should return to the executive. Handling of events is implemented in a similar manner.

Miro Samek has written extensively on this subject, and I think that his concepts warrant some consideration. The RTC concepts that he discusses in his book "Practical Statecharts in C/C++" are applicable to many problems. He takes a UML tack in presenting the material.

_________________
Michael A.


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Tue Feb 11, 2014 10:21 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8539
Location: Southern California
You or someone else posted a link to that recently, and I read it at that time, with perhaps 30% comprehension (probably from going through it too fast). Now a little more sinks in, but it still looks like it is intended for more complex systems. I'm doing projects with just a few tasks, up to about ten max, and the ones that don't have anything to do at the moment exit almost as soon as they're called. The SST method in the article still does task preemption beyond just normal interrupts that the processor services and then gets back to the same task it was working on; and the scheduler, looking for higher-priority tasks, will eat up at least several instructions' time each time, probably offsetting its own claimed benefits if the task list were as short as what I've been working on. I was surprised to read when we were discussing this kind of thing a couple of years ago that PCs may have anywhere from 50 to 200 tasks loaded at once though. In that situation, when you know most of them are domant an any given time, I can't imagine using my cyclic executive and calling them all up for nothing. It would take too long to make the rounds, and something that causes an interrupt and needs a task activated would be left waiting too long. That's a different world though, one I don't intend to ever get into. :p

Edit, 4/18/14: MichaelM, What you're saying in your last post there is what I'm doing, although I'm not doing the preemption and the prioritizing that the article talks about. The state-machine stuff recently got more complicated when I added menus and sub-menus and prompts for the user to enter info, and in some places a timed message of a couple of seconds has to be displayed in a 2x16-character LCD when transitioning states while also allowing the user to abort the function before the scheduled end of the message. The PAUSE function of a cooperative multitasker would be much easier to program for, but I did get the problem figured out, and the performance is still good and interrupts are never delayed more than two instructions' time.

Quote:
Their multi-tasking concept is not universally applicable in the sense that processor utilizing Harvard architectures may have some problems implementing the concept as presented in the article. However, a von Neumann processor like the 6502 should be able to implement the concept with little difficulty.

This is one of the advantages the 65 family has over the PICs. The 65's let you have a list of JSRs that can be directly modified, not needing indirects and data tables and tests to see when you've reached the end of the table, etc.. It's quite efficient.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Feb 12, 2014 3:20 am 
Offline

Joined: Wed Jan 03, 2007 3:53 pm
Posts: 64
Location: Sunny So Cal
Quote:
The basis for their multitasking concept is the use of a task that Runs To Completion (RTC).


At the risk of getting terribly off-topic, this is not unlike JavaScript semantics. This is particularly important for Firefox where large portions of the browser are in JavaScript, too.


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Thu Feb 13, 2014 5:22 am 
Offline

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679
The thing about SST, to my understanding, is that it's still interruptable by higher-priority tasks. The return from the higher priority task will then continue the lower priority one. Javascript's event & continuation handling model simply blocks until return before starting anything new.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor


Top
 Profile  
Reply with quote  
 Post subject: Re: Multi tasking?
PostPosted: Wed Feb 19, 2014 2:28 pm 
Offline

Joined: Wed Jan 03, 2007 3:53 pm
Posts: 64
Location: Sunny So Cal
There was an Firefox idea called supersnappy that would have been able to run a chrome task on top of a content task, actually, but it never got finished and it's all irrelevant here anyway. :)


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 52 posts ]  Go to page Previous  1, 2, 3, 4  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: