hyeonnnnn

 📌 Time Sharing

프로세서가 한 번에 하나의 프로세스를 처리할 수 있기 때문에 하나의 프로세스가 무거운 작업을 수행한다면 다른 프로세스들은 처리 기회를 얻지 못한다.

따라서 OS는 CPU 스케줄링을 통해 SJF, FIFO와 같은 방법으로 여러 프로세스가 효율적이고 공평하게 처리되도록 한다.

클라우드 서비스는 Time Sharing을 통해 여러 사용자가 공평하고 빠르게 처리된다고 느낄 것이다.

 📌 Resource Pooling

Resource Pooling은 자원을 미리 확보한 후 클라우드 환경에서 사용자가 원할 때마다 자원을 할당해주고 다시 회수한다.

예를 들어, 도서관(Pool)에서 책(Resource)을 사람들이 원할 때마다 빌리고(할당) 반납(회수)하는 것과 같다.

공유되는 자원은 유연하고 효율적으로 관리되며, 이는 가상화를 통해 구현할 수 있다.

 📌 과대자원, 과소자원이 나오게 된 배경

그래프와 같이 사용자의 요구 자원은 시간이 흐름에 따라 대체로 일정하게 증가한다.

하지만 컴퓨터의 성능은 선형적으로 증가하지 않는다. 여기서 과대자원, 과소자원의 개념이 나온다.

 📌 과대자원

사용자의 요구 자원보다 성능이 좋은 경우 과대자원이라고 한다. 즉, 자원이 넉넉한 경우이다.

클라우드 관점에서 사용자가 원하는 자원의 수준보다 성능이 높기 때문에 서비스 제공에는 문제가 없지만 자원이 남게 되어 가동률이 낮아짐에 따라 예산의 낭비가 있을 수 있다.

 📌 과소자원

반대로 요구자원보다 성능이 안좋은 경우 과소자원이라고 한다. 즉, 자원이 부족한 경우이다.

클라우드 관점에서 비용이 절약되어 좋지만 그만큼 서비스 제공에 제약이 있을 수 있다.

 📌 결론

비용 절약과 서비스 제공 사이에서 타협점을 찾는 것이 중요한데, 이성적으로는 사용자의 요구 자원 수준보다 살짝 높은 성능을 제공하는 것이다.

💡 OSI 7계층이란?

OSI 7계층은 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것

✨ OSI 7계층 모델

✨ TCP/IP 4계층 모델과의 차이

1. 물리 계층

• 리피터, 케이블, 허브 등
• 전송 단위: Bit
• 데이터를 전송하는 역할을 한다.

2. 데이터 링크 계층

• 브릿지, 스위치, 랜카드 등
• 전송 단위: Frame
• Mac 주소를 통해 통신한다.
• 네트워크 계층에서 받은 정보에 주소와 제어 정보를 헤더와 테일에 추가한다.
• 에러 검출, 재전송, 흐름제어를 한다.

3. 네트워크 계층

• 라우터, L3 스위치
• 전송 단위: Packet,
• IP 주소를 통해 통신한다.
• 상위 계층의 데이터를 작은 크기의 패킷으로 분할하여 해당 경로에 따라 전달한다.
• 데이터를 목적지까지 가장 안전하고 빠르게 전달하는 기능을 담당한다.
• 라우팅, 흐름 제어, 오류 제어, 세그멘테이션 등을 수행한다.

4. 전송 계층

• 대표적인 프로토콜로 TCP (신뢰성, 연결 지향적), UDP(비신뢰성, 비연결성, 실시간)가 있다.
• 전송 단위: Segment
• Port 번호를 통해 통신한다.
• 상위 프로토콜을 구분하고 패킷의 순서와 손상을 보장한다.
• 송신 컴퓨터의 응용 프로그램서 수신 컴퓨터의 응용 프로그램까지의 메시지 오류 복구와 흐름 제어를 관리한다.

5. 세션 계층

• API, Socket
• 전송 단위: Message
• 데이터가 통신하기 위한 논리적 연결을 담당한다.
• TCP/IP 세션을 만들고 없애는 책임을 가지고 있다.

6. 표현 계층

• JPEG, MPEG 등
• 전송 단위: Message
• 데이터 표현에 대한 독립성을 제공하고 암호화하는 역할을 담당한다.
• 파일 인코딩, 명령어를 포장, 압축, 암호화한다.

7. 응용 계층

• HTTP, FTP, DNS
• 전송 단위: Message
• 사용자와 가장 밀접한 계층으로 인터페이스 역할을 한다.
• 전자 우편, 데이터베이스 관리 등의 서비스를 제공한다.

참고
https://gyoogle.dev/blog/computer-science/network/OSI 7계층.html
https://blog.naver.com/PostView.nhn?blogId=tmk0429&logNo=222294381124
https://hahahoho5915.tistory.com/15

 📌 어셈블리어 실습 방법 - 코드 패치

1부터 100까지의 합 코드를 작성하기 전에 Immunity Debugger에서 코드 패치를 이용하여 새로운 코드를 작성하는 방법을 다루려고 한다.

디버거에서 아무 실행 파일(*.exe)을 열고, 코드 부분을 더블 클릭해서 수정하면 된다.

코드를 더블 클릭하면 

왼쪽 처럼 뜰 텐데, 여기서 코드를 수정하고 Assemble을 누르면 해당 줄의 코드가 변경되고 밑에는 NOP으로 모두 변경된다.

아래로 순서대로 코드 패치를 진행하면 된다.

 📌 1부터 100까지의 합 ver.1 (레지스터 3개 사용)

1. EAX, EBX값을 1로 초기화 시키고 EBX를 1씩 증가시키면서 EAX에 EBX를 더해준다.
2. LOOP는 EBX가 100이 될 때까지 돈다. (ECX가 0일 때까지 돈다. 여기서 LOOP 명령어는 ECX를 먼저 1감소하고 0인지 아닌지 비교함에 주의)

💻 코드

1. EAX를 1로 초기화 시킨다.
2. EBX를 1로 초기화 시킨다.
3. LOOP는 EBX가 100일 때까지 더하려면 2~100까지 즉 99번 돌아야 하므로 ECX값을 99로 정해 줘야함. 99를 16진수로 하면 63이기 때문에 63으로 초기화 시킨다.
4. 보기 편하게 한 줄 띄우기 위해 NOP 사용. (해당 줄은 없어도 된다.)
5. EBX를 1씩 증가시킨다.
   (1~100을 더하는데 EAX가 1이고 EBX도 1이기 때문에 EBX를 먼저 1증가시키고 EAX에 더하는 것을 반복한다.)
6. EAX에 EBX를 더해서 EAX에 저장한다.
7. 5번 줄과 6번줄을 EBX가 100이 될 때까지 (CX가 0이 될 때까지)반복한다.

💡 레지스터 변화 확인

1.  EAX, EBX, ECX 초기화

2.  더하는 과정

EBX값을 1 증가시킨 후 EAX에 EBX를 더한다.

3. 결과

ECX가 0이 되면 LOOP를 멈춘다. 99번 돌았기 때문에 이 시점에서 EBX값을 보면 1에서 99를 더한 64(10진수로 100)이다.

또한 EAX 값은 1에서 100까지를 더한 13BA(10진수로 5050)가 되어있는 것을 확인할 수 있다.

📌 1부터 100까지의 합 ver.2 (레지스터 2개 사용)

1. EAX값을 0으로 초기화 시키고 ECX가 100부터 0까지 -1씩 하면서 ECX를 EAX를 더한다.
2. LOOP는 ECX가 0일 때까지 돈다. (여기서 LOOP 명령어는 ECX를 먼저 1감소하고 0인지 아닌지 비교함에 주의)

💻 코드

1. EAX를 0으로 초기화 시킨다.
2. LOOP는 1~100을 더해야 하므로 ECX값을 100으로 정해 줘야함.
   100를 16진수로 하면 64이기 때문에 64으로 초기화 시킨다.
3. EAX에 ECX를 더한다. (처음엔 100, LOOP 한 번 돌 때 ECX가 -1되므로 다음엔 99를 더하는 식)
4. ADD EAX, ECX를 100번 돈다.

💡 레지스터 변화 확인

1.  EAX, ECX 초기화

2.  더하는 과정

ECX 값을 EAX에 더해주고 ECX값은 루프를 돌면서 1씩 감소한다.

3.  결과

ECX가 0이 되면 LOOP를 멈춘다.

EAX 값은 100에서 1까지를 더한 13BA(10진수로 5050)가 되어있는 것을 확인할 수 있다.

 📌 느낀점

레지스터 3개를 사용할 땐 2 ~ 100까지 99번 돌아야 해서 ECX 레지스터에 99를 16진수로 바꾼 63을 넣어줬는데,레지스터 2개를 사용할 땐 ECX가 직접 합에 관여하는 변수였기 때문에 1 ~ 100을 더해야해서 100을 16진수로 바꾼 64를 넣어주는 과정이 헷갈렸었다.

지금 생각해보면 레지스터 3개 사용할 때 EAX, EBX 초기값을 0으로 넣고 총 100번(1부터 100까지) 도는 걸로 생각해서 ECX에 64를 넣는 것이 좀 더 수월했을 수도 있을 것 같다.

 📌 분석 실습 보고서 작성

1. 메인함수 찾기
2. 서브함수 찾기
3. 레지스터(EAX, EIP) 변경 확인
4. 스택(RETURN주소 등) 변경 확인

 📌 소스 코드 및 분석 방법 설명

소스 코드: sum.c

#include <stdio.h>

int sum(int a, int b) {
	return a + b;
}

int minus(int a, int b) {
	return a - b;
}

int main() {
	int x = 9;
    int y = 7;
    printf("sum: %d \n", sum(x, y));
    printf("minus: %d \n", minus(x, y));
}

sum.c를 컴파일하여 실행 파일로 만듭니다.

그 이후 sum.exe를 Immunity Debugger에서 실행 시킵니다.

 1️⃣ 메인함수 찾기

처음 sum.exe 파일을 실행시키면 이런 화면이 뜬다.

step over(F8)로 넘어가다 보면 4번째 줄의 CALL sum.00401000을 만난 후

터미널에 결과가 나오고 함수가 종료된다.

그럼 CALL sum.00401000에 break point를 걸고 재시작(ctrl+F2) 후

해당 명령어에서 step into(F7)을 해서 해당 함수 안으로 들어간다.

그러면 해당 화면이 나온다. 여기서 main 함수로 추정되는 명령에서 step over를 하면서 터미널에 값이 나오는지 확인한다.

이 두 함수를 실행해도 터미널에 결과값이 나오지 않으니 main 함수가 아닌 걸 알 수 있다.

Step over로 넘어가다가 CALL sum.00401368을 만나 실행하면

터미널에 결과값이 출력된다. 그러므로 sum.00401368이 main 함수이다.
해당 명령어에 break point를 걸고 재시작 후 step into(F7)을 해서 main 함수로 들어간다.

 2️⃣ 메인 함수 실행 후 스택, 레지스터 값 확인

Main 함수로 들어가면 먼저 return해야하는 주소를 스택에 쌓고 처음에 원래의 EBP값을 스택에 push해준다.

그리고 원래의 ESP값을 새롭게 EBP값으로 지정해준다.

이 EBP값은 해당 함수만의 EBP값이다. 이후 EBP값을 16진수 20만큼 늘려 놓는다.

이는 변수를 저장해 놓는 곳을 확보하는 것이다.
실제로 immunity debugger에서 보자면

아까 main함수 다음 명령어 주소인 004010FD가 main 함수가 실행되자 마자 스택에 쌓이는 것을 볼 수 있다.

또한 6, 7번째 줄을 실행시키면 int x = 9, int y = 7인 코드가 실행되며 스택에 쌓이게 된다.

레지스터 값은 명령어에 따라 바뀌게 된다.

여기서 중요한 점은 스택에 9, 7 순으로 쌓였는데 스택은 LIFO 구조이므로 7이 먼저 EAX에 들어간다는 것이다.

EIP값은 늘 바로 이후에 실행할 명령어 주소를 담고 있다.

 3️⃣ 서브  함수 찾기 (sum, minus)

서브 함수도 메인 함수 찾는 것과 같이 터미널을 확인하며 진행한다.

서브 함수(sum, minus) 찾는 것은 비교적 쉬웠는데, 오른쪽에 보면 프린트문이 나와있는 것을 볼 수 있다.

역시나 해당 코드까지 실행해보니 터미널에 sum()과 minus() 결과값이 나왔다.

서브 함수인 sum(), minus()에도 breakpoint를 걸고 step into(F7)로 레지스터와 스택의 변경을 확인해보도록 한다.

4️⃣ 서브 함수의 레지스터 스택 값 확인

먼저 sum() 함수에서 step into(F7)로 들어간다. 일단 돌아 가야 할 리턴 주소 값을 스택에 넣는다.

이후 main함수 실행했던 것과 같이 원래의 EBP값은 스택으로, 원래의 ESP값을 새로운 EBP값으로 넣어주는 것을 볼 수 있다.

sum함수를 실제로 계산하는 부분은 5번째 줄이다. 그 전에 EDX에 9를, EAX에 7을 넣는 작업을 한다.

이것은 4번째 줄까지 실행시킨 후의 레지스터 값이다.

5번째 줄을 실행하면 EAX, EDX를 더해 다시 EAX에 저장한다.

EIP값은 여전히 늘 다음 명령어를 가리킨다.

헷갈리지 말아야할 점은 현재 실행되고 있는 명령어가 아니라 다음에 실행할 명령어라는 것이다.

예를 들어,

이렇게 0030125B POP EBP를 수행하면 밑에 줄에 파란 줄이 생기고

레지스터에는 이렇게 나온다.

EIP값이 파란 줄 주소와 같으므로 혼란이 올 수 있는 점을 유의한다.

sum()에서 RETN을 만나서 나온 후 print문을 만나면 터미널에 출력된다.

minus함수도 sum함수와 비슷하게 작용한다.

여기서 minus()함수인 CALL sum.0040135D에서 step into(F7)을 한다.

sum()과의 차이점은 EDX를 사용하지 않는다는 것이다. 순서대로 레지스터 값을 보면

이런 식으로 해당 명령어에 따라 ESP, EBP, EAX가 변화하고 EIP는 다음 실행할 명령어로 계속 바뀐다.

스택 값은 sum과 똑같이 작용한다. 하나만 보자면

처음 minus 실행하면 리턴 값이 스택에 쌓이게 된다.

리턴 후 print문을 만나면 터미널에 출력된다.

이후 step over(F8)로 실행하다가 ExitProcess를 만나면 종료된다.

 📌 느낀 점

 자료구조 때 배웠던 스택의 특징을 어셈블리어를 통해 실습할 수 있었다.

실행 파일이다 보니 이미 실행한 코드 한 줄을 다시 되돌릴 수가 없어서 다시 재시작 후 처음부터 봐야해서 귀찮았다 ,,

Immunity Debugger도 처음 사용해봤는데, 파란 줄로 뜨는 것이 현재 실행한 코드가 아닌 다음 실행할 코드인 게 상당히 헷갈렸다. 이럴 땐 EIP를 꼭 참고하는 걸로 !

 📌 들어가며

운영체제 수업 중 race condition에 대한 과제를 받았다.

x86 CPU 시뮬레이터를 통해 race condition과 test-and-set을 비교해서 race condition에 대해 분석하고 문제에 대한 답변을 작성하는 것이다.

그렇다면.. race condition이란?

경쟁 상태라고도 하며
두 개 이상의 프로세스가 공통 자원을 사용할 때,
타이밍이나 순서에 따라 시스템 결과값이 달라지는 것을 말한다.

race condition은 디버깅 할 때는 문제점을 찾을 수 없고, 늘 항상 같은 결과값을 보장하지 못하므로 치명적인 문제가 발생할 수 있다.

따라서 동시성 이슈를 해결해줘야한다.

📌 실습 환경

• Ubuntu OS가 설치된Linux 실습환경
• Python버전 2.x 이상 (Python 3 아님에 주의!)

 📌 분석에 필요한 파일

교수님께서 깃허브 링크를 주셔서 clone 받은 후 실습을 진행했다.
깃헙 링크를 첨부하기가.. 조금 그래서 파일 명을 가지고 설명해보도록 하겠습니다.

• x86.py
• race.s (race condition 발생 o)
• test-and-set.s (race condition 발생 x)

여기서 x86.py는 x86 시뮬레이터 파일이며,
race.s와 test-and-set.s은 count 변수의 값을 1 증가시키는 어셈블리 instruction 코드이다.

 📌 결과값 예시

왼쪽의 count는 변수, ax는 레지스터이며 Thread 0, Thread 1은 공통된 자원(count)를 공유하는 쓰레드이다.

현재는 인터럽트가 아무 것도 걸리지 않았으므로 Thread 0에서 count값을 1 더해주고, Thread 1이 1이 저장된 count값을 받아 1을 더해주었다. 따라서 최종 결과값은 count가 2인 것을 볼 수 있다.

만약, 이 코드에서 인터럽트가 걸려서 코드의 타이밍이 변경된다면 결과값이 달라질 수도 있을 것이다.

 📌 race.s 코드에서 인터럽트 빈도가 1 또는 2라면?

두 실행 결과 모두 count값이 1이 된다.

인터럽트 빈도가 1이나 2일 때는 Thread 0에서 ax값을 count에 저장하는 코드가 실행되기 직전에 인터럽트가 걸린다.

이 경우에는 count값이 공유되는 데이터이므로 Thread1이 1000번 명령어인 count값을 ax레지스터로 가지고 올 때 1로 바뀌지 않고 아직 0으로 셋팅된 count값을 가지고 오기 때문에 문제가 된다.

즉 Thread0에서 ax에 1을 더하는 것과 ax값을 count에 넣는 코드가 연달아 실행되지 않아서 Thread1은 변경되지 않은 count 값을 가지고 명령어를 수행하기 때문에 최종 count값이 1이된다.

 📌  race.s 코드에서 인터럽트 빈도가 3이상이라면?

인터럽트 빈도가 3 이상이라면 count 값은 결과적으로 2가 나온다.

인터럽트 빈도가 3이나 4일 때, 그리고 5이상(Thread0의 코드가 이미 끝난 경우)일 때에는 인터럽트 빈도가 2 이하일 경우와는 다르게 1001, 1002번 명령어인 ax에 1을 더하는 것과 ax값을 count에 저장하는 코드가 연달아 수행되기 때문에 최종 count값은 2가 된다.

 📌 race.s 코드의 race condition 문제점

ax 레지스터에 각 스레드의 결과를 저장하는 부분이 올바른 타이밍에 실행되지 않으면 결과값이 달라지는 치명적인 문제가 발생한다.

이 코드에서는 1001, 1002번 명령어가 한 번에 실행되지 않을 경우에 해당하는 것이다.

따라서 인터럽트 빈도가 1 또는 2일 경우에 count 결과값이 달라지므로 race condition 문제가 발생한다고 볼 수 있다.

 📌 test-and-set.s 코드에서 인터럽트 빈도에 따른 count 값은?

위 사진은 test-and-set.s를 인터럽트 없이 실행시킨 코드이다.

이 코드는 아까 race.s 코드와는 다르게 인터럽트 빈도를 다양하게 걸어도 race condition 문제가 발생하지 않는다.

먼저 count와 mutex는 공유되는 데이터, ax는 각각이 가진 레지스터이다.

여기서 mutex값은 lock을 걸어줬는지 아닌지를 알 수 있는 데이터로 사용된다. 

실행결과를 보면 1004번 명령어가 현재 count값을 자신의 ax레지스터로 가져오는 명령어이다. 이 명령어가 제대로 변경된 후의 count값을 가지고 오면 문제가 없을 것이다.

이 코드에서 인터럽트가 상관없는 이유는 1004번 이전의 명령어와 1007번 명령어 때문이다.

Thread1은 인터럽트를 걸고 ax값을 1로 셋팅해서 현재의 mutex값과 비교한다. Thread0이 count값을 가져오고(1004) ax에 1을 더하고(1005), ax를 count에 저장하는(1006) critical section에 해당하는 코드를 실행하기 직전에 mutex값을 1로 셋팅하기 때문에 Thread1은 mutex값을 보고 1이면 Thread0이 아직 critical section코드를 수행하고 있다고 알 수 있기 때문에 다시 1000번 명령어로 점프하게 된다.

즉, 인터럽트가 언제 걸리든 항상 Thread1은 mutex값 비교를 통해 Thread0이 count값 저장을 끝냈는지를 알 수 있다. 따라서 Thread0이 1증가된 ax값을 count에 저장하는 코드인 1006번 코드가 끝나고 mutex값을 다시 0으로 변환해주기 전까지는 Thread1이 1000번 코드로 게속 점프하게 된다. 만약 검사 했을 때 mutex값이 0이라면 Thread1에서는 더이상 1000번코드로 점프하지 않고(검사하지 않고) 비로소 1004번 코드로 넘어가게 된다.

이 코드에서 mutex값을 1로 바꿔주는 것은 critical section전 lock을 거는 것이고 mutex값을 0으로 바꿔주는 것은 lock을 해제한다는 의미를 가진다. 따라서 Thread1은 lock이 걸린지 아닌지를 확인하고 lock이 해제될 때까지 기다리다가 해제되었다고 판단되면 현재 count값을 가지고 와서 다음 명령어들을 실행한다.

결론적으로 Thread1은 count값이 1로 변경되고 나서 가지고 오기 때문에 최종 결과값은 인터럽트 빈도에 상관없이 2가 된다.

 📌 순환알고리즘 하노이 타워 문제

원반의 개수를 3에서 10까지 변경하면서 그 결과를 확인해 본다. 또한 디스크 이동 횟수도 확인해 볼 것.

** 화면 출력 예 (위치 지점을 A, B, C라고 한 경우의 예) :

#1. 디스크 1개를 A지점에서 C로 옮긴다.

#2. 디스크 1개를 B지점에서 B로 옮긴다.

.......

(*출력 줄의 수는 디스크 이동 횟수를 의미)

 📌 풀이

가장 큰(맨 밑) 원판과 나머지로 나누어서 생각해보면 가장 큰 원판을 뺀 나머지를 B로 옮긴 후 가장 큰 원판을 C로 옮기고 다시 나머지를 B에서 C로 옮긴다.

즉, 단계마다 가장 큰 원판을 제외한 나머지는 모두 B를 거쳐서 C를 간다는 것이다. (출발지에서 경유지를 들려서 목적지에 도착함.)

그러면 재귀 함수를 사용해서 예를 들어 원판이 5개가 있고 1, 2, 3, 4, 5를 크기순이라고 치면

1. 1~4를 B로 옮기고 5를 C로 옮긴다.

2. 1~3을 A로 옮기고 4를 C로 옮긴다.

3. 1~2를 B로 옮기고 3을 C로 옮긴다.

4. 1을 A로 옮기고 2를 C로 옮긴다.

5. 1을 C로 옮긴다.

이렇게 볼 수 있다.

 📌 코드1 (주석 참고)

#include <iostream> 
using namespace std;

int cnt = 0; // 이동 횟수에 이용.

void Hanoi(int n, char from, char temp, char to)
// n : 원반개수, from : 원래 위치, temp : 임시 장소, to :목적지
{
	// cnt = pow(2, n) - 1;
	// 가장 밑에 있는 원반을 제외한 모든 원반은 from -> temp -> to로 옮겨진다.

	if (n == 1) {
		cout << "#" << ++cnt << ".디스크 1개를 " << from << "지점에서 " << to << "로 옮긴다." << endl;
	}
	else {
		Hanoi(n - 1, from, to, temp); // 맨 밑 원반을 제외한 모든 원반을 from에서 temp로 옮긴다.
		cout << "#" << ++cnt << ".디스크 1개를 " << from << "지점에서 " << to << "로 옮긴다." << endl; // 맨 밑 원반을 from에서 to로 옮긴다.
		Hanoi(n - 1, temp, from, to); // 맨 밑 원반을 제외한 모든 원반을 temp에서 to로 옮긴다.
	}
}


void main()
{
	int n; //원반의 수

	cout << "원반의 갯수를 입력하세요 : ";
	cin >> n;

	Hanoi(n, 'A', 'B', 'C');    // n개의 원반을 'A'에서 'C'로 이동

	cout << "전체 원반 이동 수(원반수 : " << n << ") = " << cnt << endl;
 }

1. MIPS 시스템의 개요

-MIPS는 S(Microprocessor without interlocked pipeline stage의 약자로 컴퓨터 분야에서 밉스 테크놀로지에서 개발한 축소 명령 집합 컴퓨터(RISC)의 구조 및 그 구조를 이용한 마이크로프로세서임.
-1980년대 스탠포드대학에서 John Hennessy와 그의 동료들에 의해 개발됨
-Silicon Graphics, Nintendo, Cisco의 제품에서 사용되고 있음

2. 디자인 원리

-규칙적인 것이 간단성을 위해 좋음
-많이 발생되는 사항을 빨리 처리함
-적을수록 빠름
-좋은 설계는 좋은 절충안을 요구함

3. 설계 원칙 1

규칙적인 것이 간단성을 위해 좋음

-일관성있는 명령어 형태
-같은 수의 피연산자 (두 개의 source와 한 개의 destination)
-하드웨어로 구현하기 쉬움

명령어는 Addition(덧셈)과 Subtraction(뺄셈)뿐이다.

-Addition(덧셈)
a = b + c 는 밉스 어셈블리 코드로 add a, b, c 로 나타낼 수 있다. 여기서 add는 연산코드이며, a는 목적지, b와 c는 각각 소스1, 2이다. 밉스 어셈블리 코드에서는 무조건 destination코드 위치가 정해져있음을 주의한다.

-Subtraction(뺄셈)
a = b - c 는 밉스 어셈블리 코드로 sub a, b, c 로 나타낼 수 있다. 덧셈과 같이 sub는 연산코드, a는 목적지, b와 c는 각각 소스1, 소스2이다.

4. 설계 원칙 2

많이 발생되는 사항을 빨리 처리함

-MIPS: 단순하고, 많이 사용되는 명령어를 포함
-명령어를 해석하고 실행하는 하드웨어: 단순하고 빠름
-복잡한 명령어는 여러개의 단순한 명령어로 수행됨

명령어 한 줄을 처리하는 데 시간이 단축되어 빠르다는 장점이 있다.

컴퓨터 구조 분류

RISC (Reduced Instruction Set Computer): MIPS
CISC (Complex Set Instruction Set Computer): Intel의 IA-32

복잡한 코드: 여러개의 MIPS 명령어에 의해 처리됨

a = b + c - d 는 add t, b, c 와 sub a, t, d 라는 두 개의 밉스 명령어를 사용한다.
먼저 add t, b, c 는 t = b + c 라는 의미이며 sub a, t, c는 앞서 나온 결과 값 t를 이용하여 a = t - d 라는 의미이다. 즉 t 대신 b + c 를 넣으면 a = b + c - d 이기 때문에 같다.

5. 설계 원칙 3

적을수록 빠름

-MIPS: 적은수의 레지스터를 포함
-32개의 레지스터 (32 비트 또는 64 비트)
-32개의 레지스터로 부터 데이터를 획득하는 것이 1000개의 레지스터 또는 메모리로 부터 데이터를 획득하는 것 보다 빠름

6. MIPS 레지스터 세트(레지스터 이름 / 레지스터 번호 / 사용법)

$0 / 0 / 상수값 0
$at / 1 / 어셈블러 임시용
$v0 - $v1 / 2 - 3 / 프로시저 리턴 값(함수 결과값)
$a0 - $a3 / 4 - 7 / 프로시저 인자
&t0 - $t7 / 8 - 15 / 임시 변수
$s0 - $s7 / 16 - 23 / 저장 변수
$t8 - $t9 / 24 - 25 / 임시 변수
$k0 - $k1 / 26 - 27 / 운영체제 임시용
$gp / 28 / 전역 포인터
$sp / 29 / 스택 포인터
$fp / 30 / 프레임 포인터
$ra / 31 / 프로시저 반환 주소

레지스터 마다 각각 할 일(역할)이 정해져있다.

7. 레지스터를 사용한 명령어

a = b + c 는 $s0 = a, $s1 = b, $s2 = c 일 때, add $s0, $s1, $s2 한 것과 같다.
a = b + c - d 는 $s0 = a, $s1 = b, $s2 = c, $s3 = d 일 때, sub $t0, $s2, $s3 와 add $s0, $s1, $t0 를 한 것과 같다.

8. 워드(word) 주소 메모리

-load 명령어 (lw)

어셈블리 코드 lw $s3, 1($0) : ($0)은 상수값 0으로 1 + 0 = 1이며 워드 주소 1을 $s3에가져오라는 것이다. 즉 $s3이 목적지가 된다.

-store 명령어 (sw)

어셈블리 코드 sw $t4, 0x3($0) : ($0)은 상수값 0이므로 16진수의 3과 0을 더해 3이다. 여기서는 $t4가 source, 0x3($0)이 목적지이기 때문에 워드주소 3에 $t4의 값을 쓰라는 것이다.

9. 바이트(byte) 주소 메모리

-load 명령어 (lw)

항상 가져오는 양은 1word로 정해져있다.
어셈블리 코드 lw $s3, 4($0) : ($0)은 상수값 0으로 4 + 0 = 4이다. 이는 워드 주소 4를 $s3으로 가져오라는 것이다. 즉 $s3이 목적지가 된다.

-store 명령어 (sw)

어셈블리 코드 sw $t7, 12($0) : ($0)은 상수값 0이므로 12와 0을 더해 12이다. 1여기서는 $t7이 source, 12($0)가 목적지이다. 즉 16진수로 12는 C이기 때문에 워드주소 C에 $t7의 값을 쓰라는 것이다.

10. 빅-엔디안, 리틀-엔디안

이는 데이터를 읽어오는 방식에 대해 차이가 있다.

MSB는 제일 높은 주소, LSB는 제일 낮은 주소이다.
빅-엔디안은 높은 주소 -> 낮은 주소 순으로,
리틀-엔디안은 낮은 주소 -> 높은 주소 순으로 데이터를 읽어온다.

예제) $t0의 값이 0x23456789라고가정한다. 아래의프로그램이 Big-Endian 시스템과Little-Endian시스템에서 수행한 후에 $s0의값은?

sw $t0, 0($0)
lb $s0, 1($0) # 1+0 = 1 즉 1번지의 데이터 값을 $s0에 가져와라.

결과 값

Big-Endian: $s0 = 0x00000045
Little-Endian: $s0 = 0x00000067

해설

Big-Endian은 MSB -> LSB 순으로 데이터를 불러오기 때문에 45가 1번지이고,
Little-Endian은 LSB -> MSB 순으로 데이터를 불러오기 때문에 67가 1번지이다.

11. 설계 원칙 4

좋은 설계는 좋은 절충안을 요구함

-다중 명령어 형태는 융통성 제공
(1) add, sub: 3개의 레지스터 피연산자 사용
(2) lw, sw: 2개의 레지스터 피연산자와 상수 사용
:적은 수의 명령어 형태를 유지함

12. 기계어

기계어는 32비트 명령어로, 명령어들을 이진 표현한다. 즉 0과 1로만 나타낸다.
명령어 형태로 R-Type, I-Type, J-Type이 있다.

12-1. R-Type

레지스터의 R을 사용한 R-Type은 3개의 레지스터 피연산자(오퍼랜드)를 갖는다.
rs, rt는 source 레지스터이며, rd는 destination 레지스터이다.
다른 필드는 op 즉 operation 코드(op코드), funct(function), shamt(shift 명령어에서 사용되는 shift 양)이 있다.
R-Type명령어에서는 op코드 값이 모두 0으로 무슨 타입인지 모를 때도 op값을 보고 알 수 있다.
shamt는 예로 곱셈, 나눗셈에서 사용되며, funct는 op가 모두 0이기 때문에 명령어를 분류하기 위해 사용한다.

예시)

어셈블리 코드를 먼저 10진수의 R-Type으로 바꾸면

이렇게 된다. R-Type이기 때문에 op코드가 0, rs와 rt는 source, rd는 destination이다. 여기서는 곱셈과 나눗셈이 없으므로 둘 다 0이고 funct는 add는 32, sub은 34로 나타낸다.
이를 기계어 즉 2진수로 바꾸면

결론적으로 이런 값을 얻는다.

12-2. I-Type

즉시값(Immediate) 타입으로 3개의 피연산자(오퍼랜드)를 가진다. rs, rt는 레지스터 피연산자이며 imm은 16비트의 즉시값이다.
다른 필드로는 op코드가 있다.
R-Type과는 달리 funct가 존재하지 않는 이유는 op코드가 이미 개별적인 값을 갖기 때문이다.
여기서 중요한 점은 imm이 10진수의 상수값을 가지는 것이다.

예시)

addi에서 i는 즉시값 타입을 나타내고 있다. 여기서 rt가 목적지, rs와 imm이 source이다.
이를 I-Type으로 나타내면

addi $s0, $s1, 5에서 $s0은 rt로, $s1은 rs로 상수 5는 imm값으로 들어간다. 또한 더하는 명령어의 op코드 값인 8이 op자리에 들어간다.
lw $t2, 32($0)에서 처럼 피연산자가 하나, imm값이 하나인 경우에는 피연산자가 rt값에 들어간다.
이를 기계어 코드로 바꾸면

결론적으로 이런 값을 얻는다.

12-3. J-Type

Jump타입으로 1개의 피연산자(오퍼랜드) addr를 가진다. 이는 주소 피연산자이다.
다른 필드로는 op코드가 있다.
분기 명령어 때 사용되는 명령어 형식이다.

addr은 어디로 갈 지의 데이터가 들어있다.

13. 기계어 코드 해석

순서
(1) opcode 분석
(2) opcode가 0이면 R-Type으로 funct비트를 통해서 명령어 기능 분석
(3) opcode가 0이 아니면, I-Type 또는 J-type 명령어

예시)

먼저 0x2237FFF1은 기계어 코드를 4비트씩 쪼개 16진수로 만든 것이다. 또한 op코드가 0이 아니고 imm이 있는 것을 보면 I-Type인 것을 알 수 있다.
0x02F34022도 기계어 코드를 4비트씩 쪼개 16진수로 만든 것이며 op코드가 0이므로 R-Type인 것을 알 수 있다.

14. 조건부 분기 (beq)

먼저 i가 붙은 것을 봐서 I-Type이다. 또한 첫 번째가 목적지임을 생각하고 코드를 분석하면
$s0 = 0 + 4 = 4
$s1 = 0 + 1 = 1
$s1 = 1 << 2 = 4 이다.
여기서 sll 은 시프트 연산으로 예를들어 0001을 왼쪽으로 2 시프트 하면 0100이 되기에 4가 된다.
이후 나오는 beq에서는 $s0과 $s1이 같으면 target으로 가라는 명령어다. 현재 $s0과 $s1은 4로 같기 때문에 target으로 바로 분기한다. 따라서 beq후에 나오는 addi와 sub명령어는 수행하지 않는다.
target에서의 코드는 $s1 = 4 + 4 = 8 이다.

15. 조건부 분기 (bne)

bne는 $s0과 $s1이 같지 않을 경우 분기하는데 여기서는 같기 때문에 분기 하지 않고 다음 명령어를 수행한다.

16. 무조건 분기 (j)

무조건 분기의 경우 조건을 따지지않고 분기하기 때문에 목적지 target만 있다.
j를 만나면 바로 분기한다. 따라서 sra, addi, sub의 명령어를 수행하지 않는다.

17. 무조건 분기 (jr)

jr은 레지스터를 가지는데 그 레지스터의 데이터를 주소로 판단한다.
즉 $s0으로 무조건 분기하라는 것으로 현재 $s0은 0x2010으로 lw명령어 주소이기 때문에 그곳으로 분기한다.
따라서 사이에 있는 addi와 sra명령어를 수행하지 않는다.

18. if문

if문의 조건은 i와 j가 같으면인데 mips에서는 bne 즉 i와 j가 같지 않으면을 쓴다.
그 이유는 if조건이 같지 않으면 수행을 하지 않아야 하기 때문이다.
bne에서 조건이 같지 않으면 add를 수행하면 안되기 때문에 L1으로 분기하는 것이다.

19. if/else문

그냥 if문과는 달리 j done이 추가된 것을 볼 수 있다.
if문의 조건이 아니면 else문을 실행해야 하기 때문에 mips에서 bne(조건이 다르면) L1으로 분기하라는 것이 있으며 마만약 조건이 같으면 분기 하지 않고 add를 수행한다. 이후 else문은 수행을 하면 안되므로 j를 사용해 done으로 무조건 분기한다.

20. while루프

while문에서 pow가 128이 아닐동안 수행하는 것이기 때문에 128이 되면 while문을 돌면 안된다. 따라서 mips에서 while문이 beq인 이유가 pow가 128이면 돌지 않고 분기해야하기 때문이다. 또한 while문의 마지막에 j가 있는 이유는 계속해서 돌아야하기 때문에 while로 다시 분기를 하는 것이다.

21. for루프

for문에서 i가 10이 아닐 동안 돌아야하기 때문에 i가 10이 되면 돌지 않아야 한다. 따라서 mips에서 i가 10일 경우 분기하도록 beq $s0, $t0, done이 되어 있다. 또한 계속 돌기위해 for문 마지막에 다시 for문으로 분기하는 j 명령어가 있다.

22. Less Than 비교

먼저 볼 것은 loop에 있는 slt명령어이다. 이는 Set on less than의 약자로 slt $t1, $s0, $t0 dms 만약 $s0 < $t0이면 $t1에 1을 넣고 아니면 0을 넣으라는 것이다.
즉 slt a, b, c가 있으면 b와 c를 비교해 a값을 정하는 것이다.
또한 loop의 beq는 break코드로 이해하면 된다.
slt에서 i가 101보다 크거나 같으면 0을 넣기 때문에 beq에서 $t1이 0이면 분기하면 된다.

문제

더보기

1. MIPS assembly code로 add a, b, c가 있다. 여기서 목적지는 어디인지 쓰시오. ( )

2. MIPS assembly code로 add t, b, c sub a, t, d로 나타낼 때 이를 High-level code로 나타내시오.

( )

3. 이미지에 대한 설명으로 옳지 않은 것을 고르시오.

1) 바이트 주소 메모리이다.

2) lw명령어에서 가져오는 양은 1word로 정해져있다.

3) sw $t7, 12($0)은 워드주소 10진수 12에 $t7을 쓰라는 것이다.

4) 현재 1word당 4byte이다.

4. 보기를 리틀엔디안 시스템에서 수행한 후 $s0의 값을 구하시오.

보기) sw $t0, 0($0) lb $s0, 2($0)

( )

5. 어떤 명령어 형태인지 쓰시오. ( )

6. for루프를 MIPS assembly code로 나타내려고 한다. 빈칸에 들어갈 명령어를 쓰시오. ( )

7. High-level code를 MIPS assembly code로 바꾸려고 한다. 빈칸에 들어갈 내용을 쓰시오. ( )

답안

출처
2019 컴퓨터 구조 호준원 교수님 강의노트 9
디지털논리와 컴퓨터 설계, Harris et al. (조명완 외 번역), 사이텍미디어, 2007
컴퓨터 구조와 원리 (비주얼 컴퓨터 아키텍쳐), 신종홍 저, 한빛미디어, 2011

1. 코드

from selenium import webdriver

driver = webdriver.Chrome(r"C:\Users\SAMSUNG\Desktop\chromedriver_win32\chromedriver")
driver.get(r"http://zzzscore.com/1to50/?ts=1591020560516")

numbtn = driver.find_elements_by_xpath(r'//*[@id="grid"]/div[*]')

for i in range(1, 51):
    for n in numbtn:
        if n.text == str(i):
            n.click()
            break

2. 결과

3. 영상

1. 개념

주기억장치에 저장되어 있는 명령어와 데이터 중의 일부를 임시적으로 복사해서 저장하는 장치

cpu안에 있는 것이 아니며 주기억장치와 분리되어 있다. cpu안에 있는 것은 레지스터이다.

2. 특징

자주 사용되는 명령어들을 저장하고 있다가 cpu가 필요할 때 빠르게 제공하며 데이터를 저장하고 인출하는 속도가 주기억장치보다 빠르다. 속도가 주기억장치보다 빠르고 cpu보다 느리기 때문에 둘의 속도 차이를 줄여주는 고속완충기억장치이며 용량이 작고 비싸지만 빠르다는 장점이 있다.

3. 캐시 기억장치가 없는 시스템

-동작원리

1단계: CPU가 명령어와 데이터를 인출하기 위해서 주기억장치에 접근한다.

2단계: 주기억장치에서 명령어나 필요한 정보를 획득하여 CPU내의 명령어 레지스터 등에 저장한다.

-특징: 주기억장치에 매번 접근해야하기 때문에 속도가 너무 느리다는 단점이 있다.

4. 캐시 기억장치가 있는 시스템

-동작원리

CPU가 명령어 또는 데이터를 인출하기 위해 주기억장치보다 캐시기억장치를 먼저 조사한다. 만약 캐시기억장치에서 그 명령어 또는 데이터가 있으면 적중(hit)이라고 하고, 없으면 실패(miss)라고 한다.

적중일 경우 주기억장치를 방문하지 않고 캐시기억장치에서 얻어진 정보를 CPU로 전송한다.

실패일 경우 주기억장치 들려서 캐시기억장치에 넣고 캐시에서 가져온다. 이때, 굳이 캐시에 넣고 다시 캐시에서 꺼내오는 이유는 나중에 다시 쓸 수도 있기 때문이다.

4-1. miss

CPU가 1000번지의 워드가 필요한 경우, 지금 상황에서는 캐시기억장치가 빈 상태이기 때문에 실패상태가 된다. 

실패상태일 경우 1000번지가 필요하니까 1000번지를 가져오는데 1001, 1002, 1003도 나중에 CPU가 사용할 것이라고 유추되면 가져온다.

4-2. hit

CPU가 1002번지의 워드가 필요한 경우

캐시기억장치에 먼저 접근해서 1002번지 워드가 있는지 검사하는데 지금 상황의 경우 캐시기억장치에 1002번 워드가 있기 때문에 주기억장치에 접근하지 않고 캐시기억장치에서 바로 가져온다.

5. 캐시 기억장치의 적중률

적중률: 캐시 기억장치의 성능을 나타내는 척도

적중률이 높을수록 데이터 액세스 속도가 향상된다.

적중률은 0에서 1사이의 값으로 나타낼 수 있으며 예를들어 10번 캐시기억장치에 접근했을 때 3번 hit을 했다면 3/10으로 적중률은 0.3(30%)이다.

이를 기반으로 주기억장치와 캐시기억장치에서 데이터를 인출하는데 소요되는 평균 기억장치 접근시간을 알 수 있다.

결론적으로 Taverage = Hhit_ratio * Tcache + (1-Hhit_ratio) * Tmain으로 구할 수 있다.

예제) Tcache = 50ns, Tmain = 400ns일 때, 적중률을 증가시키면서 기억장치 접근시간 계산을 하면

여기서 알 수 있는 점은 먼저 Tcache, Tmain 값을 봤을 때 캐시 접근이 훨씬 적은 시간이 걸린다는 것과, 적중률이 커지면서 주기억장치에 접근하는 횟수가 적어지기 때문에 결론적인 기억장치 접근시간이 훨씬 줄어드는 것이다.

6. 캐시 기억장치의 설계

워드는 CPU가 한 번에 처리할 수 있는 데이터 단위이고 이 워드들이 모이면 블록이된다.

*캐시기억장치 설계시 고려해야할 요소

캐시기억장치의 크기(size)

인출방식(fetch algorithm)

사상함수(mapping function)

교체 알고리즘(replacement algorithm)

쓰기 정책(write policy)

블록 크기(block size)

캐시기억장치의 수(number of caches)

6-1. 캐시 기억장치의 크기

-캐시기억장치의 크기가 클수록 확보할 수 있는 요량이 커지기 때문에 적중률은 높아지지만 즉 hit하는 횟수가 많아지지만 캐시 내용을 모두 확인하는데 시간이 많이 걸리기 때문에 평균 접근 시간과 비용이 증가한다.

-적중률을 향상시키고 평균 접근시간에 대한 저하를 막는 최적의 크기 결정이 필요한데 1K ~ 128K 단어(word)가 최적이라고 한다.

6-2. 인출 방식

인출방식이란 주기억장치에서 캐시기억장치로 명령어나 데이터 블록을 인출해 오는 방식이다.

6-3. 사상함수

사상이란 Mapping이라고 하며 주기억장치와 캐시기억장치 사이에서 정보를 옮기는 것을 말한다.

먼저 주기억장치의 구조를 보면 하나의 주소번지에 저장되는 데이터의 단위를 단어(word)라고 하며 단어가 모이면 블록이된다. 캐시기억장치의 구조를 보면 슬롯과 태그가 있는데 슬롯은 데이터 블록이 저장되는 장소이고, 태그는 슬롯에 적재된 데이터 블록을 구분해주는 정보이다.

캐시기억장치의 사상방법에는 직접사상, 연관사상, 집합 연관 사상으로 총 3가지가 있다.

6-3-1. 직접 사상(direct mapping)

특징: 캐시기억장치로부터 데이터 블록 인출을 위해 데이터 블록의 슬롯번호에 해당하는 슬롯만 검색하면 된다.

장점: 사상 과정이 간단함

단점: 동일 슬롯 번호를 갖지만 태그가 다른 데이터 블록들에 대한 반복적인 접근은 적중률을 떨어뜨림

예제)

CPU가 00001번지의 블록을 필요로 하는 경우 실행 전 캐시기억장치는 비어있기 때문에 먼저 주기억장치의 주소를 2개, 3개로 잘라서 앞에 00은 태그로, 뒤에 001은 슬롯번호로 가며 데이터는 그대로 데이터로 넣는다.

CPU가 10001번지 블록을 필요로하는 경우도 예제 1번과 똑같이 진행된다.

하지만 CPU가 00010번지 블록을 필요로 하는 경우 예제1번과 슬롯번호가 같기 때문에 혼동이 생기며, 태그번호는 다르기 때문에 다시 주기억장치에서 새로 데이터를 가져온다.

다음으로 CPU가 00010번지의 블록을 필요로하는 경우 아까 예제 2에서 캐시 기억장치에 넣어놨으니 주기억장치에 접근하지 않고 캐시기억장치에서 바로 데이터를 가져온다.

6-3-2. 연관 사상(associative mapping)

캐시슬롯번호에 상관없이 주기억장치의 데이터블록을 캐시기억장치의 임의의 위치에 저장한다.

특징: 캐시기억장치로부터 데이터 블록 인출을 위해서 모든 슬롯에 대한 검색이 필요하다.

6-3-4. 집합 연관 사상(set-associative mapping)

직접 사상과 연관 사상 방식을 조합한 방식으로 아주 중요하다!

캐시는 v개의 집합들로 나뉘며, 각 집합들은 k개의 슬롯으로 구성된다.

직접 사상 방식에 의해 v개의 집합들 중 하나의 집합을 선택하고, 연관 사상 방식에 의해 선택한 집합 내의 k개의 슬롯 중에 하나의 슬롯을 선택한다.

집합은 무작위로 설정되며 여기서 하나의 집합에는 2개의 데이터 즉 2개의 태그가 있다.

 6-4. 교체 알고리즘

캐시기억장치의 모든 슬롯이 데이터로 채워져있는 상태 즉 full인 상태에서 실패일 때, 주기억장치에서 새로운 데이터 블록을 가져와서 캐시기억장치에 넣어야하는데 이 때 캐시에 있던 데이터 중 무엇을 제거할지 결정하는 방식이다.

직접사상은 교체 알고리즘이 필요지만 연관, 집합 연관 사상에는 교체 알고리즘이 필요하다.

종류

6-5. 쓰기 정책

-즉시쓰기(Write-though) 방식

CPU에서 생성되는 데이터 블록을 캐시기억장치와 주기억장치에 동시에 기록한다. 이는 데이터의 일관성을 쉽게 보장할 수 있지만 매번 쓰기 동작이 발생할 때바다 캐시기억장치와 주기억장치간 접근이 빈번하게 일어나고 쓰기시간이 길어지게 된다는 단점이 있다.

-나중쓰기(Write-back) 방식

캐시기억장치에 기록한 후, 기록된 블록에 대한 교체가 일어날 때 주기억장치에 기록한다. 이는 주기억장치에 기록하는 동작을 최소화 할 수 있지만 중간에 데이터의 손실이나 변조의 위험성이 있어 캐시기억장치와 주기억장치 간에 데이터 불일치가 발생할 수도 있다.

6-6. 블록 크기

블록크기가 클수록 한 번에 많은 정보를 읽어올 수 있지만 블록 인출 시간이 길어지게 된다. 블록이 커질수록 캐시기억장치에 적재할 수 있는 블록의 수가 감소하기 때문에 블록이 더 빈번히 교체과 된다. 그래서 일반적으로 4 ~ 8 단어가 적당하다.

6-7. 캐시기억장치의 수

시스템 성능 향상을 위해서 다수의 캐시기억장치들을 사용하는 것이 보편화 되었다.

캐시기억장치들을 계층적 구조나 기능적 구조로 설치한다.

문제

답안

추가 문제

답안