In the first post I described the basic Protel language. In the mid 1990s it was extended with object oriented capabilities. This was done in a number of phases and was tied into the development of a project at Nortel called Generic Services Framework (GSF). This was an object oriented reimplementation of 'call processing' on the DMS with wide scope and a huge development team. Nortel even created an 'Object Center' somewhere in Canada with a helpline that confused designers could call to get OO Protel advice. I suspect that today it would be a 'Center of Object Excellence'. I heard that the GSF project was not an unqualified success, but it did drive the evolution of Protel-2 which was used later in other products. In retrospect it seems that GSF and Protel-2 were more motivated by the Objects-with-everything zeitgeist than any particularly compelling benefits.
Protel-2 supports single inheritance with a common root class called $OBJECT. Methods can be explicitly declared to be overridable in base classes, similarly to C++'s virtual keyword. It does not support operator overloading, or overloading method names with different signatures. It supports fully abstract classes.
Like Eiffel, Protel-2 allows parameterless methods which return a value to be called without parentheses. This allows data members to be refactored to be read directly or via an accessor function method without changing the callers. I'm not sure how valuable this is in practice, especially as it does not affect assignment. Perhaps some Eiffel practitioners have experience of finding this useful? Protel-2 methods can be declared to be read-only with respect to the object instances they operate on, in a similar way to specifying const-ness in C++.
The GENERIC keyword in Protel-2 allows class definitions to be parameterised by type. This allows the creation of type-safe generic collection classes and datastructures. The type parameterisation is similar to the Generics mechanism in Java, in that it is effectively a compile-time-only mechanism. The compiler generates a single underlying class implementation and checks type-correctness at compile time. A side-effect is that all access to the parameterised class must be made via a pointer. This fits well with the requirement for online load-replacing implementation etc, but it offers much reduced power compared to C++'s code-generation style templating mechanisms.
As with most C++ implementations, Protel-2 objects contain a vtbl pointer in the first word of their data followed by data members of superclasses and the class instance. On XA-Core, this sometimes presented a problem in that the normal transactional memory ownership mechanism could create a bottleneck when used for the vtbl ptr, but often data in the rest of the class should use the transactional memory mechanism. To deal with this, special libraries were created to allow the object header to be stored in WRITEBLOCKING memory and the rest of the object to be stored in BLOCKING memory.
That's scraping the bottom of the barrel on Protel-2 information in my head. I thought there was more there (or maybe just something more interesting). At least I've written it down.
Showing posts with label protel. Show all posts
Showing posts with label protel. Show all posts
Thursday, 16 April 2009
Sunday, 12 April 2009
Protel I
Protel is the PRocedure Oriented Type Enforcing Language used for most DMS software. Currently there's not much information available about it online. An early paper describing the language is referenced here, but is hidden behind a subscription-only portal. Wikipedia offers a very minimal definition of the term but little else. I think there's some good stuff that should be recorded so I'll attempt to describe what I found interesting.
So what is Protel like? I'm told that it's similar to Modula-2 and even Modula-3 and it's true that it shares explicit BEGIN / END block syntax with Pascal, and all code is divided into modules.
One of the most basic differences between Protel and these languages is its use of the composite symbol '->' or 'Gozinta' (Goes into) for assignment. This eliminates any confusion between assignment and equality testing. This 'removal of ambiguity' is a key pattern in the design of Protel. Similar manifestations of the pattern are the rules :
Protel modules contain one or more source code files which can export definitions for use by other modules. Different source files within a module can be arranged into trees which control compile order within a module. Modules often have multiple levels of interface source files - most public and general APIs in the top level, more private and specific APIs in the lower levels. Access to definitions in each interface file can be controlled independently if required.
Basic Protel supports built-in and user defined types, pointers, arrays, an 'array slice' descriptor mechanism, and a novel extensible fixed-size type called an Area as well as some type-reflection capabilities.
A Protel DESCriptor is used to refer to a range of elements in an array of. It is used in the same way an array - with a subsript as an lvalue or rvalue to an expression (though the usual meaning of those terms is confused by the Gozinta operator!). The compiler is aware of the of the slice being DESCribed, and by inference the size of the elements. In the storage allocated to the DESC itself, it stores a pointer to the zeroth element and an upperbound in terms of elements. In this way it can provide bounds checking on accesses through the DESC. When an out-of-bounds exception is hit, the actual upperbound and the supplied subscript are available in the exception report, often allowing debugging straight from the trace. The array slice abstraction can be a nice way to deal with zero-copy in a protocol stack.
Protel offers the BIND keyword which can be used to define a local-scope alias to some variable instance. It's use is encouraged to reduce keystrokes, and it is also useful for indicating to the reader and the compiler that some dereferencing operations need only be performed once even though the referenced value is used multiple times. A side effect of its use is that it reduces the tension between short, easily typed and long, descriptive variable names, allowing long descriptive names to be shortened in use when necessary. Of course this can add to ambiguity and confusion.
Protel supports typed procedure pointers with an explicit type classifier - PROCVAR. I suspect that this type classifier exists to improve code readability rather than for any syntactic necessity as PTR to PROC can be used similarly. PROCVARs are used heavily in SOS code to allow applications to override behaviours and extend OS behaviour. SOS has unique terms for the use of procedure pointers :
As well as supporting standard composite structures similar to a C struct, Protel supports the concept of an Area which can be used to implement a form of type-inheritance. An AREA is similar to a struct, but contains as part of its definition a storage size in bits, as well as zero or more members. At compile time, it is checked that the declared member's types fit within the size given, and instances will be created with the size given. Other modules can declare further areas which REFINE this area, and add definitions to the original AREA. The compiler will check that the complete set of member definitions continue to fit in the bit size of the original AREA. This mechanism can be used to create trees of hierarchically related data types which is very useful for code modularity and extensibility as well as more basic optionality similar to a C union. Putting procedure pointers into the Area gives a rather rough extensible virtual-method mechanism in-language. However, most DMS software designers used AREA refinements for hierarchically varying data rather than allowing control flow overrides.
Protel offers some reflection capability via the TYPEDESC operator. It is applied to a type and returns a structure which can be used to determine type names, bit offsets etc. SOS supports an online extensible data dictionary which uses TYPEDESC to track types and their relationships. It is version aware and is used by Table Control and for data reformatting between software releases.
Combining PROCVARs and REFINEd AREAs allowed extensible systems to be built fairly easily without OO techniques built into the language. However, the explicit nature of the PROCVARs, the requirement to define up-front bitsizes for refinable areas and the general micromanagement required to define, initialise and use 'object' hierarchies made from these components discouraged most designers from using them in this way. Providing tools at this atomic level encouraged each designer to try their own combination of hard coding, ProcVars, extensible areas, pointers-to-extension-structs, pointers-to-data-structs-with-procvars etc. More manual visualisation effort was required to grasp these mechanisms than would be required for an equivalent language with OO extensions.
I think PROTEL was fairly state-of-the-art when it was introduced for DMS software. Especially considering its planned use for telecoms switching equipment, it is a very general purpose language, not visibly oriented towards telecoms. It has a fairly clean split between language features and runtime libraries. Perhaps if it had been more widely known of beyond the confines of Nortel/BNR then it could have enjoyed some life of its own? I believe it is still being actively used - these days SOS images run in virtualised environments with code written by outsourced employees paid by a broken company, but I imagine there must still be patches getting written. However the outlook looks bleak. With Nortel on the rocks and apparently no interesting information about Protel available on the web (except this blog of course :) ), it looks like it could vanish after 30 years.
In the mid to late nineties, Nortel added object orientation to Protel, I'll talk briefly about that in a future post.
So what is Protel like? I'm told that it's similar to Modula-2 and even Modula-3 and it's true that it shares explicit BEGIN / END block syntax with Pascal, and all code is divided into modules.
One of the most basic differences between Protel and these languages is its use of the composite symbol '->' or 'Gozinta' (Goes into) for assignment. This eliminates any confusion between assignment and equality testing. This 'removal of ambiguity' is a key pattern in the design of Protel. Similar manifestations of the pattern are the rules :
- No operator precedence rules
Unlike C, Protel assigns no built-in relative precedence to various operators. All expressions are evaluated left-to-right, and the programmer must use brackets explicitly to specify non l2r evaluation. - No preprocessor
There is no standard preprocessor and therefore no macro language. The compiler supports some limited compile time expression evaluation including sizeof() for types etc. This avoids context specific semantics for source code and non-visible code expansion - No support for pointer arithmetic
Where a pointer is to be treated as referring to some element of an array, the descriptior mechanism, which includes bounds checking, is to be used rather than pointer arithmetic. - Control structure specific end-of-block keywords
Rather than a single END keyword, Protel employs ENDBLOCK, ENDPROC, ENDWHILE, etc. to aid code readability. - No 'keystroke reduction mechanisms'
C's ++, += etc.
Protel modules contain one or more source code files which can export definitions for use by other modules. Different source files within a module can be arranged into trees which control compile order within a module. Modules often have multiple levels of interface source files - most public and general APIs in the top level, more private and specific APIs in the lower levels. Access to definitions in each interface file can be controlled independently if required.
Basic Protel supports built-in and user defined types, pointers, arrays, an 'array slice' descriptor mechanism, and a novel extensible fixed-size type called an Area as well as some type-reflection capabilities.
A Protel DESCriptor is used to refer to a range of elements in an array of
Protel offers the BIND keyword which can be used to define a local-scope alias to some variable instance. It's use is encouraged to reduce keystrokes, and it is also useful for indicating to the reader and the compiler that some dereferencing operations need only be performed once even though the referenced value is used multiple times. A side effect of its use is that it reduces the tension between short, easily typed and long, descriptive variable names, allowing long descriptive names to be shortened in use when necessary. Of course this can add to ambiguity and confusion.
Protel supports typed procedure pointers with an explicit type classifier - PROCVAR. I suspect that this type classifier exists to improve code readability rather than for any syntactic necessity as PTR to PROC can be used similarly. PROCVARs are used heavily in SOS code to allow applications to override behaviours and extend OS behaviour. SOS has unique terms for the use of procedure pointers :
- GATE
SOS name for a Procedure Variable that is expected to be set by some other module. It is a 'gate' to some other implementation. Usually gates are defined in lower-level modules. - TARGET
SOS name for a procedure implementation referenced from a GATE. This is the 'target' of a call to a 'gate'. Usually targets are defined in higher-level modules - ASPECT
SOS name for a structure containing a number of procedure variables. This can be thought of as an 'interface' in the Java sense - a set of method signatures. Often a lower-level module would provide an API for a higher-level API to add some functionality including some data and perhaps an 'aspect' of procedure variables.
As well as supporting standard composite structures similar to a C struct, Protel supports the concept of an Area which can be used to implement a form of type-inheritance. An AREA is similar to a struct, but contains as part of its definition a storage size in bits, as well as zero or more members. At compile time, it is checked that the declared member's types fit within the size given, and instances will be created with the size given. Other modules can declare further areas which REFINE this area, and add definitions to the original AREA. The compiler will check that the complete set of member definitions continue to fit in the bit size of the original AREA. This mechanism can be used to create trees of hierarchically related data types which is very useful for code modularity and extensibility as well as more basic optionality similar to a C union. Putting procedure pointers into the Area gives a rather rough extensible virtual-method mechanism in-language. However, most DMS software designers used AREA refinements for hierarchically varying data rather than allowing control flow overrides.
Protel offers some reflection capability via the TYPEDESC operator. It is applied to a type and returns a structure which can be used to determine type names, bit offsets etc. SOS supports an online extensible data dictionary which uses TYPEDESC to track types and their relationships. It is version aware and is used by Table Control and for data reformatting between software releases.
Combining PROCVARs and REFINEd AREAs allowed extensible systems to be built fairly easily without OO techniques built into the language. However, the explicit nature of the PROCVARs, the requirement to define up-front bitsizes for refinable areas and the general micromanagement required to define, initialise and use 'object' hierarchies made from these components discouraged most designers from using them in this way. Providing tools at this atomic level encouraged each designer to try their own combination of hard coding, ProcVars, extensible areas, pointers-to-extension-structs, pointers-to-data-structs-with-procvars etc. More manual visualisation effort was required to grasp these mechanisms than would be required for an equivalent language with OO extensions.
I think PROTEL was fairly state-of-the-art when it was introduced for DMS software. Especially considering its planned use for telecoms switching equipment, it is a very general purpose language, not visibly oriented towards telecoms. It has a fairly clean split between language features and runtime libraries. Perhaps if it had been more widely known of beyond the confines of Nortel/BNR then it could have enjoyed some life of its own? I believe it is still being actively used - these days SOS images run in virtualised environments with code written by outsourced employees paid by a broken company, but I imagine there must still be patches getting written. However the outlook looks bleak. With Nortel on the rocks and apparently no interesting information about Protel available on the web (except this blog of course :) ), it looks like it could vanish after 30 years.
In the mid to late nineties, Nortel added object orientation to Protel, I'll talk briefly about that in a future post.
Saturday, 28 March 2009
What is SOS? Part III
Part 1 Part 2
Online code patching and extension
A SOS system is comprised of modules, which contain code and various data segments and are vaguely similar to shared libraries or DLLs. Each function in a module has a function pointer stored at some known offset in a code header segment. The actual machine code for the function is stored in a different segment of the module. This indirection requires that all procedure calls involve a pointer dereference, but gives the flexibility to change the implementation of any procedure at any time. The code and data segments in a module also include limited 'spare' space, so that a number of extra global data variables and functions can be added to a module online. This, coupled with the ability to load completely new modules with arbitrary code and data makes a SOS system completly runtime-patchable, with all behaviours modifiable online. Online upgrade of a running module is referred to as load-replacement. In development it is used to test and debug code, and in deployment it is used to patch code, and to add small new features.
Run-time code modification is made managable by the cooperation of the standard source code control system (PLS), the Protel language compiler and linker, and SOS. At compile and link time, metadata about the header contents and sizes, and the version of source compiled is included in the module file. When SOS is asked to load-replace the module, it compares the new module with the existing module and will only allow the load-replace if it can be done safely. When a module is replaced, SOS updates its module metadata with the new module's version etc.
SOS also includes a patch management system which tracks the state of applied patches. Patches use the basic module load-replacement system in a controlled and automated way to :
Writing SOS patches is quite an art, and whole teams that write nothing but patches existed in Nortel's good times. Often the patch specialists were very technically capable and innovative, being aware of the innards of SOS and able to deal with the extra dimensions of design visualisation required to consider patch application and later removal. However, extended exposure to writing patches in the convoluted style required for safe application and removal tends to corrode a designer's sense of elegance and abstraction.
'Relational' data access system
SOS includes a table based data access layer called 'Table control'. This layer supports interactive and batch access to tables. Tables include key columns and non-key columns with a flexible type system, including inheritance. Tables are statically defined with a good deal of flexibility in the implementation of the mapping onto the underlying data source. Table control supports separate data representations at 'External', 'Logical', 'Data' and 'Physical' layers. These abstractions give great freedom to decouple the external, user visible view of the data from the internal constraint optimised storage of the data. Table control was initially designed to give a standard way to store and retrieve DMS configuration information, but over time in different products is used to give standardised access to huge databases of mobile subscriber information etc. The Table Control API was later built on to implement external data provisioning and management systems, and is a large part of the online software upgrade process.
Despite being table and column oriented, table control is only 'relational' in a limited sense. There is no SQL-style declarative language for querying data stored in tables, and no standard way to 'join' tables. However, foreign key constraints can be enforced, and DMS supports a basic scripting language which can be used to write scripts to automate cross-table analysis and maintenance.
User model
SOS supports multiple interactive user sessions, connected via telnet or older technologies. Users can have various permissions with respect to commands, table access etc, and all user activity can be logged.
Online software upgrade
Theoretically, module load-replacement can be used to upgrade software, but in practice it is only used for bug fixes and small features with economic or time-pressure reasons for in-release delivery. Writing all code to be online replacable against old code adds an excessive burden to the design and test cycles.
SOS supports online upgrade of duplex systems via the ONP process (One Night(mare) Process). What happens is :
From the application designer's point of view, they need to consider :
SOS applications generally support direct upgrade over 3 versions. In a DMS system comprising a number of smaller SOS based systems, generally the upgrades start at the leaves of the tree of systems (peripherals), and work back towards the Computing Module (CM). This implies that each system must be willing to accept old-version protocol interactions from systems higher in the tree than it, but need not worry about protocol versions for systems lower in the tree (Assuming the usual computer-science leaves-at-the-bottom tree layout). Given that individual system complexity increases as you go 'up' the tree to the root, this is a good arrangement.
Online multithreaded breakpoint capable debugger
SOS supports interactive use and one application users can use is an interactive breakpoint and tracepoint capable debugger. This tool allows a running system to be inspected, and code and data to be modified on the fly. Break and tracepoints can be made data-conditional and can use thread (process) ids to be thread conditional. The debugger also has some knowledge of symbols and offsets within modules.
Full debugging access with breakpoints is not usually made available for deployed systems as the risk of accidental damage is too great.
Well that's been a quick tour of SOS. It's an interesting system with very little documentation outside of Nortel. My own memories of it are fading fast, so please excuse mistakes and the lack of detail here. I don't intend to blog about the system in-general any more, but may cover some specific details that are of interest.
(Well of interest to me, as no-one else seems interested so far :) )
Online code patching and extension
A SOS system is comprised of modules, which contain code and various data segments and are vaguely similar to shared libraries or DLLs. Each function in a module has a function pointer stored at some known offset in a code header segment. The actual machine code for the function is stored in a different segment of the module. This indirection requires that all procedure calls involve a pointer dereference, but gives the flexibility to change the implementation of any procedure at any time. The code and data segments in a module also include limited 'spare' space, so that a number of extra global data variables and functions can be added to a module online. This, coupled with the ability to load completely new modules with arbitrary code and data makes a SOS system completly runtime-patchable, with all behaviours modifiable online. Online upgrade of a running module is referred to as load-replacement. In development it is used to test and debug code, and in deployment it is used to patch code, and to add small new features.
Run-time code modification is made managable by the cooperation of the standard source code control system (PLS), the Protel language compiler and linker, and SOS. At compile and link time, metadata about the header contents and sizes, and the version of source compiled is included in the module file. When SOS is asked to load-replace the module, it compares the new module with the existing module and will only allow the load-replace if it can be done safely. When a module is replaced, SOS updates its module metadata with the new module's version etc.
SOS also includes a patch management system which tracks the state of applied patches. Patches use the basic module load-replacement system in a controlled and automated way to :
- Load-replace existing modules to add hooks into existing code
- Load new modules to contain modified functionality and state storage space
- Execute patch application and removal steps
Writing SOS patches is quite an art, and whole teams that write nothing but patches existed in Nortel's good times. Often the patch specialists were very technically capable and innovative, being aware of the innards of SOS and able to deal with the extra dimensions of design visualisation required to consider patch application and later removal. However, extended exposure to writing patches in the convoluted style required for safe application and removal tends to corrode a designer's sense of elegance and abstraction.
'Relational' data access system
SOS includes a table based data access layer called 'Table control'. This layer supports interactive and batch access to tables. Tables include key columns and non-key columns with a flexible type system, including inheritance. Tables are statically defined with a good deal of flexibility in the implementation of the mapping onto the underlying data source. Table control supports separate data representations at 'External', 'Logical', 'Data' and 'Physical' layers. These abstractions give great freedom to decouple the external, user visible view of the data from the internal constraint optimised storage of the data. Table control was initially designed to give a standard way to store and retrieve DMS configuration information, but over time in different products is used to give standardised access to huge databases of mobile subscriber information etc. The Table Control API was later built on to implement external data provisioning and management systems, and is a large part of the online software upgrade process.
Despite being table and column oriented, table control is only 'relational' in a limited sense. There is no SQL-style declarative language for querying data stored in tables, and no standard way to 'join' tables. However, foreign key constraints can be enforced, and DMS supports a basic scripting language which can be used to write scripts to automate cross-table analysis and maintenance.
User model
SOS supports multiple interactive user sessions, connected via telnet or older technologies. Users can have various permissions with respect to commands, table access etc, and all user activity can be logged.
Online software upgrade
Theoretically, module load-replacement can be used to upgrade software, but in practice it is only used for bug fixes and small features with economic or time-pressure reasons for in-release delivery. Writing all code to be online replacable against old code adds an excessive burden to the design and test cycles.
SOS supports online upgrade of duplex systems via the ONP process (One Night(mare) Process). What happens is :
- Hardware sync-match is dropped, splitting the system into two separate systems, one active, the other inactive.
- The inactive side is rebooted with the new software
- Bulk personality and state data from the active side is transferred across to the inactive side, potentially involving data reformats for changed or extended schemas.
- Once all bulk data is transferred, up to date state data transfer starts
- Once all components agree that state transfer is reasonably up-to-date
- New Active side activity is stopped
- All remaining state is transferred
- Inactive side becomes active side (SWitch of ACTivity). IO systems are reconnected to new active side. - Users perform acceptance testing on the new system for a limited period
- If users decide to revert :
- Modified state is transferred back to newly inactive side
- SWACT is performed in reverse - If users decide to continue :
- Newly inactive side is dropped and hardware sync-match is restored.
From the application designer's point of view, they need to consider :
- Data reformats
Table control can automate some conversions which map into type-promotions. More complex conversions can be performed in user-code callbacks. - State transfer
Essential state can be transferred around SWACT using user-code callbacks - Protocol compatibility
Newer software versions must support old protocol versions until all parties can deal with newer versions. - Upgrade-abort implications
If upgrade is reverted then data and states which only exist in the new version must be avoided or dealt with.
SOS applications generally support direct upgrade over 3 versions. In a DMS system comprising a number of smaller SOS based systems, generally the upgrades start at the leaves of the tree of systems (peripherals), and work back towards the Computing Module (CM). This implies that each system must be willing to accept old-version protocol interactions from systems higher in the tree than it, but need not worry about protocol versions for systems lower in the tree (Assuming the usual computer-science leaves-at-the-bottom tree layout). Given that individual system complexity increases as you go 'up' the tree to the root, this is a good arrangement.
Online multithreaded breakpoint capable debugger
SOS supports interactive use and one application users can use is an interactive breakpoint and tracepoint capable debugger. This tool allows a running system to be inspected, and code and data to be modified on the fly. Break and tracepoints can be made data-conditional and can use thread (process) ids to be thread conditional. The debugger also has some knowledge of symbols and offsets within modules.
Full debugging access with breakpoints is not usually made available for deployed systems as the risk of accidental damage is too great.
Well that's been a quick tour of SOS. It's an interesting system with very little documentation outside of Nortel. My own memories of it are fading fast, so please excuse mistakes and the lack of detail here. I don't intend to blog about the system in-general any more, but may cover some specific details that are of interest.
(Well of interest to me, as no-one else seems interested so far :) )
Tuesday, 6 January 2009
What is SOS? part II
Part 1 Part 3
Resource Ownership Model
SOS implements an extensible resource ownership module. System resources such as memory, IPC 'mailboxes', semaphores and any user-defined resource are owned by either a loaded module or a running process. Process death results in process owned resources being freed. Module unload results in module owned resources being freed. Processes are owned by Modules.
Since all processes in SOS share memory by default (more like threads in other OS), a mechanism for cleaning up resources on process death is very useful.
Applications can arrange to have their own resources owned by a process or a module using a mechanism confusingly called 'Events'. This mechanism guarantees a callback on process death or module unload allowing arbitrary cleanup. This is essential as processes can exit at any point with no stack cleanup due to exceptions (divide by zero, bus error etc.).
Prioritised proportional scheduling
SOS processes are each placed in a process class. Each class has a guaranteed share of CPU where all process class shares sum to 100% of available CPU. Additionally, all process classes have a relative priority.
The scheduler chooses which process to run next based on answering the question "What is the highest priority class with both a runnable process and time left in it's CPU share?".
The guaranteed share mechanism is used to ensure that all process classes regularly get some share of CPU time even in a heavily loaded system, while still providing priority to high urgency tasks. This allows the system to avoid throughput or latency degradation as load increases.
The placement of processes into process classes is generally fixed at design time. The set of process class guaranteed shares (called a scheduler template) is also generally fixed, but is changed between restarts and normal operation.
Application control of scheduler pre-emption
The SOS scheduler implements pre-emptive multitasking on a single CPU core, changing the running process periodically. Processes can temporarily stop pre-emption occurring via the rather wordy setunpreemptable() call. This can be used to demarcate critical regions in code, where atomic actions are performed. All other processes can only observe the state of memory before the call to setunpreemptable(), or after a call to setpreemptable().
Since all other processes are excluded from running while the current process is unpreemptable, it is important that only bounded amounts of computation are performed while unpreemptable. To enforce this, SOS implements an unpreemptable timer, of the order of tens of milliseconds which stops the running process with an exception if it remains unpreemptable for longer than this. For this reason, activities like blocking IO and dynamic memory allocation cannot reliably be performed while unpreemptable.
Most applications are collections of message driven state machines, and run unpre-emptably in bursts, processing messages, updating state and sending responses. As well as giving low-overhead mutual exclusion, making applications non-blocking with control over pre-emption maximises the instruction cache hit rate and improves data cache locality.
That's enough for now, I'm boring myself !
Resource Ownership Model
SOS implements an extensible resource ownership module. System resources such as memory, IPC 'mailboxes', semaphores and any user-defined resource are owned by either a loaded module or a running process. Process death results in process owned resources being freed. Module unload results in module owned resources being freed. Processes are owned by Modules.
Since all processes in SOS share memory by default (more like threads in other OS), a mechanism for cleaning up resources on process death is very useful.
Applications can arrange to have their own resources owned by a process or a module using a mechanism confusingly called 'Events'. This mechanism guarantees a callback on process death or module unload allowing arbitrary cleanup. This is essential as processes can exit at any point with no stack cleanup due to exceptions (divide by zero, bus error etc.).
Prioritised proportional scheduling
SOS processes are each placed in a process class. Each class has a guaranteed share of CPU where all process class shares sum to 100% of available CPU. Additionally, all process classes have a relative priority.
The scheduler chooses which process to run next based on answering the question "What is the highest priority class with both a runnable process and time left in it's CPU share?".
The guaranteed share mechanism is used to ensure that all process classes regularly get some share of CPU time even in a heavily loaded system, while still providing priority to high urgency tasks. This allows the system to avoid throughput or latency degradation as load increases.
The placement of processes into process classes is generally fixed at design time. The set of process class guaranteed shares (called a scheduler template) is also generally fixed, but is changed between restarts and normal operation.
Application control of scheduler pre-emption
The SOS scheduler implements pre-emptive multitasking on a single CPU core, changing the running process periodically. Processes can temporarily stop pre-emption occurring via the rather wordy setunpreemptable() call. This can be used to demarcate critical regions in code, where atomic actions are performed. All other processes can only observe the state of memory before the call to setunpreemptable(), or after a call to setpreemptable().
Since all other processes are excluded from running while the current process is unpreemptable, it is important that only bounded amounts of computation are performed while unpreemptable. To enforce this, SOS implements an unpreemptable timer, of the order of tens of milliseconds which stops the running process with an exception if it remains unpreemptable for longer than this. For this reason, activities like blocking IO and dynamic memory allocation cannot reliably be performed while unpreemptable.
Most applications are collections of message driven state machines, and run unpre-emptably in bursts, processing messages, updating state and sending responses. As well as giving low-overhead mutual exclusion, making applications non-blocking with control over pre-emption maximises the instruction cache hit rate and improves data cache locality.
That's enough for now, I'm boring myself !
Friday, 12 December 2008
What is SOS?
Part 2 Part 3
SOS is either the Switch, Support or Service Operating System which runs on a number of the components making up a Digital Multiplex Switch (DMS).
Work began on the system around 1979. It is mostly written in and highly coupled to the PROTEL language and the PLS (Product Library System) SCCM tool.
It is a pre-emptive multitasking operating system with some bullet-pointable features :
Module based
The PROTEL language allows a system to be split into modules, each with multiple source code files. All definitions in the files are contained in the scope of the module. Each source file can be marked as either public interface, private interface or implementation. Modules import definitions from other module's public and permitted private interfaces. The Module concept provides a component-level encapsulation, independent of OO or other abstraction mechanisms used in the code itself.
SOS allows modules to be loaded at runtime. SOS also allows modules to be 'replaced' at runtime. This involves overwriting the object code of the module while only making safe modifications to the module's exported procedure entry points and global data. This is the basis of the online code patch system which allows any object code to be replaced while processes execute over it.
Each module can define an entry procedure. This is called when the system is performing a restart and allows the module to take different initialisation actions depending on the restart type.
A SOS system is comprised of a set of modules and an initialisation order. At the various restarts, the SOS system iterates through the modules in initialisation order, calling their entry procedures.
To allow different types of systems sharing the same source modules to be easily defined, sets of modules, and their dependencies can be grouped together to form larger components. A system can then be specified in terms of these larger components. The inter-component and inter-module dependencies are then used together with some hints to compute the module initialisation order and build a system image.
Multiple memory types
The DMS model is unusual in that memory is expected to provide sufficient persistence for most data, with disk based recovery only occasionally required. This is a reasonable assumption given fault tolerant redundant memory with redundant power supplies, arrays of lead acid batteries etc.
A number of basic memory types are defined by SOS, with a number of variants for special purposes.
DSPROT is written to by transiently removing write protection during the write. If a write is attempted while write protection is active, the writing process gets an exception. Special handling is required while DSPROT is being backed up to ensure a consistent snapshot is taken.
DSPERM remains allocated across all restart types but is reset on some (see below). This gives it the interesting property that a pointer to allocated DSPERM must be stored in DSPROT memory to ensure that the allocated memory can be 'found' again after a restart.
DSTEMP is deallocated and reset across all restart types.
The memory types tie into the set of restart types supported by the operating system (below).
One of the main benefits of this system is that it orients application designers towards thinking of their application in terms of multiple levels of state, and the benefits of throwing state away to recover from error situations.
Multiple levels of system restart
SOS defines three levels of restart :
Low level modules in SOS monitor system health indicators (number of process deaths, exceptions while in a critical region, system load etc.) and if there is a perceived problem will trigger a warm restart of the system.
If the warm restart fails, or the system does not recover correctly after a number of warm restarts, the restart type is escalated to a cold restart. Modules are generally designed to re-initialise more state during a cold restart (which as a result, generally takes longer to accomplish).
If multiple cold restarts fail, the system escalates to a Reload restart, which, again, reinitialises more state, taking longer.
If all attempts to restart the running system fail, a reboot can be attempted which reloads the system image from disk and performs a reload restart on it.
If this fails, previously backed up images are tried.
In this way, the system automatically escalates recovery efforts, resetting more and more state each time, eventually trying previous images. The driving philosophy is to *never* give up trying to recover. Never wait for a friendly user to press a key, or intervene.
What makes this different?
SOS is curious in the ways it differs from the Operating Systems in common use today but it is also similar in a number of ways :
Well done if you got this far, I'll continue boring on about SOS in another post...
SOS is either the Switch, Support or Service Operating System which runs on a number of the components making up a Digital Multiplex Switch (DMS).
Work began on the system around 1979. It is mostly written in and highly coupled to the PROTEL language and the PLS (Product Library System) SCCM tool.
It is a pre-emptive multitasking operating system with some bullet-pointable features :
- Comprised entirely of runtime reloadable modules
- Multiple memory pools with different durability + protection characteristics
- Multiple levels of system restart with restart escalation
- Strong and extensible resource ownership model
- Prioritised proportional scheduling
- Online code patching and extension
- Built-in relational style database system
- Support for multiuser interactive use
- Support for online upgrade to new version
- Contains online multi threaded trace/breakpoint debugger
Module based
The PROTEL language allows a system to be split into modules, each with multiple source code files. All definitions in the files are contained in the scope of the module. Each source file can be marked as either public interface, private interface or implementation. Modules import definitions from other module's public and permitted private interfaces. The Module concept provides a component-level encapsulation, independent of OO or other abstraction mechanisms used in the code itself.
SOS allows modules to be loaded at runtime. SOS also allows modules to be 'replaced' at runtime. This involves overwriting the object code of the module while only making safe modifications to the module's exported procedure entry points and global data. This is the basis of the online code patch system which allows any object code to be replaced while processes execute over it.
Each module can define an entry procedure. This is called when the system is performing a restart and allows the module to take different initialisation actions depending on the restart type.
A SOS system is comprised of a set of modules and an initialisation order. At the various restarts, the SOS system iterates through the modules in initialisation order, calling their entry procedures.
To allow different types of systems sharing the same source modules to be easily defined, sets of modules, and their dependencies can be grouped together to form larger components. A system can then be specified in terms of these larger components. The inter-component and inter-module dependencies are then used together with some hints to compute the module initialisation order and build a system image.
Multiple memory types
The DMS model is unusual in that memory is expected to provide sufficient persistence for most data, with disk based recovery only occasionally required. This is a reasonable assumption given fault tolerant redundant memory with redundant power supplies, arrays of lead acid batteries etc.
A number of basic memory types are defined by SOS, with a number of variants for special purposes.
- PSPROT
Program Store, protected. Used for object code. Write protected. Loaded from and Saved to a SOS image on disk/tape. - DSSAVE
Data Store. Not initialised by operating system reboot or restart. Not part of a SOS image. - DSPROT
Data Store, write protected. Used for configuration or otherwise slow changing data. Loaded from and Saved to a SOS image on disk/tape. - DSPERM
Data Store, permanently allocated, wiped by some restarts. Not part of a SOS image. - DSTEMP
Data Store, temporarily allocated, wiped by most restarts. Not part of a SOS image.
DSPROT is written to by transiently removing write protection during the write. If a write is attempted while write protection is active, the writing process gets an exception. Special handling is required while DSPROT is being backed up to ensure a consistent snapshot is taken.
DSPERM remains allocated across all restart types but is reset on some (see below). This gives it the interesting property that a pointer to allocated DSPERM must be stored in DSPROT memory to ensure that the allocated memory can be 'found' again after a restart.
DSTEMP is deallocated and reset across all restart types.
The memory types tie into the set of restart types supported by the operating system (below).
One of the main benefits of this system is that it orients application designers towards thinking of their application in terms of multiple levels of state, and the benefits of throwing state away to recover from error situations.
Multiple levels of system restart
SOS defines three levels of restart :
- Initial Program Load (IPL)
This is performed only once when a module is initially loaded - Reload restart
This is the most severe restart type and occurs as part of a reboot, or when an assertion failure or user request demands it.
DSPERM memory is reset, DSTEMP memory is deallocated and reset. All modules' entry procedures are called. - Cold restart
This is second-most-severe restart type and occurs when requested by the user, or when a number of Warm restarts have failed to clear a problem. DSTEMP memory is deallocated and reset. - Warm restart
This is the least severe restart type and occurs when requested by the user or when the system determines that a number of failure indicators suggest ill health. DSTEMP memory is deallocated and reset.
Low level modules in SOS monitor system health indicators (number of process deaths, exceptions while in a critical region, system load etc.) and if there is a perceived problem will trigger a warm restart of the system.
If the warm restart fails, or the system does not recover correctly after a number of warm restarts, the restart type is escalated to a cold restart. Modules are generally designed to re-initialise more state during a cold restart (which as a result, generally takes longer to accomplish).
If multiple cold restarts fail, the system escalates to a Reload restart, which, again, reinitialises more state, taking longer.
If all attempts to restart the running system fail, a reboot can be attempted which reloads the system image from disk and performs a reload restart on it.
If this fails, previously backed up images are tried.
In this way, the system automatically escalates recovery efforts, resetting more and more state each time, eventually trying previous images. The driving philosophy is to *never* give up trying to recover. Never wait for a friendly user to press a key, or intervene.
What makes this different?
SOS is curious in the ways it differs from the Operating Systems in common use today but it is also similar in a number of ways :
- Written in high level language
- Written for general purpose CPU and memory model
- Multitasking
- Supports interactive use
- Written in assembly language and/or
- Written in telecoms-specific DSL with severe expressivity limitations
- Designed for telecoms specific CPUs and hardware
- Cooperatively scheduled
- Very limited interactivity
Well done if you got this far, I'll continue boring on about SOS in another post...
Friday, 5 December 2008
Hardware Transactional Memory I
The first multiprocessor I worked on was Nortel's XA-Core platform. This exotic platform was a replacement for the 'Computing Module' (CM) of their DMS telecoms switching platform.
Background
Previous CM generations are built on a pair of CPUs (Motorola 88k, 68k, BNR NT40) run in lockstep through a comparator for fault tolerance. The software running on these includes a multitasking OS (SOS) and a huge amount of call processing, database, hardware support and other telecoms code written in the proprietary PROTEL language, starting around 1979. SOS supports write-protectable memory, but not per-process memory protection, so the memory map resembles a heavily multithreaded process. Shared data is commonly used with an assumption of a strictly ordered memory model. Heavy use is made of a single-global-lock to enforce mutual exclusion between processes to the extent that the bulk of the computation time is spent with a single process holding the global lock in 'jumbo' timeslices of tens of milliseconds. Much of the large code base is > 10 years old and in a 'frozen' state where changes are not possible,
The problem
How to increase CM computation capacity beyond the incremental improvements available from successive generations of CPUs without a huge software rewriting and revalidation effort and while maintaining CPU and memory fault tolerance?
The solution ( XA-Core patent)
Create a fault tolerant SMP platform with replicated hardware transactional memory. Modify the OS so that a process claiming the 'single global lock' implictly sets the boundaries on a memory transaction. Handle inter-process memory access contention by rolling back one of the contenders. Handle CPU failure by rolling back in-progress memory transactions.
The achievable level of parallelism is then limited by the memory access patterns of the concurrently running processes at the cache-line level.
Code can still be written using the 'single CPU multitasking OS with big-global-lock' approach. Incremental improvements to available parallelism can be made by changing the data access patterns of the parallel processes. Tools exist to monitor contention between competing processes and map it to stack traces and/or data structures.
The interesting details and issues
The actual hardware used, the transaction handling in the operating system, handling IO, application modifications required etc.
In the spirit of actually completing some blog entries, I'll continue this post later.
To be continued...
Background
Previous CM generations are built on a pair of CPUs (Motorola 88k, 68k, BNR NT40) run in lockstep through a comparator for fault tolerance. The software running on these includes a multitasking OS (SOS) and a huge amount of call processing, database, hardware support and other telecoms code written in the proprietary PROTEL language, starting around 1979. SOS supports write-protectable memory, but not per-process memory protection, so the memory map resembles a heavily multithreaded process. Shared data is commonly used with an assumption of a strictly ordered memory model. Heavy use is made of a single-global-lock to enforce mutual exclusion between processes to the extent that the bulk of the computation time is spent with a single process holding the global lock in 'jumbo' timeslices of tens of milliseconds. Much of the large code base is > 10 years old and in a 'frozen' state where changes are not possible,
The problem
How to increase CM computation capacity beyond the incremental improvements available from successive generations of CPUs without a huge software rewriting and revalidation effort and while maintaining CPU and memory fault tolerance?
The solution ( XA-Core patent)
Create a fault tolerant SMP platform with replicated hardware transactional memory. Modify the OS so that a process claiming the 'single global lock' implictly sets the boundaries on a memory transaction. Handle inter-process memory access contention by rolling back one of the contenders. Handle CPU failure by rolling back in-progress memory transactions.
The achievable level of parallelism is then limited by the memory access patterns of the concurrently running processes at the cache-line level.
Code can still be written using the 'single CPU multitasking OS with big-global-lock' approach. Incremental improvements to available parallelism can be made by changing the data access patterns of the parallel processes. Tools exist to monitor contention between competing processes and map it to stack traces and/or data structures.
The interesting details and issues
The actual hardware used, the transaction handling in the operating system, handling IO, application modifications required etc.
In the spirit of actually completing some blog entries, I'll continue this post later.
To be continued...
Subscribe to:
Posts (Atom)