Introducing Database:
A collection of computerized data files. In simple words it is computerized record keeping.
Examples of Database Applications
• Purchases from the supermarket
• Purchases using your credit card
• Booking a holiday at the travel agents
• Using the local library
• Taking out insurance
• Using the Internet
• Studying at university
Formal definition of Database• Shared collection of logically related data (and a description of this data), designed to meet the information needs of an organization.
• System catalog (metadata) provides description of data to enable program–data independence.
• Logically related data comprises entities, attributes, and relationships of an organization’s information.
Thursday, January 14, 2010
The Relational Data Model( database)
The Relational Data Model
The Relational Data Model has the relation at its heart, but then a whole series of rules governing keys, relationships, joins, functional dependencies, transitive dependencies, multi-valued dependencies, and modification anomalies.
The RelationThe Relation is the basic element in a relational data model.
A relation is subject to the following rules:
1. Relation (file, table) is a two-dimensional table.
2. Attribute (i.e. field or data item) is a column in the table.
3. Each column in the table has a unique name within that table.
4. Each column is homogeneous. Thus the entries in any column are all of the same type (e.g. age, name, employee-number, etc).
5. Each column has a domain, the set of possible values that can appear in that column.
6. A Tuple (i.e. record) is a row in the table.
7. The order of the rows and columns is not important.
8. Values of a row all relate to some thing or portion of a thing.
9. Repeating groups (collections of logically related attributes that occur multiple times within one record occurrence) are not allowed.
10. Duplicate rows are not allowed (candidate keys are designed to prevent this).
11. Cells must be single-valued (but can be variable length). Single valued means the following:
o Cannot contain multiple values such as 'A1,B2,C3'.
o Cannot contain combined values such as 'ABC-XYZ' where 'ABC' means one thing and 'XYZ' another.
A relation may be expressed using the notation R(A,B,C, ...) where:
• R = the name of the relation.
• (A,B,C, ...) = the attributes within the relation.
• A = the attribute(s) which form the primary key.
Keys
1. A simple key contains a single attribute.
2. A composite key is a key that contains more than one attribute.
3. A candidate key is an attribute (or set of attributes) that uniquely identifies a row. A candidate key must possess the following properties:
o Unique identification - For every row the value of the key must uniquely identify that row.
o Non redundancy - No attribute in the key can be discarded without destroying the property of unique identification.
4. A primary key is the candidate key which is selected as the principal unique identifier. Every relation must contain a primary key. The primary key is usually the key selected to identify a row when the database is physically implemented. For example, a part number is selected instead of a part description.
5. A superkey is any set of attributes that uniquely identifies a row. A superkey differs from a candidate key in that it does not require the non redundancy property.
6. A foreign key is an attribute (or set of attributes) that appears (usually) as a non key attribute in one relation and as a primary key attribute in another relation. I say usually because it is possible for a foreign key to also be the whole or part of a primary key:
o A many-to-many relationship can only be implemented by introducing an intersection or link table which then becomes the child in two one-to-many relationships. The intersection table therefore has a foreign key for each of its parents, and its primary key is a composite of both foreign keys.
o A one-to-one relationship requires that the child table has no more than one occurrence for each parent, which can only be enforced by letting the foreign key also serve as the primary key.
7. A semantic or natural key is a key for which the possible values have an obvious meaning to the user or the data. For example, a semantic primary key for a COUNTRY entity might contain the value 'USA' for the occurrence describing the United States of America. The value 'USA' has meaning to the user.
8. A technical or surrogate or artificial key is a key for which the possible values have no obvious meaning to the user or the data. These are used instead of semantic keys for any of the following reasons:
o When the value in a semantic key is likely to be changed by the user, or can have duplicates. For example, on a PERSON table it is unwise to use PERSON_NAME as the key as it is possible to have more than one person with the same name, or the name may change such as through marriage.
o When none of the existing attributes can be used to guarantee uniqueness. In this case adding an attribute whose value is generated by the system, e.g from a sequence of numbers, is the only way to provide a unique value. Typical examples would be ORDER_ID and INVOICE_ID. The value '12345' has no meaning to the user as it conveys nothing about the entity to which it relates.
9. A key functionally determines the other attributes in the row, thus it is always a determinant.
10. Note that the term 'key' in most DBMS engines is implemented as an index which does not allow duplicate entries.
Relationships
One table (relation) may be linked with another in what is known as a relationship. Relationships may be built into the database structure to facilitate the operation of relational joins at runtime.
1. A relationship is between two tables in what is known as a one-to-many or parent-child or master-detail relationship where an occurrence on the 'one' or 'parent' or 'master' table may have any number of associated occurrences on the 'many' or 'child' or 'detail' table. To achieve this the child table must contain fields which link back the primary key on the parent table. These fields on the child table are known as a foreign key, and the parent table is referred to as the foreign table (from the viewpoint of the child).
2. It is possible for a record on the parent table to exist without corresponding records on the child table, but it should not be possible for an entry on the child table to exist without a corresponding entry on the parent table.
3. A child record without a corresponding parent record is known as an orphan.
4. It is possible for a table to be related to itself. For this to be possible it needs a foreign key which points back to the primary key. Note that these two keys cannot be comprised of exactly the same fields otherwise the record could only ever point to itself.
5. A table may be the subject of any number of relationships, and it may be the parent in some and the child in others.
6. Some database engines allow a parent table to be linked via a candidate key, but if this were changed it could result in the link to the child table being broken.
7. Some database engines allow relationships to be managed by rules known as referential integrity or foreign key restraints. These will prevent entries on child tables from being created if the foreign key does not exist on the parent table, or will deal with entries on child tables when the entry on the parent table is updated or deleted.
Determinant and Dependent
The terms determinant and dependent can be described as follows:
1. The expression X Y means 'if I know the value of X, then I can obtain the value of Y' (in a table or somewhere).
2. In the expression X Y, X is the determinant and Y is the dependent attribute.
3. The value X determines the value of Y.
4. The value Y depends on the value of X.
Functional Dependencies (FD)
A functional dependency can be described as follows:
1. An attribute is functionally dependent if its value is determined by another attribute which is a key.
2. That is, if we know the value of one (or several) data items, then we can find the value of another (or several).
3. Functional dependencies are expressed as X Y, where X is the determinant and Y is the functionally dependent attribute.
4. If A (B,C) then A B and A C.
5. If (A,B) C, then it is not necessarily true that A C and B C.
6. If A B and B A, then A and B are in a 1-1 relationship.
7. If A B then for A there can only ever be one value for B.
Transitive Dependencies (TD)
A transitive dependency can be described as follows:
1. An attribute is transitively dependent if its value is determined by another attribute which is not a key.
2. If X Y and X is not a key then this is a transitive dependency.
3. A transitive dependency exists when A B C but NOT A C.
Multi-Valued Dependencies (MVD)A multi-valued dependency can be
described as follows:
1. A table involves a multi-valued dependency if it may contain multiple values for an entity.
2. A multi-valued dependency may arise as a result of enforcing 1st normal form.
3. X Y, ie X multi-determines Y, when for each value of X we can have more than one value of Y.
4. If A B and A C then we have a single attribute A which multi-determines two other independent attributes, B and C.
5. If A (B,C) then we have an attribute A which multi-determines a set of associated attributes, B and C.
Types of Relational Join
A JOIN is a method of creating a result set that combines rows from two or more tables (relations). When comparing the contents of two tables the following conditions may occur:
• Every row in one relation has a match in the other relation.
• Relation R1 contains rows that have no match in relation R2.
• Relation R2 contains rows that have no match in relation R1.
INNER joins contain only matches. OUTER joins may contain mismatches as well.
Inner Join
This is sometimes known as a simple join. It returns all rows from both tables where there is a match. If there are rows in R1 which do not have matches in R2, those rows will not be listed. There are two possible ways of specifying this type of join:
SELECT * FROM R1, R2 WHERE R1.r1_field = R2.r2_field;
SELECT * FROM R1 INNER JOIN R2 ON R1.field = R2.r2_field
If the fields to be matched have the same names in both tables then the ON condition, as in:
ON R1.fieldname = R2.fieldname
ON (R1.field1 = R2.field1 AND R1.field2 = R2.field2)
can be replaced by the shorter USING condition, as in:
USING fieldname
USING (field1, field2)
Natural Join
A natural join is based on all columns in the two tables that have the same name. It is semantically equivalent to an INNER JOIN or a LEFT JOIN with a USING clause that names all columns that exist in both tables.
SELECT * FROM R1 NATURAL JOIN R2
The alternative is a keyed join which includes an ON or USING condition.
Left [Outer] Join
Returns all the rows from R1 even if there are no matches in R2. If there are no matches in R2 then the R2 values will be shown as null.
SELECT * FROM R1 LEFT [OUTER] JOIN R2 ON R1.field = R2.field
Right [Outer] Join
Returns all the rows from R2 even if there are no matches in R1. If there are no matches in R1 then the R1 values will be shown as null.
SELECT * FROM R1 RIGHT [OUTER] JOIN R2 ON R1.field = R2.field
Full [Outer] Join
Returns all the rows from both tables even if there are no matches in one of the tables. If there are no matches in one of the tables then its values will be shown as null.
SELECT * FROM R1 FULL [OUTER] JOIN R2 ON R1.field = R2.field
Self Join
This joins a table to itself. This table appears twice in the FROM clause and is followed by table aliases that qualify column names in the join condition.
SELECT a.field1, b.field2 FROM R1 a, R1 b WHERE a.field = b.field
Cross Join
This type of join is rarely used as it does not have a join condition, so every row of R1 is joined to every row of R2. For example, if both tables contain 100 rows the result will be 10,000 rows. This is sometimes known as a cartesian product and can be specified in either one of the following ways:
SELECT * FROM R1 CROSS JOIN R2
SELECT * FROM R1, R2
The Relational Data Model has the relation at its heart, but then a whole series of rules governing keys, relationships, joins, functional dependencies, transitive dependencies, multi-valued dependencies, and modification anomalies.
The RelationThe Relation is the basic element in a relational data model.
A relation is subject to the following rules:
1. Relation (file, table) is a two-dimensional table.
2. Attribute (i.e. field or data item) is a column in the table.
3. Each column in the table has a unique name within that table.
4. Each column is homogeneous. Thus the entries in any column are all of the same type (e.g. age, name, employee-number, etc).
5. Each column has a domain, the set of possible values that can appear in that column.
6. A Tuple (i.e. record) is a row in the table.
7. The order of the rows and columns is not important.
8. Values of a row all relate to some thing or portion of a thing.
9. Repeating groups (collections of logically related attributes that occur multiple times within one record occurrence) are not allowed.
10. Duplicate rows are not allowed (candidate keys are designed to prevent this).
11. Cells must be single-valued (but can be variable length). Single valued means the following:
o Cannot contain multiple values such as 'A1,B2,C3'.
o Cannot contain combined values such as 'ABC-XYZ' where 'ABC' means one thing and 'XYZ' another.
A relation may be expressed using the notation R(A,B,C, ...) where:
• R = the name of the relation.
• (A,B,C, ...) = the attributes within the relation.
• A = the attribute(s) which form the primary key.
Keys
1. A simple key contains a single attribute.
2. A composite key is a key that contains more than one attribute.
3. A candidate key is an attribute (or set of attributes) that uniquely identifies a row. A candidate key must possess the following properties:
o Unique identification - For every row the value of the key must uniquely identify that row.
o Non redundancy - No attribute in the key can be discarded without destroying the property of unique identification.
4. A primary key is the candidate key which is selected as the principal unique identifier. Every relation must contain a primary key. The primary key is usually the key selected to identify a row when the database is physically implemented. For example, a part number is selected instead of a part description.
5. A superkey is any set of attributes that uniquely identifies a row. A superkey differs from a candidate key in that it does not require the non redundancy property.
6. A foreign key is an attribute (or set of attributes) that appears (usually) as a non key attribute in one relation and as a primary key attribute in another relation. I say usually because it is possible for a foreign key to also be the whole or part of a primary key:
o A many-to-many relationship can only be implemented by introducing an intersection or link table which then becomes the child in two one-to-many relationships. The intersection table therefore has a foreign key for each of its parents, and its primary key is a composite of both foreign keys.
o A one-to-one relationship requires that the child table has no more than one occurrence for each parent, which can only be enforced by letting the foreign key also serve as the primary key.
7. A semantic or natural key is a key for which the possible values have an obvious meaning to the user or the data. For example, a semantic primary key for a COUNTRY entity might contain the value 'USA' for the occurrence describing the United States of America. The value 'USA' has meaning to the user.
8. A technical or surrogate or artificial key is a key for which the possible values have no obvious meaning to the user or the data. These are used instead of semantic keys for any of the following reasons:
o When the value in a semantic key is likely to be changed by the user, or can have duplicates. For example, on a PERSON table it is unwise to use PERSON_NAME as the key as it is possible to have more than one person with the same name, or the name may change such as through marriage.
o When none of the existing attributes can be used to guarantee uniqueness. In this case adding an attribute whose value is generated by the system, e.g from a sequence of numbers, is the only way to provide a unique value. Typical examples would be ORDER_ID and INVOICE_ID. The value '12345' has no meaning to the user as it conveys nothing about the entity to which it relates.
9. A key functionally determines the other attributes in the row, thus it is always a determinant.
10. Note that the term 'key' in most DBMS engines is implemented as an index which does not allow duplicate entries.
Relationships
One table (relation) may be linked with another in what is known as a relationship. Relationships may be built into the database structure to facilitate the operation of relational joins at runtime.
1. A relationship is between two tables in what is known as a one-to-many or parent-child or master-detail relationship where an occurrence on the 'one' or 'parent' or 'master' table may have any number of associated occurrences on the 'many' or 'child' or 'detail' table. To achieve this the child table must contain fields which link back the primary key on the parent table. These fields on the child table are known as a foreign key, and the parent table is referred to as the foreign table (from the viewpoint of the child).
2. It is possible for a record on the parent table to exist without corresponding records on the child table, but it should not be possible for an entry on the child table to exist without a corresponding entry on the parent table.
3. A child record without a corresponding parent record is known as an orphan.
4. It is possible for a table to be related to itself. For this to be possible it needs a foreign key which points back to the primary key. Note that these two keys cannot be comprised of exactly the same fields otherwise the record could only ever point to itself.
5. A table may be the subject of any number of relationships, and it may be the parent in some and the child in others.
6. Some database engines allow a parent table to be linked via a candidate key, but if this were changed it could result in the link to the child table being broken.
7. Some database engines allow relationships to be managed by rules known as referential integrity or foreign key restraints. These will prevent entries on child tables from being created if the foreign key does not exist on the parent table, or will deal with entries on child tables when the entry on the parent table is updated or deleted.
Determinant and Dependent
The terms determinant and dependent can be described as follows:
1. The expression X Y means 'if I know the value of X, then I can obtain the value of Y' (in a table or somewhere).
2. In the expression X Y, X is the determinant and Y is the dependent attribute.
3. The value X determines the value of Y.
4. The value Y depends on the value of X.
Functional Dependencies (FD)
A functional dependency can be described as follows:
1. An attribute is functionally dependent if its value is determined by another attribute which is a key.
2. That is, if we know the value of one (or several) data items, then we can find the value of another (or several).
3. Functional dependencies are expressed as X Y, where X is the determinant and Y is the functionally dependent attribute.
4. If A (B,C) then A B and A C.
5. If (A,B) C, then it is not necessarily true that A C and B C.
6. If A B and B A, then A and B are in a 1-1 relationship.
7. If A B then for A there can only ever be one value for B.
Transitive Dependencies (TD)
A transitive dependency can be described as follows:
1. An attribute is transitively dependent if its value is determined by another attribute which is not a key.
2. If X Y and X is not a key then this is a transitive dependency.
3. A transitive dependency exists when A B C but NOT A C.
Multi-Valued Dependencies (MVD)A multi-valued dependency can be
described as follows:
1. A table involves a multi-valued dependency if it may contain multiple values for an entity.
2. A multi-valued dependency may arise as a result of enforcing 1st normal form.
3. X Y, ie X multi-determines Y, when for each value of X we can have more than one value of Y.
4. If A B and A C then we have a single attribute A which multi-determines two other independent attributes, B and C.
5. If A (B,C) then we have an attribute A which multi-determines a set of associated attributes, B and C.
Types of Relational Join
A JOIN is a method of creating a result set that combines rows from two or more tables (relations). When comparing the contents of two tables the following conditions may occur:
• Every row in one relation has a match in the other relation.
• Relation R1 contains rows that have no match in relation R2.
• Relation R2 contains rows that have no match in relation R1.
INNER joins contain only matches. OUTER joins may contain mismatches as well.
Inner Join
This is sometimes known as a simple join. It returns all rows from both tables where there is a match. If there are rows in R1 which do not have matches in R2, those rows will not be listed. There are two possible ways of specifying this type of join:
SELECT * FROM R1, R2 WHERE R1.r1_field = R2.r2_field;
SELECT * FROM R1 INNER JOIN R2 ON R1.field = R2.r2_field
If the fields to be matched have the same names in both tables then the ON condition, as in:
ON R1.fieldname = R2.fieldname
ON (R1.field1 = R2.field1 AND R1.field2 = R2.field2)
can be replaced by the shorter USING condition, as in:
USING fieldname
USING (field1, field2)
Natural Join
A natural join is based on all columns in the two tables that have the same name. It is semantically equivalent to an INNER JOIN or a LEFT JOIN with a USING clause that names all columns that exist in both tables.
SELECT * FROM R1 NATURAL JOIN R2
The alternative is a keyed join which includes an ON or USING condition.
Left [Outer] Join
Returns all the rows from R1 even if there are no matches in R2. If there are no matches in R2 then the R2 values will be shown as null.
SELECT * FROM R1 LEFT [OUTER] JOIN R2 ON R1.field = R2.field
Right [Outer] Join
Returns all the rows from R2 even if there are no matches in R1. If there are no matches in R1 then the R1 values will be shown as null.
SELECT * FROM R1 RIGHT [OUTER] JOIN R2 ON R1.field = R2.field
Full [Outer] Join
Returns all the rows from both tables even if there are no matches in one of the tables. If there are no matches in one of the tables then its values will be shown as null.
SELECT * FROM R1 FULL [OUTER] JOIN R2 ON R1.field = R2.field
Self Join
This joins a table to itself. This table appears twice in the FROM clause and is followed by table aliases that qualify column names in the join condition.
SELECT a.field1, b.field2 FROM R1 a, R1 b WHERE a.field = b.field
Cross Join
This type of join is rarely used as it does not have a join condition, so every row of R1 is joined to every row of R2. For example, if both tables contain 100 rows the result will be 10,000 rows. This is sometimes known as a cartesian product and can be specified in either one of the following ways:
SELECT * FROM R1 CROSS JOIN R2
SELECT * FROM R1, R2
Wednesday, January 13, 2010
FIFO Dynamics
FIFO Dynamics
As you recall, the FIFO passes the data from the producer to the consumer. In general, the rates at which data are produced and consumed can vary dynamically. Humans do not enter data into a keyboard at a constant rate.
Even printers require more time to print color graphics versus black and white text. Let tp be the time (in sec) between calls to PutFifo, and rp be the arrival rate (producer rate in bytes/sec) into the system. Similarly, let tg be the time (in sec) between calls to GetFifo, and rg be the service rate (consumerrate in bytes/sec) out of the system.
rg=1/tg
rp=1/tp
If the minimum time between calls to PutFifo is greater than the maximum time between calls to GetFifo,
min tp > max tg
the other hand, if the time between calls to PutFifo becomes less than the time between calls to GetFifo because either
• the arrival rate temporarily increases
• the service rate temporarily decreases
then information will be collected in the FIFO. For example, a person might type very fast for a while followed by long pause. The FIFO could be used to capture without loss all the data as it comes in very fast. Clearly on average the system must be able to process the data (the consumer thread) at least as fast as the average rate at which the data arrives (producer thread). If the average producer rate is larger than the average consumer rate
rp > rg
then the FIFO will eventually overflow no matter how large the FIFO. If the producer rate is temporarily high, and that causes the FIFO to become full, then this problem can be solved by increasing the FIFO size.
There is fundamental difference between an empty error and a full error. Consider the application of using a FIFO between your computer and its printer. This is a good idea because the computer can temporarily generate data to be printed at a very high rate followed by long pauses. The printer is like a
turtle. It can print at a slow but steady rate (e.g., 10 characters/sec.) The computer will put a byte into the FIFO that it wants printed. The printer will get a byte out of the FIFO when it is ready to print another character. A full error occurs when the computer calls PutFifo at too fast a rate. A full error is serious,
because if ignored data will be lost. On the other hand, an empty error occurs when the printer is ready to print but the computer has nothing in mind. An empty error is not serious, because in this case the printer just sits there doing nothing.
As you recall, the FIFO passes the data from the producer to the consumer. In general, the rates at which data are produced and consumed can vary dynamically. Humans do not enter data into a keyboard at a constant rate.
Even printers require more time to print color graphics versus black and white text. Let tp be the time (in sec) between calls to PutFifo, and rp be the arrival rate (producer rate in bytes/sec) into the system. Similarly, let tg be the time (in sec) between calls to GetFifo, and rg be the service rate (consumerrate in bytes/sec) out of the system.
rg=1/tg
rp=1/tp
If the minimum time between calls to PutFifo is greater than the maximum time between calls to GetFifo,
min tp > max tg
the other hand, if the time between calls to PutFifo becomes less than the time between calls to GetFifo because either
• the arrival rate temporarily increases
• the service rate temporarily decreases
then information will be collected in the FIFO. For example, a person might type very fast for a while followed by long pause. The FIFO could be used to capture without loss all the data as it comes in very fast. Clearly on average the system must be able to process the data (the consumer thread) at least as fast as the average rate at which the data arrives (producer thread). If the average producer rate is larger than the average consumer rate
rp > rg
then the FIFO will eventually overflow no matter how large the FIFO. If the producer rate is temporarily high, and that causes the FIFO to become full, then this problem can be solved by increasing the FIFO size.
There is fundamental difference between an empty error and a full error. Consider the application of using a FIFO between your computer and its printer. This is a good idea because the computer can temporarily generate data to be printed at a very high rate followed by long pauses. The printer is like a
turtle. It can print at a slow but steady rate (e.g., 10 characters/sec.) The computer will put a byte into the FIFO that it wants printed. The printer will get a byte out of the FIFO when it is ready to print another character. A full error occurs when the computer calls PutFifo at too fast a rate. A full error is serious,
because if ignored data will be lost. On the other hand, an empty error occurs when the printer is ready to print but the computer has nothing in mind. An empty error is not serious, because in this case the printer just sits there doing nothing.
Two pointer/counter FIFO implementation
Two pointer/counter FIFO implementation
The other method to determine if a FIFO is empty or full is to implement a counter. In the following code, Size contains the number of bytes currently stored in the FIFO.
The advantage of implementing the counter is that FIFO 1/4 full and 3/4 full conditions are easier to implement. If you were studying the behavior of a system it might be informative to measure the current Size as a function of time.
/* Pointer,counter implementation of the FIFO */
#define FifoSize 10 /* Number of 8 bit data in the Fifo */
char *PutPt; /* Pointer of where to put next */
char *GetPt; /* Pointer of where to get next */
unsigned char Size; /* Number of elements currently in the FIFO */
/* FIFO is empty if Size=0 */
/* FIFO is full if Size=FifoSize */
char Fifo[FifoSize]; /* The statically allocated fifo data */
void InitFifo(void) { char SaveSP;
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
PutPt=GetPt=&Fifo[0]; /* Empty when Size==0 */
Size=0;
asm(" ldaa %SaveSP\n tap"); /* end critical section */
}
int PutFifo (char data) { char SaveSP;
if (Size == FifoSize ) {
return(0);} /* Failed, fifo was full */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
Size++;
*(PutPt++)=data; /* put data into fifo */
if (PutPt == &Fifo[FifoSize]) PutPt = &Fifo[0]; /* Wrap */
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); /* Successful */
}
}
int GetFifo (char *datapt) { char SaveSP;
if (Size == 0 ){
return(0);} /* Empty if Size=0 */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
*datapt=*(GetPt++); Size--;
if (GetPt == &Fifo[FifoSize]) GetPt = &Fifo[0];
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); }
}
Program 5.18. C language routines to implement a two pointer with counter FIFO.
To check for FIFO full, the above PutFifo routine simply compares Size to the maximum allowed
value. If the FIFO is already full then the routine is exited without saving the data. With this
implementation a FIFO with 10 allocated bytes can actually hold 10 data points.
To check for FIFO empty, the following GetFifo routine simply checks to see if Size equals 0.
If Size is zero at the start of the routine, then GetFifo returns with the "empty" condition signified.
The other method to determine if a FIFO is empty or full is to implement a counter. In the following code, Size contains the number of bytes currently stored in the FIFO.
The advantage of implementing the counter is that FIFO 1/4 full and 3/4 full conditions are easier to implement. If you were studying the behavior of a system it might be informative to measure the current Size as a function of time.
/* Pointer,counter implementation of the FIFO */
#define FifoSize 10 /* Number of 8 bit data in the Fifo */
char *PutPt; /* Pointer of where to put next */
char *GetPt; /* Pointer of where to get next */
unsigned char Size; /* Number of elements currently in the FIFO */
/* FIFO is empty if Size=0 */
/* FIFO is full if Size=FifoSize */
char Fifo[FifoSize]; /* The statically allocated fifo data */
void InitFifo(void) { char SaveSP;
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
PutPt=GetPt=&Fifo[0]; /* Empty when Size==0 */
Size=0;
asm(" ldaa %SaveSP\n tap"); /* end critical section */
}
int PutFifo (char data) { char SaveSP;
if (Size == FifoSize ) {
return(0);} /* Failed, fifo was full */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
Size++;
*(PutPt++)=data; /* put data into fifo */
if (PutPt == &Fifo[FifoSize]) PutPt = &Fifo[0]; /* Wrap */
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); /* Successful */
}
}
int GetFifo (char *datapt) { char SaveSP;
if (Size == 0 ){
return(0);} /* Empty if Size=0 */
else{
asm(" tpa\n staa %SaveSP\n sei"); /* make atomic, entering critical*/
*datapt=*(GetPt++); Size--;
if (GetPt == &Fifo[FifoSize]) GetPt = &Fifo[0];
asm(" ldaa %SaveSP\n tap"); /* end critical section */
return(-1); }
}
Program 5.18. C language routines to implement a two pointer with counter FIFO.
To check for FIFO full, the above PutFifo routine simply compares Size to the maximum allowed
value. If the FIFO is already full then the routine is exited without saving the data. With this
implementation a FIFO with 10 allocated bytes can actually hold 10 data points.
To check for FIFO empty, the following GetFifo routine simply checks to see if Size equals 0.
If Size is zero at the start of the routine, then GetFifo returns with the "empty" condition signified.
First In First Out Queue
Introduction to FIFO’s
As we saw earlier, the first in first out circular queue (FIFO) is quite useful for implementing a buffered I/O interface. It can be used for both buffered input and buffered output. The order preserving data structure temporarily saves data created by the source (producer) before it is processed by the sink (consumer). The class of FIFO’s studied in this section will be statically allocated global structures.
Because they are global variables, it means they will exist permanently and can be carefully shared by more than one program. The advantage of using a FIFO structure for a data flow problem is that we can decouple the producer and consumer threads. Without the FIFO we would have to produce 1 piece of data, then
process it, produce another piece of data, then process it. With the FIFO, the producer thread can continue to produce data without having to wait for the consumer to finish processing the previous data. This decoupling can significantly improve system performance.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used
when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the
DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the
printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
As we saw earlier, the first in first out circular queue (FIFO) is quite useful for implementing a buffered I/O interface. It can be used for both buffered input and buffered output. The order preserving data structure temporarily saves data created by the source (producer) before it is processed by the sink (consumer). The class of FIFO’s studied in this section will be statically allocated global structures.
Because they are global variables, it means they will exist permanently and can be carefully shared by more than one program. The advantage of using a FIFO structure for a data flow problem is that we can decouple the producer and consumer threads. Without the FIFO we would have to produce 1 piece of data, then
process it, produce another piece of data, then process it. With the FIFO, the producer thread can continue to produce data without having to wait for the consumer to finish processing the previous data. This decoupling can significantly improve system performance.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used
when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
You have probably already experienced the convenience of FIFO’s. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are put (calls PutFifo) in a FIFO whenever you hit the key. When the
DOS command interpreter is free it calls GetFifo for more keyboard data to process. A FIFO is also used when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the
printing occurs in the background. To implement this magic of background printing we will need interrupts.
There are many producer/consumer applications. In the following table the processes on the left are producers that create or input data, while the processes on the right are consumers which process or output data.
When to use interrupts
When to use interrupts
The following factors should be considered when deciding the most appropriate mechanism to synchronize hardware and software. One should not always use gadfly because one is too lazy tO implement the complexities of interrupts. On the other hand, one should not always use interrupts because they are fun and exciting.
isition&control
The following factors should be considered when deciding the most appropriate mechanism to synchronize hardware and software. One should not always use gadfly because one is too lazy tO implement the complexities of interrupts. On the other hand, one should not always use interrupts because they are fun and exciting.
isition&control
Interrupt Service Routines
The interrupt service routine (ISR) is the software module that is executed when the hardware requests an interrupt. From the last section, we see that there may be one large ISR that handles all requests (polled interrupts), or many small ISR's specific for each potential source of interrupt (vectored interrupts). The design of the interrupt service routine requires careful consideration of many factors that will be discussed in this chapter. When an interrupt is requested (and the device is armed and the I bit is one), the microcomputer will service an interrupt:
1) the execution of the main program is suspended (the current instruction is finished),
2) the interrupt service routine, or background thread is executed,
3) the main program is resumed when the interrupt service routine executes iret .
When the microcomputer accepts an interrupt request, it will automatically save the execution state of the main thread by pushing all its registers on the stack. After the ISR provides the necessary service it will execute a iret instruction. This instruction pulls the registers from the stack, which returns control to the main program. Execution of the main program will then continue with the exact stack and register values that existed before the interrupt. Although interrupt handlers can allocate, access then deallocate local variables, parameter passing between threads must be implemented using global memory variables. Global variables are also equired if an interrupt thread wishes to pass information to itself, e.g., from one interrupt instance to another. The execution of the main program is called the foreground thread, and the executions of interrupt service routines are called background threads.
Interrupt definition
Interrupt definition
An interrupt is the automatic transfer of software execution in response to hardware that is asynchronous with the current software execution. The hardware can either be an external I/O device (like a keyboard or printer) or an internal event (like an op code fault, or a periodic timer.) When the hardware needs service (busy to done state transition) it will request an interrupt. A thread is defined as the path of
action of software as it executes. The execution of the interrupt service routine is called a background thread. This thread is created by the hardware interrupt request and is killed when the interrupt service routine executes the iret instruction. A new thread is created for each interrupt request. It is important to consider each individual request as a separate thread because local variables and registers used in the interrupt service routine are unique and separate from one interrupt event to the next. In a multithreaded system we consider the threads as cooperating to perform an overall task. Consequently we will develop ways for the threads to communicat and synchronize with each other. Most embedded systems have a single common overall goal. On the other hand general-purpose computers can have multiple unrelated functions to perform. A process is also defined as the action of software as it executes. The difference is processes do not necessarily cooperate towards a common shared goal. The software has dynamic control over aspects of the interrupt request sequence. First, each potential interrupt source has a separate arm bit that the software can activate or deactivate. The software will set the arm bits for those devices it wishes to accept interrupts from, and will deactivate the arm bits
within those devices from which interrupts are not to be allowed. In other words it uses the arm bits to individually select which devices will and which devices will not request interrupts. The second aspect that the software controls is the interrupt enable bit, I, which is in the status register (SR). The software can
enable all armed interrupts by setting I=1 (sti), or it can disable all interrupts by setting I=0 (cli). The disabled interrupt state (I=0) does not dismiss the interrupt requests, rather it postpones them until a later time, when the software deems it convenient to handle the requests. We will pay special attention to these
enable/disable software actions. In particular we will need to disable interrupts when executing nonreentrant code but disabling interrupts will have the effect of increasing the response time of software. There are two general methods with which we configure external hardware so that it can request an interrupt. The first method is a shared negative logic level-active request like IRQ . All the devices
that need to request interrupts have an open collector negative logic interrupt request line. The hardware requests service by pulling the interrupt request IRQ line low. The line over the IRQ signifies negative logic. In other words, an interrupt is requested when IRQ is zero. Because the request lines are open
collector, a pull up resistor is needed to make IRQ high when no devices need service.
Normally these interrupt requests share the same interrupt vector. This means whichever device requests an
interrupt, the same interrupt service routine is executed. Therefore the interrupt service routine must first
determine which device requested the interrupt.
The original IBM-PC had only 8 dedicated edge-triggered interrupt lines, and the current PC I/O bus only has 15. This small number can be a serious limitation in a computer system with many I/O devices.
Observation: Microcomputer systems running in expanded mode often use shared negative logic
level-active interrupts for their external I/O devices.
Observation: Microcomputer systems running in single chip mode often use dedicated edgetriggered
interrupts for their I/O devices.
Observation: The number of interrupting devices on a system using dedicated edge-triggered
interrupts is limited when compared to a system using shared negative logic level-active interrupts.
Observation: Most Motorola microcomputers support both shared negative logic and dedicated edge-triggered interrupts.
An interrupt is the automatic transfer of software execution in response to hardware that is asynchronous with the current software execution. The hardware can either be an external I/O device (like a keyboard or printer) or an internal event (like an op code fault, or a periodic timer.) When the hardware needs service (busy to done state transition) it will request an interrupt. A thread is defined as the path of
action of software as it executes. The execution of the interrupt service routine is called a background thread. This thread is created by the hardware interrupt request and is killed when the interrupt service routine executes the iret instruction. A new thread is created for each interrupt request. It is important to consider each individual request as a separate thread because local variables and registers used in the interrupt service routine are unique and separate from one interrupt event to the next. In a multithreaded system we consider the threads as cooperating to perform an overall task. Consequently we will develop ways for the threads to communicat and synchronize with each other. Most embedded systems have a single common overall goal. On the other hand general-purpose computers can have multiple unrelated functions to perform. A process is also defined as the action of software as it executes. The difference is processes do not necessarily cooperate towards a common shared goal. The software has dynamic control over aspects of the interrupt request sequence. First, each potential interrupt source has a separate arm bit that the software can activate or deactivate. The software will set the arm bits for those devices it wishes to accept interrupts from, and will deactivate the arm bits
within those devices from which interrupts are not to be allowed. In other words it uses the arm bits to individually select which devices will and which devices will not request interrupts. The second aspect that the software controls is the interrupt enable bit, I, which is in the status register (SR). The software can
enable all armed interrupts by setting I=1 (sti), or it can disable all interrupts by setting I=0 (cli). The disabled interrupt state (I=0) does not dismiss the interrupt requests, rather it postpones them until a later time, when the software deems it convenient to handle the requests. We will pay special attention to these
enable/disable software actions. In particular we will need to disable interrupts when executing nonreentrant code but disabling interrupts will have the effect of increasing the response time of software. There are two general methods with which we configure external hardware so that it can request an interrupt. The first method is a shared negative logic level-active request like IRQ . All the devices
that need to request interrupts have an open collector negative logic interrupt request line. The hardware requests service by pulling the interrupt request IRQ line low. The line over the IRQ signifies negative logic. In other words, an interrupt is requested when IRQ is zero. Because the request lines are open
collector, a pull up resistor is needed to make IRQ high when no devices need service.
Normally these interrupt requests share the same interrupt vector. This means whichever device requests an
interrupt, the same interrupt service routine is executed. Therefore the interrupt service routine must first
determine which device requested the interrupt.
The original IBM-PC had only 8 dedicated edge-triggered interrupt lines, and the current PC I/O bus only has 15. This small number can be a serious limitation in a computer system with many I/O devices.
Observation: Microcomputer systems running in expanded mode often use shared negative logic
level-active interrupts for their external I/O devices.
Observation: Microcomputer systems running in single chip mode often use dedicated edgetriggered
interrupts for their I/O devices.
Observation: The number of interrupting devices on a system using dedicated edge-triggered
interrupts is limited when compared to a system using shared negative logic level-active interrupts.
Observation: Most Motorola microcomputers support both shared negative logic and dedicated edge-triggered interrupts.
Subscribe to:
Posts (Atom)