Homework # 2
Date: Novomber 1, 1998 Due Date: Novomber 8, 1998
Question 1 (2- pp. 167) (20 Points)
If a computer uses direct addressing and it has different instruction formats, then this will cause the following problems for the relocation bits technique:
Relocation bits cannot be associated with a single word, they need to
be associated with different combinations
of words depending on the instruction format.
Relocation masks will be different from one text record to another text record.
One solution to this problem is to attach the relocation bit to the
instruction. For example, the leftmost bit of each instruction will be a relocation bit.
When this instruction needs to be relocated that bit is set to one (1). Otherwise, it is
left as zero (0).
Question 2 (8- pp. 167) (35 Points)
To use the reference number technique we need a new data structure,
namely a one-dimension array. The subscript of this array is the reference
number of the symbol corresponding to it. This array, which we will call the Reference
Table (REFTAB) will be used locally in each control section.
It looks like the following:
1 |
Control Section Address |
2 |
Ext. Sym. 1 Address |
3 |
Ext. Sym. 2 Address |
. |
. . . |
. |
. . . |
Now, we need to modify the algorithm in Figure 3.11 to use the above
changes. The modification should be done only to Pass 2 since it is only then
the addresses of all external symbols are defined. The lines that are added or modified
are shown in italic.
begin {PASS 2}
. . .
While record type ¹ 'E do
begin
if record type = 'R' then
for each symbol in the record search ESTAB to obtain its address and store it in REFTAB using the reference number in the Refer record.
end {if 'R'}
. . .
else if record type ='M' then
begin
search REFTAB using modifying symbol number to obtain the actual address
add or subtract symbol value at location (CSADDR + actual address)
end {if 'M'}
. . .
Question 3 (1- pp. 171) (45 Points)
To handle automatic library search by the linking loader we need to
modify Pass 1 of the algorithm in Figure 3.11 while Pass 2 will not change.We will
check every symbol in the Refer record with the symbols in the ESTAB. If it is there we
ignore it, otherwise we enter it and indicates that its value is
undefined. If the symbol is later defined in a Define record we enter its address in the
ESTAB. By the end of Pass 1 we search the ESTAB for undefined
symbols. If we found any we call the operating system through a service request to
obtain the address from the library. If the symbol is not found then
we flag it as an error "Undefined external symbol", otherwise we enter its
address in the ESTAB. The lines that are added or modified are shown in italic.
Begin {PASS 1}
. . .
While record type ¹ 'E do
begin
if record type = 'R' then {enter symbols in the ESTAB if they were not there}
for each symbol in the record do
begin
search ESTAB for symbol name
If not found then
enter symbol in ESTAB with value * "undefined".
end {for}
else if record type = 'D' then
for each symbol in the record do
begin
search ESTAB for symbol name
if found and value ¹ '*' then {if the symbol is already there with value ¹ '*'}
set error flag (duplicate external symbol)
else {if the symbol is already there with value '*' or is not there}
enter symbol into ESTAB with value (CSADDR + indicated address)
end {for}
end {while ¹ 'E'}
add CSLTH to CSADDR {starting address for next control Section}
end {while not EOF}
for each symbol in ESTAB do
begin
if the address value is not defined '*' then
call O. S. to search for the symbol in the routines library
if found then
store the address in the ESTAB
else
set error flag (undefined external symbol name)
end {for}
end {PASS 1}