먼저, Matplotlib을 사용하려면 다음과 같이 모듈을 가져와야 합니다:

import matplotlib.pyplot as plt

그리고 그래프를 Jupyter Notebook에서 인라인으로 표시하려면 다음 명령을 실행합니다:

%matplotlib inline

그래프 그리기

Matplotlib에서 가장 중요한 함수 중 하나는 plot 함수로, 2D 데이터를 그리는 데 사용됩니다. 아래는 간단한 예제입니다:

import numpy as np

# 사인 곡선을 위한 x와 y 좌표 계산
x = np.arange(0, 3 * np.pi, 0.1)
y = np.sin(x)

# Matplotlib을 사용하여 점들을 그림
plt.plot(x, y)

위 코드는 사인 함수를 그래프로 그리는 예제입니다.

그리고 조금 더 작업을 추가하여 여러 개의 선을 동시에 그리고 제목, 범례, 축 레이블을 추가할 수 있습니다:

y_sin = np.sin(x)
y_cos = np.cos(x)

# 사인과 코사인 함수를 그래프로 그림
plt.plot(x, y_sin)
plt.plot(x, y_cos)
plt.xlabel('x 축 레이블')
plt.ylabel('y 축 레이블')
plt.title('사인과 코사인')
plt.legend(['사인', '코사인'])

서브플롯

subplot 함수를 사용하여 동일한 그림 안에 다른 그래프를 그릴 수 있습니다. 아래는 서브플롯을 사용한 예제입니다:

x = np.arange(0, 3 * np.pi, 0.1)
y_sin = np.sin(x)
y_cos = np.cos(x)

# 2x1 그리드 설정하고 첫 번째 서브플롯을 활성화
plt.subplot(2, 1, 1)

# 첫 번째 그래프 그리기
plt.plot(x, y_sin)
plt.title('사인')

# 두 번째 서브플롯을 활성화하고 두 번째 그래프 그리기
plt.subplot(2, 1, 2)
plt.plot(x, y_cos)
plt.title('코사인')

# 그림 표시
plt.show()

위 코드는 두 개의 서브플롯을 하나의 그림에 그리는 예제입니다.

Matplotlib에 대한 더 자세한 내용은 Matplotlib의 공식 문서에서 확인할 수 있습니다. 이를 통해 다양한 그래프 스타일 및 기능을 배울 수 있습니다.

분할 정복의 이해

분할 정복을 이용한 정렬

분할 정복을 통한 문제 해결

그리디 알고리즘

설계 및 응용

정렬을 위한 기본 알고리즘

보다 빠른 정렬을 위한 방법

특수한 상황에서의 정렬

공간 복잡도

BIG-O 표기법

여러가지 점근적 표기법

Brute Force와 시간 복잡도

Numpy는 파이썬에서 과학 계산을 위한 핵심 라이브러리로, 다차원 배열 객체와 이러한 배열들을 다루는 도구를 제공합니다.

Numpy를 사용하려면 먼저 numpy 패키지를 가져와야 합니다:

import numpy as np

배열 (Arrays)

Numpy 배열은 동일한 유형의 값으로 구성된 grid로, 양의 정수 튜플에 의해 인덱싱됩니다. 배열의 차원 수는 배열의 Rank이며, 배열의 모양은 각 차원별로 배열의 크기를 제공하는 정수 튜플입니다.

중첩된 파이썬 리스트에서 numpy 배열을 초기화하고, 대괄호를 사용하여 요소에 접근할 수 있습니다.

a = np.array([1, 2, 3])  # 랭크 1의 배열 생성
print(type(a), a.shape, a[0], a[1], a[2])
a[0] = 5                 # 배열 요소 변경
print(a)

<class 'numpy.ndarray'> (3,) 1 2 3
[5 2 3]

b = np.array([[1,2,3],[4,5,6]])   # 랭크 2의 배열 생성
print(b)

[[1 2 3]
 [4 5 6]]

Numpy는 또한 다음과 같이 배열을 생성하는 많은 함수를 제공합니다:

a = np.zeros((2,2))  # 모든 요소가 0인 배열 생성
print(a)

[[0. 0.]
 [0. 0.]]

b = np.ones((1,2))   # 모든 요소가 1인 배열 생성
print(b)

[[1. 1.]]

c = np.full((2,2), 7) # 상수 배열 생성
print(c)

[[7 7]
 [7 7]]

d = np.eye(2)        # 2x2 단위 행렬 생성
print(d)

[[1. 0.]
 [0. 1.]]

```python
e = np.random.random((2,2)) # 무작위 값으로 채워진 배열 생성
print(e)

[[0.8690054  0.57244319]
 [0.29647245 0.81464494]]

배열 인덱싱 (Array Indexing)

Numpy는 배열에 대한 여러 가지 인덱싱 방법을 제공합니다.

슬라이싱 (Slicing): 파이썬 리스트와 유사하게, numpy 배열도 슬라이싱할 수 있습니다. 배열이 다차원일 수 있으므로 각 차원에 대한 슬라이스를 지정해야 합니다:

# 다음과 같은 모양의 랭크 2 배열을 생성합니다 (3, 4)
# [[ 1  2  3  4]
#  [ 5  6  7  8]
#  [ 9 10 11 12]]
a = np.array([[1,2,3,4], [5,6,7,8], [9,10,11,12]])

# 슬라이싱을 사용하여 첫 2개의 행과 1번째 및 2번째 열로 이루어진 하위 배열을 가져옵니다.
# b는 다음과 같은 모양의 배열입니다 (2, 2):
# [[2 3]
#  [6 7]]
b = a[:2, 1:3]
print(b)

[[2 3]
 [6 7]]

배열의 슬라이스는 동일한 데이터의 뷰(View)이므로 수정하면 원래 배열도 수정됩니다.

print(a[0, 1])   # 0번째 행, 1번째 열의 요소 출력
b[0, 0] = 77     # b[0, 0]은 a[0, 1]과 같은 데이터입니다.
print(a[0, 1])   # b를 수정하면 a도 수정됩니다.

2
77

정수 인덱싱과 슬라이스 인덱싱을 혼합해서 사용할 수도 있지만, 그렇게 하면 원래 배열보다 낮은 랭크의 배열이 생성됩니다. 이것은 MATLAB에서 배열 슬라이싱을 처리하는 방식과 매우 다릅니다.

# 다음과 같은 모양의 랭크 2 배열을 생성합니다 (3, 4)
a = np.array([[1,2,3,4], [5,6,7,8], [9,10,11,12]])
print(a)

[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

데이터의 중간 행에 대한 데이터에 접근하는 두 가지 방법입니다. 정수 인덱싱과 슬라이스를 혼합하면 원래 배열보다 낮은 랭크의 배열이 생성됩니다. 슬라이스만 사용하면 원래 배열과 동일한 랭크의 배열이 생성됩니다.

row_r1 = a[1, :]    # a의 두 번째 행에 대한 랭크 1 뷰(View)
row_r2 = a[1:2, :]  # a의 두 번째 행에 대한 랭크 2 뷰(View)
row_r3 = a[[1], :]  # a의 두 번째 행에 대한 랭크 2 뷰(View)
print(row_r1, row_r1.shape)
print(row_r2, row_r2.shape)
print(row_r3, row_r3.shape)

[5 6 7 8] (4,)
[[5 6 7 8]] (1, 4)
[[5 6 7 8]] (1, 4)

열에 대한 데이터에 접근할 때도 동일한 구분을 할 수 있습니다:

col_r1 = a[:, 1]
col_r2 = a[:, 1:2]
print(col_r1, col_r1.shape)
print()
print(col_r2, col_r2.shape)

[ 2  6 10] (3,)
[[ 2]
 [ 6]
 [10]] (3, 1)

정수 배열 인덱싱 (Integer Array Indexing): 슬라이싱을 사용하여 numpy 배열에 인덱싱할 때 결과 배열은 항상 원래 배열의 하위 배열(View)입니다. 반면, 정수 배열 인덱싱을 사용하면 다른 배열의 데이터를 사용하여 임의의 배열을 구성할 수 있습니다.

a = np.array([[1,2], [3, 4], [5, 6]])

# 정수 배열 인덱싱의 예시입니다.
# a의 원소 중 값이 2보다 큰 원소를 찾아냅니다. 결과는 a와 동일한 모양의 불리언 배열입니다.
bool_idx = (a > 2)
print(bool_idx)

[[False False]
 [ True  True]
 [ True  True]]

불리언 배열 인덱싱을 사용하여 a에서 값이 2보다 큰 원소를 선택할 수 있습니다.

# 불리언 배열 인덱싱을 사용하여 a의 값이 2보다 큰 원소를 선택하여 랭크 1 배열을 만듭니다.
print(a[bool_idx])

# 위의 예시를 한 문장으로 간략하게 작성할 수도 있습니다.
print(a[a > 2])

[3 4 5 6]
[3 4 5 6]

더 자세한 내용은 numpy 배열 인덱싱에 대한 문서를 참조하세요.

데이터 타입 (Datatypes)

Numpy 배열은 항상 동일한 유형의 요소로 구성됩니다. Numpy는 배열을 만들 때 데이터 타입을 추측하지만, 배열을 생성하는 함수에는 데이터 타입을 명시적으로 지정할 수 있는 옵션 인수도 포함됩니다. 예를 들어:

x = np.array([1, 2])  # Numpy가 데이터 타입을 자동으로 선택하게 합니다.
y = np.array([1.0, 2.0])  # Numpy가 데이터 타입을 자동으로 선택하게 합니다.
z = np.array([1, 2], dtype=np.int64)  # 특정 데이터 타입을 강제로 지정합니다.

print(x.dtype, y.dtype, z.dtype)

int64 float64 int64

모든 numpy 배열은 동일한 데이터 타입의 요소로 구성되며, 데이터 타입을 명시적으로 지정할 수 있습니다. numpy 데이터 타입에 대한 자세한 내용은 numpy 문서를 참조하세요.

배열 수학 (Array Math)

기본 수학 함수는 배열의 각 요소에 대해 작동하며, 연산자 오버로드로도 사용할 수 있으며 numpy 모듈의 함수로도 사용할 수 있습니다:

x = np.array([[1,2],[3,4]], dtype=np.float64)
y = np.array([[5,6],[7,8]], dtype=np.float64)

# 요소별 합; 두 방법 모두 배열을 생성합니다.
print(x + y)
print(np.add(x, y))

[[ 6.  8.]
 [10. 12.]]
[[ 6.  8.]
 [10. 12.]]

# 요소별 차; 두 방법 모두 배열을 생성합니다.
print(x - y)
print(np.subtract(x, y))

[[-4. -4.]
 [-4. -4.]]
[[-4. -4.]
 [-4. -4.]]

# 요소별 곱; 두 방법 모두 배열을 생성합니다.
print(x * y)
print(np.multiply(x, y))

[[ 5. 12.]
 [21. 32.]]
[[ 5. 12.]
 [21. 32.]]

# 요소별 나눗셈; 두 방법 모두 배열을 생성합니다.
# [[ 0.2         0.33333333]
#  [ 0.42857143  0.5       ]]
print(x / y)
print(np.divide(x, y))

[[0.2        0.33333333]
 [0.42857143 0.5       ]]
[[0.2        0.33333333]
 [0.42857143 0.5       ]]

# 요소별 제곱근; 배열을 생성합니다.
# [[ 1.          1.41421356]
#  [ 1.73205081  2.        ]]
print(np.sqrt(x))

[[1.         1.41421356]
 [1.73205081 2.        ]]

MATLAB과 달리 *는 요소별 곱셈이며 행렬 곱셈이 아닙니다. 행렬의 내적, 행렬과 벡터의 곱셈, 행렬 곱셈을 계산하려면 dot 함수를 사용합니다. dot 함수는 numpy 모듈의 함수로 사용하거나 배열 객체의 인스턴스 메서드로 사용할 수 있습니다:

Copy code
x = np.array([[1,2],[3,4]])
y = np.array([[5,6],[7,8]])

v = np.array([9,10])
w = np.array([11, 12])

# 벡터의 내적; 두 방법 모두 스칼라 219를 생성합니다.
print(v.dot(w))
print(np.dot(v, w))

219
219

numpy의 dot 연산자(@)를 사용하여도 동일한 결과를 얻을 수 있습니다:

print(v @ w)

219

# 행렬 / 벡터 곱셈; 두 방법 모두 랭크 1 배열 [29 67]을 생성합니다.
print(x.dot(v))
print(np.dot(x, v))
print(x @ v)

[29 67]
[29 67]
[29 67]

# 행렬 / 행렬 곱셈; 두 방법 모두 랭크 2 배열을 생성합니다.
# [[19 22]
#  [43 50]]
print(x.dot(y))
print(np.dot(x, y))
print(x @ y)

[[19 22]
 [43 50]]
[[19 22]
 [43 50]]
[[19 22]
 [43 50]]

Numpy는 배열을 사용한 계산을 수행하기 위한 많은 유용한 함수를 제공합니다. 그 중에서도 가장 유용한 함수 중 하나는 sum입니다:

x = np.array([[1,2],[3,4]])

# 모든 원소의 합 계산; "10"을 출력합니다.
print(np.sum(x))

# 각 열의 합 계산; "[4 6]"을 출력합니다.
print(np.sum(x, axis=0))

# 각 행의 합 계산; "[3 7]"을 출력합니다.
print(np.sum(x, axis=1))

모든 수학 함수의 전체 목록은 numpy 문서에서 찾을 수 있습니다.

수학 함수를 배열에 대해 계산하는 것 외에도 데이터를 다시 모양을 변경하거나 다른 방식으로 조작해야 할 때가 자주 있습니다. 가장 간단한 예는 행렬의 전치(transpose)입니다. 행렬을 전치하려면 배열 객체의 T 속성을 사용하면 됩니다:

print(x)
print("전치\n", x.T)

[[1 2]
 [3 4]]
전치
[[1 3]
 [2 4]]

브로드캐스팅 (Broadcasting)

브로드캐스팅은 numpy가 산술 연산을 수행할 때 다른 모양의 배열과 함께 작업할 수 있게 하는 강력한 메커니즘입니다. 종종 더 작은 배열과 더 큰 배열이 있고 작은 배열을 여러 번 큰 배열에 적용하여 어떤 연산을 수행하려고 합니다.

예를 들어, 행렬의 각 행에 상수 벡터를 더하려고 한다고 가정해보겠습니다. 이를 다음과 같이 수행할 수 있습니다:

# x 행렬의 각 행에 v 벡터를 더하고 결과를 y 행렬에 저장합니다.
x = np.array([[1,2,3], [4,5,6], [7,8,9], [10, 11, 12]])
v = np.array([1, 0, 1])
y = np.empty_like(x)   # x와 동일한 모양의 빈 행렬을 생성합니다.

# 명시적 루프를 사용하여 x 행렬의 각 행에 v 벡터를 더합니다.
for i in range(4):
    y[i, :] = x[i, :] + v

print(y)

[[ 2  2  4]
 [ 5  5  7]
 [ 8  8 10]
 [11 11 13]]

이렇게 작업은 잘 작동하지만, 행렬 x가 매우 큰 경우 파이썬에서 명시적 루프를 계산하는 것은 느릴 수 있습니다. 상수 벡터를 행렬 x의 각 행에 더하는 것은 사실 v를 수직으로 여러 번 쌓아서 vv 행렬을 형성한 다음 x와 vv의 요소별 합을 계산하는 것과 동일합니다. 이 접근 방식을 다음과 같이 구현할 수 있습니다:

vv = np.tile(v, (4, 1))  # v 벡터를 세로로 4번 복사하여 vv 행렬을 만듭니다.
print(vv)

[[1 0 1]
 [1 0 1]
 [1 0 1]
 [1 0 1]]

그런 다음 x와 vv의 요소별 합을 계산합니다:

y = x + vv  # x와 vv의 요소별 합 계산
print(y)

[[ 2  2  4]
 [ 5  5  7]
 [ 8  8 10]
 [11 11 13]]

Numpy 브로드캐스팅을 사용하면 v를 여러 번 복사하지 않고도 이 계산을 수행할 수 있습니다. 다음은 브로드캐스팅을 사용한 예제입니다:

# x 행렬에 v 벡터를 각 행에 더하는 작업을 수행합니다.
x = np.array([[1,2,3], [4,5,6], [7,8,9], [10, 11, 12]])
v = np.array([1, 0, 1])
y = x + v  # 브로드캐스팅을 사용하여 x와 v의 요소별 합을 계산합니다.
print(y)

[[ 2  2  4]
 [ 5  5  7]
 [ 8  8 10]
 [11 11 13]]

브로드캐스팅을 사용하면 코드가 더 간결하고 이해하기 쉬워집니다. 또한 브로드캐스팅은 더 높은 차원의 배열에도 적용됩니다.

이외에도 Numpy에서는 다양한 수학 함수, 선형 대수, 통계, 난수 생성 등을 다룰 수 있습니다. 이러한 내용에 대한 자세한 정보는 Numpy 공식 문서를 참조하시기 바랍니다.

출처 CS231n Python, Numpy Tutorial, Colab Link

• mathematical notations
• principles of learning
• linear regression
• overfitting
• regularization

Vectors, Matrices and Norms

Problem solving agent가 목표로의 동작을 산출하기 위해 에이전트가 수행하는 계산 과정

Uninformed Search Methods

깊이 우선 탐색 (Depth-First Search) 너비 우선 탐색 (Breadth-First Search) 균일 비용 탐색 (Uniform-Cost Search)

Reflex Agents

• Choose action based on current percept (현재 인식 기반 행동 선택)

• May have memory or a model of the world’s current state

• Do not consider the future consequences of their actions (미래 결과 고려하지 않음)

• Consider how the world IS

Can a reflex agent be rational?

반사 에이전트는 간단한 규칙 기반 시스템으로 주어진 상황에서 즉각적인 반응을 생성하는데 중점을 둡니다. 이러한 에이전트는 현재 상황에서 가장 적합한 동작을 선택하고 실제로 많은 문제에서 효과적일 수 있습니다. 그러나 몇 가지 제약사항이 있습니다:

제한된 상황: 반사 에이전트는 현재 상황만 고려하고, 과거 또는 미래 정보를 고려하지 않습니다. 따라서 환경이 매우 동적이거나 예측이 필요한 상황에서는 한계가 있을 수 있습니다.

제한된 문제 해결 능력: 반사 에이전트는 주어진 규칙에 따라 동작하므로 문제 해결 능력이 제한됩니다. 복잡한 문제나 추론을 필요로 하는 문제에 대해서는 효과적이지 않을 수 있습니다.

환경 변화에 취약: 환경이 빠르게 변할 때, 반사 에이전트는 이러한 변화에 대응하기 어려울 수 있습니다. 새로운 규칙을 추가하거나 기존 규칙을 변경하는 작업이 필요할 수 있습니다.

따라서 반사 에이전트는 간단하고 특정한 상황에서는 합리적인 선택을 할 수 있지만, 일반적인 정의에서 보면 합리적인 에이전트라고 보기 어려울 수 있습니다. 합리성은 주어진 목표를 달성하고 최선의 결과를 얻기 위한 지능적인 판단과 추론을 요구하는 개념입니다. 이런 면에서 반사 에이전트는 더 복잡한 문제 해결 능력을 가진 합리적인 에이전트와 비교하면 상대적으로 한계가 있습니다.

Planning agents

계획 에이전트는 주어진 상황에서 최적의 행동 계획을 수립하는 데 사용되는 컴퓨터 프로그램 또는 시스템입니다. 아래에서 각 항목을 자세히 설명하겠습니다:

"What If" 질문하기:

계획 에이전트는 "만약 이렇게 행동하면 어떻게 될까?"와 같은 "what if" 질문을 제기할 수 있습니다. 이것은 가능한 행동과 그에 따른 결과를 고려함으로써 미래 상황을 시뮬레이션하는 것을 의미합니다. 행동의 가상 결과에 기반한 결정:

계획 에이전트는 다양한 행동을 시도하고, 각 행동의 가상 결과를 고려하여 최선의 선택을 내립니다. 이를 통해 미래에 발생할 수 있는 다양한 시나리오를 고려하고 최적의 행동을 결정합니다. 세계가 행동에 대한 반응을 모델화:

계획 에이전트는 세계가 어떻게 작동하는지에 대한 모델을 가져야 합니다. 이 모델은 행동이 취해질 때 세계가 어떻게 변화하는지를 설명합니다. 목표(테스트) 설정:

계획 에이전트는 달성하고자 하는 목표를 명확하게 설정해야 합니다. 이 목표를 달성하기 위한 최적의 행동 계획을 수립합니다. 세계가 어떻게 될 것인지 고려:

계획 에이전트는 현재 상황에서 어떤 행동을 취할지 결정하기 위해 세계가 어떻게 변화할 것인지 고려합니다. 이를 통해 미래의 상태를 예측하고 최적의 행동을 선택합니다. 최적 vs. 완전한 계획:

최적의 계획은 목표를 가장 효율적으로 달성하는 계획을 의미합니다. 그러나 최적의 계획을 찾는 것은 계산적으로 매우 어려울 수 있습니다. 완전한 계획은 가능한 모든 행동 시나리오를 고려하여 답을 찾는 것을 의미합니다. 계획 vs. 재계획:

계획 에이전트는 초기 계획을 세울 때와 실제 행동 중에 상황이 변경할 때 재계획을 수행할 수 있습니다. 재계획은 새로운 정보나 변화된 조건을 고려하여 행동 계획을 조정하는 것을 의미합니다. 계획 에이전트는 다양한 응용 분야에서 사용됩니다. 예를 들어 로봇 제어, 자율 주행 자동차, 게임 AI, 비즈니스 의사 결정, 및 자원 할당 등 다양한 분야에서 계획 에이전트가 활용됩니다. Example: Traveling in Romania • State space: ▪ Cities • Successor function: ▪ Roads: Go to adjacent city with cost = distance • Start state: ▪ Arad • Goal test: ▪ Is state == Bucharest? • Solution? What’s in a State Space? 16 COSE361 Artificial Intelligence: Search The world state includes every last detail of the environment • Problem: Pathing ▪ States: (x,y) location ▪ Actions: NSEW ▪ Successor: update location only ▪ Goal test: is (x,y)=END • Problem: Eat-All-Dots ▪ States: {(x,y), dot booleans} ▪ Actions: NSEW ▪ Successor: update location and possibly a dot boolean ▪ Goal test: dots all false State Space Sizes? • World state: ▪ Agent positions: 120 ▪ Food count: 30 ▪ Ghost positions: 12 ▪ Agent facing: NSEW • How many ▪ World states? 120x(230)x(12 2)x4 ▪ States for pathing? 120 ▪ States for eat -all -dots? 120x(230 ) Quiz: Safe Passage • Problem: eat all dots while keeping the ghosts perma-scared • What does the state space have to specify? ▪ (agent position, dot booleans, power pellet booleans, remaining scared time) State Space Graphs and Search Trees 19 COSE361 Artificial Intelligence: Search State Space Graphs • space graph: A mathematical representation of a search problem ▪ Nodes are (abstracted) world configurations ▪ Arcs represent successors (action results) ▪ The goal test is a set of goal nodes (maybe only one) • In a state space graph, each state occurs only once! • We can rarely build this full graph in memory (it’s too big), but it’s a useful idea State Space Graphs • space graph: A mathematical representation of a search problem ▪ Nodes are (abstracted) world configurations ▪ Arcs represent successors (action results) ▪ The goal test is a set of goal nodes (maybe only one) • In a state space graph, each state occurs only once! • We can rarely build this full graph in memory (it’s too big), but it’s a useful idea 21 COSE361 Artif

Translation Lookaside Buffer

What is memory virtualization?

메모리 가상화

• OS virtualizes its physical memory.
• OS provides an illusion memory space per each process.
• It seems to be seen like each process uses the whole memory

메모리 가상화는 운영 체제가 물리적인 메모리를 가상화.

• 각 프로세스마다 메모리 공간이 있는 것처럼 보이도록 한다.
• 각 프로세스가 전체 메모리를 사용하는 것처럼 보이게 한다.

Benefit of Memory Virtualization

Ease of use in programming

• 물리적인 메모리의 세부 사항을 신경 쓰지 않고 프로그램을 작성할 수 있다.

• 각 프로세스는 자신만의 독립된 메모리 공간을 가지므로, 다른 프로세스의 영향을 받지 않고 프로그래밍할 수 있다.`

Memory efficiency in terms of times and space

• 가상 메모리를 사용하면 물리적인 메모리 크기보다 큰 프로그램을 실행할 수 있다.

• 필요한 메모리 영역만 실제로 물리적 메모리에 로드되고, 나머지 부분은 디스크의 가상 메모리로 저장됩니다.
• 프로그램의 실행에 필요한 메모리 공간을 효율적으로 관리할 수 있습니다.

The guarantee of isolation for processes as well as OS Protection from errant accesses of other processes 프로세스 및 운영 체제의 격리 보장, 다른 프로세스의 잘못된 접근으로부터 보호

각 프로세스는 독립된 메모리 공간을 할당받으며, 다른 프로세스의 메모리에 접근할 수 없습니다. 이로써 프로세스 간의 충돌이나 비정상적인 접근으로 인한 문제를 방지할 수 있습니다.

OS in The Early System

초기 운영체제는 메모리에 상주하는 루틴의 집합이었다. 물리 메모리에 하나의 실행 중인 프로그램(프로세스)이 존재하였고, 나머지 메모리를 사용하였다.

가상화는 거의 존재하지 않았다.

• Load only one process in memory.
• Poor utilization and efficiency

Multiprogramming and Time Sharing

Multiprogramming (Load multiple processes in memory).

• Execute one for a short while.
• Switch processes between them in memory.
• Increase utilization and efficiency. 효율성 개선, CPU 이용률 증가

시분할(Time Sharing)을 구현하는 한 가지 방법은 하나의 프로세스를 짧은 시간동안 실행하는 것이다. 해당 기간동안 프로세스에게 모든 메모리를 접근 할 권한이 주어진다. 여러 프로세스를 메모리에 로드하고, 실행 준비상태에 있다. 운영체제는 그들을 전환하면서 실행한다.

한 프로세스를 잠시 실행한 후, 메모리에서 프로세스를 전환한다.

• 한 프로세스가 입출력을 실행하면, CPU는 다른 프로세스로 전환하였다.

프로그램이 메모리에 동시에 존재하려면 보호(Protection)이 중요한 문제가 된다.

Cause an important protection issue.

• Errant memory accesses from other processes

다른 프로세스로부터의 잘못된 메모리 접근으로 인한 문제가 발생할 수 있다.

한 프로세스가 다른 프로세스의 메모리 영역에 잘못된 접근을 시도하는 경우가 있을 수 있다.

이러한 잘못된 메모리 접근은 다른 프로세스나 운영 체제에 대한 예기치 않은 동작을 유발할 수 있으며, 시스템의 안정성과 보안을 위협할 수 있다.

이러한 보호 문제를 해결하기 위해 운영 체제는 메모리 가상화를 통해 각 프로세스에게 독립된 가상 메모리 공간을 제공한다. 이를 통해 각 프로세스는 자신의 메모리 영역에만 접근할 수 있으며, 다른 프로세스의 메모리에는 접근할 수 없다.

Virtual Address Space

사용하기 쉬운 메모리 개념 OS creates an abstraction of physical memory.

• The address space contains all about a running process.
• That consists of program code, heap, stack and etc

실행중인 프로그램이 가정하는 메모리의 모습 주소공간은 실행 프로그램의 모든 메모리 상태를 갖고 있다.

Code(명령어) Where instructions live 프로그램의 명령어들이 저장되는 영역 반드시 메모리에 존재해야 하고, 주소공간도 존재한다.

실행 가능한 기계어 코드가 위치하며, 정적이기 때문에 메모리에 저장하기 쉽다.

주소공간의 상단에 배치하며 프로그램이 실행되면서 추가 메모리를 필요로 하지 않는다.

Heap Dynamically allocate memory.(동적으로 할당되는 메모리를 위해 사용)

• malloc in C language
• new in object-oriented language(C++, java)

동적으로 할당되는 메모리가 저장되는 영역이다.두 프로그램의 실행 중에 필요에 따라 메모리를 동적으로 할당하고 해제할 수 있다. 프로그램에 실행에 더불어 확장되거나 축소될수 있으므로 상단에 힙이 존재하고 하단에 스택이 존재한다.

두 메모리 영역은 확장할 수 있어야 하기 때문에 이런 방식으로 배치하고, 주소 공간의 양 끝단에 배치해야 두 영역 모두 확장하는 것이 가능하다. (두 영역의 확장 방향은 반대 방향이다)

합은 코드 바로 뒤 1KB부터 시작하고 아래방향으로 확장한다.

Stack 함수 호출 체인 상의 현재 위치, 지역 변수, 함수 인자와 반환 값 들을 저장하는데 사용한다. Store return addresses or values. Contain local variables arguments to routines.

함수 호출과 관련된 정보들이 저장되는 영역이다. 함수 호출 시에 지역 변수, 매개변수, 복귀 주소 등이 스택에 저장되며, 함수 호출이 완료되면 해당 정보들은 스택에서 제거된다.

스택은 16KB에서 시작하고 위쪽 방향으로 확장한다.

하지만 이는 관례이며 다른 방식으로 배치할 수 있다. 실제로 프로그램이 물리주소 0에서 16KB사이에 존재하는 것은 아니며 실제로는 임의의 물리 주소에 탑재된다.

주소공간에 여러 쓰레드가 공존할 떄는 이런식으로 주소 공간을 나누게 되면 동작하지 않는다.

정적으로 초기화된 영역 데이터(Data) 영역: 전역 변수와 정적(static) 변수가 저장되는 영역입니다. 초기화된 데이터는 데이터 영역에 저장되고, 초기화되지 않은 데이터는 BSS(Block Started by Symbol) 영역에 할당됩니다.

힙과 스택 사이의 영역: 힙과 스택 사이에는 사용되지 않는 공간이 존재할 수 있습니다. 이는 힙과 스택의 크기가 동적으로 변경될 수 있기 때문입니다.

Process memory layout

#include <stdio.h>
#include <stdlib.h>

int global_variable;  // 전역 변수 (데이터 영역)

int main() {
    int stack_variable = 5;  // 지역 변수 (스택 영역)
    int *heap_variable = (int*)malloc(sizeof(int));  // 동적으로 할당된 변수 (힙 영역)

    if (heap_variable == NULL) {
        printf("힙 메모리 할당에 실패했습니다.");
        return 1;
    }

    *heap_variable = 10;

    printf("전역 변수: %d\n", global_variable);
    printf("스택 변수: %d\n", stack_variable);
    printf("힙 변수: %d\n", *heap_variable);

    free(heap_variable);  // 동적 할당 해제

    return 0;
}

Virtual Address

Every address in a running program is virtual.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
printf("location of code : %p\n", (void *) main);
printf("location of heap : %p\n", (void *) malloc(1));
int x = 3;
printf("location of stack : %p\n", (void *) &x);
return x;
}

A simple program that prints out addresses 포인터를 출력하는 C 프로그램에서 출력되는 값은 모두 Virtual address이다. User level 프로그램이 볼 수 있는 모든 주소는 가상 주소이다. 명령어와 데이터가 탑재되어있는 물리 메모리 주소는 운영체제뿐이다.

The output in 64-bit Linux machine

location of code : 0x40057d
location of heap : 0xcf2010
location of stack : 0x7fff9ca45fcc

OS translates the virtual address to physical address

주소공간에서 코드가 제일 먼저 등장하고, 다음에 힙이 배치되고 마지막으로 대규모 가상 공간의 반대편에 스택이 위치한다. 모든 주소느 가상주소이며 저장된 실제 물리 메모리 위치에서 값을 반입하기 위해 운영체제와 하드웨어에 의해 물리 주소로 변환된다.

Address Translation

Hardware transforms a virtual address to a physical address.

• The desired information is actually located in a physical address.

The OS must get involved at key points to set up the hardware.

• The OS must manage memory to judiciously intervene.

하드웨어는 가상 주소를 물리 주소로 변환합니다. 실제로 원하는 정보는 물리 주소에 위치하게 됩니다. 이를 위해 운영 체제는 핵심적인 지점에서 하드웨어를 설정하는 역할을 수행해야 합니다. 또한, 운영 체제는 메모리를 관리하여 필요한 시점에 적절히 개입해야 합니다.

가상 주소와 물리 주소 간의 변환은 가상 메모리 관리 기술을 통해 이루어집니다. 가상 메모리는 각 프로세스가 자신만의 독립된 가상 주소 공간을 가지며, 이 가상 주소는 물리적인 메모리 주소와 매핑됩니다. 하드웨어의 메모리 관리 유닛(MMU, Memory Management Unit)은 가상 주소를 받아들이고 이를 물리 주소로 변환하여 실제 메모리에 액세스합니다.

가상 주소를 물리 주소로 변환하는 과정에서 운영 체제는 페이지 테이블이라는 데이터 구조를 관리하며, 이는 가상 주소와 물리 주소 간의 매핑 정보를 담고 있다. 운영 체제는 프로세스의 가상 주소 공간을 적절히 관리하고, 필요한 페이지를 메모리에 로드하거나 페이지를 디스크에 스왑하는 등의 작업을 수행한다.

Example: Address Translation

void func() {
int x=3000;
...
x = x + 3; // this is the line of code we are interested in
}

1. Load a value from memory
2. Increment it by three
3. Store the value back into memory

컴파일러는 이 코드를 어셈블리 코드로 변환한다.

Assembly

128 : movl 0x0(%ebx), %eax ; load 0+ebx into eax
132 : addl $0x03, %eax ; add 3 to eax register
135 : movl %eax, 0x0(%ebx) ; store eax back to mem

1. Load the value at that address into eax register.
2. Add 3 to eax register.
3. Store the value in eax back into memory.

x의 주소는 레지스터 ebx에 저장되어 있다고 가정한다. 이 주소에 저장되어 있는 값을 movl명령어(longword를 이동하는 명령어)를 사용하여 범용 레지스터 eax에 넣는다. 다음 명령은 eax에 3을 더하고 마지막으로 eax의 값을 같은 위치의 메모리에 저장한다.

코드와 데이터가 프로세스 주소공간에 배치되어있는 그림

세개의 명령어 코드는 주소 128에 위치하고 변수 x의 값은 15KB(아래 쪽 스택)에 위치한다. x의 초기값은 3000이다.

• Fetch instruction at address 128 • Execute this instruction (load from address 15KB) • Fetch instruction at address 132 • Execute this instruction (no memory reference) • Fetch the instruction at address 135 • Execute this instruction (store to address 15 KB)

프로그램 관점에서 주소 공간은 주소 0부터 시작해서 최대 16KB 까지이다. 프로그램이 생성하는 모든 메모리 참조는 이 범위 내에 있어야한다.

Dynamic Relocation: Base and Bound

동적 (하드웨어 기반) 재배치 The OS wants to place the process somewhere else in physical memory, not at address 0. The address space start at address 0.

동적 재배치(Dynamic Relocation)은 운영 체제가 프로세스를 물리적인 메모리의 다른 위치에 위치시키려는 경우를 의미한다. 이 때 프로세스의 주소 공간은 보통 0번지에서 시작된다.

동적 재배치를 통해 운영 체제는 프로세스의 메모리 위치를 자유롭게 조정할 수 있다. 이는 메모리 공간을 효율적으로 활용하고, 프로세스 간의 충돌을 방지하며, 시스템의 유연성을 높이는 데 도움을 준다.

각 CPU마다 2개의 하드웨어 레지스터가 필요하다. 하나는 베이스(base) 레지스터, 다른 하나는 바운드(bound)레지스터

Base and Bounds Register

Dynamic(Hardware base) Relocation

Base Register는 프로세스의 가상 주소 공간에서 물리 메모리의 시작 위치를 가리키는 주소를 저장하는 레지스터이다. Bound Register는 프로세스의 주소 공간의 크기를 나타내는 값이 저장되는 레지스터이다. 이 베이스와 바운드 쌍은 우리가 원하는 위치에 주소공간을 배치할 수 있게 하며 배치와 동시에 프로세스가 오직 자신의 주소공간에만 접근한다는 것을 보장한다.

When a program starts running, the OS decides where in physical memory a process should be loaded.

• Set the base register a value.

프로세스를 메모리에 로드할 때, 운영 체제는 Base Register를 설정하여 프로세스의 가상 주소 공간을 물리 메모리의 원하는 위치로 이동시킨다.

physical address $=$ virtual address $+$ base

프로세스가 생성하는 메모리 참조는 가상 주소이다. 하드웨어는 베이스 레지스터의 내용을 이 주소에 더하여 물리 주소를 생성한다.

• Every virtual address must not be greater than bound and negative.

$0 \leq$ virtual address $<$ bounds

Relocation and Address Translation

명령어가 하나 실행될 때 일어나는 변화

# Fetch instruction at address 128 
128 : movl 0x0(%ebx), %eax

# 32896 = 128 + 32KB(Base)

PC(프로그램 카운터)는 128로 설정된다. 하드웨어가 이 명령어를 반입할 때 먼저 PC값을 베이스 레지스터의 값 32KB(32768)에 더해 32896의 물리 주소를 얻는다.

그 뒤에 하드웨어는 해당 물리주소에서 명령어를 가져온다. 그리고 프로세서는 명령어의 실행을 시작한다.

가상주소 15KB의 값을 load하라는 명령어를 받아서 다시 15KB(Base)를 더해 물리주소 47KB에서 원하는 내용을 load한다.

가상주소에서 물리주소로의 변환이 주소변환이라고 불리는 기술이다. 하드웨어는 프로세스가 참조하는 가상주소를 받아들여 데이터가 실제로 존재하는 물리주소로 변환한다. 이 주소의 재배치는 실행시에 일어나고 프로세스가 실행을 시작한 이후에도 주소공간을 이동할 수 있기 때문에 동적 재배치라고 불린다.

동적 재배치는 프로그램 실행시에 일어나며 프로세스 실행중에도 주소공간의 이동이 가능하기 때문에 동적 재배치라고 불린다.

Bounds Register

바운드 레지스터는 보호를 지원하기 위해 존재한다. 프로세서는 먼저 메모리 참조가 합법적인지 확인하기 위해 가상주소가 바운드 안에 있는지 확인한다. the processor will first check that the memory reference is within bounds to make sure it is legal

앞의 예시에서 바운드 레지스터는 항상 16KB로 설정된다. 프로세스가 바운드보다 큰 가상주소 또는 음수인 가상 주소를 참조하면 CPU는 예외를 발생시키고 프로세스는 종료된다.

바운드의 요점은 프로세스가 생성한 모든 주소가 합법적이고 프로세스의 범위에 있다는 것을 확인하는 것이다.

베이스와 바운드 레지스터는 CPU칩 상에 존재하는 하드웨어 구조이다. CPU당 1쌍 주소 변환에 도움을 주는 프로세서의 일부를 메모리 관리 유닛(MMU, Memory Management Unit)이라고 부른다.

베이스와 바운드를 이용한 주소변환을 이해하기 위해 주소공간의 크기가 4KB인 프로세스가 물리 주소 16KB에 탑재되어있다고 가정하자. 주소변환의 결과는 다음과 같다. 가상주소 -> 물리주소 0KB -> 16KB 1KB -> 17KB 3000 -> 19384(16384 + 3000) 4400 -> 20784 (Fault, 바운드에서 벗어남) 20KB(20480)을 넘었기 때문에 폴트를 일으킨다. (예외 발생)

Hardware Requirements

Privileged mode 두 가지 CPU모드가 필요하다. 운영체제는 Privileged mode(커널 모드)에서 실행하며 컴퓨터 전체에 대한 접근 권한을 가진다.

응용프로그램은 사용자 모드에서 실행되며, 할 수 있는 일에 제한이 있다.

프로세서 상태 워드(Processor status word) 레지스터의 한 비트가 비트가 CPU의 현재 실행 모드를 나타낸다.

특정한 순간(시스템 콜 또는 다른 종류의 예외나 인터럽트 발생 시) CPU는 모드를 전환한다.

Base/Bounds registers 하드웨어는 베이스와 바운드 레지스터를 자체적으로 제공한다. CPU는 메모리 관리 장치(MMU)의 일부인 추가의 레지스터 쌍을 가진다.

Ability to translate virtual addresses and check if within bounds 프로그램이 실행 중인 경우 하드웨어는 프로그램이 생성한 가상 주소에 베이스 값을 더하여 주소를 변환한다. 하드웨어는 주소가 유효한지 검사할 수 있어야 한다. 이 검사는 바운드 레지스터와 CPU내의 일부 회로를 사용하여 이루어진다.

Privileged instructions to update base/bound 하드웨어는 베이스와 바운드의 레지스터 값을 변경하는 특권 명령어를 제공해야한다. 커널 모드에서만 레지스터를 변경할 수 있다.

Privileged instructions to register exception handlers CPU는 사용자 프로그램이 바운드를 벗어난 주소로 불법적인 메모리 접근을 시도하려는 상황에서 예외(Exception)를 발생시킬 수 있어야 한다. segmentation fault 이 경우 CPU는 사용자 프로그램의 실행을 중지하고 운영체제의 바운드 벗어남 예외 핸들러Exception handler가 실행하도록 조치해야한다. 이때 운영체제 핸들러는 어떻게 대처할지 결정할 수 있다. 이 경우 프로세스를 종료시킬 확률이 매우 높다.

Ability to raise exceptions 사용자 프로그램이 특권이 필요한 베이스와 바운드 레지스터 값의 변경을 시도하면 CPU는 예외를 발생시키고 사용자 모드에서의 특권 연산 발생 핸들러를 실행시켜야 한다. CPU는 이 핸들러들의 주소를 파악하기 위한 방법을 제공해야하고, 몇 개의 특권 명령어가 더 필요하다.

하드웨어 요구사항 정리

특권 모드, 베이스/바운드 레지스터 특권 모드(커널 모드)는 사용자 모드 프로세스가 특권 명령을 실행하지 못하도록 하며, Base/bounds 레지스터는 주소 변환과 경계 검사를 지원하기 위해 사용된다.

• 가상 주소를 변환하고 Bound(범위)안에 있는지 검사

• 베이스/바운드를 갱신하기 위한 특권 명령어
• 예외 핸들러 등록을 위한 특권 명령어
• 예외 발생 기능

운영 체제는 특권 명령을 사용하여 레지스터 값을 설정하고 업데이트하며, 예외 처리기 코드를 등록하여 예외 발생 시 처리할 수 있도록 한다. 또한, 예외 처리를 위해 하드웨어는 예외를 발생시킬 수 있는 기능을 갖추고 있어야 한다.

작성중

OS Issues for Memory Virtualizing

The OS must take action to implement base-and-bounds approach.

운영체제가 반드시 개입되어야 하는Three critical actions:

1. When a process starts running: Finding space for address space in physical memory

2. When a process is terminated:
   Reclaiming the memory for use 프로세스가 종료되면, 운영 체제는 해당 프로세스가 사용한 메모리를 회수하여 다른 프로세스가 사용할 수 있도록 해야 합니다. 이를 위해 운영 체제는 종료된 프로세스의 메모리 영역을 식별하고 해당 영역을 물리 메모리의 사용 가능한 공간으로 표시합니다. 메모리 회수는 메모리 관리 기법에 따라 다를 수 있으며, 종료된 프로세스의 메모리를 효율적으로 관리하여 메모리 자원의 최적 활용을 추구합니다.

3. When context switch occurs: Saving and storing the base-and-bounds pair 문맥 교환(Context switch)는 실행 중인 프로세스와 다른 프로세스 사이의 전환을 의미합니다. 컨텍스트 스위치가 발생할 때, 운영 체제는 현재 프로세스의 base와 bounds 값을 저장하고, 새로운 프로세스의 base와 bounds 값을 복원해야 합니다. 이를 통해 다른 프로세스로 전환되더라도 올바른 주소 공간에 접근할 수 있도록 보장합니다. 컨텍스트 스위치는 프로세스 간의 공유되는 자원 및 상태를 관리하는 중요한 작업이며, base와 bounds 값을 적절히 관리하여 올바른 메모리 접근을 유지합니다.

OS Issues: When a Process Starts Running

The OS must find a room for a new address space. 프로세스가 실행을 시작할 때, 운영 체제는 물리 메모리에서 주소 공간을 위한 공간을 찾아야 합니다. 각 주소공간은 물리 메모리의 크기보다 작고 크기가 일정하다라는 가정하에서는 운영체제가 쉽게 처리할 수 있다. 운영체제는 물리메모리를 슬롯의 배열로 보고 각 슬롯의 사용 여부를 관리한다. 새로운 프로세스가 생성되면 운영체제는 새로운 주소공간 할당에 필요한 영역을 찾기 위해 빈공간 리스트(Free list)라고 불리는 자료구조를 검색한다. free list : A list of the range of the physical memory which are not in use.

OS Issues: When a Process Is Terminated

The OS must put the memory back on the free list.

OS Issues: When Context Switch Occurs

The OS must save and restore the base-and-bounds pair.

• In process structure or process control block(PCB)

OS Issues: provide exception handlers

the OS must provide exception handlers, the OS installs these handlers at boot time (via privileged instructions Exception handler for segmentation fault

Inefficiency of Base and Bound registers

Internal fragmentation The relocated process is using physical memory from 32 KB to 48 KB The process stack and heap are not too big, all of the space between the two is simply wasted

Base and Bound registers 기법의 비효율성은 내부 단편화(Internal fragmentation)와 관련이 있습니다. 재배치된 프로세스가 32 KB에서 48 KB까지의 물리 메모리를 사용한다고 가정해봅시다. 이 경우 프로세스의 스택과 힙이 그다지 크지 않다면, 두 공간 사이의 모든 공간이 단순히 낭비되는 현상이 발생합니다.

내부 단편화는 메모리 할당 방식에서 발생하는 현상으로, 할당된 메모리 공간 중에서 실제로 사용되지 않는 공간이 존재하는 경우를 말합니다. Base and Bound registers 기법에서는 프로세스의 주소 공간을 물리 메모리에 연속적으로 배치하기 때문에, 스택과 힙 사이에 미사용 공간이 존재할 수 있습니다.

예를 들어, 프로세스의 스택이 32 KB까지, 힙이 48 KB부터 시작한다고 가정해봅시다. 이 경우 스택과 힙 사이의 32 KB ~ 48 KB 사이의 공간은 프로세스가 사용하지 않는 미할당 공간입니다. 이렇게 낭비된 공간은 내부 단편화를 초래하며, 메모리의 효율성을 저하시킬 수 있습니다.

내부 단편화는 메모리 할당의 효율성을 감소시키고, 메모리 자원의 낭비를 초래할 수 있습니다. 이는 메모리가 제한적인 시스템에서 특히 중요한 문제입니다. 이러한 단편화를 해결하기 위해 다른 메모리 관리 기법이나 할당 알고리즘을 사용할 수 있습니다. 예를 들어, 페이지 기반의 가상 메모리 관리에서는 페이지 크기에 맞게 메모리를 할당하여 내부 단편화를 최소화할 수 있습니다. 또는 메모리 단편화를 해결하기 위해 외부 단편화를 줄이는 방법을 사용할 수도 있습니다. 이러한 기법들은 메모리의 효율성을 향상시키고, 더 많은 프로세스를 실행하는 데 도움을 줄 수 있습니다.

Summary

Address translation: hardware support and OS support 주소 변환(Address translation)은 하드웨어와 운영 체제의 지원을 통해 이루어집니다. 주소 변환은 가상 주소와 물리 주소 간의 매핑을 수행하는 과정을 말합니다. Basic form: base and bound Base는 가상 주소 공간에서 물리 메모리의 시작 위치를 가리키는 주소를 저장하는 레지스터이며, Bound는 주소 공간의 크기를 나타내는 값이 저장되는 레지스터이다. 이 두 레지스터를 사용하여 가상 주소를 물리 주소로 변환한다. 베이스-바운드로 알려진 가상화의 한 형태는 베이스 레지스터를 가상 주소에 더하고 생성된 주소가 바운드를 벗어나는지 검사하기 위한 간단한 하드웨어 회로만 추가하면 되기 때문에 Fragmentation issue 하지만 base와 bound 기법을 사용하는 경우에는 단편화(fragmentation)라는 문제가 발생할 수 있습니다. 내부 단편화는 할당된 메모리 공간 중에서 사용되지 않는 공간이 존재하는 경우를 의미하며, 외부 단편화는 여러 개의 작은 빈 공간이 분산되어 할당할 수 있는 큰 공간이 부족한 경우를 의미합니다. 이러한 단편화는 메모리의 효율성을 저하시키고, 메모리 자원의 낭비를 초래할 수 있습니다.

주소 변환에서는 단편화 문제를 해결하기 위해 다양한 기법과 알고리즘이 사용될 수 있습니다. 이를 통해 메모리 할당의 효율성을 향상시키고, 더 많은 프로세스를 실행하는 데 도움을 줄 수 있습니다. 이러한 일반화 된 베이스-바운드 기법을 세그멘테이션이라고 부른다.

• In this chapter, we study very simple file system (vsfs)

  • Basic on-disk structures, access methods, and various policies of vsfs

• We will study...

  • How can we build a simple file system?
  • What structures are needed on the disk?
  • What do they need to track?
  • How are they accessed?

• What types of data structures are utilized by the file system?

• How file system organize its data and metadata?

• Understand access methods of a file system.

  • open(), read(), write(), etc.

Overall Organization

• Let’s develop the overall organization of the file system data structure.
• Divide the disk into blocks.
  • Block size is 4 KB.
  • The blocks are addressed from 0 to N -1.

Data region in file system

• Reserve data region to store user data

• File system has to track which data block comprise a file, the size of the file, its owner, etc.

Inode table in file system

• Reserve some space for inode table
  • This holds an array of on-disk inodes.
  • Ex) inode tables : 3 ~ 7, inode size : 256 bytes
    • 4-KB block can hold 16 inodes.
    • The file system contains 80 inodes. (maximum number of files)

Allocation structures

• This is to track whether inodes or data blocks are free or allocated.
• Use bitmap, each bit indicates free(0) or in-use(1)
  • data bitmap (d) : for data region
  • inode bitmap (i) : for inode table

정보가 한 방향으로만 흐르는 인공 신경망이다. 이전 데이터에 대한 시간적인 개념이나 기억을 가지고 있지 않다.

Recurrent neural network (RNN)

순환 신경망(RNN)은 순차적인 데이터를 처리하기 위해 설계된 신경망으로, 시간적 종속성을 포착할 수 있는 능력을 갖고 있다.

RNN에서는 정보가 여러 방향으로 흐르며 각 뉴런은 현재 입력뿐만 아니라 이전 은닉 상태를 고려하기 위한 순환 연결을 가지고 있다. (hidden state vector $h_t$)

RNN은 시간적인 개념과 기억을 갖추고 있으며 언어 모델링, 음성 인식, 시계열 분석 등의 작업에 적합하다.

Time Delay Neural Network (TDNN)

• TDNN is a FFNN whose purpose is to classify temporal patterns with shift-invariance (independency on the beginning points to insure data i.i.d for MLP, so we may shuffle) in sequential data like 1D Conv with stride 1.

• It is the simplest way of controlling time-varying sequential data and allows conventional backpropagation algorithms.

• TDNN gets its inputs by sliding a window of size n across multiple time steps in sequential data and treating these n consecutive data samples as one input data.

Disadvantages of TDNN

The success of TDNN depends on finding an appropriate window size.

• small window size does not capture the longer dependencies.
• large window size increases the parameter number and may add unnecessary noise.

small window size는 더 긴 의존성(dependencies)을 포착하지 못합니다. large window size 매개 변수 수를 증가시키고 불필요한 노이즈를 추가할 수 있습니다.

TDNN works well for some short-memory problems such as Atari games, but cannot handle long-memory problems over hundreds of time steps such as stock prediction.

일부 단기 기억 문제에는 잘 작동하지만, 주가 예측과 같은 수백 개의 시간 단계를 거치는 장기 기억 문제를 다루기 어렵습니다.

Because TDNN has a fixed window size, it cannot handle sequential data of variable length such as language translation.

TDNN은 고정된 창 크기를 가지고 있기 때문에 언어 번역과 같은 가변 길이의 순차 데이터를 처리할 수 없습니다.

FFNNs do not have any explicit memory of past data. Their ability to capture temporal dependency is limited within the window size. Even for a particular time window, input data is treated as a multidimensional feature vector rather than as a sequence of observations, so we lose the benefit of sequential information. (Unaware of the temporal structure)

FFNN(Feedforward Neural Network)은 이전 데이터에 대한 명시적인 기억이 없습니다. 시간 의존성을 포착하는 능력은 창 크기 내에서 제한적입니다. 특정 시간 창에 대해 입력 데이터는 연속된 관측값의 순차열이 아닌 다차원 특징 벡터로 처리되므로, 순차적인 정보의 이점을 잃게 됩니다. (시간 구조에 대해 알지 못함)

따라서 TDNN은 일부 단기 기억 문제에 대해 효과적이지만, 장기 기억 문제나 가변 길이의 순차 데이터 처리에는 제한이 있습니다.

시간 지연 신경망 (TDNN)은 변동에 불변한 특성을 유지하면서 순차적인 데이터에서 시간적 패턴을 분류하기 위한 특정 유형의 피드포워드 신경망(FFNN)입니다.

TDNN은 고정된 크기의 윈도우를 사용하여 연속된 데이터를 처리하며, 이를 통해 시간적으로 지역적인 패턴을 파악할 수 있습니다. 하지만 TDNN은 고정된 창 크기를 가지고 있어 가변 길이의 순차 데이터를 처리할 수 없으며, 장기 기억 문제에는 제한이 있습니다.

TDNN은 입력 데이터를 다차원 특징 벡터로 처리하여 순차적인 정보를 잃게 됩니다.

이와 달리 RNN은 시간적 의존성을 인코딩하기 위해 순환 구조를 사용하며, LSTM은 RNN의 한 종류로서 장기적인 의존성을 학습하기 위해 설계된 메모리 유닛을 포함하고 있습니다.

Recurrent Neural Network (RNN) • RNN (LSTM) makes predictions based on current and previous inputs recurrently, while FFNN makes decisions based only on the current input. • RNN processes the input sequence one data xt at a time (current input) and maintains a hidden state vector ht as a memory for past information (previous inputs). • It learns to selectively retain relevant information to capture temporal dependency or structure across multiple time steps for processing sequential data. • RNN does not require a fixed sized time window and can handle variable length sequences.

순환 신경망 (RNN)은 현재 및 이전 입력에 기반하여 재귀적으로 예측을 수행하는 반면, 피드포워드 신경망 (FFNN)은 현재 입력에만 기반하여 결정을 내립니다. RNN은 입력 시퀀스를 하나의 데이터 xt(현재 입력)씩 처리하며, 과거 정보(이전 입력)를 기억하기 위해 hidden state vector ht를 유지합니다. RNN은 순차적인 데이터를 처리하기 위해 여러 시간 단계를 거쳐 시간적 의존성이나 구조를 포착하기 위해 관련된 정보를 선택적으로 보존하는 방법을 학습합니다. RNN은 고정 크기의 시간 창이 필요하지 않으며 가변 길이의 시퀀스를 처리할 수 있습니다.

RNN (Recurrent Neural Network)은 순차적인 데이터나 시계열 데이터와 같이 이전 단계의 정보를 현재 단계에 전달하는 데 특화된 인공 신경망입니다. RNN은 반복적인 구조를 가지며, 이전 단계의 출력이 현재 단계의 입력으로 사용됩니다. 이를 통해 RNN은 순차적인 패턴을 학습하고 시간적 의존성을 인코딩할 수 있습니다.

하지만 기본적인 RNN은 "기울기 소실" 또는 "기울기 폭발"과 같은 문제를 가지고 있습니다. 긴 시퀀스를 처리할 때, 이러한 문제로 인해 이전 정보가 제대로 전달되지 않고 학습이 어려워집니다. 이를 해결하기 위해 LSTM (Long Short-Term Memory)이라는 RNN의 변형이 개발되었습니다.

LSTM is designed to capture long-term dependency and overcomes the vanishing/exploding gradient problem in SimpleRNN.

LSTM은 RNN의 단점을 보완하기 위해 설계된 네트워크 구조입니다. LSTM은 입력 게이트(input gate), 삭제 게이트(forget gate), 출력 게이트(output gate) 등의 구조적인 요소를 사용하여 장기적인 의존성을 학습할 수 있습니다. LSTM의 핵심 아이디어는 "셀 상태(cell state)"라는 메모리 유닛을 도입한 것입니다. 셀 상태는 정보를 보존하고 업데이트하는 역할을 수행하여 긴 시간 동안 정보를 기억할 수 있습니다.

각 게이트는 시그모이드 함수와 함께 동작하여 어떤 정보를 유지하고, 어떤 정보를 삭제하고, 어떤 정보를 출력할지를 결정합니다. 이러한 메커니즘을 통해 LSTM은 장기적인 의존성을 학습하면서도 "기울기 소실" 문제를 해결하고 더 효과적으로 시계열 데이터를 모델링할 수 있습니다.

요약하면, RNN은 순차적인 데이터 처리에 특화된 네트워크이며, LSTM은 RNN의 한 종류로서 장기적인 의존성을 학습할 수 있는 메모리 유닛을 포함한 구조로 기울기 소실 문제를 해결하는 데 효과적입니다.

• AE encoder directly produces a latent vector $z$ (single value for each attribute). Then, AE decoder takes these values to reconstruct the original input.

Goal is getting a compressed latent vector of the input. • VAE encoder produces 2 latent vectors mean µ and standard deviation σ of Gaussian N(µ, σ2) approximating the posterior distribution p(z| x) of each attribute (Variational inference).

Then, using sampled latent vectors from the distributions, the decoder reconstructs the input. Goal is generating many variations of the input (probabilistic encoder + generative decoder).

VAE encoder would like to produce the posterior $p(z|x)$ instead of a single point $z$, but because of the intractability of $p(z|x)$, we approximate it by variational posterior $q_θ(z|x)$ which is Gaussian $N(µ_x, σ^2_x)$ so that the encoder network $q_θ$ is enforced to produce $µ_x$ and σx.

Reparametrization trick