Introduction.
Real-Time systems are computer systems in which succesful task performance depends on two factors:
- succesful result of computation,
- exact deadline time in which task was performed.
When a task execution time exceeds it's time deadline, we can say that system failed.
Hard, Firm & Soft Real-time Systems.
In the 'Hard Real-time Systems' missing a deadline is a total system failure. Hard realtime systems are created when missing a deadline can result in hardware damage or costs lives or health.
In 'Firm Real-time Systems' infrequent deadline misses are tolerable, but may degrade the system's quality of service. The usefulness of a result is zero after its deadline, but no damage or personnel loss occurs.
In 'Soft Real-time Systems' the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.
Requirements.
For a computer system to meet criteria of the 'Hard Real-time System', requirements are:
- well understood & fast enough hardware,
- real-time operating system (for example: RTLinux),
- every software piece must adhere to the 'hard real-time requirements'; software must generate results in the deadline time.
Friday, 24 March 2023
Classic Concurrency Problems.
1. Mutual Exclusion.
Let's assume that two processess want to access critical section of code. They are acting as such:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Critical section is this program fragment, that can be executed by at most one process at once.
We assume that each process which enters critical section, will leave it in finite time.
See also: Petersen's Algorithm.
2. Producers & Consumers.
There are P>0 processes in system, which produce certain data, and K>0 processes which receive data from producers. Between producers and consumers there can be buffer with capacity B, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data --- consumers. Task is about synchronizing work of producers and consumers, such as that:
* Consumer would wait for data receive in situation when buffer is empty.
* Producer, when putting data in buffer would not overwrite data already written, but not received yet by consumer. It requires stopping temporarily producer in situation when there is no empty space in buffer.
* If many consumers wait for when data arrives in buffer, and if constantly new data is produced, then each waiting consumer will get something from buffer.
* Won't happen such situation, that certain consumer will wait infinitely for getting data, if data arrives in buffer constantly.
* If many producers wait for buffer's free space, and consumers constantly get something from buffer, then each of waiting producers will be able to put something into buffer. There won't happen situation such as certain producer will wait infinitely, if constantly something is taken from buffer.
There are variants to this problem:
* Buffer might be infinite.
* Cyclic buffer with finite space.
* No buffer at all.
* Many producers or only one.
* Many consumers or only one.
* Data might be produced and consumed at quicker rate (more than one unit at once).
* Data has to be read in writing order, or not.
Producers and consumers problem is abstraction of many situations existing in computer systems, for example: keyboard data write to buffer by keyboard device driver, and it's read by operating system.
3. Readers and Writers.
There are C>0 processes working in system. They read certain data. There are P>0 processes which write data. Processes writing data we'll call writers, processes reading data --- readers. Moment when processes have access to data, we'll call 'reading room visit' or 'reading room stay'.
Let's notice that many processes can read data at once. If someone wants to modify that data, then it's reasonable to block access to this data for all other processes for the time of read. It prevents read of inconsistent data (for example, partially modified data). Overall schema for processes work is such:
process Reader;
begin
repeat
personal_affairs;
begining_reader_protocol;
READ;
ending_reader_protocol;
until false
end
process Writer;
begin
repeat
personal_affairs;
begining_writer_protocol;
WRITE;
ending_writer_protocol;
until false
end
Beginning and ending protocols of selected processes should be written in a way, that allows for these conditions to be met:
* Many readers should have simultaneous access to reading room.
* If in reading room there's writer, then no one else does not write or read.
* Each reader, which wishes for data read, at some point will read them.
* Each writer, which wishes for data modification, at some point will write such modifications.
There are variants to this problem:
* In reading room many readers can spend their time at once.
* Reading room may have limited capacity.
* Writers may have priority over readers (but then we'll resign from readers liveness).
* Readers may have priority over writers (but then we'll resign from writers liveness).
4. Five Philosophers.
This problem does not have practical analogies, unlike previous classic problems, but it very well illustrates problems happening when concurrent programs are made.
Five philosophers dine by round table. Before each there's plate. Between plates lie forks. In middle of the table there's serving dish with fish. Each philosopher thinks. When he gets hungry, he reaches for forks laying at his right and left side, then starts eating. When he's done eating, he puts forks away and again devotes himself to thinking.
Scheme of such philospoher is such then:
process Philospher (i: 0..4);
begin
repeat
think;
beginning_protocol;
eating;
ending_protocol;
until false
end;
Task is to write beginning and ending protocols, such as following conditions would be met:
* Only one philospoher ate with the same fork at the same time.
* Each of the philosophers ate only and always with two (and always those which lay near his plate) forks.
* No philosopher would die of starvation.
* Also we want that each of the philosophers would act the same way.
Solution to this riddle is to use waiter to let only four philosophers at the dining table at the same time, and let fifth wait. When philosopher is done eating, he leaves table and joins queue and can only return to table when waiter allows him to do this.
See also, if You wish: Basics of Concurrent Programming.
Let's assume that two processess want to access critical section of code. They are acting as such:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Critical section is this program fragment, that can be executed by at most one process at once.
We assume that each process which enters critical section, will leave it in finite time.
See also: Petersen's Algorithm.
2. Producers & Consumers.
There are P>0 processes in system, which produce certain data, and K>0 processes which receive data from producers. Between producers and consumers there can be buffer with capacity B, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data --- consumers. Task is about synchronizing work of producers and consumers, such as that:
* Consumer would wait for data receive in situation when buffer is empty.
* Producer, when putting data in buffer would not overwrite data already written, but not received yet by consumer. It requires stopping temporarily producer in situation when there is no empty space in buffer.
* If many consumers wait for when data arrives in buffer, and if constantly new data is produced, then each waiting consumer will get something from buffer.
* Won't happen such situation, that certain consumer will wait infinitely for getting data, if data arrives in buffer constantly.
* If many producers wait for buffer's free space, and consumers constantly get something from buffer, then each of waiting producers will be able to put something into buffer. There won't happen situation such as certain producer will wait infinitely, if constantly something is taken from buffer.
There are variants to this problem:
* Buffer might be infinite.
* Cyclic buffer with finite space.
* No buffer at all.
* Many producers or only one.
* Many consumers or only one.
* Data might be produced and consumed at quicker rate (more than one unit at once).
* Data has to be read in writing order, or not.
Producers and consumers problem is abstraction of many situations existing in computer systems, for example: keyboard data write to buffer by keyboard device driver, and it's read by operating system.
3. Readers and Writers.
There are C>0 processes working in system. They read certain data. There are P>0 processes which write data. Processes writing data we'll call writers, processes reading data --- readers. Moment when processes have access to data, we'll call 'reading room visit' or 'reading room stay'.
Let's notice that many processes can read data at once. If someone wants to modify that data, then it's reasonable to block access to this data for all other processes for the time of read. It prevents read of inconsistent data (for example, partially modified data). Overall schema for processes work is such:
process Reader;
begin
repeat
personal_affairs;
begining_reader_protocol;
READ;
ending_reader_protocol;
until false
end
process Writer;
begin
repeat
personal_affairs;
begining_writer_protocol;
WRITE;
ending_writer_protocol;
until false
end
Beginning and ending protocols of selected processes should be written in a way, that allows for these conditions to be met:
* Many readers should have simultaneous access to reading room.
* If in reading room there's writer, then no one else does not write or read.
* Each reader, which wishes for data read, at some point will read them.
* Each writer, which wishes for data modification, at some point will write such modifications.
There are variants to this problem:
* In reading room many readers can spend their time at once.
* Reading room may have limited capacity.
* Writers may have priority over readers (but then we'll resign from readers liveness).
* Readers may have priority over writers (but then we'll resign from writers liveness).
4. Five Philosophers.
This problem does not have practical analogies, unlike previous classic problems, but it very well illustrates problems happening when concurrent programs are made.
Five philosophers dine by round table. Before each there's plate. Between plates lie forks. In middle of the table there's serving dish with fish. Each philosopher thinks. When he gets hungry, he reaches for forks laying at his right and left side, then starts eating. When he's done eating, he puts forks away and again devotes himself to thinking.
Scheme of such philospoher is such then:
process Philospher (i: 0..4);
begin
repeat
think;
beginning_protocol;
eating;
ending_protocol;
until false
end;
Task is to write beginning and ending protocols, such as following conditions would be met:
* Only one philospoher ate with the same fork at the same time.
* Each of the philosophers ate only and always with two (and always those which lay near his plate) forks.
* No philosopher would die of starvation.
* Also we want that each of the philosophers would act the same way.
Solution to this riddle is to use waiter to let only four philosophers at the dining table at the same time, and let fifth wait. When philosopher is done eating, he leaves table and joins queue and can only return to table when waiter allows him to do this.
See also, if You wish: Basics of Concurrent Programming.
Petersen's Algorithm.
It's solution to problem of synchronizing two processess (running programs) wanting to enter critical section of code (section that cannot be accessed by more than one process at the same time).
Using global variables (that indicate which process[-es] want to enter critical section, and which process waits) and simple programming instructions we can ensure that only one process enters critical section at given time.
Pseudocode:
var
process1wants: boolean := false;
process2wants: boolean := false;
whoWaits: 1..2 := 1;
process P1;
begin
while true do
begin
personalAffairs;
process1wants := true;
who_waits := 1;
while process2wants and (whoWaits = 1) do {nothing};
criticalSection;
process1wants := false;
end
end;
process P2;
begin
while true do
begin
personalAffairs;
process2wants := true;
who_waits := 2;
while process1wants and (whoWaits = 2) do
criticalSection;
process2wants := false;
end
end;
Using global variables (that indicate which process[-es] want to enter critical section, and which process waits) and simple programming instructions we can ensure that only one process enters critical section at given time.
Pseudocode:
var
process1wants: boolean := false;
process2wants: boolean := false;
whoWaits: 1..2 := 1;
process P1;
begin
while true do
begin
personalAffairs;
process1wants := true;
who_waits := 1;
while process2wants and (whoWaits = 1) do {nothing};
criticalSection;
process1wants := false;
end
end;
process P2;
begin
while true do
begin
personalAffairs;
process2wants := true;
who_waits := 2;
while process1wants and (whoWaits = 2) do
criticalSection;
process2wants := false;
end
end;
Basics of Concurrent Programming.
Concurrent work is multiple works happening at the same time, processor time quants are divided among many processes.
Process is a running program.
Thread (lightweigh process, LWP) is object inside heavyweight process that has it's own control & that shares resources with other threads in the same process.
Critical Section.
Critical section is a code section that can be accessed by only one process or thread at the same time.
Critical section has uses for example in banking: we do not want data to be overwritten as it's written by other process, or read during writing.
Example pseudocode:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Readers & Writers.
In computer science, the readers-writers problem is an example of a common computing problem in concurrency.
Shared resource is abstracted as a Reading Room.
More than one Reader may be in a Reading Room, but if writer is in a Reading Room - no one else can be there.
An example algorithm for handling the readers-writers problem is as follows:
Reader's beginning protocol:
reader waits (goes asleep), if there's writer in a reading room.
Writer's beginning protocol:
writer waits (goes asleep), if there's someone in a reading room.
Reader's end protocol:
if is last exitting person, then awakens & lets writer in - if writer waits.
Writer's end protocol:
if readers wait, then awakens them all, otherwise, if writer waits, awakens one.
There should be a limit on maximum number of readers let in in a reading room, when writer(s) is/are awaiting.
See also: Petersen's Algorithm, Classic Concurrency Problems.
Process is a running program.
Thread (lightweigh process, LWP) is object inside heavyweight process that has it's own control & that shares resources with other threads in the same process.
Critical Section.
Critical section is a code section that can be accessed by only one process or thread at the same time.
Critical section has uses for example in banking: we do not want data to be overwritten as it's written by other process, or read during writing.
Example pseudocode:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Readers & Writers.
In computer science, the readers-writers problem is an example of a common computing problem in concurrency.
Shared resource is abstracted as a Reading Room.
More than one Reader may be in a Reading Room, but if writer is in a Reading Room - no one else can be there.
An example algorithm for handling the readers-writers problem is as follows:
Reader's beginning protocol:
reader waits (goes asleep), if there's writer in a reading room.
Writer's beginning protocol:
writer waits (goes asleep), if there's someone in a reading room.
Reader's end protocol:
if is last exitting person, then awakens & lets writer in - if writer waits.
Writer's end protocol:
if readers wait, then awakens them all, otherwise, if writer waits, awakens one.
There should be a limit on maximum number of readers let in in a reading room, when writer(s) is/are awaiting.
See also: Petersen's Algorithm, Classic Concurrency Problems.
Saturday, 21 January 2023
Automated Tests.
Application Design & Use Cases.
Often, when a customer orders application, she or he orders a collection of a certain functionalities.
For example:
- logging into online email application,
- deleting all spam in spam inbox,
- logging off automatically after a given time,
- configuring email sorting preferences,
- ...
Use cases are means of specifying these functionalities, defined by a number of steps (click here, scroll here, type something here, read report's field #n, etc ...).
A minimal set of use cases often determines how user interface should look, is often a formal requirement for ordered application functionalities - can be a part of the business contract between a customer & a developer company.
Automated Tests, Changes & Debugging.
Often tests for use cases can be automated, can be performed after any change is introduced into the code ... just before program's compilation, just before running an application, or at any other convenient moment.
By using Automated Use Case Tests, programmers can be comfortable that when they (or their teammates) change parts of the code, the older parts of the code (previous functionalities) that they are responsible for - won't prove erroneous after the new code additions.
Automated Use Case tests often show when part of the code is erroneous after changes, and while these are far from being 'proofs of code's correctness', these are extremely practical nevertheless. Even if not every error is caught by these - carefully designed tests can quickly find basic functionality failures. Other errors can still be found & fixed using other methods, and it's still easier to fix one error than multiple overlapping ones.
More than that - carefully designed automated tests can help programmer to create 'Mental Test Harness' that let's them more boldly & quickly do larger changes in code without inspecting the same things over & over, without fearing of application breakages so much.
This also builds Trust & Responsibility in the teams - with tests it's quick & easy to find out when someone breaks other teammate's code parts - at early stage of failure at that, so it can be addressed before error turns to be too complex to address quickly, before true stress, psychological dramas & employee firings start, before project's budgets & time schedules are endangered.
In many ways, Automated Tests help to develop applications with much more of the speed & security, with only a small amount of extra code at start (tests have to be designed & written too) & with a small amount of maintenance (when requirements change, tests have to be modified).
Documentation & Automated Tests.
Important aspect of code's quality are automated tests and documentation.
Developers should not write in documentation anything they please, there should be formal standards on what to write and how.
Class documentation should state the Contract between class user and class creator - class responsibility, invariants, what results code provides on which conditions. Results are not only returned values of methods, but also exceptions thrown, state changes, methods called and events raised.
As of how classes should be documented - there's for example Javadoc writing guidelines and requirements, these are about style, keywords and syntax.
Automated Tests for each of classes should be grouped in a single file.
Within that file many tests can be provided, one or more tests for each of tested class' methods.
Tests should check if documented contracts are intact, should check every of 'border criteria'.
Tests can also be written for software's use cases.
... for Java's automated testing tools, check, if You wish:
- JUnit 5,
- EasyMock.
See also: Software Development & Quality.
Often, when a customer orders application, she or he orders a collection of a certain functionalities.
For example:
- logging into online email application,
- deleting all spam in spam inbox,
- logging off automatically after a given time,
- configuring email sorting preferences,
- ...
Use cases are means of specifying these functionalities, defined by a number of steps (click here, scroll here, type something here, read report's field #n, etc ...).
A minimal set of use cases often determines how user interface should look, is often a formal requirement for ordered application functionalities - can be a part of the business contract between a customer & a developer company.
Automated Tests, Changes & Debugging.
Often tests for use cases can be automated, can be performed after any change is introduced into the code ... just before program's compilation, just before running an application, or at any other convenient moment.
By using Automated Use Case Tests, programmers can be comfortable that when they (or their teammates) change parts of the code, the older parts of the code (previous functionalities) that they are responsible for - won't prove erroneous after the new code additions.
Automated Use Case tests often show when part of the code is erroneous after changes, and while these are far from being 'proofs of code's correctness', these are extremely practical nevertheless. Even if not every error is caught by these - carefully designed tests can quickly find basic functionality failures. Other errors can still be found & fixed using other methods, and it's still easier to fix one error than multiple overlapping ones.
More than that - carefully designed automated tests can help programmer to create 'Mental Test Harness' that let's them more boldly & quickly do larger changes in code without inspecting the same things over & over, without fearing of application breakages so much.
This also builds Trust & Responsibility in the teams - with tests it's quick & easy to find out when someone breaks other teammate's code parts - at early stage of failure at that, so it can be addressed before error turns to be too complex to address quickly, before true stress, psychological dramas & employee firings start, before project's budgets & time schedules are endangered.
In many ways, Automated Tests help to develop applications with much more of the speed & security, with only a small amount of extra code at start (tests have to be designed & written too) & with a small amount of maintenance (when requirements change, tests have to be modified).
Documentation & Automated Tests.
Important aspect of code's quality are automated tests and documentation.
Developers should not write in documentation anything they please, there should be formal standards on what to write and how.
Class documentation should state the Contract between class user and class creator - class responsibility, invariants, what results code provides on which conditions. Results are not only returned values of methods, but also exceptions thrown, state changes, methods called and events raised.
As of how classes should be documented - there's for example Javadoc writing guidelines and requirements, these are about style, keywords and syntax.
Automated Tests for each of classes should be grouped in a single file.
Within that file many tests can be provided, one or more tests for each of tested class' methods.
Tests should check if documented contracts are intact, should check every of 'border criteria'.
Tests can also be written for software's use cases.
... for Java's automated testing tools, check, if You wish:
- JUnit 5,
- EasyMock.
See also: Software Development & Quality.
Contracts.
Introduction.
Design by Contract is the Software Collaboration Method.
Contract / between class user and class author / should state under which condition class will provide it's services to class user, and what these services are.
Contract.
There are Preconditions, Postconditions and Invariants that regulate contract.
Precondition is a condition that is required for something to happen. Precondition can be simple or complex, complex precondition consists of multiple simple or complex preconditions as well.
Postcondition is something that is guaranteed to happen if preconditions are met & program behaves correctly.
Invariants is something that is guaranteed to hold, at least in observable moments in time, or perhaps even all the time.
If class user provides 'correct' / or using alternative wording: 'legal' / preconditions to object, methods will ensure that postconditions are met.
Invariants are always met / though some disagree, for there's 'observable moment' argument /, or contract is broken.
Examples for Preconditions:
- requirements for method arguments allowed values,
- concurrency requirements,
- perhaps more.
Examples for Postconditions:
- program's process(-es) will compute and provide results correctly,
- program will finish within the agreed time frame in at least 90% of situations,
- perhaps more.
Examples for Invariants:
- heat in Reactor will never go above the Critical Value,
- variable 'divisor' will never have '0' value,
- variable 'divisor' will never have '0' value during computations phase,
- perhaps more.
Inheritance / in simple words /.
To not break contract, following conditions must be met:
1. subclasses must require no more than it's neccessary for superclass to work correctly / but can require less /.
2. subclasses must meet all requirements of superclass / but perhaps can give more /.
This is related with the Liskov's Substitution Principle / LSP /.
Exceptions in Java.
When contract is broken during Runtime, an Exception should be thrown.
Design by Contract is the Software Collaboration Method.
Contract / between class user and class author / should state under which condition class will provide it's services to class user, and what these services are.
Contract.
There are Preconditions, Postconditions and Invariants that regulate contract.
Precondition is a condition that is required for something to happen. Precondition can be simple or complex, complex precondition consists of multiple simple or complex preconditions as well.
Postcondition is something that is guaranteed to happen if preconditions are met & program behaves correctly.
Invariants is something that is guaranteed to hold, at least in observable moments in time, or perhaps even all the time.
If class user provides 'correct' / or using alternative wording: 'legal' / preconditions to object, methods will ensure that postconditions are met.
Invariants are always met / though some disagree, for there's 'observable moment' argument /, or contract is broken.
Examples for Preconditions:
- requirements for method arguments allowed values,
- concurrency requirements,
- perhaps more.
Examples for Postconditions:
- program's process(-es) will compute and provide results correctly,
- program will finish within the agreed time frame in at least 90% of situations,
- perhaps more.
Examples for Invariants:
- heat in Reactor will never go above the Critical Value,
- variable 'divisor' will never have '0' value,
- variable 'divisor' will never have '0' value during computations phase,
- perhaps more.
Inheritance / in simple words /.
To not break contract, following conditions must be met:
1. subclasses must require no more than it's neccessary for superclass to work correctly / but can require less /.
2. subclasses must meet all requirements of superclass / but perhaps can give more /.
This is related with the Liskov's Substitution Principle / LSP /.
Exceptions in Java.
When contract is broken during Runtime, an Exception should be thrown.
Friday, 20 January 2023
A few thoughts on code quality - mostly for Java, but can be abstracted and used with different technologies.
In my opinion java code of quality should have following properties:
1. Proper naming of classess, methods, variables and constants.
2. Single, properly defined and documented responsibility of each class and method. No unneccessary code (to remove code duplication you can use constants (final keyword, UPPERCASE_NAMES) and split methods with large chunks of code into few smaller methods so you can reuse them. To ensure single responsibility of method or class move some code into another method or class. Single responsibility class or method is more reausable and easier to document, read, test and modify. [or to break if someone wants to try firing quality coder].). Single responsibility of method may involve calling more than one instruction as long as it is considered atomic. For example: changeStateWithSideEffect(...);
3. Documented methods headers (first lines of methods and all information therein, including variable names) according to javadoc documentation.
4. Use of 'assert' keyword, software contracts, preconditions, postconditions and invariants.
5. Fitting 'a complete code part' on a 'single screen', if possible and worthwhile; ... easier thinking, less scrolling, perhaps more.
Later JUnit/Easymock automated tests can be added to build test harness.
Also, code should be properly formatted.
Commits / to code repository, using technologies such as SVN or Git / should be commented.
Methods should be abstract, empty or final.
Ideally, methods should consists of three instructions. init(...); transform(...); return [(...)]; Complex instruction counts as single instruction;
There can be more requirements / for example: coding in idiomatic way / , but in practice it's almost perfect if these are used. Professionals after all have no time to comment code, or they want to be priceless and unfirable by bosses, in a not-so-nice, unfair way.
See also: Design by Contract.
1. Proper naming of classess, methods, variables and constants.
2. Single, properly defined and documented responsibility of each class and method. No unneccessary code (to remove code duplication you can use constants (final keyword, UPPERCASE_NAMES) and split methods with large chunks of code into few smaller methods so you can reuse them. To ensure single responsibility of method or class move some code into another method or class. Single responsibility class or method is more reausable and easier to document, read, test and modify. [or to break if someone wants to try firing quality coder].). Single responsibility of method may involve calling more than one instruction as long as it is considered atomic. For example: changeStateWithSideEffect(...);
3. Documented methods headers (first lines of methods and all information therein, including variable names) according to javadoc documentation.
4. Use of 'assert' keyword, software contracts, preconditions, postconditions and invariants.
5. Fitting 'a complete code part' on a 'single screen', if possible and worthwhile; ... easier thinking, less scrolling, perhaps more.
Later JUnit/Easymock automated tests can be added to build test harness.
Also, code should be properly formatted.
Commits / to code repository, using technologies such as SVN or Git / should be commented.
Methods should be abstract, empty or final.
Ideally, methods should consists of three instructions. init(...); transform(...); return [(...)]; Complex instruction counts as single instruction;
There can be more requirements / for example: coding in idiomatic way / , but in practice it's almost perfect if these are used. Professionals after all have no time to comment code, or they want to be priceless and unfirable by bosses, in a not-so-nice, unfair way.
See also: Design by Contract.
Subscribe to:
Posts (Atom)