辅导

一、计算机系统概论业

内容：了解编译系统的工作原理；了解程序在计算机上的执行过程；了解存储的层次结构；了解操作系统的作用和主要组成部分。200092

 659 76674

二、信息在计算机中的内部表示与处理研

内容：2进制与16进制；字；数据的大小；寻址方式和字节顺序（little endian和big endian）；字符串的机器表示；代码的机器表示；C语言中的位运算，C语言中的逻辑运算，C语言中的移位运算；整数数据类型；有符号和无符号整数及其原码和补码表示；有符号整数和无符号整数的转换；C语言中的有符号整数和无符号整数；整数的位扩展；整数的位截断；无符号整数和有符号整数的加减法与溢出；整数的乘法、除法和移位运算；IEEE浮点数表示，浮点数的舍入。65976 455

 

三、程序的机器级表示1号

内容：数据格式；IA32寻址方式；IA32数据传送、算术、逻辑与控制指令；C语言条件分支、循环、switch结构与相应汇编代码的对应关系，使用跳转表实现switch结构；IA32过程调用的实现：程序栈帧的结构，过程调用和返回指令，寄存器使用惯例(Caller saved and Callee saved registers)，递归调用，对一个过程调用全部过程的整体把握和理解；数组的分配和访问，多维数组，动态分配数组，数组与循环；结构与联合；指针、指针运算、指针与数组、结构、联合；数据对齐（alignment）；缓冲区溢出的基本原理。共

 

四、链接1号

内容：了解链接在编译系统中的作用；ELF可重定位目标文件格式，了解该格式中每个section的作用；理解ELF符号表条目的结构；理解链接器符号解析机制：强符号与弱符号，解析多重定义的规则，使用静态库解析引用的规则；理解链接器重定位机制：重定位的两个步骤，ELF重定位表目的结构，理解R_386_PC32和R_386_32两种符号引用类型的重定位算法，理解重定位时ELF符号表条目和ELF重定位表目的相互作用关系；了解ELF可执行目标文件格式，了解它与ELF可重定位目标文件的格式的异同；了解加载器的基本功能；了解共享库与动态链接的基本概念。共济网

 研

五、异常控制流机制021-

内容：异常机制的工作原理，作用与分类；使用进程实现多控制流，进程的虚拟地址空间，操作系统的用户模式与内核模式，进程的上下文切换，系统调用基本原理和作用；理解若干Unix系统调用:getpid，getppid，exit，fork，wait，waitpid，sleep，pause，execve，getenv，setenv，unsetenv；信号的概念及其基本实现原理，信号发送、信号接收与信号处理；非本地跳转。共

 kaoyantj

六、存储器的层次结构

内容：了解基本存储技术；程序的局部性与存储器的层次结构；cache的结构及其工作原理；write through和wirte back cache；了解影响cache性能的基本因素，理解cahce对程序性能的影响，理解编写cache友好代码的基本技术。

 

七、虚存

内容：地址空间和虚存的概念；地址翻译：页表的作用与结构，页命中与缺页中断，TLB的作用与结构，多级页表；物理内存、cache、虚存、页表、TLB几者之间相互联系以及它们在地址翻译过程中的相互作用，地址翻译的流程；虚存的作用与重要性：使用虚存管理存储器，使用虚存实现存储器保护；Pentium地址翻译；Linux虚存系统：Linux虚存存储区域，Linux缺页异常处理；存储器映射：共享对象，copy-on-write，fork与execve系统调用与虚存和存储器映射相关的操作；使用mmap函数进行用户级存储器映射；存储器的动态分配；垃圾收集技术；常见的与存储器相关的错误。

 

八、系统I/O

内容：理解几个基本的Unix I/O系统调用的功能:open,read,write,stat,fstat,dup,dup2；unix内核用于I/O操作的主要数据结构：文件描述符表，打开文件表，V-node表；共享文件；使用Rio包进行健壮的读和写。

 

九、并发编程

内容：并发的概念；并发编程的主要模式：基于进程的并发编程，基于I/O多路复用的并发编程，基于线程的并发编程；多线程程序中的共享变量；用信号量同步线程；基于预线程化的并发服务器。

 

例题：

1．Data representation，Byte ordering，Alignment

 

Consider the following program:

struct s {

char c;

double d;

float f;

short s;

};

union u {

unsigned char buf[24];

struct s a;

int i;

} u1;

int main()

{

int i,j;

memset(&u1.a, 0, sizeof(struct s));

u1.a.c = 0xac;

u1.a.d = -3.3;

u1.a.f = 0x1;

u1.a.s = 0xbcde;

u1.i = 0x12345678;

 

/* print out the bytes of u1.buf as 2 digit hexidecimal numbers with a line break after every 8 bytes */

for(i = 0; i < 3; i++) {

for(j = 0; j < 8; j++)

printf("0x\%.2x ",u1.buf[i*8+j]);

printf("\n");

}

}

 

This program is compiled and run on a Linux/x86 machine. Fill in the output below. Write “??” if the value cannot be determined from the information provided.

 

0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____

0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____

0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____

 

Answer：

0x78 0x56 0x34 0x12 0x66 0x66 0x66 0x66

0x66 0x66 0x0a 0xc0 0x00 0x00 0x80 0x3f

0xde 0xbc 0x00 0x00 0x00 0x00 0x00 0x00

 

 

2．The representation of program

 

The following problem tests your understanding of how for loops in C relate to IA32 machine code. Consider the following IA32 assembly code for a procedure dog():

 

dog:

pushl %ebp

movl %esp, %ebp

movl 12(%ebp), %ecx

movl $1, %eax

movl 8(%ebp), %edx

cmpl %ecx, %edx

jge .L7

.L5:

imull %edx, %eax

addl $2, %edx

cmpl %ecx, %edx

jl .L5

.L7:

popl %ebp

ret

 

Based on the assembly code, fill in the blanks below in its corresponding C source code. (Note: you may only use symbolic variables x, y, i, and result, from the source code in your expressions below — do not use register names.)

 

int dog(int x, int y)

{

int i, result;

result = ________;

for (i = ________; _____________; ________)

result = _________________;

return result;

}

 

Answer：

int dog(int x, int y)

{

  int i, result;

  result = 1;

  for(i=x;i< y;i+=2)

    result = result*i;

  return result;

}

 

 

3. virtural memory

 

The following problem concerns the way virtual addresses are translated into physical addresses. The memory is byte addressable, and memory accesses are to 1-byte (not 4-byte) words; Virtual addresses are 18 bits wide; Physical addresses are 13 bits wide; The page size is 512 bytes; The TLB is 8-way set associative with 16 total entries; The cache is 2-way set associative, with a 4-byte line size and 32 total entries. In the following tables, all numbers are given in hexadecimal. The contents of the TLB and the page table for the first 32 pages, and the cache are as follows:

 

TLB

 

Page Table:

 

Cache

 

For the given virtual addresses, indicate the TLB entry accessed and the physical address. Indicate whether the TLB misses and whether a page fault occurs.If there is a cache miss, enter “-” for “Cache Byte Returned.” If there is a page fault, enter “-” for “PPN” and leave part 3 blank.

 

Virtual Address: 0x1A854

 

1. Virtual address format (one bit per box)

 

2. Address translation

 

3. Physical address format (one bit per box)

 

4. Physical memory reference

 

Answer:

1.      Virtual address format (one bit per box)

 

2. Address translation

 

3. Physical address format (one bit per box)

 

4. Physical memory reference

 

 

Problem 4: Linking

The program below consists of three source files: common.h, main.c and sub.c.The corresponding relocatable object modules is also listed. Please fill in blanks and answer questions.

 

common.h:

typedef struct node {

__________ x;// x must be a scalar

    unsigned short y;

    struct node *next;

    struct node *prev;

} node_t;

 

main.c:

#include "common.h"

void sub();

node_t n;

int main() {

    sub();

    return 0;

}

 

sub.c:

#include "common.h"

extern node_t n;

void sub() {

    node_t *m;

    m = n.next->prev;

      = 16;

    return;

}

(a) C code

 

00000000 <main>:

   0:   55        push   %ebp

   1:   89 e5      mov    %esp,%ebp

   3:   83 ec 08    sub    $0x8,%esp

   6:   83 e4 f0    and    $0xfffffff0,%esp

   9:   e8 fc ff ff ff               call    a <main+0xa>

    a: R_386_PC32   sub

   e:   b8 00 00 00 00         mov    $0x0,%eax

  13:   c9          leave

  14:   c3          ret

(b) .text section of relocatable object file main.o

 

00000000 <sub>:

   0:   55        push    %ebp

   1:   89 e5      mov    %esp,%ebp

   3:   a1 0c 00 00 00         mov    0xc,%eax

    4: R_386_32     n

   8:   8b 40 10   mov    0x10(%eax),%eax

   b:   66 c7 40 08 10 00      movw   $0x10,0x8(%eax)

  11:   c9          leave

  12:   c3          ret

(c) .text section of relocatable object file sub.o

 

Questions:

Suppose the linker had decided to locate function main at 0x80482f4 and locate function sub at 0x08048308 and determined that the address of symbol n is 0x80494d0.

A.     What is the hex address of the relocated reference to sub?

B.     What is the hex value of the relocated reference to sub?

C.     What will the third instruction(a1 0c 00 00 00) of sub.o be after relocation?

 

The types must be chosen from the following table, assuming the sizes and alignment given.

 

Answer:

填空部分：double、m->y

问答部分：A. 0x80482fe       B. 0x6    C. a1 dc 94 04 08 

 

 

Problem 5: Exception control flow

This problem tests your understanding of Unix process control. Consider the following C program.

 

int main()

{

int status;

int counter = 1;

if (fork() == 0) {

counter++;

printf("%d",counter);

}

else {

if (fork() == 0) {

printf("9");

counter--;

printf("%d",counter);

exit(0);

}

else {

if (wait(&status) > 0) {

printf("6");

}

}

}

printf("8");

exit(0);

}

 

For each of the following strings, circle whether (Y) or not (N) this string is a

possible output of the program.

A. 298068   Y    N

B. 291688    Y    N

C. 920688   Y    N

D. 268908   Y    N

E. 906828    Y    N

 

Answer:

A. Y、   B. N、   C. Y、   D. N、  E. Y

 

 

Problem 6: I/O

Suppose the disk file foobar.txt consists of the 6 ASCII characters “foobar”. Then what is the output of the following program on the stdout?

 

#include “csapp.h”

int main()

{

       int fd1, fd2, fd3;

       char c;

      

       fd1 = Open(“foo.txt”, O_RDONLY, 0);

       if(Fork() == 0)

{

    fd2 = Open(“foo.txt”, O_RDONLY, 0);

    Read(fd1, &c, 1);

    Dup2(fd2, fd1);

    Read(fd1, &c, 1);

    printf(“fd1 = %d\n”, fd1);

    printf(“c = %c\n”, c);

       }

       wait(NULL);

       fd3 = Open(“foo.txt”, O_WRONLY, 0);

       Write(fd3, “Hi”, 2);

       Read(fd1, &c, 1);

       printf(“fd3 = %d\n”, fd3);

       printf(“c = %c\n”, c);

}

 

Answer:

fd1 = 3

c = f

fd3 = 5

c = i

fd3 = 4

c = i