BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

操作系统代写 | Class CSCI-GA.2250-001: Operating Systems

操作系统代写 | Class CSCI-GA.2250-001: Operating Systems

 这次操作系统代写是实现一个two-pass链接器

Class CSCI-GA.2250-001: Operating Systems Summer 2020  
A) operand is an absolute address which will never be changed in pass2; however it can’t be “>=” the machine size (512);  
The linker must process the input twice (that is why it is called two-pass) (to preempt the favored question: “Can I do it in  
one pass?” NO). Pass One parses the input and verifies the correct syntax and determines the base address for each  
module and the absolute address for each defined symbol, storing the latter in a symbol table. The first module has base  
address zero; the base address for module X+1 is equal to the base address of module X plus the length of module X (defined  
as the number of instructions in a module). The absolute address for symbol S defined in module M is the base address of M  
plus the relative address of S within M. After pass one print the symbol table (including errors related to it (see rule2 later)).  
Do not store parsed tokens, the only data you should and need to store between passes is the symboltable.  
Pass Two again parses the input and uses the base addresses and the symbol table entries created in pass one to generate the  
actual output by relocating relative addresses and resolving external references. You should reuse pass-1 parser code just with  
different actions. You must clearly mark your two passes in the code through comments and/or proper function naming.  
Other requirements: error detection, limits, and space used.  
To receive full credit, you must check the input for various errors (test inputs will have lots of errors). All errors/warnings  
should follow the message catalog provided below. We will do a textual difference against a reference implementation to  
grade your program. Any reported difference will indicate a non-compliance with the instructions provided and is reported as  
an error and results in deductions.  
Page 1 of 7 –  
Programming Assignment #1 (Lab 1): Linker  
Professor Hubertus Franke  
Class CSCI-GA.2250-001: Operating Systems Summer 2020  
You should continue processing after encountering an error/warning (other than a syntax error) and you should be able to  
detect multiple errors in the same run.  
1
.
You should stop processing if a syntax error is detected in the input, print a syntax error message with the line  
number and the character offset in the input file where observed. A syntax error is defined as a missing token (e.g. 4  
used symbols are defined but only 3 are given) or an unexpected token. Stop processing and exit.  
If a symbol is defined multiple times, print an error message and use the value given in the first definition. The error  
message is to appear as part of printing the symbol table (following symbol=value printout on the same line).  
If a symbol is used in an E-instruction but not defined anywhere, print an error message and use the value absolute  
zero.  
2
3
.
.
4
5
.
.
If a symbol is defined but not used, print a warning message and continue.  
If an address appearing in a definition exceeds the size of the module, print a warning message and treat the address  
given as 0 (relative to the module).  
6
7
.
.
If an external address is too large to reference an entry in the use list, print an error message and treat the address as  
immediate.  
If a symbol appears in a use list but is not actually used in the module (i.e., not referred to in an E-type address),  
print a warning message and continue.  
8
9
.
.
If an absolute address exceeds the size of the machine, print an error message and use the absolute value zero.  
If a relative address exceeds the size of the module, print an error message and use the module relative value zero  
(
that means you still need to remap “0” that to the correct absolute address).  
1
1
0. If an illegal immediate value (I) is encountered (i.e. >= 10000), print an error and convert the value to 9999.  
1. If an illegal opcode is encountered (i.e. op >= 10), print an error and convert the <opcode,operand> to 9999.  
The following exact limits are in place.  
a) Accepted symbols should be upto 16 characters long (not including terminations e.g.\0’), any longer symbol names  
are erroneous.  
b) a uselist or deflist should support 16 definitions, but not more and an error should be raised.  
c) number of instructions are unlimited (hence the two pass system), but in reality they are limited to the machine size.  
d) Symbol table should support at least 256 symbols (reference program supports exactly 256 symbols).  
There are several sample inputs and outputs provided as part of the sample input files / output files (see NYU Classes).  
The first (input-1) is shown below and the second (input-2) is a re-formatted version of the first. They both produce the same  
output as the input is token-based and hence present the same content to the linker. Some of the input sets contain errors that  
you are to detect as described above. Note that when you have questions regarding errors, please first make sure the structure  
of the input is not messing with your mind.  
We will run your lab on these (and other) input sets.  
1
2
5
0
1
6
0
1
2
1
2
3
xy 2  
z xy  
R 1004 I 5678 E 2000 R 8002 E 7001  
z
R 8001 E 1000 E 1000 E 3000 R 1002 A 1010  
z
R 5001 E 4000  
z 2  
xy z  
A 8000 E 1001 E 2000  
Your output is expected to strictly follow this format (with exception of empty lines):  
Symbol Table  
xy=2  
z=15  
Memory Map  
0
0
00: 1004  
01: 5678  
Page 2 of 7 –  
Programming Assignment #1 (Lab 1): Linker  
Professor Hubertus Franke  
Class CSCI-GA.2250-001: Operating Systems Summer 2020  
0
0
0
0
0
0
0
0
0
0
0
0
0
0
02: 2015  
03: 8002  
04: 7002  
05: 8006  
06: 1015  
07: 1015  
08: 3015  
09: 1007  
10: 1010  
11: 5012  
12: 4015  
13: 8000  
14: 1015  
15: 2002  
The following output is heavily annotated for clarity and class discussion. You won’t be creating this output. However, it  
should help you understand the operation and mapping of symbols etc.  
Symbol Table  
xy=2  
z=15  
Memory Map  
+
0
1
2
3
4
+
0
1
2
3
4
5
+
0
1
+
0
1
2
0
:
:
: xy: E 2000 ->z  
:
:
5
:
:
:
:
:
:
11  
:
:
13  
:
R 1004  
I 5678  
1004+0 = 1004  
5678  
2015  
8002+0 = 8002  
7002  
R 8002  
E 7001 ->xy  
R 8001  
8001+5 = 8006  
1015  
1015  
3015  
1002+5 = 1007  
1010  
E 1000 ->z  
E 1000 ->z  
E 3000 ->z  
R 1002  
A 1010  
R 5001  
E 4000 ->z  
5001+11= 5012  
4015  
A 8000  
E 1001 ->z  
E 2000 ->xy  
8000  
1015  
2002  
:
z:  
Note that even an empty program should have the “Symbol Table” and “Memory Map” line.  
For a test case to pass you must catch ALL warning/errors and generate the correct output for a given input file.  
Example:  
Symbol Table  
X21=3  
X31=4  
Memory Map  
0
0
0
0
0
00: 1003  
01: 1003  
02: 1003  
03: 2000 Error: Absolute address exceeds machine size; zero used  
04: 3000 Error: Relative address exceeds module size; zero used  
Page 3 of 7 –  
Programming Assignment #1 (Lab 1): Linker  
Professor Hubertus Franke  
Class CSCI-GA.2250-001: Operating Systems Summer 2020  
Warning: Module 3: X31 was defined but never used  
Parse errors should abort processing.  
Error messages must be following the instruction as shown above.  
Warnings message locations are defined further down.  
Module counting starts at 1.  
I provide in C the code to print parse errors, which also gives you an indication what is considered a parse error.  
void __parseerror(int errcode) {  
static char* errstr[] = {  
NUM_EXPECTED”,  
SYM_EXPECTED”,  
ADDR_EXPECTED”,  
SYM_TOO_LONG”,  
TOO_MANY_DEF_IN_MODULE”,  
TOO_MANY_USE_IN_MODULE”,  
TOO_MANY_INSTR”,  
// Number expect  
// Symbol Expected  
// Addressing Expected which is A/E/I/R  
// Symbol Name is too long  
// > 16  
// > 16  
// total num_instr exceeds memory size (512)  
};  
printf(“Parse Error line %d offset %d: %s\n”, linenum, lineoffset, errstr[errcode]);  
}
(
Note: line numbers start with 1 and offsets in the line start with 1, offsets should indicate the first character offset of the  
token that is wrong, not the last). Tabs (‘\t’) count as one character.  
Error messages have the following text and should appear right at the end of the line you are printing out  
Error: Absolute address exceeds machine size; zero used”  
Error: Relative address exceeds module size; zero used”  
Error: External address exceeds length of uselist; treated as immediate”  
(see rule 8)  
(see rule 9)  
(see rule 6)  
(see rule 3)  
(see rule 2)  
(see rule 10)  
(see rule 11)  
Error: %s is not defined; zero used”  
(insert the symbol name for %s)  
Error: This variable is multiple times defined; first value used”  
Error: Illegal immediate value; treated as 9999″  
Error: Illegal opcode; treated as 9999″  
Warning messages have the following text and are on a separate line.  
Warning: Module %d: %s too big %d (max=%d) assume zero relative\n”  
Warning: Module %d: %s appeared in the uselist but was not actually used\n”  
Warning: Module %d: %s was defined but never used\n”  
(see rule 5)  
(see rule 7)  
(see rule 4)  
Locations for these warnings are:  
Rule 5: to be printed after each module in pass1  
Rule 7: to be printed after each module in pass2 (so actually interspersed in the memory map (see out-9)  
Rule 4: to be printed after pass 2 (i.e. all modules have been processed) ( see out-3).  
Parse Error Location:  
Parse errors are to be located at the first character of the wrong token, or if end-of-file is reached at the end of file location.  
There is one special case when the eof ends with `\n’. My expectation is that the line number reported actually exists in the  
file and that an editor (e.g. vi) can jump to it. In this particular case the linenumber to be reported is the last line read and the  
last position of that line, not the next line and offset 1 (see input-12 for an example). The error is at the very last position of  
the line. Reason is when one does a linecount on the file (“wcl input-12”) it shows 3.  
Hint: for each parser error and warning error mentioned above you should have code checking for that.
Programming Assignment #1 (Lab 1): Linker  
Professor Hubertus Franke  
Class CSCI-GA.2250-001: Operating Systems Summer 2020  
Program Specification  
Only C/C++ are allowed for this lab. The program should take a single command line argument for input file. The output of  
the program should go to the standard output.  
The program should run on the linserv1.cims.nyu.edu machine of NYU, which is where it will be graded, so please make  
sure your program runs there. We realize you code on your own machine and transferring to linserv1 machine exposes  
occasionally some linker errors. In that case use static linking (such as not finding the appropriate libraries at runtime),  
though hopefully that is now resolved with the “module” approach discussed at the end.  
Testing your program before submission  
As part of the lab1_samples.tar.Z in NYU Classes you will see a runit.sh and a gradeit.sh script (the same we will use for  
grading albeit with more inputs). Understand the script and what it does. If you can’t pass this script, things will be flagged  
during the grading process as well. Don’t assume that just because you pass for these inputs, it will pass for all inputs.  
Carefully go through the rules above and ensure covered each rule with some code (if/then/else) and it is at the right location.  
Execute as follows:  
Create yourself a directory <your-outdir> where your outputs will be created.  
>
cd labsamples  
>
./runit.sh <your-outdir> <your-executable and optional arguments>  
# make your output directory different  
The above will create all the outputs for the available inputs (1-20)  
>
./gradeit.sh . <your-outdir>  
# note the 2nd argument is a DOT for the local directory where the reference output is.  
The above will compare the reference outputs (out-[1-20]) with the ones created with your program and tell you how many  
you got right and which ones are wrong. There will be a file called <your-outdir>/LOG that contains which cases you got  
wrong and where the differences are. If you want to analyze further please run the “diff –b B –E” by hand on a particular  
output pair.  
The reference program used during grading is located on /home/frankeh/Public/linker on cims systems. So feel free to try it in  
order to answer any questions you might have on what is expected for a particular input.  
What to submit  
Submit a zip archive containing (i) source code (ii) makefile to compile your code (iii) ReadMe (If running the program is  
not straightforward, otherwise not required). Please make sure the zip doesn’t have any input and/or output files nor contains  
other zip or tar files or backup files.  
Grading  
The lab is graded using a “diff –b B –E” against the reference output created by my test program using a grading harness.  
Inputs will be the ones provided in NYU Classes as well as other ones and will be checked for all of the error conditions.  
It is imperative that you match the output as generated by the ref program to allow for the automated testing for yourself as  
well.  
We score this lab as 100pts. You will receive 40 pts for a submission that attempts to solve the problem. The rest you get  
6
0/N points for each successful test that passes the “diff”. In order to institute a certain software engineering discipline, i.e.  
following a specification and avoiding unintended releases of code and data in real life, we account for the following  
additional deductions:  
Reason  
Deduction How to avoid  
Makefile not working on CIMS or  
missing.  
1pts  
Make sure your source compiles with your Makefile  
Programming Assignment #1 (Lab 1): Linker  
Professor Hubertus Franke  
Class CSCI-GA.2250-001: Operating Systems Summer 2020  
Storing Tokens instead of reparsing the 2pts  
file. All you should store is the  
Symboltable between passes.  
Follow instructions on parsing. After that copy the shell of the parser  
nd  
for the 2 pass. Close the file, reopen the file and parse again, just  
st  
change the actions taken between 1 (error checking, module &  
nd  
symbol table creation) and 2 pass (instruction transformation).  
Late submission  
2pts/day  
Upto 7 days. After which reach out to me or TA but work on next lab  
(
don’t fall behind).  
Inputs/Outputs or *.o files in the  
submission  
Output not going to the screen but to a  
file  
1pt  
1pt  
Go through your intended submission and clean it up.  
We utilize the output to <stdout> during the runit.sh and gradeit.sh  
so just use printf or cout.  
bestdaixie