Things to Remember

<Compiler vs Interpreter>

• Compiler

1. Translates the entire source code in a single run 

2. Compile을 실행(execution)전에 수행 

3. High MEM usage

4. 오류를 동시에 표시 

5. Ex) C / C++

• Interpreter

1. Translates the entire code line by line 

2. Compile과 실행(execution)이 동시에 실행 

3. Low MEM usage 

4. 각 줄의 오류를 하나씩 표시 

5. Ex) Python

<Instance method vs Static method>

• Static method란 method앞에 static이 붙은 메소드를 말한다. 객체 생성없이 호출이 가능하다.

• Static method belongs to a class, while an instance method belongs to an instance of a class.

• Instance method can access the instance methods and variable 

• Instance method can access the static methods and variable 

• Static method can access the static methods and variable 

• Static method cannot access the instance method and variable

<Call Stack>

• Dynamic data structure maintained inside the RAM by OS 

• The purpose is to control the way procedures and functions call each other and to control the way they pass parameters to each other.

• Local variables on the call stack is part of the rootset in garbage collection.

<Procedure Call>

• Procedure Call이 발생하면 반드시 일어나는 것들

1. Program counter가 update된다 

2. Stack pointer가 update된다. (함수호출이 완료된 이후 돌아오는 위치를 Stack에 저장)

• Stack pointer register: Stack에 데이터를 쌓거나 반환하기 위해서는 현재 어느위치까지 데이터를 저장했는지 기억해야 함. 호출된 함수가 종료시에 stack frame 단위로 sp register 값을 이동시켜야 한다. 

<Stack Frame>

• Stack frame is a frame of data that gets pushed onto the stack. In the case of call stack (see above), a stack frame would represent a function call and its argument data.

• The function's return address is pushed onto the stack first, then the arguments and space for local variables. Together, they make the frame.

• 메모리의 스택(stack)영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역이다.

• 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.

• 함수가 호출되면 stack에는 함수의 매개변수, 함수에서 선언된 지역변수, 호출이 끝난 뒤 돌아갈 반환주소값등이 저장된다. 

<Functional Completeness>

• {NOT, AND}

• {NOT, OR}

• {XOR, AND}

• {XOR, OR}

<Sequential circuit vs Combinational circuit>

• Sequential circuit (순차회로): Counter(= filp-flop with gate), 기억이나 상태의 저장 

• Combinational circuit (조합회로): 산술연산과 논리연산, 연산또는 직접적인 제어 

1. Decoder: n비트로 구성된 주소를 받아서 2^n개의 개별라인을 활성화 시키는 장치이다. 하나의 입력을 여러개의 출력으로 만들어준다. 여러출력으로 만들어 준다는 것은 '적절한 출력 Line에 데이터를 보내준다'는 뜻이다.

2. Multiplexer: 2^n개의 입력선 중에서 하나를 선택하여 출력선에 연결시켜 주는 회로. 여러 입력 중 하나를 출력하는 기능을 한다. MUX는 여러 데이터 중 하나를 출력한다.

<DMA (Direct Memory Access)>

• DMA is a method that allows an I/O device to send or receive data directly to or from the main memory (MEM), by-passing the CPU to speed up memory operations.

<Distributed System>

• 하나의 시스템처럼 보이는 독립된 컴퓨터들의 집합

• 왜 우리는 distributed system이 필요한가? (1) 자원의 부족, (2) 장애시 대처, (3) 자원 접근의 편리성

<Symmetric Difference>

• See the below figure.

<Static (Lexical) scoping = Dynamic scoping>

• Static (Lexical) scoping: 변수나 함수가 정의된 곳의 (=부르는 곳의) context를 사용

• Dynamic scoping: 변수나 함수의 불려진 곳의 context를 사용. 거기까지가서 (=함수를 타고가서) 그 함수에 정의되어 있는 것(=변수)를 사용. 이전에 정의 되었던 것이 있다면 그냥 그것을 덮어쓴다. 

<Direct representation vs Indirect representation>

• Direct representation (Stack storage): accessing of component is fast

• Indirect representation (Heap storage): compilation time is fast.

• When the storage size of some private component of a variable changes, indirect representation minimizes the number of recompilations of source modules that must be performed.

<Ripple Carry Adder>

• 계산시간: Tc * (k - 1) + Ts (k bits을 연산한다고 가정)

  • Tc: Carry output delay 

  • Ts: Sum output delay

<Church-Turing Thesis = Church's thesis = Church's conjecture = Turing's thesis>

• 이 가설은 기계적인 방법으로 수행될 수 있는 모든 계산은 어떤 튜링기계에 의해여 실행될 수 있다는 것을 말한다.

• 모든 효율적인(effective) 계산이나 알고리즘은 Turing machine에서 수행될 수 있다.

• 이 Thesis는 하나의 정리(theorem)의 형태를 가지고 있지 않으며 증명될 수 없다. 

<Master Theorem>

• The Master Theorem is used in calculating the time complexity of recurrence relations (divide and conquer algorithms) in a simple and quick way.

<Raymonds tree based algorithm>

• Raymonds tree based algorithm ensures no deadlock but starvation may occur.

• 4 principles of OOP (Object Oriented Programming)

1. Encapsulation: Class로 묶어주는 것

2. Inheritance: 상속

3. Abstraction: 공통적인 속성과 기능을 정의함으로서 코드의 중복을 줄이고 클래스간 관계를 효과적으로 설정하고 유지/보수를 용이하게 한다. 

4. Polymorphism: Overloading

• (For all x) P(x) V (For all x) Q(x) ---> (For all x) (P(x) V Q(x)).  반대방향으로는 불가능하다. 묶어주는 것은 가능하나, 펼쳐주는 것은 불가능하다.

• (There exists x) P(x) V (There exists x) Q(x) ---> (There exists x) (P(x) V Q(x)). 반대방향으로 불가능하다. 묶어주는 것은 가능하다, 펼쳐주는 것은 불가능하다. 

<1's complement vs 2's complement>

• 1's complement:

  • 방법: 그냥 비트를 다 반전시켜주면 된다. 

  • 예를들어 0011의 1's complement는 1100이다.

• 2's complement 

  • 방법: 비트를 반전시킨 후, LSB에 1을 더해준다.

  • 2진수로 표현된 숫자의 가장 큰 자리수비트(MSB)를 부호를 표기하는데 사용한다. 앞자리가 0이면 양수이고 앞자리가 1이면 음수이다.

  • 예를들어 0010(=십진수로 2)의 2's complement를 구하는 방법은 다음과 같다. 0010 -- 비트반전 --> 1101 -- LSB에 1을 더해준다 --> 1110(=십진수로 -2)

  • 0010 + 1110 = 10000인데 앞에 1은 버려준다 (애초에 4bit밖에 없었기 때문).

<Logic>

• Tautology: 항상 참

• Contradiction: 항상 거짓

• Contingency: Sometimes 참, sometimes 거짓. It is the status of propositions that are neither true under every possible valuation (i.e. tautologies) nor false under every possible valuation (i.e. contradictions)

• Satisfiability: At least 하나는 TRUE이다.

<Static allocation vs Stack allocation>

• Static allocation does not make data structure dynamically (recursive procedures X)

• Stack allocation make data structure and objects dynamically (recursive produres O)

<Garbage Collection>

• Reference counting

1. '스마트포인터'라는 것이 있는데 이는 내부적으로 레퍼런스 카운드를 유지하고 있다가, 이 값이 0이 되면 그 때 해당 객체의 메모리를 해제하는 것이다. 

2. Reference count가 0인 객체들의 메모리는 더 이상 쓰이지 않는다고 봐도 좋으며 Garbage collection의 대상이 된다. 

3. GC Root로 부터 닿지 않는 사이클(cycle)이 생긴 객체들도 Garbage collection의 대상이 된다. 

4. 단점: 참조 횟수를 track하여야 하는데, 이는 overhead 발생 시킬 수 있다. 또한 cyclic reference때문에 memory leak이 발생할 수 있다. 

• Mark and Sweep

1. GC Root로 부터 시작하여 닿을 수 있는(reachable) 객체들을 식별하고, 닿지 않는 객체들은 정리하여 그 객체들이 사용하던 메모리를 다시 사용할 수 있도록 한다. 

2. Mark: GC Root로 부터 시작하여 닿을 수 있는 모든 객체들을 식별하며, 그것을 기록해둔다.

3. Sweep: Mark단계에서 식별되지 못한, 즉 닿을 수 없는 객체들의 메모리를 해제하여 재사용 할 수 있도록 한다. 

4. 메모리의 파편화(fragmentation)문제가 발생한다. 

• Stop the world:

1. Garbage collection이 일어나면 돌고 있던 애플리케이션 thread들은 잠시 하던 일을 멈추어야 한다. 애플리케이션 thread가 멈추어야 현재 메모리 상에서 살아 있는 객체를 정확히 식별 할 수 있기 때문이다. 

2. 이렇게 애플리케이션의 thread가 잠시 멈추는 것을 Stop the world라 부른다.