View unanswered posts | View active topics It is currently Thu Oct 17, 2019 1:42 pm



Reply to topic  [ 9 posts ] 
 Ready Queues 
Author Message

Joined: Sat Feb 02, 2013 9:40 am
Posts: 920
Location: Canada
I have discovered the beauty of using hardware fifos to implement ready queues for a multi-tasking OS. Previously I'd been using software managed linked lists. fifos allow the same task to be added more than once to a ready queue. This can be used to give it more run time than average. They're also very easy to use. Removing an item from the ready queue is easy: just leave it there and wait until it gets read. But check the status to see if it's actually ready when the fifo is read. If it's not supposed to be ready, then just read the next fifo entry.
The great thing is the fifos can be available in the system for other operations as well. It's a generic component, not a specialized one.

_________________
Robert Finch http://www.finitron.ca


Thu Jun 01, 2017 11:06 pm
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1277
This confuses me a bit. If you can do something with a hardware fifo, surely you can do it with a circular buffer in software? The BBC Micro's OS uses circular buffers to manage input and output.


Fri Jun 02, 2017 6:58 am
Profile

Joined: Wed Apr 24, 2013 9:40 pm
Posts: 179
Location: Huntsville, AL
But one thing that is difficult to reliably do in SW is to easily make this operation atomic.

Of course, it also possible to include an instruction specific to this type of activity to make the operation atomic and significantly faster than with a stream of interruptable instructions.

Oh, that would be very bad. Cannot forget to disable interrupts around this stream of interruptable instructions. Oh, that would add jitter to the processor's interrupt response. Oh my, what can we do: none of the options are particularly satisfying. Oh yes, we can do something like what Rob has added to his core. Unfortunately, we are still stuck with all of those commercial processors, RISC and CISC, that don't have the feature that Rob's FPGA solution provides.

Rock on Rob. :D

If I correctly recall discussions on current instruction sets I've read recently, there appears to be movement in this area with most processor cores supporting a larger number of atomic operations like the one Rob has implemented to support OS functions. Rob solution appears to be in line with current processor development directions. In addition, if I recall correctly, the Inmos transputer did most of these things in non-interruptable microcode, which seamlessly provides the atomic OS-related functionality that is missing from many modern instruction sets. Sort of supports the notion that there is a balance between RISC and CISC processor design approaches.

_________________
Michael A.


Fri Jun 02, 2017 12:18 pm
Profile

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1277
Fair point: looks like the Beeb's OS masks interrupts in the buffer handling code. See
http://mdfs.net/Docs/Comp/BBC/OS1-20/E435


Fri Jun 02, 2017 12:26 pm
Profile

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1277
BTW, I don't mean to belittle Rob's FIFO idea - offload engines can be a very good plan, and this is in a sense an offload engine.


Fri Jun 02, 2017 12:31 pm
Profile

Joined: Sat Feb 02, 2013 9:40 am
Posts: 920
Location: Canada
Quote:
surely you can do it with a circular buffer in software
Surely it could be done that way. I was going cross-eyed trying to code linked list and other OS operations in 6502/65816 assembler. Given the instruction set, I thought it would be easier to implement with hardware. It's much shorter code and faster too to use hardware support.
Quote:
But one thing that is difficult to reliably do in SW is to easily make this operation atomic.
Yes, it's not so easy as just setting the interrupt mask sometimes. Throw multiple cpu's into the mix then semaphore's need to be used. And getting atomic bus operations may not be simple, the hardware has to support it. I added support for atomic operations to the system memory controller, but that made it more complex.
I had a problem using the interrupt mask because enabling interrupts incurred a three instruction delay. This caused interrupts to be enabled for the wrong task sometimes depending on when a task switch occurred. The following code didn't work:
Code:
PLP        ; clears interrupt mask by restoring it
RTT        ; switches back to original task

Quote:
the Inmos transputer did most of these things in non-interruptable microcode, which seamlessly provides the atomic OS-related functionality that is missing from many modern instruction sets.
I noticed that large sections of code are run with interrupts disabled anyways, so a micro-coded approach seems like a reasonable alternative to getting things done quickly.

I've gone ahead and added a hardware supported timeout list as well. The timeout list component manages the timeouts using a linked list internal to the component. It has to walk a linked list and can do so while running asynchronously to the processor.

_________________
Robert Finch http://www.finitron.ca


Fri Jun 02, 2017 9:22 pm
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1277
Ah, of course, even better point about multi-cpu shared-memory systems. (The transputer is not a shared-memory system so it ends up in a slightly different situation)


Fri Jun 02, 2017 9:24 pm
Profile

Joined: Wed Apr 24, 2013 9:40 pm
Posts: 179
Location: Huntsville, AL
Great explanation of the options that you explored. Your explanation certainly provides the justification for the HW solution that you are using at the moment. I have come to appreciate the instruction set options that your own designs provide.

I certainly appreciate your blogs on the various CPU designs you are pushing around. Like BigEd, I too am somewhat in awe of the number of different designs that you are carrying along, and cut and paste is not the reason for the productivity we see.

Keep up the good work.

_________________
Michael A.


Fri Jun 02, 2017 11:06 pm
Profile

Joined: Sat Feb 02, 2013 9:40 am
Posts: 920
Location: Canada
Thanks, for the most part "my own design" stuff a lot of it has come from researching existing designs. I'm trying to get an eclectic mix of design ideas.
Quote:
I too am somewhat in awe of the number of different designs that you are carrying along, and cut and paste is not the reason for the productivity we see.

I probably have more time available than most people. I'm not sure exactly that I'd classify the mess of designs as "productive" a lot of it is still a work-in-progress as opposed to something complete. I used to have a problem with completion, but I got past it. Some people feel need to get things completed to perfection before they'll make anything available. 95% of the effort is in the last 5% of perfection. I'll wait for the right design before perfecting it :) I also have to admit I use the repository as an inexpensive backup for some files. That makes them available but it doesn't mean they're finished and working.

_________________
Robert Finch http://www.finitron.ca


Sun Jun 04, 2017 4:27 am
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 9 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


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:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software