a = !(x + 1);
b = !x;
c = !((x & 0xff) ^ 0xff);
d = !(x >> ((sizeof(int) - 1) << 3) & 0xff);
// 暴力做法，每一次都假定x满足要求，然后把对应bit转化为0bool int_shifts_are_arithmetic(){
return !!((-1 >> 1) ^ INT_MAX);
// 逻辑右移的情况下，-1>>1是INT_MAX，与自身进行Xor操作得0
}/* Return 1 when x contains an odd number of 1s; 0 otherwise.
Assume w=32. The function cantains less than 12 operations. */
int odd_ones(unsigned x){
x ^= (x >> 16);
x ^= (x >> 8);
x ^= (x >> 4);
x ^= (x >> 2);
x ^= (x >> 1);
return x & 1;
// 由于Xor操作的性质，不会改变操作数的奇偶性
// 用二分方法，每一次操作都把高(len/2)位的奇偶性加载到低(len/2)上
}第一题：A有一点小问题，其他正确
第二题：有误
第三题：正确
第一行：208、0 1100 1110、208
第二行：-7/1024、1 0000 0111、-7/1024
第三行：5/131072、0 0000 0001、1/1024
第四行：-4096、1 1110 1111、-248
第五行：768、0 1111 0000、+INF
float_bits float_negate(float_bits f){
int exp = (f >> 23) & 0xff;
int frac = f & 0x7fffff;
if (!(exp ^ 0xff) && frac){
return f;
}
return f ^ (1 << 31);
}int float_f2i(float_bits f){
int sign = (f >> 31) & 1;
int exp = (f >> 23) & 0xff - 127; // 计算2的幂指数部分
int frac = f & 0x7fffff;
if (exp >= 32 || (exp == 31 && !frac)){ // INF的情况需要向0舍入
return 0x80000000;
}else if (exp < 0){
return 0;
}
frac += 0x800000; // 将尾数加上隐藏的1
int frac = f & 0x7fffff + 0x800000; // 将尾数加上隐藏的1
if (exp >= 23){
if (sign)
return -(frac << (exp - 23));
else
return (frac << (exp - 23));
}else{
if (sign)
return -(frac >> (23 - exp)); //直接右移可以达到向0取整的目的
else
return (frac >> (exp - 23));
}
}第一题：正确
第二题：正确
第三题：有一点小错误
A. %rdi，%esi，%eax，%rdx
B.0，1
C.mask != 0
D.每一次左移n位
E.每一次或(mask & x)
long loop (long x, int n){
long result = 0;
long mask;
for (mask = 1; mask != 0; mask = mask << n){
result |= (mask & x);
}
}typedef enum {MODE_A, MODE_B, MODE_C, MODE_D, MODE_E} mode_t;
long switch3(long *p1, long *p2, mode_t action){
long result = 0;
switch(action){
case MODE_A:{
result = *p2;
*p2 = (long)action;
return result;
}
case MODE_B:{
result = *p1;
result += *p2;
*p1 = result;
return result;
}
case MODE_C:{
*p1 = 59;
result = *p2;
return result;
}
case MODE_D:{
result = *p2;
*p1 = result;
result = 27;
return result;
}
case MODE_E:
return (result = 27);
default:{
return (result = 12);
}
}
}对于一个给定的三维数组A[R][C][H]：
A. &A[i][j][k] = x0 + L * ( i * C * H + j * H)，其中x0为数组的起始地址，L为单位元素的字节长度。
B. R = 7; S = 5; T = 13;
第一题：正确
第二题：MODE_A有误（另外，最好用break，代码最后有return result;）
第三题：A有误
A = 9; B = 5;
A. CNT = 7;
B.
typedef struct{
long idx;
long x[4];
} a_struct;A. 0, 8, 0, 8;
B. 16;
C.
void proc(union ele *up){
up->e2.x = *(up->e2.next->e1.p) - up->e2.next->e1.y;
}第一题：正确
第二题：正确
第三题：正确
// C Code
#include <stdio.h>
int a[8] = {8, 7, 6, 5, 4, 3, 2, 1};
void bubble_a(int *data, int count){
long i, last;
for (last = count - 1; last > 0; last--){
for (i = 0; i < last; i++){
if (*(data + i + 1) < *(data + i)){
int t = *(data + i + 1);
*(data + i + 1) = *(data + i);
*(data + i) = t;
}
}
}
}
int main(){
bubble_a(a, 8);
return 0;
}
-----------------------------------------------
// Y86 code with sample data
# Execution begins at address 0
.pos 0x0
irmovl stack,%esp
irmovl stack,%ebp
call main
halt
main:
pushl %ebp
rrmovl %esp,%ebp
irmovl 8,%eax
pushl %eax
irmovl 0x194,%eax
pushl %eax
call bubble_a
irmovl $8,%ebx
addl %ebx,%esp
irmovl $0,%eax
rrmovl %ebp,%esp
popl %ebp
ret
bubble_a:
pushl %ebp
rrmovl %esp,%ebp
irmovl $0x10,%eax
subl %eax,%esp
mrmovl 12(%ebp),%eax
irmovl $1,%ebx
subl %ebx,%eax
rmmovl %eax,-8(%ebp)
jmp check1
loop1:
irmovl $0,%ebx
rmmovl %ebx,-12(%ebp)
jmp check2
loop2:
mrmovl -12(%ebp),%eax
irmovl $1,%ebx
addl %ebx,%eax
addl %eax,%eax
addl %eax,%eax
rrmovl %eax,%edx
mrmovl 8(%ebp),%eax
addl %edx,%eax
mrmovl (%eax),%edx
mrmovl -12(%ebp),%eax
addl %eax,%eax
addl %eax,%eax
rrmovl %eax,%ecx
mrmovl 8(%ebp),%eax
addl %ecx,%eax
mrmovl (%eax),%eax
rrmovl %edx,%ebx
subl %eax,%ebx
jge check3
mrmovl -12(%ebp),%eax
irmovl $1,%ebx
addl %ebx,%eax
addl %eax,%eax
addl %eax,%eax
rrmovl %eax,%edx
mrmovl 8(%ebp),%eax
addl %edx,%eax
mrmovl (%eax),%eax
rmmovl %eax,-4(%ebp)
mrmovl -12(%ebp),%eax
irmovl $1,%ebx
addl %ebx,%eax
addl %eax,%eax
addl %eax,%eax
rrmovl %eax,%edx
mrmovl 8(%ebp),%eax
addl %eax,%edx
mrmovl -12(%ebp),%eax
addl %eax,%eax
addl %eax,%eax
rrmovl %eax,%ecx
mrmovl 8(%ebp),%eax
addl %ecx,%eax
mrmovl (%eax),%eax
rmmovl %eax,(%edx)
mrmovl -12(%ebp),%eax
addl %eax,%eax
addl %eax,%eax
rrmovl %eax,%edx
mrmovl 8(%ebp),%eax
addl %eax,%edx
mrmovl -4(%ebp),%eax
rmmovl %eax,(%edx)
check3:
irmovl $1,%ebx
mrmovl -12(%ebp),%eax
addl %ebx,%eax
rmmovl %eax,-12(%ebp)
check2:
mrmovl -12(%ebp),%eax
mrmovl -8(%ebp),%ebx
subl %ebx,%eax
jl loop2
irmovl $1,%ebx
mrmovl -8(%ebp),%eax
subl %ebx,%eax
rmmovl %eax,-8(%ebp)
check1:
mrmovl -8(%ebp),%eax
irmovl $0,%ebx
subl %ebx,%eax
jg loop1
nop
rrmovl %ebp,%esp
popl %ebp
ret
.align 4
data:
.long 0x8
.long 0x7
.long 0x6
.long 0x5
.long 0x4
.long 0x3
.long 0x2
.long 0x1
.pos 1000
stack:// changes:
# Predict next value of PC
int f_predPC = [
# BBTFNT: This is where you'll change the branch prediction rule
f_icode == IJXX && f_ifun != UNCOND && f_valC < f_valP : f_valC;
f_icode == IJXX && f_ifun == UNCOND : f_valC;
f_icode == ICALL : f_valC;
1 : f_valP;
];
## What address should instruction be fetched at
int f_pc = [
# Mispredicted forward
M_icode == IJXX && M_ifun != UNCOND && M_Cnd && M_valE >= M_valA: M_valE;
# Mispredicted backward
M_icode == IJXX && M_ifun != UNCOND && !M_Cnd && M_valE < M_valA: M_valA;
# Completion of RET instruction.
W_icode == IRET : W_valM;
# Default: Use predicted value of PC
1 : F_predPC;
];
# BBTFNT: When some branches are predicted as not-taken, you need some
# way to get valC into pipeline register M, so that
# you can correct for a mispredicted branch.
## Select input A to ALU
int aluA = [
E_icode in { IRRMOVL, IOPL } : E_valA;
E_icode in { IIRMOVL, IRMMOVL, IMRMOVL, IJXX } : E_valC;
E_icode in { ICALL, IPUSHL } : -4;
E_icode in { IRET, IPOPL } : 4;
# Other instructions don't need ALU
];
## Select input B to ALU
int aluB = [
E_icode in { IRMMOVL, IMRMOVL, IOPL, ICALL,
IPUSHL, IRET, IPOPL } : E_valB;
E_icode in { IRRMOVL, IIRMOVL, IJXX} : 0;
# Other instructions don't need ALU
];
bool D_bubble =
# Mispredicted branch
(E_icode == IJXX && E_ifun != UNCOND && e_Cnd && e_valE >= E_valA) ||
(E_icode == IJXX && E_ifun != UNCOND && !e_Cnd && e_valE < E_valA) ||
# BBTFNT: This condition will change
# Stalling at fetch while ret passes through pipeline
# but not condition for a load/use hazard
!(E_icode in { IMRMOVL, IPOPL } && E_dstM in { d_srcA, d_srcB }) &&
IRET in { D_icode, E_icode, M_icode };
# Should I stall or inject a bubble into Pipeline Register E?
# At most one of these can be true.
bool E_stall = 0;
bool E_bubble =
# Mispredicted branch
(E_icode == IJXX && E_ifun != UNCOND && e_Cnd && e_valE >= E_valA) ||
(E_icode == IJXX && E_ifun != UNCOND && !e_Cnd && e_valE < E_valA) ||
# BBTFNT: This condition will change
# Conditions for a load/use hazard
E_icode in { IMRMOVL, IPOPL } &&
E_dstM in { d_srcA, d_srcB};A.
// 内循环代码的图形化表示
%rbp %rax %xmm0 %rcx %rbx +----+
+-----|-----|------|-----|---------------->| |
| | | +-----|---------------->|load| // load udata
| | | | | | |--------------------+
| | | | | +----+ |
| +-----|------|-----|---------------->| | |
| | | +-----|---------------->|load| // load vdata [%xmm1]
| | | | | | |-------+ |
| | | | | +----+ [unknown] |
| | | | | | |<------+ |
| | | | | |mul |<-------------------+
| | | | | | |-------+
| | | | | +----+ [%xmm1]
| | +------|-----|---------------->| | |
| | | | |add |<------+
| | +------|-----|-----------------| |
| | | | | +----+
| | | +-----|---------------->| |
| | | | |add |
| | | +-----|-----------------| |
| | | | | +----+
| | | +-----|---------------->| |
| | | | +---------------->|cmp |
| | | | | | |-------+
| | | | | +----+ [unknown]
| | | | | | |<------+
| | | | | |jne |
| | | | | | |
| | | | | +----+
%rbp %rax %xmm0 %rcx %rbx
// 关键路径
%xmm %rcx
| |
|[load1]<---------+
| | [load1]<---+
| | | |
| [ mul ] [ add ]
| | |
[ add ] |
| |
%xmm0 %rcxB. 这条关键路径的CPE下界为浮点类型add操作，CPE=3.0
C. 整数类型的关键路径的CPE下界为整数类型add操作，CPE=1.0
D. 浮点乘法不在关键路径上，不存在数据关联，因此可以做流水线处理，每个时钟周期发射一条
A. 每一个元素对应两次load操作，三次整形add操作，由于能够进行load操作的只有两个功能单元。因此限制CPE不可能降低到1.0以下。
B. 浮点add操作具有数据相关性，会受到延迟界限（CPE=3.0）的限制。
第一题：正确
第二题：正确
第三题：正确（画的很棒啊！！！）
第四题：代码呢？？
| 符号 | swap.o.symtab条目？ | 符号类型 | 定义符号的模块 | 节 |
|---|---|---|---|---|
| buf | 是 | 外部 | m.o | .data |
| bufp0 | 是 | 全局 | swap.o | .data |
| bufp1 | 是 | 局部 | swap.o | .bss |
| swap | 是 | 全局 | swap.o | .text |
| temp | 否 | — | — | — |
| incr | 是 | 局部 | swap.o | .text |
| count | 是 | 局部 | swap.o | .bss |
void f(){
*(long*)(&x) = ((long)15212 << 32) + ((long)15213);
}- 0x4004f8 + (-4) - (0x4004e0 + 0xa) = 0xa (0a 00 00 00)
- 0x400500 + (-4) - (0x4004d0 + 0xa) = 0x22 (22 00 00 00)
- libc.a中一共有1649个.o文件，libm.a中一共有713个.o文件
- 是相同的（测试了一个简单的c代码）
- libc.so.6和ld-linux-x86-64.so.2
第一题：有一处错误
第二题：正确
第三题：正确
第四题：正确
| 进程对 | 并发地？ |
|---|---|
| AB | 否 |
| AC | 是 |
| AD | 是 |
| BC | 是 |
| BD | 是 |
| CD | 是 |
ACE是可能的，进行两次fork，最后是4个进程输出，第一次fork得到的子进程的后代会在结束时输出“2”，因此一定有一个2前面有1，另一个2前面有0。
#include "csapp.h"
#define N 2
#define MAXLEN 50
int main()
{
int status, i;
pid_t pid;
for (i = 0; i < N; i++)
if ((pid = Fork()) == 0){
char src = NULL;
strcpy(src, "It's a joke.\n");
}
while ((pid = waitpid(-1, &status, 0)) > 0) {
if (WIFSIGNALED(status)){
char sbuf[MAXLEN];
sprintf(sbuf, "child %d terminated by signal %d", pid, WTERMSIG(status));
psignal(WTERMSIG(status), sbuf);
}
}
if (errno != ECHILD)
unix_error("waitpid error");
exit(0);
}"fd2 = 4\n"
if (Fork() == 0){
fd = open("foo.txt", O_RDONLY, 0);
dup2(fd, STDIN_FILENO);
close(fd);
Execve("fstatcheck", agrv, envp);
}第一题：正确
第二题：正确
第三题：正确
第四题：正确
第五题：错误
// 编写虚页页号打印程序，打印出本进程能够访问到的所有虚页页号
// VirtualPage.c
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#define MAXLEN (1 << 10)
#define L (1 << 5)
int main(){
pid_t pid = getpid();
char addr[MAXLEN];
sprintf(addr, "/proc/%d/maps", pid); // get right address for file maps
FILE* fp = fopen(addr, "r"); // /proc/<PID>/maps contains memory info
char buf[MAXLEN];
char tmp[L];
long long last = -1;
while(fgets(buf, MAXLEN - 1, fp) != NULL){ // read in single line
long long begin,end;
sscanf(buf, "%llx-%llx", &begin, &end);
for(long long i = (begin >> 12); i <= (end >> 12); i++){// VP = addr/4KB
if (last != i)
printf("virtual page:0x%llx\n", i);
last = i; // avoid repeated output
}
}
fclose(fp);
return 0;
}void sigchld_hdlr(int sig);
void sigchld_hdlr(int sig){
int olderrno = errno;
while(waitpid(-1, NULL, WNOHANG) > 0){
}
errno = olderrno;
}
int main(int argc, char **argv)
{
int listenfd, connfd;
char hostname[MAXLINE], port[MAXLINE];
socklen_t clientlen;
struct sockaddr_storage clientaddr;
if (Signal(SIGCHLD, sigchld_hdlr) == SIG_ERR)
unix_error("signal error\n");
/* Check command line args */
if (argc != 2) {
fprintf(stderr, "usage: %s <port>\n", argv[0]);
exit(1);
}
listenfd = Open_listenfd(argv[1]);
while (1) {
clientlen = sizeof(clientaddr);
connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen); //line:netp:tiny:accept
Getnameinfo((SA *) &clientaddr, clientlen, hostname, MAXLINE,
port, MAXLINE, 0);
printf("Accepted connection from (%s, %s)\n", hostname, port);
doit(connfd); //line:netp:tiny:doit
Close(connfd); //line:netp:tiny:close
}
}void serve_static(int fd, char *filename, int filesize)
{
int srcfd;
char *srcp, filetype[MAXLINE], buf[MAXBUF];
/* Send response headers to client */
get_filetype(filename, filetype); //line:netp:servestatic:getfiletype
sprintf(buf, "HTTP/1.0 200 OK\r\n"); //line:netp:servestatic:beginserve
sprintf(buf, "%sServer: Tiny Web Server\r\n", buf);
sprintf(buf, "%sConnection: close\r\n", buf);
sprintf(buf, "%sContent-length: %d\r\n", buf, filesize);
sprintf(buf, "%sContent-type: %s\r\n\r\n", buf, filetype);
Rio_writen(fd, buf, strlen(buf)); //line:netp:servestatic:endserve
printf("Response headers:\n");
printf("%s", buf);
/* Send response body to client */
srcfd = Open(filename, O_RDONLY, 0); //line:netp:servestatic:open
srcp = Malloc(filesize);
Rio_readn(srcfd, srcp, filesize);
Rio_writen(fd, srcp, filesize); //line:netp:servestatic:write
Close(srcfd); //line:netp:servestatic:close
Free(srcp);
}第一题：有误
第二题：正确