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...
|
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 Mr. Nick Huang,
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.
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 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.
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.
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"
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.
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.
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?
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.