Replies to post #21175 on e.Digital Corporation (fka EDIG)

[D.inkie]

Wongyal


A Dos cluster is a bucket ( small or large) that can be filled or not, but always takes up the same space.

Cluster buckets need to be stored next to each other.

Mos uses buckets that hold just the right amount and have no wasted space.
Mos buckets do not have to be stored in any particular order.
Mos keeps track of where the buckets are and which one is needed next.


Dos needs to sequentaly search all buckets to find what you want.

Mos buckets are directly accesed from wherever.
You can access Mos buckets faster than Dos buckets.






Contiguous array data must be stored adjacent to each other needing the starting segment block and size address of a user created file.

Linked list links data segments physically with a pointer from one segment to the next segment where ever the data segments might be on the storage media and lacks any high level of hierarchy.

Sequential access,has great characteristics of data storage with no wasted space as the individual segments can be stored tightly..or any where.

The advantage of linked lists, as compared to arrays, are that you can add or remove elements in the middle of the list easily, without shifting other items around to make room for the new element or to "fill the hole" left by the removed value.



Posted by: doni
In reply to: doni who wrote msg# 19062 Date:11/25/2002 1:01:53 AM
Post #of 21175

repost...D.inkie MOS is not devised around the cluster...

scheme like FAT. It's devised around the generic link list allocation without tables.

=========================================================
MOS... where it fits in
...there are 4 basic methods of allocation that make up the industry.

1.Contiguous array...being the simplest method to build a system around...not many devise any high level of hierarchy around it...all data must be stored adjacent to each other or touching, only needing the starting segment block and size address of a user created file...Random access.. has poor characteristics of data storage because of wasted space. A contiguous array always includes a private variable pointing to the first data segment block.

2.Linked list....this is a step above contiguous...it gives an advantage over contiguous....to the extent that data segments do not have to be stored adjacent and touching each other. It eases the confinement of contiguous storage by linking data segments physically with a pointer from one segment to the next segment...etc.. for a complete file makeup, where ever the data segments might be on the storage media, however, as a stand alone there lacks any high level of hierarchy. Sequential access,
has great characteristics of data storage with no wasted space as the individual segments can be stored tightly..or any where.
A linked list always includes a private variable pointing to the first data segment of a user created file. A double-linked list will contain a variable pointing to the last data segment in the list.. as well as the first, which lets you follow the list both forward and backward.
The advantage of linked lists, as compared to arrays, are that you can add or remove elements in the middle of the list easily, without shifting other items around to make room for the new element or to "fill the hole" left by the removed value.


These two basic structures, contiguous and noncontiguous(linked list) are generic. Utilized in both the PC and embedded environment to varying degrees... depending on the private methods of data segment starting variables....such as indexing.


3 Linked list indexed....Indexing the linked list(such as FAT (file allocation tables) ) give the maximum benefit of hierarchy to the link list...it breaks the limited bonds of contiguous and simple linked list...and allows you to incorporate the two(contiguous/noncontiguous) in a same system for many different variations. This is the typical MSFT system, all information(name,size...etc.) of a file are stored on the FAT file...now called MFT or master file tables for the New technology file system NTFS. The only problem is... the index which is a file or combination of files are an overhead burden...the files must be tracked and up dated at all times on RAM... along with free space ...which is the management of used and unused space on the storage media..
This would be considered a typical PC system and is not a real time system. The industry...through different methods...try to shrink down this type of system to fit the embedded enviornment. As for mating these types of systems to embedded flash or any LBA device...they utilize such methods as Msystems FTL(flash translation layer) which MSFT calls FFS(flash file system or now TFFS.. true flash file system) giving a hardware free mate , however, there is a burden of translation combined with the indexing overhead.. The bios of MSFT for addressing the storage media has not changed too dramatically in some time...and to an extent have the industry in a bind...with everyone doing work a rounds. Some day this will change, CHS(cylinder head sector) addressing will give way to LBA (logical block) addressing. This system would be partially physical and virtual(FAT files)

4.Indexed Inode tables...A noncontiguous system somewhat like indexed linked list.. only to the extent of indexing ....As inode file table combinations create the hierarchy of the system.
The difference is..the information of a user created file (name,size,...etc) are held within the data segments of the file, and tables of individual numbers or inodes(pointers).... point to individual data segments on the storage media making up the file... without physically linking the data segments. The problem with this type system is that there is no link list....which means that for all data segments.. you need individual pointers(inodes)from tables pointing out to individual data segments for the makeup of a file. Accordingly...as the data segments grow so do the inodes. This is an overhead burden to a system, ... its addressing scheme, however, is LBA capable.... this would be the bones of a UNIX free base system. Linux is a free Unix-type operating system originally created by Linus Torvalds with the assistance of developers around the world. This system would be all virtual(inode tables)...Without physical link.
This type of system is also utilized in the embedded environment to vearying degrees.

e.Digitals system is not like the full blown hierarchy indexed systems noted above. It utilizes physical link list...like MSFT does...but without an index...eliminating system overhead. They have devised a real time system with a scheme of hierarchy within the simple linked list. The RTOS is devised to function around it's novel DLlink file structure...utilizing a full compliment of high level API, a low level bios management(device management)...along with security at all levels of the hierarchy and format. The system is capable of attributes of MSFT and other systems currently in use today. This is a real time all physical noncontiguous unrestrained full blown hierarchy system capable contiguous storage as well....and is very un typical...and the allocation structure is patented. Very little of this system is being utilized...and they have hardly broken the surface...It can be mixed and matched with all the above.

e.digital has a private method of data segment starting variables...Patented.
doni

[doni]

Wongyal..In your analogy you're correct..."wasted space". The clusters are a fixed number...that started with a 65,000 or so count...When you divvy up a hard drive into 65,000 units(clusters) the cluster size increases as the memory size increases.

Through extinctions to FAT16 the management of larger drives came about for FAT systems.....It's all about sizing the cluster and memory to the size of expected files....MOS is also variable and can operate at below 512bytes(the industry standard sector size)...it can function at 256bytes....it all depends on the device it is managing at what variable it functions at.
Just a Note on clusters:
Clusters are made up of the standard 512byte physical sector.
A 4K cluster as you not above would be 8 x 512 or 4096bytes exactly....etc

From Edigs web site..." is independent of data and erase block sizes."


"With MOS the entire 4 liters is used up or close to it."
The 4 liters are not used up....however, you have access to the unused space....where in cluster management you do not.


There's more to it than cluster sizes....the schemes to manage the FAT tables(MSFT) and inode tables(unix)...are where the problems lay.

Lets say you want to manage media at the exact physical 512byte with a unix system....which by the way started out managing at this level. It takes a lot of virtual inodes/tables(mountains of pointers)to manage such small data segment sizes....unix for optimum performance...is noted to be best fitted to function at 4k(8 sectors) just like Cluster....depends on the media size to be managed.

MOS, because it does not function with Inode tables or FAT tables....is capable of functioning at the 256byte level...without all the pointers....yet have a full secured hierarchy.

Now imagine what you could do if a minimum Unix or MSFT sat on top of MOS!

And again there's more to it than Fat tables and inode tables...There's a problem of addressing...FAT12&16/cluster... utilize CHS or cylinder head sector addressing...as the system is derived from the hard drive business they must be translated to Block devices such as Flash. Unix utilizes block addressing or LBA logical block addressing...however, it has the overhead problems.

MOS is LBA....without overhead problems.


As to your ending question...

Less blue screen!!....for the allocation structure of MOS lends it self to fault tolerant devices....A must!! for first class devices.


doni