CS107 [OS] System Call이 호출될때 사용되는 Trap 코드 (xv6) 시스템 콜은 예전부터 사용하면서 Limited direct execution 이라는 개념을 알고 있었지만, 이게 코드상으로 어떻게 구현되는지는 확인해보지 않았었다. 그러다 문득, fork()와 같은 system call()이 사용자 정의 함수가 아닌 System Call 인 것을 어떻게 알고 인터럽트가 발생하게 되어 사용하는 것일까?라는 생각이 들었다. 이에 대한 답변을 위해 스스로 학습한 내용을 정리하고자 한다. 1. User Mode와 Kernel Mode의 전환 Limited direct execution에서는 user mode에서 kernel mode로 mode switch 할 때 trap을 사용하게 됩니다. 그렇다면 OS는 trap을 어떻게 사용할 수 있을까요? OS가 trap을 처리하기 위해선.. CS/OS (2022-1) 2024. 4. 13. [계산 이론] The Halting Problem 컴퓨터를 전공 배우고 있는 사람 입장에서, Halting Problem정도는 한번 증명해 보고 정리해 두면 좋을 것 같다 생각하여 글을 남겨봅니다! 1. Halting Problem 이란? 우선 정의부터 살펴보자! There’s no algorithm that can look at a program’s source code and always correctly determine if the program will run forever or not. 사람의 언어로 조금 바꿔보면, 유한시간안에 프로그램을 실행해보지 않고 정지할지 말지를 결정하는 알고리즘은 존재하지 않는다는 의미이다! 2. Proof by contradiction 다음과 같이 "input과 output을 갖는 halt라는 프로그램(알고리즘)이.. CS/Computation Theory (2023-2) 2023. 12. 12. [계산 이론] Some languages are not Turing-recognizable 이번 증명을 통하여 Turing Machine이 recognize하지 못하는 Language가 있음을 보일 것 이다. 1. 모든 Turing Machine은 countable 하다 모든 튜링머신이 Countable함을 보이기 전에, 우선 모든 String의 집합(∑*)이 모든 alphabet ∑에 대하여 count할 수 있음을 보일것 입니다. ∑* 의 list를 길이가 0, 길이가 1, 길이가 2 ... 순으로 아래로 적어내려 갈 수 있습니다. 또한 각 lenght마다 finite한 수의 String이 있습니다. 이를 그림으로 살펴보면 다음과 같은데, 길이가 0인 String에는 입실론이, 1에는 0과 1, 등등 이 존재합니다. 모든 자연수 1, 2, 3, ... N에 대하여 mapping가능한 하나의 .. CS/Computation Theory (2023-2) 2023. 12. 12. [계산 이론] Non-Context-Free Languages 1. The Pumping Lemma for Context-Free-Languages(CFL) 우리는 보조 정리인 Pumping Lemma를 활용하여 CFL이 아님을 보일 것 이다. 만약 A가 Context-free-lenaguage라면, pumping length p가 존재하며, A의 어떤 String S라도 최소 p만큼의 길이를 갖는다. 또한 그러한 S는 5조각, 즉 S = uvxyz로 나눌 수 있으며, 다음 조건을 만족한다. 조건 2에 의하여 v 또는 y 가 동시에 empty string일수는 없다. 조건 3에 의하여 v,x,y의 길이는 최대 p이다. 2. Proof G를 CFL A의 Context-Free-Grammer(CFG)라 하자. b를 symbol의 최대 수 라고 하자. 예를 들면 다음 C.. CS/Computation Theory (2023-2) 2023. 12. 10. [컴퓨터 구조] 4. 프로세서 4.1 서론 4.1.1) 구현에 대한 개요 우선 모든 명령어의 첫 2단계는 다음과 같이 동일하다. 프로그램 카운터(PC)를 프로그램이 저장되어 있는 메모리에 보내서 메모리로부터 명령어를 가져온다. 읽을 레지스터를 선택하는 명령어 필드를 사용하여 하나 또는 2개의 레지스터를 읽는다. 워드 적재 명령어는 레지스터 하나만 읽으면 되지만 대부분의 다른 명령어는 레지스터 2개를 읽는다. 이 2단계 이후는 명령어의 종류에 따라서 달라진다. 다행히 3가지 명령어 종류(메모리 참조, 산술/논리 연산, 분기) 각각에 대해서는 명령어가 무엇인지에 상관없이 필요한 행동들이 대부분같다. MIPS 명령어 집합은 단순하고 규칙적이기 때문에 여러 종류의 명령어 실행이 비슷해서 구현이 간단하다. 예를 들어 Jump명령어를 제외한 모.. CS/Computer Organization Design (2023-1) 2023. 6. 16. [컴퓨터 구조] 3. 컴퓨터 연산 이번 장에서는 소수와 실수의 표현과 그 연산과정에 대하여 학습하는 시간이다. 기본적인 덧셈과 뺄샘의 정리는 생략 3.3 곱셈 우선 연필로 곱셈하는 과정을 살펴보자. 0과 1로만 구성된 십진수의 곱셈을 살펴보자. 1000(ten) 곱하기 1001(ten)은 다음과 같다. 첫 번째 피연산자는 피승수(multiplicand)라고 부르고 두 번째 피연산자는 승수(multiplier)라고 부른다. 최종 결과는 곱(product)라고 부른다. 일반적으로 수학에서 우리가 곱셈을 할때 승수의 자릿수를 오른쪽에서 왼쪽으로 가면서 한 번에 하나씩 택해서 이것을 피승수와 곱한 뒤 그 곱셈의 결과를 직전의 곱보다 한 자리 왼쪽에 놓는다. 주목할 점은 최종 곱셈 결과의 자릿수가 피승수나 승수와 비교해서 상당히 크다는 것 이다... CS/Computer Organization Design (2023-1) 2023. 5. 9. [컴퓨터 구조] 2. 명령어: 컴퓨터 언어 2.2 하드웨어 연산 다음 MIPS 어셈블리 언어는 두 변수 b, c를 더해서 그 합을 a에 넣으라고 컴퓨터에게 지시하는 것 이다. add a, b, c MIPS 산술 명령어는 반드시 한 종류의 연산자만 지시하며 항상 변수 3개를 갖는 형식을 엄격하게 지킨다. 변수 b, c, d, e의 합을 구하여 a에 집어 넣는 예를 생각해보자. add a, b, c // a에 (b + c)를 대입한다 add a, a, d // a에 d를 더한다 add a, a, e // a에 e를 더한다 따라서 네 변수의 합을 구하려면 명령어 3개가 필요하다. 덧셈과 같은 연산자의 피연산자(operand)는 더해질 숫자 2개와 합을 기억할 장소 하나, 장소가 모두 3개인 것 이 자연스럽다. 이렇게 모든 명령어가 피연산자를 반드시 3.. CS/Computer Organization Design (2023-1) 2023. 4. 17. [컴퓨터 구조] 1. 컴퓨터 추상화 및 관련 기술 1.4 케이스를 열고 컴퓨터의 고전적 구성 요소 다섯가지는 다음과 같다. 1) 입력 2) 출력 3) 메모리 4) 데이터패스, datapath 5) 제어 유닛, control unit 이중 뒤의 2개를 합쳐서 프로세서라고 부르기도 한다. 위 그림은 컴퓨터의 표준 구성을 보여주는 그림이다. 이 구성은 하드웨어 기술과는 독립적이다. 1.4.1) 상자를 열고 다음 그림은 Apple iPhone Xs MAX 스마트폰의 내용물이다. 컴퓨터의 고전적인 5대 구성요소 중 입출력 장치의 비중이 큰것은 놀라울 일이 아니다. 입출력 장치로는 정전용량식 멀티터치 LCD 디스플레이 등이 있으며, 데이터패스, 제어 유닛, 메모리는 구성 요소 중의 작은 일부를 차지하고 있다. 다음 그림에는 직접회로(Intergrated circu.. CS/Computer Organization Design (2023-1) 2023. 3. 21. [자료구조] The Halting Problem (정지 문제) 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 1. Halting Problem이란? 어떤 프로그램이 어떠한 입력값을 받았을 때 종료되는지 아닌지를 돌려보기 "전에" 알 수 있는가? 당연히 프로그램을 돌려봐서 끝난다면 끝난다는 것 을 알수 있지만, 우리는 프로그램을 돌리기 전에 먼저 알고싶다! 코드를 작성하다보면 컴파일에러도 잡아주고, 문법에러도 잡아준다, 어찌 저찌 잘 해보면 실행전에 종료되는지의 유무를 알수 있지 않을까? 1 - 1) 문제의 목적 세상엔 컴퓨터로 풀기 쉬운 문제가 있고, 풀기 어려운 문제가 있다. 그런데 세상엔 컴퓨터로 풀 수 없는 문제도 있다. 정지 문제는 컴퓨터로 풀 수 없는 문제들 중 하나이다... CS/Data Structure (2021-1) 2023. 3. 5. [OS] Virtual Memory - 2 본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다. 3. 다양한 캐싱 환경 ▶ 캐싱 기법 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식이다. 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용한다. ▶ 캐시 운영의 시간 제약 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 거리는 경우 실제 시스템에서 사용할 수 없다. 버퍼 캐싱이나 웹 캐싱의 경우 O(1)에서 O(log N)까지 허용한다. 페이징 시스템의 경우 Page Fault의 경우에만 OS가 관여한다. 페이지가 이미 메모리에 존재하는 경우 참조 시각 등의 정보를 OS가 알 수 없다. 즉 반쪽짜리 정보를 알게된다. O(1)인.. CS/OS (2022-1) 2022. 11. 30. [OS] Virtual Memory - 1 본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다. 1. Demand Paging 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식 얻는 장점 : I/O 양의 감소, Memory 사용량 감소, 빠른 응답 시간, 더 많은 사용자 수용 ▶ Valid-Invalid bit 사용 무효(invalid)의 의미 사용되지 않는 주소 영역인 경우 페이지가 물리적 메모리에 없는 경우 처음에는 모든 페이지의 유효-무효 비트가 무효 값으로 초기화된다. 특정 페이지가 참조되어 메모리에 적재되는 경우 해당 페이지의 무효 비트가 유효 값으로 바뀐다. CPU 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 무효 비트로 세팅되어 있는 경.. CS/OS (2022-1) 2022. 11. 30. [OS] Memory Management - 3 본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다. 2. Segmentation 프로그램은 의미 단위인 여러 개의 segmentation으로 구성될 수 있다. 작게는 프로그램을 구성하는 하나 하나를 세그먼트로 정의 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨 의미를 어떻게 나누는지에 따라 달라짐 세그먼트는 다음과 같은 logical unit이다. main() function global variables stack symbol table arrays 2 - 1) Segmentation 기법 논리적 주소는 으로 나뉘어 사용된다. 세그먼트 번호(s)는 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째.. CS/OS (2022-1) 2022. 11. 30. 이전 1 2 3 4 ··· 9 다음
