Context-Free Languages (CFL)문맥-자유 언어 - 문맥-자유 문법에 의해 생성되는 언어를 지칭한다. * Parsing (파싱)- 문장을 문법적 유도를 통하여 설명하는 과정이다.- 문장의 구조를 표현하는 방법 중 하나이다.- \(L(G)\)에 속하는 \(w\)가 유도되는데 사용된 일련의 생성규칙들을 찾는 과정이다. Context-Free Grammars (문맥-자유 문법) Definition 5.1 CFG (Context-Free Grammar; 문맥-자유 문법)문법 \(G = (V, T, S, P)\) 에서 모든 생성 규칙이\(A \to x\)\((A \in V, x \in (V \cup T)^*)\)의 형태를 가지면,\(G\)를 문맥-자유 문법(CFG)이라 한다.※ CFG의 생성..
System Call 시스템 콜 - OS가 수행하는 Service를 프로그램에 제공하는 Interface 역할을 하는 함수이다. - C언어의 함수와 형태가 같으나, 실제로는 H/W Interrupt Instruction으로 구현되어 있다. Types of System Calls (시스템 콜의 종류) - 시스템 콜은 아래와 같이 4가지로 분류될 수 있다. 1) Process Manegement (프로세스 제어) - 프로세스 생성 : fork() - 프로세스 종료 : exec 계열 - 시그널 2) File, I/O Management (파일 및 입출력 관리) - 생성 및 종료 - 열기 및 닫기 - read 및 write 3) Communication (통신) - connect(), accept() 등 4) ..
Process Model 프로세스 구조 * Process - 실행중에 있는, 메인 메모리에 Load되어 있는 프로그램이다. - 프로그램은 일련의 명령어로 구성된 파일이다. - 각 프로세스들은 독립적인 주소공간(Virtual Address)이 할당되어 각자의 Code를 처리한다. - Kernel 프로세스*를 제외한 모든 프로세스는 Parent 프로세스에 의한 fork()로 생성된다. (fork() 호출 이외의 방법은 없다.) - Kernel은 exec() System Call을 통해 프로그램을 메인 메모리에 Load하고, IP(Instruction Pointer)를 해당 프로그램의 시작 주솟값으로 설정하여 프로세스를 시작한다. (즉, exec() 계열 함수가 Loader의 역할을 하는 것이다.) * Ker..
Chapter 3. Memory Management ※ Memory는 통상 D-RAM을 의미한다. * Goal of Memory Management - 메모리는 Scarce한 자원이기 때문에 여러 프로세스들이 메모리를 요청하는데, 이 때 Performance는 최대화하고, Overhead는 최소화 하면서 Memory를 Allocation하는 방법을 찾는다. - 프로그래밍에서 효율적인 Abstraction을 제공한다. - 프로그래머는 메모리가 0에서 N까지의 주솟값을 가진 Linear한 구조라 생각하고, 메모리 구조에 대한 상세한 지식 없이 프로그래밍할 수 있다. * Mechanisms for Memory Management - Physical Address Space, Virtual Address Spa..
Properties of Regular Languages 정규 언어의 성질 - 어떤 언어가 Regular Language가 아님을 입증하기 위해서는, 해당 언어가 Regular Language의 성질을 만족하지 않음을 보여야 한다. Closure Properties of Regular Languages (정규 언어의 폐포 성질) Example. 어떤 Regular Language \(L_1, L_2\)가 있으면, \(L_1\)과 \(L_2\)의 합집합 또한 Regular Language이다. 이를 두고, "The Family of Regular Language is Closed under Union."라 표현한다. ("정규 언어군은 합집합에 대해 폐포되어 있다."라 표현한다.) Closure under ..
POSIX Signal Handling POSIX 신호 처리 - UNIX에서 Signal은 Process에 어떤 Event가 발생했음을 알리는 수단이다. - Signal은 Kernel이 User-Process에게 전달할 수도 있고, 다른 User-Process가 전달할 수도 있다. - Signal을 S/W Interrupt라 부르기도 한다. - 대부분의 Signal은 Asynchronous하게 발생되기 때문에, Process는 Signal이 발생한 정확한 시점을 알 수 없다. - Signal들은 발생했을 때의 대처방법인 Disposition(=Action)대로 수행된다. * signal Linux Manual Page (URL) Signal Dispositions (Signal Actions) - 발생한..
Full Adder Modeling 전가산기 모델링 - 세 개의 입력 A, B, Z와 두 개의 출력 Carry(C), Sum(S)을 가진다. - Z는 아래 자릿 수에서의 덧셈의 결과로 파생된 Carry를 의미한다. Truth Table for FA Inputs Outputs Z A B C S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 * Binary Adder - Full Adder (URL) Full Adder - Behavioral Model -- Entity Declaration ENTITY Full_Adder IS PORT (X, Y, Z : IN bit; S, C : OUT bit ); END F..
Half Adder Modeling 반가산기 모델링 - 두 개의 입력 A, B와 두 개의 출력 Carry(C), Sum(S)을 가진다. * Truth Table for Half Adder Inputs Outputs A B S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 * Binary Adder - Half Adder (URL) Half Adder - Behavioral Model -- Entity Declaration ENTITY Half_Adder IS PORT ( A, B : IN bit; Sum, Carry : OUT bit ); END Half_Adder; -- Architecture Body ARCHITECTURE Behavioral_Design of Half_Adder IS ..
