NucleoOS -- An OS for the 84+/84+SE

For months I have been catching up on my knowledge of z80 assembly, 84+ hardware, OS design, and many other things, so that I could begin to work on a project I've been considering tackling for a long time: a simple, but fully fledged operating system for the 84+ and 84+SE.  My quest finally began earlier this week, when I set up a nice little dev environment for my operating system, and started organizing my concept code for the layout and how different modules would work together.  I currently am still working on setting up hardware and such, not much more than a period of time spent fleshing out initializing components, and RTFMing at WikiTI (thanks for the site Brandon, and everyone else who submitted information there -- it's extraordinarily helpful).  

I have a few inspirations in mind for my endeavors; namely, MenuetOS (x86) for it's simplicity and very small size, KOS (z80) for its decently handled process scheduling, and GlassOS (z80) to some extent for cranking the full possible use out of the 84+'s hardware.  The name of the project is NucleoOS, since Nucleo in Italian means "core"; the main goal of NucleoOS is to be as small as possible, only holding the core necessities and a few limited "sweets" in its hull.  It is planned to sport the following:


multiprocessing capabilities

Likely the largest planned element, and placed closest to my personal expectations goals for this whole project.  Planned to support to 16 processes running at the same time, accomplished in a mix of Round-robin and Priority ranking scheduling techniques.  Each process will be given a flash page for execution in bank $4000-$7FFF, which allows for consistency in program execution space, and in a sense a slight feeling of pseudo-virtualization of process memory.  Processes taking more than 2^14 bytes of memory, and therefore not fitting into a single execution flash page, will have to act similarly to how multi-paged flash apps do on TI-OS -- manually call for swapping pages through the OS to access later chunks of code or data; single page processes will not have to worry about this at all.  Processes can have a priority level of 0-3.  The values corresponding to priorities are as follows, with some examples of the types of processes that would be in these priority ranks:

   0 - services, very idle (link-port/battery monitor)
   1 - non-interactive, background tasks (background real time clock)
   2 - interactive, CPU/IO semi-intensive (text editor)
   3 - real-time, CPU/IO intensive (games, something using the LCD for grayscale)

Rank 3 processes will get ~70% shared CPU time, 2 gets ~20%, 1 gets ~8%, and services get ~2%.  Processes are time sliced in order in a round robin formation, but get a higher throughput ratio and longer timeslice based on their rank.  Processes will have the ability to halt for a  set period of time; if the time limit is reached during another process's timeslice, and the currently running process is of a lower or equal rank, execution of the current process will be forked over to the other process of which the limit was reached; if the current process is more critically ranked, execution will be forked over to the limit-reaching process after the current process has finished its slice.

Threading within a process so that both may share the same execution space and CPU time is semi-planned out at this point; I'm thinking of having a system call to initialize new threads, with given label/addresses within the current process:

   thread_init: executed on creation of thread, ran to entirety, ignoring thread/process scheduling
   thread_run: executed on a thread's timeslice within the process timeslice
   thread_kill: executed upon the killing of the thread, and this whole set of code will be run to it's entirety, ignoring thread/process scheduling

Scheduling will be handled through hardware timer-based interrupts set at a higher speed, in IM 1.  I plan on having a Short-term/Dispatcher pair working together to shift all the processes and their execution flash page in and out of the bank; the short term scheduler keeps track of how many scheduler time slice calls from the interrupt a process has run through, to handle priority ranking effectively.  A long term scheduler is planned to keep the amount of running processes relatively clean, so that very idle processes in ranks 1-3 will be set aside until their wanted wakeup signal is reached (essentially, a signal that tells that the amount of high-ranked processes has dropped quite a bit, and there is more CPU time for them to take advantage of); services take up very little time as it is, so they won't be affected by the long term scheduler.  The long term scheduler is planned to be very minimal, only being activated every 16 or so short-term runs, to minimize slowdowns where possible.  Since the programs aren't all stored in the same chunk of memory at the same time, and therefore don't need to be swapped out per-se, there is no mid term scheduler planned.


Primitive MMU (Memory Management)

Since the 84+(SE) has code execution limit hardware, I am putting it to use so that executable code running only in user space in bank $4000-$7FFF is limited to running almost strictly in that address space.  If a jump is made outside that realm, a reset will occur, which NucleoOS will catch and determine if the reset was caused by a process, and if so will call for the process to be terminated and set the last recorded signal to be SIGMEMACC (signal message illegal memory access).  The definition between user space and priv space is solely determined by address range, and when execution veers out of user space back into priv space,  I.e. With the short term scheduler interrupt, the limits are relieved and the OS has execution space of $0000-$7FFF.

The hardware enabling this is fortunately there, but unfortunately, it is extremely limited, almost solely to page and address execution limits; therefore, it would be possible for user space programs to take control of priv space, but since the whole point of memory management and priv leveling here is to make user space programs generally safer, there's really no incentive of the user hacking into the internals, since I'll likely provide some syscalls to do some of that with services and rank 1 processes anyways.  I could always scan a program to see if it edits the limits of these ports before dispatching it, but what's the fun in making an OS like the restrictive one made by TI corporate pigs? The whole point is safety and organization, but if the user wants to go amuck with the system, they're open to do it, it's their calculator, not mine


Simple device drivers/hardware interaction modules

I plan on making hardware interfacing routines in driver modules for some devices up front (some of which are already coded):

   LCD  - provide an easy way to send/get LCD data, change some status modes, very simple sprite routines, and allow for use of the LCD's internal RAM for extra scratch space (thinking of options on how to do this, and if I'll only allow it if no other process is using it)

   Link port - not thought out much; most driver functions will likely be for sending some simple data, setting the line states, etc.

   USB - far out goal, near the end of my actual priorities.

   Timers - support for using the second and third crystal timers easily.


Coding Timeline

This project is now finally on my list of project in the works, and will stay that way; it'll likely be lower on scale than TaN, replacing most of my time being spent elsewhere on Raptor.  Don't expect super fast progress.  I hope to have basic CPU control, the LCD driver, and a few simple OS routines done in a week or so, and the goal after that will be to get full multiprocessing done by sometime in summer.  I feel ready with the knowledge base to take on such a project, and I am 100% aware of the amount of time it will require to fulfill even the basic operations.  I don't even have no plan of a GUI yet, or for that matter, even some sort of terminal emulator, so I'm hopefully not off on the wrong track of expectations that others have run into

I will be asking help in this thread as often as I will be updating; until a few months ago when I started my OS inner workings crash course, I knew nothing about how an OS should work, and I'm still far from knowing a lot.  Most questions will likely be technical ones about why some code is causing nasty stuff to happen, but I'll definitely be asking for help with advice for general OS structure.

I'm not very far into actual coding now, so if you see something in my plans above that sounds awful or plain wrong, please tell me if you can!  My only reason for taking on this project is as a personal learning experience, so I'm fine with blunt answers or advice; I'll learn more that way -- hit me with your best design rebuttals!

(PS -- sorry for being so technical with my descriptions above, I want to throw as much out here as I can for the best advice, and to show I actual put thought/research into all this; this is also all the current digital documentation available right now, most other documentation is drawn out diagrams of how things would work together)

Happy to hear of another OS starting up!

An important thing to think about is he flash chip and how it will be used. A filesystem (or other storage method is needed in order to run programs on the calc. Second thing to think about is how to put programs on the calc. Linkport is great if you have the ability to use it (which is why GlaßOS has USB and no IO code). This will only be needed once the kernel is mature and the functionality is ready for processes (you can embed test programs or code into the 8xu).

Second point, I see that you mentioned that multi-paged app functionality will be allowed. I will throw out the idea of shared libraries.

For the LCD, be careful when allowing the user to background tasks that use their own drawing. If you have one buffer and the program isn't made aware that the lcd is dirty, then you would have a process resumed and the lcd would not be updated. GlaßOS has an lcd buffer for each process and restores it when resuming. If you want only one, then I suggest some sort of signal sending or flag setting method to alert about a dirty lcd buffer.

For the memory execution protection hardware, someone correct me if needed, but this simply reboots the calc. You will not be able to catch it as having the calc reset from a battery pull starts the os the same way an execution reset starts it.

For priority 3 processes that use greyscale, would the greyscale drawing be done? Manually via a timer? OS-provided?

Also, in the current likely state of the 84pse, how will you divide up 48 KB of ram into 32 pieces, a stack and other data section per each 16 processes?

Good luck!

Good point -- I'm still in early design of the filesystem, so I'm drawing out how it might work. It would be cool to use a widely-used ext filesystem, that would probably be either too large or slow to work with; what type of system does GlassOS use?



Not a bad bit of input -- though I'm still sure some apps would have to have over 2^14 memory space available, so I might still have to go this route.




So each process has it's own LCD buffer assigned already at dispatch? Hmm, not a bad idea, actually.



Me and Fishbot talked about this last night, and basically I'm coming to the conclusion that this part of the whole thing might be chucked. My original plan was to catch it by having some sort of flag in flash memory that would update with each process switch, but that would probably slow down the short term scheduler now that I think of it, and really wear down the flash chip. If anyone familiar with how to control a reset caused by ports 25h & 26h can help with conceptualizing, that would be superb!



I'm thinking of somehow reserving the first crystal timer for this, but there's not currently as much priority for this right now so I'll leave that up to me later on to figure out.



Oh crap, I forgot to talk about RAM usage basically, the first page of RAM is planned to use a small stack, virtual BP and SP "registers", and open space for processes (for now, probably 800 bytes). The second page is basically purely for dynamically allocated memory, and the third will hold some extra space for processes that can be requested, system flags, the kernel stack, executable code space for doing hardware-related stuff that needs to be done in RAM (probably the dispatch sheduler) and a few other things. On models with extra RAM, I'm unsure what to do with it, though it'd probably be requestable RAM or even something like swap space of some sort.



Thanks, I'll definitely need it!

Sounds like a good start so far.

Since I've taken an interest in process scheduling, I have a few questions and ideas to throw out here.

First, will a process be able to run if there are any runnable higher-priority processes? For example, if a priority 3 process is waiting for CPU time, will any priority 2 processes get to run before the priority 3 process? Also, are the CPU percentages fixed per priority, or would the ratios fluctuate as the number of runnable processes changes? Say a system has 3 priority 2 processes and 1 priority 1 process. Would the priority 2 processes each get ~7% CPU while the single priority 1 process get 8% CPU?

Some time ago I learned about a simple but flexible/fair/low-latency scheduler called BFS (I won't write its full name here ). That link has a good description of how it works, but I'll summarize a few relevant points here. BFS (like most *nix schedulers) works best when processes sleep while they wait for events, such as a timer expiration or a key press, and where the kernel handles timers and keys. One a timer expires, or a key is pressed, the scheduler puts the sleeping process back on the run queue, and that process will likely have an earlier virtual deadline than the currently running process (since it's been sleeping) so it will get to run again immediately, thereby having good responsiveness.

This scheduler might be a little too "heavy" for a calculator because it has to look at the deadline of every runnable process every time the scheduler runs. However, I've found that the time slice can actually be relatively long to reduce scheduling overhead without affecting the responsiveness of interactive processes. I experimented with BFS on my Linux desktop, and even with a time slice of one second, programs were still quite responsive. I wrote my own process scheduler for Punix based on BFS, and I set the time slice to one second there too with similar results.

Of course, BFS in its current form wouldn't fit your needs as it has support for multiple scheduling policies (real-time, normal, etc) which aren't needed in your small kernel. The only scheduling policy you might need is the normal one which gives you some control over how CPU time is divided up among process of various priorities by setting the "nice" value of each process as appropriate. For example, your priority 0 process might have a nice value of 20, and your priority 3 process might be at nice -20. BFS uses priority ratios internally which are calculated from the nice value, but you could calculate the ratios directly from your priorities 0-3 instead to simplify it a bit.

GlassOS uses a custom filesystem design. i have it explained somewhere in the GlassOS thread.



GlassOS actually does this by checking (during interrupts) if the PC wanders out of 0x4000-0x7FFF and killing it (reporting the error ofc).


Yup!

Assuming you mean in the order of timeslicing, yes, it possibly could, since processes are just given time in a round circle; it could be interrupted halfway through by the second hardware timer reaching a process_wait_ms limit, and either way the rank 3 one will have more time to execute. So, it's yes, it's planned to be possible.



Wow... I didn't think of that possibility! I'm tempted to say I would keep it that way, but I think I could change the design to use ratios based on the entire left processing power, instead of in partitioned CPU chunks. So, yeah, the plan was to have them static in ratio, but now I'm rethinking that.



Hey, that's actually a pretty cool idea -- I'm surprised it works that well with such a large timeslice period, too. Just to make sure I followed correctly, it basically keeps track of living and sleeping processes, living ones getting their timeslice and sleeping ones waiting for an event, with no timeslice. Also, 'nice' values are used to pull ratios based on the current amount of processes and their ranks. A quick googling shows that nice values are usually set to 0 on quite a few *nix systems, and can be manually set from -20 to [19|20], -20 being high and [19|20] being low. Please correct me if I understood wrong



Ah, that actually seems really really smart. That way it's controlled, and while a process has the time to go awry and nasty up the system, you can at least cleanly control process ending, and throw the signal.


Thanks for the ideas and thought-provoking questions, guys!

As a small update, I now have a very simple frame for memory access violation checking in place (EDIT: for now, I'm just using AHelper's method, Fishbot further suggested I use a Grenade WDT, but unfortunately I lack the hardware besides the hacky ports 25h and 26h to mask the addressing space ), IM1 interrupt handling, a few driver updates, and started chipping away at organizing it like crazy, documenting everything like crazy, and started the part of the boot process where memory is setup; hopefully all this technical stuff will be completed in a week or so, and I can start working on the next two goals before multitasking, which are some sort of a filesystem and then making a rudimentary form of the dynamic memory allocation heap.

I was kind of surprised too, but it works well because the scheduler tends to give preference to processes that sleep a lot, which are typically the interactive processes.


Well, the scheduler only cares about the "living" (runnable) processes. Only runnable processes will be given CPU time. Something else (perhaps an interrupt) has to wake up sleeping processes and put them back on the runnable queue.

The scheduler selects a process to run in only three cases:

1. When a new or sleeping process is put onto the runnable queue
2. When the currently running process uses up its whole timeslice
3. When the currently running process voluntarily gives up the CPU

BFS calculates a new deadline and refills the timeslice only in case 2.


BFS calculates a process's deadlines only from its nice value. Higher nice values get a longer deadline. This gives nice processes less CPU time because they are selected less frequently than processes with earlier deadlines. Each increase in the nice value increases the deadline by 10%, so a nice 20 process has a deadline about 6.7 times as long as a nice 0 process, and about 45 times as long as a nice -20 process. 1.1^20 ~= 6.7, 1.1^40 ~= 45. These are the priority ratios to which BFS refers.


That's exactly right.

Sounds interesting, thanks for pointing me in that direction Christop! I'll be sure to implement my multitasking more like that, it seems as if it would be a better way almost altogether.

That being said, finally have update news! Memory now gets set correctly, with distinct RAM for the Kernel and for processes, along with setting up all my current drivers correctly, and added a few other gadgets as well. I'm finally done right now with the boot sequence until I need to add more drivers and call their setup code, so I'm off with adding some syscalls (currently only able to be used by the kernel -- processes will have to branch to RST 08h to call syscalls, using a vector table ID). I also added a simple set of PUTC routines and a respective text buffer in the kernel RAM for, the drawing routine shown in action once the system has booted:



(I'm aware the uppercase text is offbalance, I will fix tomorrow, it's a 1-px error in my source pic, I just need to add an empty row)

Yep, I'm using the ASCII set from IBM page 437 I at one point took some time ripping/converting from the picture on the wikipedia article:



It has cool characters like smilies and borders and other cool jazz, for those who don't know what it is. There will be a PUTS routine that uses all of these characters and simply puts them to the buffer, and a PUTSF routine that using the control codes like '\n' to denote a newline instead of whatever code page 437 character replaces it.

Things are running along faster now that my silly RAM setup mistake was fixed earlier (I set it all up correctly -- but I couldn't clear ram with a ldir loop, the verdict was simply because my IM1 interrupt destroyed current registers (fixed, now the shadow registers are being used almost solely for the interrupt) and broke the ldir in the middle of it's execution). Hoping to have a decent set of syscalls done by the weekend!

EDIT: got the larger font working perfectly with character and string routines, using a console buffer and buffer updater now. Also, I used a bit of a smaller sized font for the large text:



The small text I am working on is 4x6, very similar to TIOS's font in some ways. I got that one from a "purist code 437 tilesheet", which is of course credited to the author in the comments of the source.

Small update, but... boot sequence works!



(the cursor at the beginning is the Emulator (WabbitEmu) running TIOS; I dragged NucleoOS's .8xu to it during TIOS execution, which explains the cursor and slight pause between TIOS execution and NucleoOS execution -- also, NucleoK is short for NucleoKernel there )

Now, onto making the dynamic memory heap, and smaller font routines!

Woo, many hours of hard work on this since last update! Finally got small text working, settable console line wrapping, status bar mode settable (basically, lowers the amount of usable console space by one, removing the last row and allowing space for some sort of place where battery status, busy signal, etc. can be shown), easy toggling between large and small text console, and more!

It's looking great, sir! I assume that those lines are mostly just spam to test the terminal rather than actual stuff happening; is that a proper assumption? I'm quite impressed how this is progressing. It's still a constant-width font though, right?

Yes, very random stuff spamming it in the boot sequence to test it. The whole system boots up in about 5 milliseconds, and I don't plan for the graphical boot up to be more than 5 seconds total (which that test probably exceeds). The font, unlike TI-OS font, is constant-width (4*6 in small mode, 8*8 right now in large (might decrease to 6*8 eventually)). Hopefully I'll soon have it working with itoa functions showing the beginnings of the heap in action!

Edit: to give you an idea of how fast the actual sequence goes, and how spammy it is, here it is spewing about 1/3 of the data I plan on it spewing:

Not bad, not bad. But of course that leads me to further questions, such as whether you're actually scanning for and counting RAM/ROM pages, or checking the device flags/ports and using those and a lookup table to populate the RAM/ROM page stuff.

For now I'm just checking the ports, I'll eventually do a bigger scan when I'm actually trying to do stuff with a filesystem.

Good stuff. I ask because seeing that made me wonder if there would be a way to count pages, such as trying to set and read a byte on each page and seeing what happened, something along those lines. What's on the near-future NucleOS to-do list?

How difficult would this be to port to SH-3/4 devices? Is it z80 specific?

It wouldn't really make sense to directly port an OS like this to the Prizm, since things like its memory address and protection architecture are much different. For the Prizm, I'd almost rather start with a Linux kernel, build a little bootloader and set of drivers, and throw that together.

It is not possible to port this OS to another architecture since NucleoOS is written in z80 assembly and the two CPUs are very different.

OK, so it is not practical to port z80 ASM to SH3ASM? They are that different?