CS/컴퓨터구조 & OS

[OS] 저수준에서 교착 상태에 대비하는 방법

1. 교착 상태란? 면접관: 교착 상태에 대해 설명해주시면 채용하겠습니다. 면접자: 저를 채용해주시면 교착 상태에 대해 설명하겠습니다. 간단하게 예를 들면 이런 상황이라고 할 수 있다. 면접관은 내가 교착 상태를 설명하기를 기다리고 있지만 면접자는 자신을 채용해주기를 기다리고 있다. 누군가가 양보하지 않는 한 둘은 영원히 기다리게 될 것이다. 이번엔 코드로 예시를 들어보겠다. 스레드 1은 아래의 함수를 실행한다. void *do_work_one() { pthread_mutex_lock(&first_mutex); pthread_mutex_lock(&second_mutex); /* Do some work */ pthread_mutex_lock(&second_mutex); pthread_mutex_lock(&..

배열 인덱스와 캐시 미스

결론적으로 메모리에 적게 접근하는 것보다 캐시 미스 비율을 낮추는 게 성능에 더 큰 영향을 미친다. 즉, 메모리에 자주 접근을 하더라도 배열 인덱스에 효율적으로 접근하게 코드를 작성하면 좋다는 것이다. 우선 캐시와 캐시 미스가 무엇인지, 이것과 배열 인덱스는 또 무슨 상관인지 알아볼 것이다. 1. 배열 인덱스만 바꿔도 성능이 바뀐다 for(i = 0; i (0, 1) -> (0, 2) -> (0, 3) ... for(i = 0; i < N; i++) for(j = 0; j < N; j++) sum += arr[j][i] 반면에 이..

저수준에서 최적화하는 여러가지 방법

CSAPP 5장이 컴파일러의 최적화 기법에 대한 내용인데 통념과 다른 점이나 재미있는 기법들이 많았다. 그 중 몇 가지를 소개한다. 1. 연산을 줄인다고 해서 성능이 좋아지는 것은 아니다 두 코드를 비교해보자. // 곱셈 2번 하는 버전 double poly(double a[], double x, long degree){ long i; double result = a[0]; double xpwr = x; for(i = 1; i = 0; i--){ result = a[i] + x*result; } return result; } 이 코드에서 계산하는 다항식은 \(a[0] + x(a[1] + x(a[2] + ... + x(a[degree - 1] + xa[degree])))\)이다. 위의 다항식과 똑같다. 단..

[CSAPP] 반복문, 조건문, 배열 어셈블리 코드

3.60 음 아래의 어셈블리 코드와 동일한 프로그램이 되도록 C 코드의 빠진 부분을 채워라. 함수 결과가 레지스터 %rax에 저장되는 것을 기억하라. # long loop(long x, int n) # x in %rdi, n in %esi loop: movl%esi, %ecx movl$1, %edx movl $0, %eax jmp.L2 .L3: movq%rdi, %r8 andq%rdx, %r8 orq%r8, %rax salq%cl, %rdx .L2: testq%rdx, %rdx jne.L3 rep; ret long loop(long x, long n) { long result = _____; long mask; for(mask = _____; mask _____; mask = _____) { result..

[CSAPP 2장] 숙제문제4 - 부동소수점

2.83 0.y y y y ...와 같은 무한 스트링으로 이뤄진 이진 표시를 갖는 숫자들에 대해 생각해보자. y는 k비트 길이의 순열이다. 예를 들어 \( \frac{1}{3} \)을 이진수로 표시하면 0.0101010101...(y = 01, k = 2)이며, \( \frac{1}{5} \)은 0.001100110011...(y = 0011, k = 4)료 표시한다. A. \(Y = B2U_k(y)\)라고 하자. 즉 Y는 이진수 표시 y를 갖는 십진수이다. 무한 스트링으로 나타낸 값을 Y와 k를 사용한 식으로 나타내시오. 힌트: 이진 소수점을 k만큼 우측으로 이동한 효과에 대해 생각해보라. B. 다음과 같은 y 스트링의 숫자 값은 얼마인가? (a) 101 (b) 0110 (c) 010011 A. n =..

[CSAPP 2장] 숙제문제3 - 오버플로우, 곱셈 & 나눗셈 비트 연산

2.76번 빌드업XDR 라이브러리의 보안 취약성XDR 라이브러리는 널리 사용되는 프로그램 간 자료구조를 공유하는 모듈이다. 이 라이브러리를 구현한 코드에서 곱셈 결과를 프로그램에 알려주지 않은 채로 오버플로우를 발생시키는 보안 취약성이 있다는 것이 발견되었다.void *copy_elements(void *ele_src[], int ele_cnt, size_t ele_size) { /* * 각각 ele_size 바이트 크기를 갖는 ele_cnt개의 객체를 * 빈 버퍼로 복사한 후 버퍼를 리턴한다 */ void *result = malloc(ele_cnt * ele_size); if(result == NULL) return NULL; void *next = result; int i;..

[CSAPP 2장] 숙제문제2 - 비부호형, 부호형의 비트 연산

2.64 x의 홀수 번째 비트가 1이면 1을 리턴하고 아닐 경우에는 0을 리턴하는 함수를 작성하시오. 정답 코드 #include int any_odd_one(unsigned x) { return !!(0x55555555 & x); } int main(void) { int no_one = 0x2; int any_one = 0x7; printf("%d\n", any_odd_one(no_one)); printf("%d\n", any_odd_one(any_one)); return 0; } 5는 2진수로 0101이고 이는 홀수 번째 비트만 1로 뒀을 때의 수이다. 그래서 5와 & 연산을 하면 하나라도 1인 홀수 번째 비트를 갖는 수는 결과가 true가 나온다. 0이나 1로 딱 떨어지진 않고 거의 양수가 나와서 &..

[CSAPP 2장] 숙제 문제

https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter2/ Representing and Manipulating Information - CASPP 3e Solutions Chapter 2 Representing and Manipulating Information Everything is physics and math.by Katherine Johnson solutioncode filetest... dreamanddead.github.io 내가 풀긴 풀되 더 나은 답안과 비교하기 위해 이곳을 참고하면서 풀기로 한다. 2.55 여러분이 사용할 수 있는 여러 가지 머신에서 show_bytes를 사용하는 샘플 코드를 컴파일하고 실행하라. 이 머신들의 바이트 순서..