Puzzle

Precedence and other issues

Hi Professor Ford,

I am your student in course comp238, and it seems to be a stupid question. but still I want to make clear about what I thought about the "precedence of logical operators".

In class, you mentioned that operator "and" and operator "or" have same precedence. And at same time you said that if no parentheses are added there will be ambiguity. In this sense, I guess there is no sense to define any two operator with same precedence which also will give ambiguity for operating sequence. In one word, "and" and "or" operators are just not SAME precedence at all.

I checked with text book, on page no. 10, it is said "Another general rule of precednece is that the conjunction operator takes precedence over the disjunction operator, so that ....". Also on table 7 at same page "Precedence of Logical Operators" clearly listed that "not" operator has 1 precedence, "and" has 2 precendence, "or" has 3 precendence, "conditional" operator has 4 precendence, "biconditional" has 5 precendence.

One more evidence is that when I program with C++, the logical operator "&&" which is "and" is always taking first precedence over "||" , "or " operator.

Hope it does bother you.

¡¡

Best regards,

¡¡

QingZhe Huang

One's Complement and Two's Complement

The section U of course COMP228 is like hell! The instructor is a chinese woman who is continually nervous, shy, avoiding to face questions proposed by students, lack of confidence of what she was trying to express. In one word, she is unqualified.

1's complement and 2's complement is rather a typical illustration of evolution of computer architechure which demonstrated the practicalism of human toword computer science. Computer from very beginning is just a tool for human and people are just want to use it with convenience. So, in this sense, almost all aspect of computer design is from the purpose of convenience and efficience. There is no nonsense empty-talk involved which is a common phenomenon in many humanic "science", if we can call them sciences. 1's complement and 2's complement is only the choice of no-choice. I often say that in computer science, it always seems that Nature-Creator leaves only one choice which means we have no other choice. Only in this sense, we can say that "no choice is our best choice". So is the situation of 1's and 2's complement.

I originally heard this in York university in Toronto. I still remember the professor vividly demonstrated step by step that it is our only solution to problem of representing of "signed numbers". However, in Concordia, this woman instructor made nobody understand what it really means.

Just imagine that one byte can have 256 unique combinations of bits which can represent number of 0-255. But for "signed numbers", we need to reserve one bit for "signs". And it is for our convenience we use MSB(most significant bit) to represent signs. It is only by convention that we use the left-most(logically) bit to represent minus number when it is 1 and 0 for positive numbers. Therefore within one byte we are left with 7bits to represent numbers apart from one sign number.

(Signed Number)

Sign number (MSB) | combination of other 7 bits | Range of number
1 | 128 | 0000,0000 ---0111,1111 (0 to 127)
0 | 128 | 1000,0000 ---1111,1111 (0 to -127)

This is pretty straight forward to represent signed number. However, it is quite useless. As we have to implement two algorithm for minus and plus operation.

So, in order to simplify the two operation into one operation, like 5-3 = 5+(-3), which always use plus operation. We introduce the 1's complement, that is flip all number to make its minus couterpart.

(1's complement)

Sign number (MSB) | combination of other 7 bits | Range of number
1 | 128 | 0000,0000 ---0111,1111 (0 to 127)
0 | 128 | 1111,1111 --- 1000,0000 (0 to -127)

You can see that 1's complement is just change our usual concept for minus number---"the absolute value bigger, the value is smaller." Actually it is opposite so that minus operation becomes plus operation.

But it still has the problem of "TWO" zeros: 0000,0000 for +0 and 1111,1111 for -0. Then we have a solution with 2's complement that after we flip, we add 1 to "move" all minus number by one to delete the annoying -0.

Sign number (MSB) | combination of other 7 bits | Range of number
1 | 128 | 0000,0000 ---0111,1111 (0 to 127)
0 | 128 | 1111,1111 --- 1000,0000 (-1 to -128)

We can notice that the difference is that 1111,1111 is becoming -1 instead of -0. So, all is perfect.

Reply from Dr. Ford by E-mail

    You are right!

    The "and" operator has precedence over "or" and the
    "conditional" operator has precedence over "biconditional".

    I will clear this up in class tomorrow.

    -- FORD

About Context Switch and DMA

It starts here...

`Dear Sir, Regarding I/O, I have some doubts: 1. At what point of time, does the context switching happen? Before CPU sent INTA or just before transfer control to interrupt-service-routine? ¡¡`

`
Context switching is done before the "main body" of the interrupt service routine. It is done after INTA. Take note that INTA (interrupt acknowledge) is sent by the CPU to determine which device needs attention, and the address of the interrupt service routine for that device. Before executing the interrupt service routine, context switching must be implemented so that the CPU could go back to the interrupted work properly after doing the interrupt service routine.
¡¡`

¡¡ | ¡¡ | `2. Suppose DMA starts transfer data, can CPU use data bus and address bus during the whole process of DMA copying data? Or in other words, is it true that DMA is using data bus and address bus continually during transfering data? ¡¡`

`
The CPU is always the master of the hardware system whether a DMA is being executed or not. To access the memory, for example, CPU takes control. Only when the CPU does not use the memory that the DMA controller takes over -- you call this stealing memory cycles from the CPU.
Concerning the buses, concurrency is implemented -- if there are 3 buses, for example, 3 events could happen at the same time. There are instances that the CPU wouldn't need one or two or all the 3 of these buses, the DMA controller "steals" them. In other words, CPU activity and DMA data transfer are happening at the same time, but the buses are not assigned to DMA controller to the duration of the transfer. In fact, DMA priority is low that it is just "stealing" resources to do its task.
And it continues...`

`At 05:39 PM 10/04/2003 +0000, you wrote:
¡¡`

¡¡

¡¡

`Hi Sir,
Thank you for your prompt reply. I still have a couple of questions:
1. >Context switching is done before the "main body" of the interrupt
¡¡`

¡¡ | ¡¡ | `service routine. It is done after INTA. ¡¡`

`
When I discussed context switching here awhile ago, I was discussing the context switching related to the registers that will be destroyed or modified by the "main body" of the interrupt service routine. For example, the main body of the ISR modifies reg1 and reg2, then we need to push reg1 and reg2 before going into the body of the ISR. After the body of the ISR, reg2 and reg1 are popped out. That is what I meant there by context switching; this context switching is actually the first instructions in the ISR.
The other context switching is preserving the returned address and the flags before the ISR is called. This is done by pushing the code pointers and condition flag register before the ISR, then ISR, then popping these code pointer and flag registers (in 8086, it means pushing CS, IP and Flag Registers). This is done automatically when there is a call to an interrupt (in the same way that when there is a call to a procedure, it is automatic that the returned address is pushed onto the stack before a procedure is executed).
The interrupt vector is the actual address of the interrupt service routine. In 8086/Pentium, this address must be the value of CS and IP. So before destroying the content of IP and CS, the IP and CS (and the flag registers) are pushed onto the stack (This is the context switching that you are interested about), after that, the CS and IP modified by the interrupt vector (the segment address --> CS, and the offset --> IP).
So here is the summary:
1. an INTR is made
2. an INTA is returned
3. an interrupting device is identified
3. a search in the IVT is made for that device
4. a vector interrupt (the address of the interrupt service subroutine) is known
5. the CS, IP, and flag registers are saved/pushed (one context switching)
6. the address in the vector interrupt is assigned to CS and IP
7. the CPU goes to that address (ISR)
8. the ISR first statements are generally pushing registers that would be modified by the main body of the ISR (another context switching)
9. performing ISR main body
10. popping out the registers pushed in step 8
11. the ISR is done
12. the last statement in ISR is iret (interrupt return) which means popping out CS, IP and flag register.
¡¡`

¡¡

¡¡

`You said that context switching is done after INTA. But after INTA, the interrupt vector will be returned from Port, right? and CPU need some calculation to get the "real" interrupt vector table address, (I am not quite sure about the interrupt vector meaning, I guess it is only an offset in IVT like 21h, 35h??). Then at this point, CPU need register to hold the interrupt vector for calculation of address, then the data in register would be destroyed. So, I guess the context switch should be done BEFORE INTA. This is my doubt.
And if you can explain exactly how CPU get interrupt table address, I will be very grateful.
2. Thank you for your explanation for DMA. I now understand that DMA has low priority to use data bus and address bus. So, is it correct that DMA is actually "ask" CPU to let him to use bus by "bus request" and get confirmation by "bus grant"? I read it somewhere, but not sure.
¡¡`

`
Yes, in general literature of computer organization, this is correct.
¡¡`

¡¡ | ¡¡ | `And more importantly, as I read the slides and noticed that DMA actually "steals" MEMORY CYCLE, not CPU clock cycle. So, I think there will not by sychronization between CPU clock and memory cycle, right? ¡¡`

`
Yes, the CPU has no idea when the DMA would complete its work. DMA controller will inform the CPU when the data transfer is done.
¡¡`

¡¡

¡¡

`Then at some point, DMA is actually using bus, and it is the turn for CPU to require DMA to give control of bus back to CPU. This is rather complicated situation! Can this happen if memory cycle are not same as CPU clock cycle? I am rather confused about memory cycle.
¡¡`

`
A memory cycle is the time it takes to do a memory read or memory write. It is about 10 times the clock cycle. One clock cycle is the time it takes to transfer data from one register to another register.
Here is what usually happens:
1. CPU is doing something
2. DMAR is made to the CPU
3. Device receives DMAA
4. DMA I/O waits for free bus. This means step 5 won't be done unless step 4 yield a free bus
5. DMA I/O takes over the bus to access memory (send address, data and write to memory)
6. DMA frees the bus
7. steps4, 5 and 6 are repeated until all the data transfer is completed`

`
MoreOver...`

`DMA
Cycle stealing means that the DMA controller releases the bus
after each byte is transferred. Transferring 512 bytes would
therefore require that the DMA controller request the CPU bus (by
asserting HRQ) 512 times. Each byte transferred causes DREQn* to
be asserted so DREQn* will also be asserted 512 times. Since
data is being transferred from the peripheral to memory, IOR*
will be asserted.
Why should we use literals?`

Hi Professor,
¡¡
I asked you some question about literals and constants in comp229, and you asked me to do some reading. Now I want to confirm the following:
¡¡
1. Literals are similar to constants except that they are automatically defined by assembler.
2. Unlike constants which is defined by programmer, they are typically defined in form of * =X'05' by assembler at end of program (after end instruction) if no "LTORG" directive is used.
3. They are not using immediate addressing mode. They are simply a constant, referred by their addresses.
¡¡
If above are correct, my question is what purpose do we use literals?
1. The purpose of using constants is that we can define them in one place and change them all once a time. But for literals, we use them like constants but value is not able to be defined somewhere like constants because we use whatever their value are. If we want to change the value, we have to track each of them and modify one by one. So, it has no advantages of constants.
2. The purpose of using immediate value is to write the value as part of instruction so that processor doesnot need to visit memory to fetch operand. For literals, they are similar to constants, that is, the instruction simply use their address for operand. During execution time, value of that address needs to be fetched. So literals have no advantages like immediate value.
¡¡
Since it has no advantages of either constants and immeidate values, then why do we use literals?
¡¡
Thank you very much for your time in advance,
¡¡
Best regards,
¡¡
Nick Huang/Qingzhe Huang
¡¡
Because it is a literal...

Hi Mr. Nick Huang,

¡¡
Literals are useful in long programs as they can be defined anywhere in the program and will automatically be grouped together at the LTAB by the assembler. For example, normally we define
EOF DB C'EOF'
and use the memory address EOF in instructions. In the case of literals, we can define them as * =C'EOF' anywhere and any number of times within the program and the assembler simply stores the data C'EOF' in appropriate place in memory and use the memory address in all the instructions using the literal (as =C'EOF'). Thus, the programmer does not have to worry (1) whether the constant has already been defined, (2) at what memory location the data is stored at etc. while coding. As you can imagine this avoids going back and forth in large programs thereby making the programmers life easy.
¡¡
If you have any further question, we may discuss in the class tomorrow. R. Jayakumar

FAQ:

1. Since assembler can automatically detect whether format 4 of instruction should be used or not, why should

we design to allow programmer to explicitly show in assembly code that "format 4" is used by adding "+" at

beginning of code?

It gives programmer more flexibility to control.

2. Since assembly directive "Base ASymbol" informs assembler how to calculate base relative, then why should

we still need write "LDB ASymbol" to actually load "ASymbol" address into "base" register? Why don't we allow

assembler generates code automatically?

It simply gives programmer more flexibility and also more responsibility to take care.

¡¡

Assignment 1

1. Problem 8, page 112

In our SIC/XE model, the ¡°SYMTAB¡± does not store the references of an operand. So, we need to add one column in ¡°SYMTAB¡± as ¡°References¡± which is somewhat a linked list.

Symbol | Value | Flag | References
Alpha | 1003, 1009 | Error | 1000, 1003

In the ¡°pass 2¡± when operands are checked, also adds the referred location counter number to ¡°SYMTAB¡± at column ¡°References¡±. Then when error message is output, we can also output the referred lines or location counter number of the duplicated-declared operands.

¡ïThe following part is suggested by Mr. Fang.

¡ïOne more point here, the "value" column should also be a linked list to store all "duplicated defined" symbols. So, even in "pass 1", when duplicated defined symbols are encountered, not only the error flag should be written into "SYMTAB" for the symbol, but also the address should be stored in value column so that these "labels" are also able to be printed out. So, the value field should also be a linked list instead of a single address.¡ï

2. Problem 12, page 116

The problem for assembler is that for the same mnemonic code like ¡°ADD¡±, different object code needs to be generated according to its operand. In other words, mnemonic code is not one-to-one with machine code. As for a machine that the length of instruction is not fixed, the only possible way to differentiate instructions is by its unique OPCODE. Since the operands are different, the OPCODE must be different either. Otherwise processor is unable to decode instruction correctly. Therefore assembler need to do some extra job to check the type of operand to decide which OPCODE should be used accordingly. Taking ¡°MASM¡± as an example, the same mnemonic ¡°ADD¡± will have different OPCODE according to different operands.

To solve this problem, during ¡°pass 2¡± the OPCODE will not be generated until the type of operand has been determined by checking the operand in ¡°SYMTAB¡±. And accordingly in ¡°SYMTAB¡± we need to add one more column for symbols----¡°Type¡±. So, when assembler parsed the definition of a symbol, it needs to store its ¡°type¡± in ¡°SYMTAB¡± for future reference.

3. Problem 8, page 118

a. LDA #3

This is using immediate addressing mode, that is the target address is ¡°0003¡±. And its object code should be ¡°012003¡±.

b. LDA #THREE

This is also using immediate addressing mode, however, the operand is a symbol ¡°THREE¡±. The target address should be the value of this symbol in ¡°SYMTAB¡±. Usually the value of a symbol in ¡°SYMTAB¡± is its address. But the assembly directive

¡°THREE EQU 3¡± will let assembler to store value ¡°3¡± into ¡°SYMTAB¡± instead of its address which is the value in ¡°location counter¡±. So, the target address becomes 003. And if we assume PC relative mode is used, the object code should be ¡°012003¡±. It is same as a.

c. LDA THREE

This code is meaningless! As in ¡°SYMTAB¡± the value of symbol ¡°THREE¡± is 3 which is not the address of this symbol by ¡°EQU¡± directive. And immediate addressing mode is not indicated. During execution time, processor will try to fetch value at memory address of ¡°003¡± which is incorrect!

4. Problem 24, page 121

The reason of RDREC-COPY is an invalid expression is because ¡°COPY¡± is not a symbol stored in ¡°SYMTAB¡±. So, the obvious solution is to add file name---¡°COPY¡± into ¡°SYMTAB¡± which has the same value or address as ¡°FIRST¡± or the first label in program.

¡ïThe above is totally wrong!

The reason of RDREC-COPY is an invalid expression is because ¡°COPY¡± and "RDREC" are not available at assembly time. They are only known at loading time by the loader, so, for assembler it should provide enough information for loader to modify the address at loading time when the exact address of ¡°COPY¡± and "RDREC" are known. This can be done by adding modification records in object file. Suppose this expression appears in "COPY" block, then "RDREC" would be like a "EXTREF" which need to be modified in loading time.

5. Problem 5, page 122

My solution is to write whatever the immediate value or defined operand first into the operand part of object code and later add the undefined symbol value when its definition is met.

Symbol | Value
¡ | ¡
ENDFIL | *
¡ | ¡

So, the instruction ¡°JEQ ENDFIL+3¡± would be interpreted first as 30 0003, please note that the value ¡°+3¡± is write at the operand part and undefined symbol ¡°ENDFIL¡± is entered SYMTAB. When definition of ¡°ENDFIL¡± is later encountered, its address, say 2024, will be ¡°ADD¡± to the operand part. That is 2024 + 0003 = 2027. So, forward reference is not replacing the operand part, instead ¡°CALCULATED¡± at operand part.

Further to the question, say we want to handle minus sign of forward reference like:

¡°JEQ 3-ENDFIL¡± where operand may have different sign here. My solution is to add one sign column in reference linked list in SYMTAB as following:

Symbol | Value
¡ | ¡
ENDFIL | *
¡ | ¡

So, when updating forward reference according reference link list, assembler need to check the sign column to decide whether the value should be ¡°POSITIVE¡± OR ¡°NEGATIVE¡±. Say the ENDFIL address is 2024, now the operand should be 0003 + (-2024) = -2021.

Assignment 2

1. Problem 9, page 167

First of all, it is desirable for programmer to indicate in source code that this reference is an absolute value by adding a special sign before the symbol, say ¡°#¡±. Secondly, we need add a flag column in the EXTREF in head record. See below:

R^02^00^LISTB 03^01^MAXLEN ¡

Please note that after the index column, we add a flag column simply indicating if the reference is an absolute value or not. Then during linking time, when linker write modification record, it will understand that MAXLEN is referring to an absolute value and no modification record needed.

2. Problem 12, page 168

The advantage is that this will greatly reduce the modification record number when this external symbol is referred for many times in same block. Since the address of this external symbol, say ¡°xyz¡±, is stored in the local pointer words, only one modification record is needed. That is to modify the contents of that local pointer by inserting the address of ¡°xyz¡±. So, it avoids to add modification records to all references in block wherever the symbol is referred.

However, the disadvantage is obvious. During executing time, it takes longer to fetch operand by indirect addressing mode.

3. Problem 16, page 169

Similarly as described in page 85, the assembler should establish three independent location counters for each TI, TV and TC records, each of them will start from 0. (This can be done by adding a block number in the location counter.) When assembler encounters a symbol, it will increment corresponding location counter accordingly. Thus all statements of each of three type record will be loaded consecutively and each the three type block will be able to loaded in memory in different address because each of their location.

In the object file, the head record need to specify the length of each type of record so that loader can request from operation system for correspondent space of memory to load each record. Also in the ¡°text¡± record, the beginning should indicate the type of record as following. Taking TI as an example:

¡

TI^002024^19^001000^001003¡

¡

Therefore loader can load the object code into its correspondent memory address according its type.

And the first occurrence of TI, TV and TC record in ¡°text¡± record should have a starting address as ¡°000000¡± indicating it is relocatable.

4. Problem 4, page 172

We should discuss it from implementation of assembler, loader and linker. First of all, if a data reference is able to be dynamic loadable, it need to be a separate program block so as to be able to pin point when loading. And of course it should be included within directory so as to be reachable when linker is searching the directory for external reference.

Secondly, the programmer should make certain directive to indicate that the data reference need not to be resolved during linking time by, say a directive of somewhat like ¡°no link: SymbolName¡±. Then the linker will try to do late binding for this external reference.

Assignment 3

1. Problem 6, page 300

For a batch system, as memory is divided into partitions of number of processes. So, the size of memory can limit the upper bound of number of processes. Also batch system swap jobs when one job primarily concentrate on I/O and the other one concentrates on calculating. So, the other resources like I/O limits the number of co-existence of jobs or processes.

For a time-sharing system, the primary requirement is the response time of each processes should be acceptable by user. As swapping between processes requires context switching, the number of co-existence of processes is limited when context switching of process takes too long that the responding time of each process become too long.

2. Problem 7, page 300

In a batch system, all jobs are setup and there is no need for user¡¯s interactive. So, the response time is not an important factor taken into consideration when designing the system. However, in a time-sharing system it is designed to respond quickly for user¡¯s request. As each process is given a small chunk of processor time by system, there are very good chance that processes will be able to respond almost instantly at request.

This is completely wrong!!! It should be like following which is from solution.

Since there is no other process in system, resource sharing and memory, process management would not be needed. Only file system is still necessary.

¡¡

3. Problem 5, page 319

#include <stdio.h>

int main()

{

FILE* in,*out;

char ch;

in = fopen("./test", "r");

out = fopen("./output","w");

while (!feof(in))

{

fread(&ch, 1, 1, in);

fwrite(&ch, 1, 1, out);

}

return 0;

}

4. Problem 2, page 335

Batch system would be the one which no multiprogramming is required.

5. Problem 5, page 336

Since the stack segment register is modified, processor cannot pinpoint stack correctly anymore, hence the return address which is stored in stack won¡¯t be able retrieved and the program can never return from the subroutine. The program simply crash.

If the code segment register is modified, processor cannot pin point code address correctly, the program simply cannot go on since no instruction can be read into processor.

¡¡

I think I messed up with "virtual fork" with real "fork"

Hi Professor,
¡¡
As I asked you after class today, the "exec" actually overwrites the code where the program is called. And another assumption is that "fork" doesn't copy an extra copy of code when child process is created. Then the following code cannot be explained:
¡¡
#include <stdio.h>
#include <unistd.h>
#include <strings.h>
¡¡
extern int errno;
¡¡
int main()
{
pid_t pid=0;
if ((pid=fork())==0)
{
printf("%s%i\n", "this is child with pid=", pid);
execl("show", "./show", 0);
printf("%s\n", strerror(errno));
exit(0);
}
printf("%s%i\n", "the parent is alive after exec with pid=", pid);
return 0;
}
¡¡
¡¡
The runtime result is like following, and the program "show" only print a single line of message "this is a test ....":
[qingz_hu@sunset ~] % ./pros
the parent is alive after exec with pid=11553
this is child with pid=0
[qingz_hu@sunset ~] % this is a test program and will only show this message
¡¡
1. If "execl" overwrites the code of child process, then the parent process should be unable to print any message since "fork" allow parent and child process share code.
2. So, the answer is either "execl" doesn't overwrites code or "fork" copies code when creating child process. But on book of page 562, it is written very clearly that "exec overlaying its memory space with a new program". The only solution is that "fork" create a copy of code which was destroyed or overwritten by "execl". Right? Usually process has its own code and data, so does when creating a new child process, I guess.
3. I actually compared the "pid" of parent and child (by creating another child process of THE child process, I obtained pid for THE child process.) with another simple program. The pid of child and parent are different which means they are actually different process or unrelated processes. Only by coincidence that the child process copied the code of parent process which is copied to memory space of child process.
4. In conclusion, I think I messed up with "virtual fork" with real "fork" which actually copies code of process to create an independent process. This is my wild guess and hope you can justify these ideas.
¡¡
Thank you for your time,
¡¡
¡¡
Nick Huang/Qingzhe Huang
¡¡

A concise solution to midterm according to my notes in comp229

1. a) First it is not a load-and-go assembler, instead the assembler will write to an object file. Otherwise

the program written in memory will be all the same.

Secondly for one-pass assembler the forward reference cannot be settled until assembler meets the

definition later. So, assembler simply write more text record forward reference is able to be settled.

While for two-pass assembler the assembler can settle all forward reference and no extra text record is

needed.

b) As one-pass assembler create machine code right away. So, it is inefficient for assembler to create all

machine code before it checks if some symbols are undefined. And two-pass assembler avoids such by

checking SymTab during first pass. So, two-pass assembler is efficient than one-pass to avoid writing

machine code before checking undefined symbols.

c) One-pass assembler is faster in generating program than two-pass since it only reads source program once.

Two-pass assembler need to read source program twice so it takes more time to assembly program.

2.a) Not relocating: as bootstrap loader always loads program to same address.

Not linking: as code not need to be changed and as O.S. needs to be as small as possible. So it is

always already linked version.

Bootstrap only loads O.S. and it is not the only absolute loader in O.S. and other loader loads user

program.

b) Yes, one-pass assembler can treat external reference similar way as to treat forward references. To

establish an ExtTab just like Symtab to store all ext. ref. When ext. symbols are defined, write back its

address to ExtTab.

c) Using relative addressing mode makes program relocatable. Using no data makes program sharable among

multi-program since each program keeps each own data in its own address space.

3.a) It provides abstraction of hardware. It makes O.S. or other program to use different type of hardware

in a uniformal way by calling the interface of hardware. It enable different O.S. to run same hardware

if only the O.S. know its hardware interface.

b) O.S.I. is abstraction of O.S. implementation to hide details of O.S. And API is application-specific

abstraction. Usually it is a set of functions for applications of having common features. For different

type of application, there will be a set of API's for each type. But OSI is only one way to implement,

So, there is only one OSI.

c) Abstraction is aiming hardware using easily. Sharing resource is aiming to maximize utilization of

resource. All other system software is running over O.S. and sharing cannot allow multi-controller. So,

only O.S. is giving authority to handle sharing as it is trusted.

4.a) It is a script specifying the full-path of program. Command shell reads the line and loads the csh shell

and pass all other text as parameter. We can omit the line by type in: csh in command line.

b)It should not be omitted in general when you want to terminate program in middle. In the given case,

program will stop at end even with "exit" being omitted.

c) It refers to file name to be outputed. In given case, it refers to screen.

It refers to contents in each line. It will print out all contents in screen without empty line in

between.

Assignment 4 Theory part

1. Process descriptor is the basic data structure used to represent specific environment for each process. The descriptor keeps track the process's execution status including following:

.. Its current processor register contents.

.. Its processor state;

.. Its memory state;

.. A pointer to its stack.

.. Which resources have been allocated to.

.. Which resources it needs.

Parent process descriptor and list of child process descriptors are helping process manager to justify the behaviour of each process. For example, parent process may want to suspend one of its child process. So, it is necessary to keep this information in record. Except from the very first system initial process, all process are created by its parent process. So, as soon as a process creates one child process, its child process descriptor is added to its list of child process descriptor and its process descriptor is added to the child process parent process descriptor field.

List file descriptor keeps track the resources it used, especially the file resources. When the process opens a file, the process manager or resource manager add the file descriptor to this field of process descriptor. When it closes one file, the corresponding file descriptor is removed from the list. Therefore process manager can keep track information what resources have been allocated or it has requested.

CPU status register content and general register content are all data process is handling. By storing all these information, process manager can swap out the process without affecting all its execution when swap it in again, for example in context switching, by storing all register contents in process descriptor, when the process is swapped in. All need to do is simply copy all contents back to register. And process will continue work as if there is no swapping happened.

2. a) When the O.S. has more processes created than the limit of entry number of process descriptor table, there will be problem to store new process descriptor. But usually it is not the practical problem as each O.S. has its capacity of running maximum number of processes. Exceeding the limit will result in unbearable low efficiency of performance which means the O.S. is not workable. So, this situation is not really a problem.

b) The contents in process descriptor is important information which is not supposed to be accessible for user program. Because if ill-attempted program is allowed to access the contents of process table, it may destroy the whole o.s.. for example, if user program can access process table, it has chance to modify the processor status register which contains the mode bit of supervisor or user. Then the process has the chance to access all system memory address and it can do whatever it wants to do, including crashing the system.

3. a) Blocked state can only go to running state by being allocated with resources which it requests. And all processes need to be put into a ready-queue in order to compete for processor through scheduler. So, there is a ready state between blocked and running which cannot be skipped.

b) Only in non-pre-emptive system there is no edge from running to ready. If in pre-emptive system, there should be an edge from running to ready because the scheduler will take process from CPU when its time is up.

However, in co-operative system process will only leave from CPU by either requested resource not available or terminate. In first case it will go to blacked state from running, waiting resources to be allocated. In second case, it will exit from "done" edge. The only chance it can go from running state to ready state is by "yield".

There is one problem to allow an edge from running to ready that is if a process is requesting some resources which is unavailable, it should go to blocked state instead of ready state. Otherwise it will never get resource because it has no chance to be put into waiting queue for resources. So, there should be no edge from running to ready directly.

c) When a process is first created, the process manager should create an new entry--a process descriptor--- in process table and initialize for it, like PID etc. And the state of process will be set to be ready and the process will be put into ready queue for competing for CPU. When process terminates, process manager will deallocate the process descriptor from process table and release all resources it has been allocated. And delete the process descriptor finally.

4. a) There should be an edge from running state to ready state, representing that the process give up CPU when "yield" is encountered. The process is moved to ready queue.

b) Because co-operative system is based on assumption that programmer will write appropriate program to voluntarily give up CPU by "yield". However, it is not always possible for application programmer to timing correctly by writing appropriate "yield" at appropriate position of program. And what's worse, suppose program is badly-written and the process may never give up CPU which crash the whole system. In contrast in using pre-emptive policy, all process will be taken off from CPU when its time is up. The system stability is not based on programmer's correct programming style. Thus the system will not crash even one or more application program behave improperly.

5. a) User thread is implemented by programmer with thread library while kernel thread requires support from O.S.. Therefore user thread may not be dependent on platform while kernel thread have to be. Usually kernel thread have high efficiency than user thread in acquire resources, so in some task which require different process need same computations, kernel thread will performance better.

b) i) since threads are within same process, they share data and code of parent process, only contents of CPU register need to be swapped.

ii) As threads in different process they have different code, data, so all its parent process descriptor should be swapped.

iii) Different processes have different code, data, so all process descriptor contents will be swapped.

¡¡

Comp229 Assignment 5

1. a) Taking bank account records as an example, the transaction of various customers usually is stored in file sequentially. So, when request of printing all transactions during a period of time is issued, the file will be read in sequential way. That is one record after another one. However, suppose we are interested in a particular customer¡¯s transaction records, then the information is typically stored all around the file. Therefore the file should be accessed randomly.

b) Indexed sequential file needs to keep track an extra field of index in the head of each record. That is when we write a record, we need to also write the index into the head of record. When read a record, we have also to read the index field. All these increase overhead for indexed sequential file compared with pure sequential file.

2. a) Yes, for example, in windows, we can divide one physical disk into two file system: NTFS, FAT32. Because each file system will be a partition of one disk and they can co-exist.

b) Yes, in windows, we have one FAT32 file system that includes two or more hard disks under one file system. Each block pointer has some bits to identify disk and the other bits identifying block numbers. Therefore, the file can be pinpointed by the block pointer.

c) No, if the file is not in file system, then we can never access it. So there is no way to create it or destroy it. It can never be created.

d) Yes, in Unix directory is just a common file like other file so it also needs a ¡°descriptor¡± to describe it.

e) A file is always file-system-dependent because the data block is specific designed by the file system for accessing. However, suppose some software can use the API of file system to access the file and make a mapping into another file system. Then the file is seemingly accessible form other file system by simulation. However, the file is still located in its original file system. There is no way to make one file both existing in two systems.

3. a) Each block can contain 8k/4 = 2k pointers

The number of maximum addresses is:

12+2k+ 2k*2k + 2k*2k*2k= 8G+4M+2k+12.

However, the file pointer is 32bits which means that it can only hold maximum 4G different addresses. So, the maximum file addresses in this file system is 4G and each location is of size of 8k. So the total size of maximum file is 4G*8K=32k*G or roughly 32000G

b) For each disk block pointer, the 28bits will represent different block locations. So, the maximum number of blocks in one partition of disk is 256M and each block is of size of 8k. The maximum file size is 256M*8k= 1024G

c) Singly indirect pointer will hold up to 8k/4=2k different blocks and plus 12 direct pointers. So the maximum size of file is (2k+12)*8k is less than 27423956. So, we need doubly indirect pointer and obviously we don¡¯t need triply indirect pointer. Therefore we need to access memory 4 times. First we access file ¡°inode¡± to get doubly indirect pointer P1, and then access the doubly index block pointed by doubly indirect pointer to find the particular index block pointer P2. Through P2 we find the index block P3, we access the block pointed by P3 to get all data in the block in order to get the byte we need.

4. (1) a) Each block will contain 8k/4=2k different disk block pointers

The maximum number of blocks in Linux is 12+2k+2k*2k. So the file size of maximum is (12+2k+2k*2k)*8k or roughly 32G

b) The 28bits represents maximum number of blocks to be in single partition, that is 256M. So the total size of partition is 256M*8k=1024G.

c) The access number of memory is still 4 times.

(2) a) As the 32bits will represent 4G different block locations. The maximum file size is 4G*8k=32kG or roughly 32000G

b) Each partition will be 4G*8k=32000G

c) 27423956/8k is rounded to be 3347 which means we need 3348 blocks to hold this size of file. Therefore we need 3348 times to find the block pointer and 1 more time to get the data. So total 3349.

5. a) 1. Application process requests a write operation. 2. The device driver queries the status register of device to see if device is idle or not. If device is busy, driver will wait until it is edle.

3. The driver stores an output command in controller¡¯s command register, thereby starting the device.

4. When the driver completes its job, it saves information regarding the operation into ¡°device status table¡±, such as the return address of original call, any special parameter for the I/O operation. Then the CPU can be used for other program. The driver terminates.

5. Eventually the device completes the operation and interrupt CPU, thereby causing the interrupt handler to run.

6. The interrupt handler determines which device caused the interrupt. It then branches to the device handler for that device.

7. The device handler retrieves the pending I/O status information from the device status table.

8. The device handler copies the contents of the controller¡¯s data register into the user process¡¯s space.

9. The device handler then returns control to the application process.

b) Because when a user process invokes the device driver for an operation, the driver queries the device and after that it writes the user process¡¯s information into ¡°device status table¡±, such as the return address, special parameters etc. Then device driver terminates and return control to other programs. After the device controller finishes operation, it invokes CPU by interrupt and interrupt handler will check to see which device invokes and it will invokes corresponding device handler. The device handler will look up the device status table to retrieve user process¡¯s information stored previously, accomplishing operations and return control to user process.

c) No, since the system does not have reconfigurable device drivers, there is no need to have driver-kernel interface. Because all device drivers is already combined with O.S. and O.S. will call device driver interface directly. The driver-kernel interface is intentioned to let O.S. have flexibility to add new device driver or reconfigure device drivers. So, O.S. need a kind of uniform interface between driver interface and O.S.I..

Is there any binding between function name and library name?

Hi professor,
¡¡
regarding the question I asked you in class, is there any binding between the executable file with dynamic library? What I understood from your explanation is that there is purely no relation between an executable file with the dynamic library that it is going to call. Or in other words, when we link them together as following, no dynamicl library name is written into executable files. So, executable file will only rely on O.S. to help it find out which function is located in which library:
¡¡
1. Write a main.c which simply call a function not defined in it which is defined in dynamic library, say "dynaCall".
2. Write a dynamic library which only defines a simple function "dynaCall".
3. Compile dynamic library with options of "-shared -fPIC" to make a dynamic library, naming it as "dynaLib.a".
4. Link main.c with "dynaLib.c" to generate executable file named as "main".
5. Using "setenv" to setup library searching path to include current path.
6. Run "main" and will correctly see main does call "dynaCall".
7. Rename "dynaLib.a" to be other name.
8. Run "main" again and system shows some error message clearly INDICATING THAT O.S. IS LOOKING FOR FILE "dynaLib.a".
9. To make things worse, I write a some other dynamic libraries and each of them will include a function called "dynaCall". And run "main" again. The O.S. is STILL LOOKING FOR FILE "dynaLib.a" even though logically I have written many other version of "dynaCall" in other libraries which are all within the O.S. SEARCHING PATH. But it seems that there is A KIND OF BINDING BETWEEN FUNCTIONS AND LIBRARY NAMES.
¡¡
10. I recalled in windows system, the Microsoft "COM" mechanism uses "GUID" to register each "COM" with specific library in Registry, so that when an application is calling a "COM", O.S. will search Registry to find out the path and library name information for loader to check if the library need to be loaded. Although I think UNIX should be different from windows, I guess there should be some similar data structure like "DIRECTORY" to store the library name with each associated function calls. Can you be kind enough to explain me a little bit. Or possibly in next lecture?
¡¡
Thank you for your time,
¡¡
B.rgds,
¡¡
Nick Huang/Qingzhe Huang
¡¡
p.s. attached files are simply simple source file mentioned above.
¡¡
ÎÒµÄÕ÷³¾ÊÇÐÇ³½´óº£¡£¡£¡£(Chinese)
http://www.staroceans.com/
¡¡
The dirt and dust from my pilgrimage become oceans of stars...(English)
http://www.staroceans.com/english.htm
¡¡

¡¡

COMP 346 Theory Assignment 1 Winter 2004

Issued: week of January 12 Due: Week of January 26

1) a) The smallest number of 'n' is m+1 because the I/O phase can have a maximum of

number of m jobs in a manner that each job is exactly one time unit later than

one of other job. Or in other words, m jobs are executing I/O concurrently and

will finish I/O each time unit with one job. So, at the same time, we need still

one more job to do the compute phase. Therefore we need at least m+1 jobs to keep

CPU occupied all the time.

b) C stands for computation, IO stands for I/O operation and W stands for waiting which means the job is idle in ready queue.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
a | C | IO | IO | IO | C | IO | IO | IO | C |  |
b | W | C | IO | IO | IO | C | IO | IO | IO | C |
c | W | W | C | IO | IO | IO | C | IO | IO | IO | C

c)

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
a | C | IO | IO | W | C | IO | IO | W | C |  |  |
b | W | C | IO | IO | W | C | IO | IO | W | C |  |
c | W | W | C | IO | IO | W | C | IO | IO | W | C |
d¡¡ | W | W | W | C | IO | IO | W | C | IO | IO | W | C

If the definition of latency is defined as time interval from start to end of execution, then the average latency of job in multi-programming is (9+10+11+12)/4=10.5

The latency for mono-programming is 9.

If the definition of latency is sum of waiting time in ready queue and I/O phase, then the average latency of job in multi-programming is (9+10+11+12-3x4)/4=7.5

The latency for mono-programming is 4.

2)

a) Since these 4 identical disks and 3 identical disks are from two different vendors, it¡¯s supposed to have two distinct device-driver programs for these disks. When a user program requiring disk I/O from some disk calls an OS procedure in the device independent I/O subsysterm, the system call will be trapped by OS and since IO access need privilege mode. The user process will be switched to kernel mode and the procedure in device-independent IO sub-system will be attached to user process. Then the procedure activates the device driver to access IO. For each disk to be accessed, a device driver process should be created.

b) Each kind of disk from different vendor has its own device driver. However, OS has a ¡°virtual driver¡± to abstract all implementation detail in device driver by setting up a set of universal interfaces. Therefore each kind of disk should be accessed through a standardized set of functions¡ªan interface. The differences are encapsulated in kernel modules. Making all the disk drivers implement precisely the same interface to the device-independent I/O subsystem can realize that new peripherals can be attached to a computer without developing support code to OS.

Therefore, if we did this, no OS reprogramming would be.

3) Because when having the device driver poll the device for command completion, it requires busy waiting which is a continual looping. It will waste CPU cycles that some other processes might be able to use productively. The same reason causes it is not efficient for writing the device driver as an infinite loop.

4)

At beginning process A is running, then it is blocked by IO request which will create an interrupt to activate interrupt handler ¡°ctsw¡± to do the job of context switch. ¡°ctsw¡± will save all register values and all other necessary process-related information into its PCB. By doing this, process A is put into IO queue. And then it will select the head process in ready queue, in this case process B, to load the process-related information back CPU. Process B is now running. After process B¡¯s time slice expires when system is time sharing, or when it is blocked by IO in case of batch system, context switch happens again. Since process A is put into IO queue earlier than process B, we have reasons that process B will be in a later place in IO queue and therefore in ready queue.

5) If the instructions of setting the register values were not privileged, even under the user mode, the process address space can be changed via changing the base and limit in the registers. Therefore, the user process can remove its restriction on accessing memory space which means user program have the possibility to access wherever it wants to. This is extremely dangerous from point view of OS which gives no security.

¡¡