I/O 장치와 CPU는 동시에 작동할 수 있다. I/O 작업은 기본적으로 장치(Device)와 컨트롤러(Controller)의 로컬 버퍼 사이에서 데이터를 이동하는 것을 의미한다.

여기서 CPU는 직접 I/O 장치와 통신하는 대신, 컨트롤러의 버퍼와 메인 메모리 사이에서 데이터를 옮기는 역할을 한다.

각 I/O 장치는 장치 컨트롤러라는 전담 관리자를 가진다. 이 컨트롤러는 자체적인 로컬 버퍼와 특별한 레지스터(register)를 가지고 있어서, I/O 장치와의 통신을 제어한다.

A device driver for every device controller라는 문장의 의미는 다음과 같다.

장치 드라이버(Device Driver)는 해당 장치 컨트롤러의 세부 사항을 알고 있는 소프트웨어이다.

이 드라이버는 운영체제(OS)의 나머지 부분에 균일한 인터페이스(uniform interface)를 제공한다.

예를 들어, open, close, read, write와 같은 표준화된 함수들을 통해 개발자가 복잡한 하드웨어의 작동 방식을 일일이 알지 못해도 쉽게 I/O 작업을 할 수 있게 한다. 즉, OS와 애플리케이션이 장치와 소통하는 통역사 역할을 한다.

I/O 장치에 접근하는 방법

Memory Mapped I/O

원리 : 메모리 공간과 I/O 장치의 주소 공간이 분리되지 않고, I/O 장치가 마치 일반적인 메모리처럼 취급된다.

작동 방식 : CPU는 I/O 장치에 접근할 때 load (읽기)나 store (쓰기)와 같은 일반적인 메모리 명령어(instruction)를 사용한다.

장점 : 별도의 특별한 I/O 명령어가 필요 없기 때문에 프로그래밍이 간편한다.

현황 : 강의 자료에 따르면 이 방식이 더 일반적으로 사용된다.

Special I/O

원리 : CPU가 I/O 장치를 위한 별도의 독립된 버스(separate bus)를 가진다.

작동 방식 : I/O 장치에 접근하기 위해서는 IN 또는 OUT과 같이 I/O 전용으로 설계된 특별한 명령어(special instructions)가 필요하다.

장점: 메모리 주소와 I/O 주소 공간이 완전히 분리되어 있어, 메모리 보호 기능과 관련하여 더 명확한 구분이 가능하다.

Polling I/O

폴링은 programmed I/O라고도 불리며, 모든 I/O 작업이 CPU의 직접적인 제어 아래 이루어지는 방식이다.

작동 방식 : CPU가 I/O 장치의 상태를 계속해서(continuously) 확인하면서 작업이 완료되었는지 묻는 방법이다. 마치 "끝났니? 끝났니?" 하고 끊임없이 물어보는 것과 같다.

비효율성 : 이 방식의 가장 큰 문제는 CPU 낭비이다. CPU는 I/O 장치의 작업이 끝날 때까지 바쁜 대기(busy waiting) 상태에 빠진다. 이 때문에 CPU는 다른 중요한 작업(다른 프로그램 실행 등)을 할 수 없게 되어 전체 시스템의 효율성이 크게 떨어진다.

폴링에서 인터럽트로의 전환 이러한 폴링의 문제를 해결하기 위해 인터럽트(Interrupt) 방식이 도입되었다.

작동 방식 : CPU가 I/O 작업을 시작하라고 지시한 뒤, 작업이 끝날 때까지 기다리지 않고 다른 일을 합니다. I/O 장치가 작업을 완료하면, 직접 CPU에게 "저 끝났습니다!"라고 신호를 보내는데, 이 신호가 바로 인터럽트이다.

효율성 : CPU는 인터럽트 신호가 올 때만 하던 작업을 잠시 멈추고 I/O 장치에게 관심을 기울이면 됩니다. 이 덕분에 CPU는 I/O 작업을 기다리느라 시간을 낭비하지 않고 다른 유용한 작업을 수행할 수 있게 됩니다.

비유

폴링 : 요리사가 냄비 앞에서 물이 끓었는지 계속 뚜껑을 열어보는 것. (CPU 낭비)

인터럽트 : 요리사가 냄비에 타이머를 맞춰두고 다른 요리를 하다가, 타이머가 울리면 그때 가서 냄비를 확인하는 것. (CPU 효율성 증대)

Polling의 다른 문제 원인 : I/O 장치 컨트롤러의 로컬 버퍼는 크기가 제한되어 있다. CPU가 너무 느리게 버퍼의 데이터를 가져가면, 새로운 데이터가 계속 들어와 기존의 데이터를 덮어쓰거나 유실될 수 있다.

결과 : 이로 인해 데이터 유실이라는 심각한 문제가 발생할 수 있으며, 이는 폴링 방식이 고속 I/O 장치에 부적합한 이유 중 하나이다.

인터럽트의 기본 원리

작동 방식 : CPU와 I/O 장치 사이에 전용 신호선(line)이 있다. I/O 장치가 작업을 완료하면 이 신호선을 통해 CPU에게 신호를 보낸다. 이 신호는 CPU에게 어떤 사건(event)이 발생했음을 알려주는 역할을 한다.

결과 : 이로써 CPU는 더 이상 I/O 장치를 계속 확인하지 않고도, 필요할 때만 I/O 작업에 응답할 수 있게 된다.

Context : CPU가 현재 실행 중인 작업(프로세스 또는 스레드)에 대한 모든 정보를 담고 있는 상태 정보 : CPU 레지스터의 값, 메모리 상태, 파일 정보

Interrupt와 Context의 관계

인터럽트가 발생하면 CPU는 하던 작업을 잠시 멈추고 인터럽트 핸들러를 실행해야 한다. 이때 CPU가 기존에 하던 작업을 그대로 이어가려면, 인터럽트가 발생하기 직전의 컨텍스트를 안전하게 저장해야 한다.

저장 (Save Context) : CPU는 인터럽트가 발생하면 현재 실행 중이던 작업의 컨텍스트를 스택이나 특정 메모리 영역에 저장한다. 이 과정은 인터럽트 핸들러가 실행되는 동안 원래 작업의 상태가 손상되지 않도록 보호하는 역할을 한다.

복원 (Restore Context) : 인터럽트 핸들러가 자신의 작업을 모두 마치면, 저장해 두었던 컨텍스트를 다시 불러와 CPU 레지스터에 복원한다. 이렇게 하면 CPU는 인터럽트가 발생하기 전의 작업을 중단 없이 그대로 이어서 실행할 수 있다.

결론적으로, 컨텍스트는 CPU가 여러 작업을 오가며 효율적으로 멀티태스킹을 할 수 있게 해주는 핵심 정보이다.

인터럽트 처리 절차

1. 컨텍스트 저장 : CPU가 현재 실행 중인 작업의 상태(context)를 보존한다.

2. 유형 결정 : 인터럽트의 유형을 파악합니다. 주로 벡터 인터럽트 시스템을 사용한다.

3. 핸들러 실행 : 인터럽트를 처리하기 위한 ISR(Interrupt Service Routine) 또는 인터럽트 핸들러로 제어권을 넘긴다.

인터럽트 타임라인

인터럽트가 발생하면 CPU는 I/O 작업 완료를 기다리는 대신 다른 작업을 처리하고, I/O 장치가 작업(예: 데이터 전송)을 완료하면 CPU에 인터럽트 신호를 보낸다. 이 신호를 받은 CPU는 하던 작업을 잠시 멈추고 인터럽트 처리에 돌입합니다. 이로써 CPU와 I/O 장치가 동시에 실행(concurrent execution)될 수 있습니다.

Direct Memory Access (DMA)

문제점 : 인터럽트 방식은 I/O 작업이 완료될 때마다 CPU가 개입해야 하므로, 특히 디스크 I/O처럼 대량의 데이터를 이동할 때는 오버헤드가 매우 크다. 즉, 한 바이트(byte)마다 인터럽트가 발생하여 비효율적이다.

해결책 : 이러한 높은 오버헤드를 해결하기 위해 DMA(Direct Memory Access) 방식이 도입되었습니다. DMA는 CPU의 개입 없이 I/O 장치와 메인 메모리 사이에서 직접 데이터를 전송합니다.

작동 방식 : CPU는 DMA 컨트롤러에게 전송할 데이터의 시작 주소, 크기 등 필요한 정보를 알려주고 작업을 시작하도록 프로그래밍합니다. 그 후 CPU는 다른 작업을 계속 수행합니다. DMA 컨트롤러는 I/O 장치로부터 데이터를 블록(block) 단위로 직접 메모리로 전송합니다.

결과 : 전체 데이터 블록 전송이 완료되었을 때 단 한 번의 인터럽트만 발생시키므로, CPU의 낭비 시간을 최소화할 수 있습니다. 이는 고속 I/O 장치에 매우 유용합니다.

현대 인터럽트 처리 (Modern Interrupt Handling)

현대 운영체제는 단순히 인터럽트를 처리하는 것을 넘어, 효율성과 안정성을 위해 더욱 정교한 메커니즘을 요구한다.

다중 레벨 인터럽트 : 중요도에 따라 높고 낮은 우선순위를 구별하는 다중 레벨 인터럽트를 사용한다. 이를 통해 우선순위가 높은 인터럽트가 낮은 우선순위의 처리를 선점(pre-empt)할 수 있다.

PIC(Peripheral Interrupt Controller): 인터럽트 관리를 위해 특별화된 PIC를 사용한다.

두 가지 인터럽트 라인

1. 마스킹 가능 인터럽트: 중요한 처리 전에 일시적으로 비활성화할 수 있다.

2. 마스킹 불가능 인터럽트: 심각한 오류(예: 복구 불가능한 메모리 오류)를 알리기 때문에 끌 수 없다.

인터럽트 벡터(Interrupt Vector)

인터럽트 벡터는 인터럽트가 발생했을 때 적절한 인터럽트 핸들러를 찾기 위한 메커니즘이다.

구조 : 인터럽트 신호에는 해당 인터럽트 벡터를 가리키는 주소(address)가 포함되어 있다.

역할 : 이 인터럽트 벡터 테이블은 각기 다른 인터럽트 핸들러의 주소를 담고 있다. 따라서 OS는 인터럽트 번호를 이용해 인터럽트 벡터 테이블에서 해당 핸들러의 주소를 찾아 실행하게 된다.

체이닝(Chaining): 만약 인터럽트 벡터의 항목 수보다 장치 수가 더 많을 경우, 하나의 주소에 여러 인터럽트 핸들러의 리스트를 연결하는 체이닝(chaining) 방식을 사용한다.

Traps and Exceptions

작동방식

1. 실행중인 프로세스를 정지
2. Context 저장
3. 핸들러 호출 : 컨텍스트 저장이 완료된 후에야 CPU는 해당 문제 처리를 위한 전용 핸들러(Handler)를 호출하여 실행.
4. 상태 복원 : 핸들러의 작업이 끝나면, 저장해 두었던 컨텍스트를 다시 불러와 CPU 레지스터에 복원하고, 중단되었던 프로세스를 이어서 실행.

2 단계는 인터럽트 발생 시 시스템의 안정성과 연속성을 보장하는 핵심적인 단계이다. 이러한 과정이 없다면, 인터럽트가 발생할 때마다 기존 작업이 손상되어 시스템이 멈추거나 오작동할 수 있다.

Protection의 필요성

보호 메커니즘이 필요한 주된 이유는 시스템의 올바른 작동을 보장하기 위해. 멀티태스킹 환경에서 여러 프로그램이 동시에 실행되면서 다양한 문제가 발생할 수 있다.

애플리케이션 프로그램 문제: 악의적이지 않더라도, 버그가 있는 프로그램이 다른 메모리 영역을 덮어쓰거나(scribbling into memory) 무한 루프에 빠져 CPU를 독점할 수 있다.

사용자 간 간섭: 다른 사용자가 무분별하게(Gluttonous) 자원을 사용하거나 악의적(Evil) 으로 시스템에 해를 가할 수도 있다.

Protecting Memory

주된 이유

1. 다른 프로그램으로부터 프로그램 보호: 한 프로그램이 다른 프로그램의 데이터를 함부로 접근하지 못하게 함.

2. 사용자 프로그램으로부터 OS 보호: 사용자 프로그램이 OS 영역을 침범하지 못하게 막음.

가장 단순한 메모리 보호 방법은 Base and Limit Registers를 사용하는 것.

Base Register (베이스 레지스터): 프로그램이 접근할 수 있는 메모리 영역의 시작 주소를 저장.

Limit Register (리미트 레지스터): 프로그램이 접근할 수 있는 메모리 영역의 크기(길이)를 저장.

이 두 레지스터는 프로그램이 실행되기 전에 운영체제(OS)가 값을 설정한다. 프로그램이 실행되는 동안 CPU가 메모리에 접근할 때마다, 하드웨어는 해당 주소가 베이스 레지스터 값부터 베이스 레지스터 + 리미트 레지스터 값 사이에 있는지 확인한다. 만약 유효한 범위를 벗어나면 하드웨어는 인터럽트를 발생시켜 해당 프로그램을 강제로 종료한다. 이를 통해 다른 프로그램이나 OS의 메모리 영역을 안전하게 보호할 수 있다.

CPU Protection

"협력적 접근(Cooperative approach)"은 프로그램이 시스템 콜(System Call)을 자발적으로 호출하여 제어권을 OS에 넘겨주는 방식이다. 이는 프로그램이 OS의 도움을 받기 위해 스스로 요청하는 경우이다.

하지만, 만약 프로그램이 악의적이거나 버그로 인해 시스템 콜을 호출하지 않고 무한 루프(infinite loop)에 빠지면 어떻게 될까? 이 경우 CPU 제어권을 되찾을 수 있는 다른 방법이 필요하다.

Timer Hardware

타이머(Timer)의 역할 *타이머는 사용자 프로그램의 *무한 루프(infinite loops)나 CPU 독점(CPU monopoly)을 방지하기 위해 사용된다. 이는 시스템의 안정성과 공정성을 보장하는 핵심 메커니즘이다.

비협력적 접근(Non-cooperative approach) : 타이머는 프로그램이 자발적으로 제어권을 반환하지 않을 때, OS가 강제로 제어권을 회수하는 방식.

타이머 작동 방식

1. 타이머 설정 : OS가 CPU 제어권을 사용자 프로그램에 넘기기 전에, 인터럽트가 발생할 시간을 타이머에 미리 설정. 이 시간 단위는 일반적으로 퀀텀(quantum).

2. 프로그램 실행 : 설정된 시간이 지나면, 타이머는 자동으로 타이머 인터럽트(timer interrupt)를 발생시킨다.

3. 제어권 회수 : 이 인터럽트를 통해 OS는 CPU의 제어권을 다시 가져온다.

이 과정을 통해 버그가 있거나 악의적인 프로그램이 무한 루프에 빠져도, OS는 반드시 CPU 제어권을 되찾을 수 있습니다.

특권 명령어(Privileged Instruction) 타이머 값을 설정하는 작업은 매우 중요하므로, 특권 명령어(privileged instruction)로 지정됩니다. 이는 오직 OS만이 실행할 수 있는 명령어이며, 사용자 프로그램이 마음대로 타이머를 조작하여 CPU를 독점하는 것을 방지합니다.

특권 명령어 사용 예시 하드웨어 자원에 대한 직접 접근 : 디스크나 프린터와 같은 I/O 장치에 직접 접근하는 명령어.

메모리 관리 상태 조작 : 페이지 테이블 포인터(page table pointers)나 TLB(translation look-aside buffer) 로딩 등 메모리 관리와 관련된 상태를 변경하는 명령어.

시스템 레지스터 접근 : 제어 레지스터(Control registers)나 인터럽트 핸들러 테이블(interrupt handler table)의 위치와 같은 시스템 레지스터에 접근하는 명령어.

CPU 모드 비트 설정 : 듀얼 모드(사용자/커널)를 구분하는 모드 비트를 설정하는 명령어.

시스템 정지 : 컴퓨터를 정지(halt)시키는 명령어.

타이머 설정 : 타이머 값을 설정하는 명령어 는 사용자 프로그램의 무한 루프를 방지하기 위해 오직 OS만 사용 가능하도록 제한.

CPU 작동 모드 (CPU Modes of Operation)

CPU 작동 모드는 운영체제가 자신과 다른 시스템 구성 요소를 보호하기 위한 메커니즘.

사용자 모드 (User mode): 일반적인 사용자 프로그램이 실행되는 모드. 이 모드에서는 특권 명령어 실행이 제한.

커널 모드 (Kernel mode): 운영체제가 실행되는 모드. 이 모드에서는 모든 명령어와 하드웨어 자원에 접근할 수 있다.

CPU는 하드웨어에 의해 제공되는 모드 비트(mode bit)를 통해 현재 실행 중인 모드를 식별한다. 모드 비트는 커널 모드일 때 0, 사용자 모드일 때 1과 같이 설정된다.

모드 전환

사용자 → 커널 : 사용자 프로그램이 시스템 콜을 호출하면, 트랩(trap)을 통해 모드 비트가 변경되어 커널 모드로 전환.

커널 → 사용자 : 시스템 콜 처리가 끝나면 RTI (return from interrupt) 명령어를 사용하여 모드 비트가 다시 변경되어 사용자 모드로 돌아옴.

사용자 프로그램은 원칙적으로 특권 명령어를 직접 실행할 수 없기 때문에, 이러한 작업이 필요할 때는 시스템 콜(System Call)을 통해 운영체제에게 대신 수행해 달라고 요청해야 한다.

두 아키텍처 모두 보호된 레지스터의 상태 비트(status bit)를 통해 현재의 모드를 설정하고 식별합니다. 이 모드 비트는 시스템 콜을 통해 커널 모드로 전환되고, RTI(Return from Interrupt) 명령어를 사용하여 다시 사용자 모드로 돌아옵니다.

Crossing Protection Boundary

사용자 프로그램은 시스템의 중요 자원을 보호하기 위해 직접 하드웨어에 접근할 수 없다. 따라서 OS가 제공하는 특권 작업을 수행하려면, 시스템 콜(System Call)이라는 특별한 메커니즘을 통해 OS에 요청해야 한다.

1. 사용자 모드에서 요청 : 사용자가 작성한 프로그램(user process)은 평소와 같이 사용자 모드에서 실행된다. 이 프로그램이 OS의 도움이 필요한 작업(예: 파일 열기)을 만나면, 라이브러리에 있는 시스템 콜 API를 호출한다.

2. 트랩(Trap) 발생 : 시스템 콜 API의 마지막 명령어는 trap(소프트웨어 인터럽트)이다. 이 명령어가 실행되면, CPU의 모드 비트(mode bit)가 사용자 모드(1)에서 커널 모드(0)로 전환된다.

3. 커널 모드에서 실행 : 이제 제어권이 OS의 커널로 넘어가고, 커널은 요청된 시스템 콜을 실행한다. 이 과정에서 커널은 모든 하드웨어와 자원에 대한 완전한 권한을 가진다.

4. 복귀 : 시스템 콜 처리가 끝나면, 커널은 return 명령어를 실행하여 모드 비트를 다시 사용자 모드(1)로 바꾸고 , 원래의 사용자 프로세스에게 제어권을 돌려준다.

System Call

시스템 콜은 사용자 프로그램이 운영체제로부터 서비스를 받기 위해 사용하는 프로그래밍 인터페이스이다.

API와 시스템 콜: 사용자는 API(예: printf())를 호출하고, 이 API는 내부적으로 시스템 콜 구현(예: write())을 호출한다. API는 사용자가 접근하기 쉽도록 높은 수준의 언어로 작성되지만, 실제로는 커널에 존재하는 시스템 콜을 실행하는 것이다.

시스템 보호: OS는 시스템 콜을 통해 시스템을 보호.

1. 불법 요청 거부: 사용자 프로그램이 권한이 없는(illegal) 요청을 하면, OS는 이를 거부하고 에러를 반환하여 시스템의 안정성을 지킨다.

2. 자원 할당: "OS는 특정 자원의 몫을 부과한다"는 말은 OS가 자원을 할당할 때 공정하게 분배한다는 뜻이다. 예를 들어, CPU 시간이나 메모리 같은 자원을 여러 프로그램에 공정하게 나누어 할당하여 한 프로그램이 자원을 독점하지 않도록 한다.

3. 공정성 보장: 여러 프로그램이 동시에 자원을 요청할 때, OS는 공정성(fairness)을 고려하여 순서를 정하고 자원을 공유한다.

보호된 절차 호출: 시스템 콜은 일종의 보호된 프로시저(절차) 호출이다. 시스템 콜 루틴은 OS의 코드 안에 있으며, 실행은 항상 커널 모드에서 이루어진다. 따라서 사용자 모드에서 시스템 콜을 호출할 때 모드가 커널 모드로 바뀌었다가, 시스템 콜 처리가 끝나면 다시 사용자 모드로 돌아온다.

시스템 콜의 접근 방식 "API를 사용하는 프로그램에 의해 가장 접근된다"는 말은, 대부분의 개발자는 시스템 콜을 직접 호출하지 않고, API를 통해 간접적으로 접근한다는 의미이다.

API의 역할: 프로그래밍 라이브러리(C 라이브러리, Java 라이브러리 등)는 개발자가 사용하기 쉬운 API를 제공한다. 이 API들은 내부적으로 해당 작업을 수행하기 위한 시스템 콜을 호출한다.

예시: C 언어에서 파일을 열기 위해 사용하는 fopen() 함수는 API이다. 이 함수를 호출하면, 라이브러리 내부에서는 실제로 파일을 열기 위한 open() 시스템 콜이 호출되어 OS에게 요청이 전달된다.

1. 데이터베이스 기본 용어

데이터(Data): 의미를 가지며 기록될 수 있는 알려진 사실들입니다.

데이터베이스(Database): 서로 관련있는 데이터들의 모임입니다.

DBMS(데이터베이스 관리 시스템): 데이터베이스의 생성과 관리를 담당하는 소프트웨어 패키지입니다.

데이터베이스 시스템(Database System): 데이터베이스와 이를 관리하는 소프트웨어(DBMS), 응용 프로그램을 모두 포함하는 용어입니다.

미니월드(Mini-world): 데이터베이스 구축의 대상이 되는 현실 세계의 일부분을 가리킵니다.

2. 데이터베이스의 구조: 3단계 스키마 아키텍처

데이터베이스는 사용자와 물리적 저장 구조의 분리를 목표로 3단계 스키마 아키텍처를 사용하며, 이를 통해 데이터 독립성을 보장합니다.

외부 스키마(External Schema): 개별 사용자가 보는 데이터베이스의 관점입니다. 사용자마다 관심 있는 데이터의 일부만

뷰(View) 형태로 제공하여 전체 복잡성으로부터 사용자를 보호합니다.

개념 스키마(Conceptual Schema): 조직 전체의 데이터베이스를 통합한 논리적 구조입니다. 데이터베이스에 저장될 모든 데이터, 관계, 제약 조건을 기술하며, 데이터의 물리적 저장 구조와는 독립적입니다.

내부 스키마(Internal Schema): 데이터가 물리적으로 저장되는 방식을 기술합니다. 데이터가 저장되는 파일, 인덱스 등 세부적인 물리적 정보를 포함하며, 하드웨어 및 운영체제에 종속적일 수 있습니다.

3. 데이터 독립성

3단계 스키마 아키텍처는 두 가지 유형의 데이터 독립성을 제공합니다.

논리적 데이터 독립성: 개념 스키마가 변경되어도 외부 스키마(사용자 뷰)는 영향을 받지 않습니다.

물리적 데이터 독립성: 내부 스키마(물리적 저장 구조)가 변경되어도 개념 스키마는 영향을 받지 않습니다.

4. 데이터베이스의 주요 특징

자기 기술성(Self-describing): DBMS는 데이터베이스 자체에 대한 정의(메타데이터)를 데이터 카탈로그에 스스로 저장합니다. 이로 인해 응용 프로그램과 데이터의 연결이 느슨해져, 데이터 구조가 변경되어도 응용 프로그램을 최소한으로 수정하거나 전혀 수정하지 않아도 됩니다. 이는 프로그램-데이터 독립성을 가능하게 합니다.

데이터 추상화: 데이터 모델을 사용하여 저장 구조의 세부 사항을 숨기고 개념적인 뷰만 제공합니다.

데이터 공유 및 다중 사용자 트랜잭션 처리: 여러 사용자가 동시에 데이터를 안전하게 공유할 수 있게 합니다.

트랜잭션(Transaction): 한 번 이상의 데이터베이스 접근을 포함하는 프로그램의 단위 또는 프로세스 수행으로, 원자성과 고립성을 만족해야 합니다.

원자성(Atomicity): 트랜잭션 내의 모든 연산이 하나의 단위로 묶여 부분적 실행이 불가능함을 의미합니다.

고립성(Isolation): DBMS가 다양한 기술(예: 잠금)을 사용해 각 트랜잭션이 마치 독립적으로 실행되는 것처럼 보이게 하는 기능입니다.

동시성 제어(Concurrency Control): 여러 트랜잭션이 동시에 실행되더라도 데이터의 일관성을 유지하는 기능입니다.

복구(Recovery): 시스템 장애 시에도 데이터 손실을 방지하는 기능입니다.

5. DBMS의 장점 및 사용 효과

데이터 중복성 제어: 데이터 중복을 방지하고 데이터 일치성을 보장합니다.

데이터 공유 및 동시 접근 보장: 다수 사용자 간의 데이터 공유와 동시 접근을 보장합니다.

권한 없는 접근 통제: 보안 및 권한 서브시스템을 통해 접근을 통제합니다.

지속성 기억 공간 제공: 프로그램 객체를 위한 영구적인 저장 공간을 제공합니다.

효율적인 질의 처리: 저장 구조 및 탐색 기법을 통해 질의를 효율적으로 처리합니다.

백업과 회복: 백업 및 회복 기능을 제공하여 데이터를 복구합니다.

다양한 사용자 인터페이스 제공: 다양한 인터페이스를 통해 데이터에 접근할 수 있게 합니다.

복잡한 관계 표현: 데이터 간의 복잡한 관계를 표현합니다.

무결성 제약 조건 시행: 데이터의 정확성과 일관성을 유지하기 위한 제약 조건을 강제합니다.

표준화된 데이터 관리: 업무 효율성을 증대시킵니다.

데이터 구조 변경의 유연성: 데이터 구조가 변경되어도 사용자에게 미치는 영향이 거의 없습니다.

응용 프로그램 개발 시간 단축: 응용 프로그램의 많은 부분을 DBMS가 처리해주어 개발 시간을 단축합니다.

최신 정보 제공: 한 사용자의 갱신이 다른 사용자에게 즉시 반영됩니다.

규모의 경제성: 통합된 DB 관리를 통해 비용을 절감합니다.

6. DBMS가 불필요한 경우

높은 초기 투자 비용과 오버헤드: DBMS의 기능(보안, 동시성 제어, 복구)이 필요하지 않은 경우, 오버헤드가 되어 성능에 부정적 영향을 줄 수 있습니다.

단순하고 변경 가능성이 적은 응용: 응용 프로그램이 단순하고 잘 정의되어 있으며, 변경될 가능성이 적을 때.

실시간 데이터 처리 요구사항: DBMS의 오버헤드로 인해 엄격한 실시간 데이터 처리 요구사항을 만족시키기 어려울 수 있습니다.

다중 사용자 접근이 필요하지 않은 경우: 단일 사용자 환경에서는 DBMS의 복잡한 기능이 필요하지 않습니다.

1. H/W : 기본 컴퓨팅 자원을 제공(CPU, 메모리,I/O 장치, ..)

2. OS : 하드웨어의 사용을 조절하고 통합한다. 다양한 어플리케이션 프로그램 사이에서.

3. System & Application Programs : 시스템 자원 안에 있는 s/w은 사용자의 컴퓨팅 문제를 해결하기위해사용된다.(워드 프로세서, 웹 브라우저, 비디오 게임 등..)

4. User : 사람, 기계, 다른 컴퓨터

OS란 무엇인가

Application view

: 프로그램을 실행하기 위한 실행 환경을 제공한다.

: 추상적인 관점 제공한다, 컴퓨터 시스템의 밑에있는 (H/W 캡슐화로 인해)

System view

: 컴퓨터 시스템의 다양한 자원을 관리한다.

: 장치를 바쁘게 유지한다.(효율적 측면)

: Sharing, Protection, Fairness, Efficiency, Concurrency

(resource : CPU, memory, I/O devices, Queues, Energy...)

Implementation view

: Highly-concurrent, event-driven software

핵심은 "Highly-concurrent, event-driven software" 라는 표현에 있다. 이는 운영체제가 여러 작업을 동시에 처리하고(highly-concurrent), 외부에서 발생하는 사건(event)에 반응하며 동작하는(event-driven) 소프트웨어라는 뜻

Event-driven (이벤트 중심):

사용자가 키보드를 누르거나 마우스를 클릭하는 것, 네트워크 패킷이 도착하는 것, 디스크에서 데이터를 읽는 작업이 완료되는 것 등은 모두 이벤트(Event)이다.

운영체제는 이러한 이벤트가 발생했을 때 적절한 처리를 해야 한다.

그림에서는 'Interrupts(인터럽트)'를 통해 하드웨어(Device 1, 2, 3)로부터 발생하는 이벤트를 OS가 감지하는 과정을 보여주고 있다. 하드웨어가 어떤 작업(예: I/O)을 마치면 CPU에 인터럽트를 걸어 OS에 알려준다.

Highly-concurrent (고도의 동시성):

동시성(Concurrency)이란 여러 작업이 동시에 진행되는 것처럼 보이게 만드는 것을 의미한다.

그림에는 'App 1', 'App 2', 'App 3'과 같이 여러 개의 애플리케이션이 실행되고 있다.

애플리케이션은 'System calls(시스템 호출)'이라는 통로를 통해 운영체제에 특정 기능(예: 파일 읽기, 쓰기)을 요청한다.

이때 'trap(트랩)'이라는 메커니즘을 사용해 사용자 모드에서 커널 모드(운영체제가 실행되는 영역)로 전환하여 요청을 처리하게 된다.

운영체제는 이러한 시스템 호출과 인터럽트를 효율적으로 처리함으로써 여러 애플리케이션이 끊김 없이 동시에 실행되는 듯한 환경을 만들어냅니다.

요약 Implementation view는 운영체제가 단순히 자원을 관리하는 것을 넘어, 하드웨어와 애플리케이션 사이의 복잡한 상호작용을 처리하기 위해 인터럽트와 시스템 호출이라는 이벤트 기반 메커니즘을 통해 고도의 동시성을 달성하는 소프트웨어라는 점을 강조한다.

OS의 역사

1. Early Systems (OS 없는 초기 시스템)

특징: 이 시기에는 운영체제가 존재하지 않았습니다. 프로그래머가 메모리 스위치를 사용하여 직접 이진 코드를 입력하고, 모든 작업을 수동으로 처리했습니다. 컴파일러나 유틸리티는 나중에 추가되었습니다.

비효율성: 한 번에 하나의 작업만 실행할 수 있었고, 작업이 완료되면 다음 작업을 수동으로 준비해야 했습니다. 이는 매우 비효율적이었고, 컴퓨터 자원을 낭비하는 원인이 되었습니다.

2. Batch Processing Systems (2세대)

등장 배경: Early Systems의 비효율성을 극복하기 위해 등장했습니다. 여러 작업을 한데 모아(batch) 한 번에 처리하는 방식이 도입되었습니다.

특징: 펀치 카드에 담긴 작업들을 작업자가 카드 리더에 넣어 순차적으로 실행했습니다. 시스템의 성능은 느린 I/O 장치(카드 리더, 프린터)의 속도에 크게 의존했습니다.

한계: 여전히 한 번에 하나의 작업만 실행했기 때문에, CPU가 계산을 하는 동안 I/O 장치가 유휴 상태가 되거나 반대로 I/O 작업 중 CPU가 놀게 되는 비효율성이 있었습니다.

3. Multi-programming Systems

등장 배경: Batch Processing System의 가장 큰 문제점인 낮은 CPU 활용률을 개선하기 위해 등장했습니다.

핵심 원리: 여러 작업을 메인 메모리에 동시에 올려놓고, 하나의 작업이 I/O 작업을 위해 CPU를 기다리는 동안 OS가 다른 작업에 CPU를 할당했습니다. 이로 인해 CPU와 I/O 작업이

겹쳐서(overlap) 진행되는 동시성(concurrency)이 가능해졌습니다.

주요 기능

Spooling: 느린 I/O 장치와 CPU 사이에 디스크 버퍼를 두어, CPU가 I/O 작업을 기다리지 않고 즉시 다음 작업을 처리할 수 있게 하는 기술입니다.

Protection: 메모리에 여러 작업이 동시에 존재하면서 발생할 수 있는 메모리 침범 문제를 해결하기 위해 도입되었습니다. 한 작업이 다른 작업의 메모리 영역에 접근하지 못하도록 보호하는 기능입니다.

결과: CPU 활용률과 시스템 처리량(Throughput)이 크게 향상되었습니다.

4. Time-sharing Systems (3세대)

등장 배경: Multi-programming은 시스템 효율성을 높였지만, 사용자가 직접 상호작용하기 어려운 오프라인(off-line) 방식이었습니다. 사용자에게 빠른 응답성을 제공하기 위해 등장했습니다.

핵심 원리: 여러 사용자가 동시에 컴퓨터에 접속하여 상호작용할 수 있도록 온라인(on-line) 처리를 지원합니다. OS가 각 프로세스(사용자에 의해 생성된 실행 중인 프로그램)에 CPU 시간을 매우 짧게 할당하고 번갈아 가며 실행하는

Time-slice 메커니즘을 사용했습니다.

결과: 사용자는 마치 컴퓨터를 단독으로 사용하는 것처럼 느끼게 되어 응답 시간(response time)이 크게 개선되었습니다. 이는 오늘날의 모든 PC 및 서버 운영체제(Linux, Windows 등)의 기반이 되는 개념입니다.

5. 4세대 운영체제 (1980년대 이후)

원인: LSI(대규모 집적 회로) 및 VLSI(초대규모 집적 회로) 기술의 발전으로 컴퓨터 하드웨어가 크게 발전했습니다. 마이크로프로세서가 더 작고 빨라졌고, 저장 공간도 커지며 속도가 향상되었습니다. 또한, CPU의 작업 일부를 I/O 장치로 분담시키는 기술이 발전했습니다. 이로써 개인용 컴퓨터(PC)의 시대가 열렸습니다.

현대 OS의 특징:

GUI (그래픽 사용자 인터페이스): 사용자가 아이콘과 창을 통해 컴퓨터와 상호작용할 수 있게 되었습니다.

멀티미디어: 오디오 및 비디오와 같은 멀티미디어 콘텐츠를 처리하는 기능이 추가되었습니다.

인터넷 및 웹: 네트워크 기능이 OS의 필수적인 부분이 되었습니다.

네트워크/분산 시스템: 여러 컴퓨터를 네트워크로 연결하여 자원을 공유하고 협업하는 개념이 발전했습니다.

*멀티프로세서 시스템 (SMP) *

특징: 여러 개의 CPU가 하나의 공유 메모리(Shared common memory)를 사용하는 시스템입니다. 오늘날의 듀얼/쿼드 코어 시스템과 같은 멀티코어 시스템이 여기에 속합니다.

장점:

고성능: 여러 CPU가 병렬로 작업을 처리하여 성능이 향상됩니다.

높은 신뢰성: 일부 CPU가 고장 나도 전체 시스템은 작동을 계속할 수 있습니다.

어려움: 각 CPU가 로컬 캐시를 가지고 있어 메모리 접근 충돌을 줄이지만 , 캐시 불일치(cache inconsistency) 문제가 발생할 수 있습니다. 이를 해결하기 위한 하드웨어 캐시 일관성 프로토콜이 필요합니다. 소프트웨어는 단일 CPU 시스템과 동일하지만 하드웨어 구현이 어렵습니다.

*분산 시스템 (클러스터 시스템) *

특징: 네트워크로 연결된 여러 컴퓨터가 협력하여 단일 시스템처럼 작동하는 시스템입니다. 각 노드는 자체 로컬 메모리를 가집니다.

목표:

자원 공유: 원격 자원을 사용할 수 있습니다.

병렬 컴퓨팅: 여러 컴퓨터에서 동시에 프로세스가 실행됩니다.

높은 신뢰성: 일부 컴퓨터가 고장 나도 시스템 전체가 멈추지 않습니다.

어려움: 하드웨어는 기존의 개별 컴퓨터를 그대로 사용하기 때문에 상대적으로 쉽습니다. 하지만, 사용자에게 원격과 로컬을 구분 짓지 않고 마치 하나의 시스템처럼 동작하는 것처럼 보이게 하려면 이를 지원하는 운영체제(OS)와 미들웨어와 같은 소프트웨어가 매우 중요하고 복잡해집니다. 클라우드 서버나 분산 파일 시스템(NFS)이 분산 시스템의 예입니다.

*클라우드 컴퓨팅 *

특징: 분산 서버, 하이퍼바이저, 가상 머신(Virtual Machines, VM)으로 구성됩니다. 하이퍼바이저는 가상 머신을 관리하는 소프트웨어입니다.

서비스 유형:

SaaS (Software as a Service)

IaaS (Infrastructure as a Service)

PaaS (Platform as a Service)

DaaS (Desktop as a Service)

*임베디드 시스템 *

특징: 특정 목적을 위해 설계된 하드웨어에 탑재되는 특수 목적의 소프트웨어 시스템입니다. 스마트폰, 가전제품, 자동차, 의료 기기 등이 여기에 속합니다.

고려사항:

모바일 환경: 무선 통신 및 배터리 전원 관리가 중요합니다.

실시간 시스템: 안전 및 임무 수행에 중요한 경우(예: 무기 시스템, 의료 기기), 실시간 처리가 필수적입니다.

비용 민감성: 가격 경쟁력이 중요합니다.

가혹 환경: HDD보다 충격에 강한 NVRAM(NAND flash)을 주로 사용합니다.

OS: VxWorks, WinCE, QNX 등 다양한 임베디드 OS가 사용됩니다. 모바일 기기에는 안드로이드, iOS, WebOS 등이 사용됩니다.

핵심 키워드: 임베디드 시스템은 유비쿼터스 컴퓨팅, 사물 인터넷(IoT) 등과 밀접하게 관련되어 있습니다.

문자열을 입력받고, 이를 대문자 혹은 소문자로 전체 바꿔서 for문으로 각 알파벳의 개수를 알아내어 구한 문자를 대문자로 출력한다.

s = input().upper()
s_list = list(set(s))
cnt = []
for i in s_list:
    count = s.count(i)
    cnt.append(count)
if cnt.count(max(cnt)) >= 2:
    print("?")
else:
    print(s_list[cnt.index(max(cnt))])

입력받은 문자열을 리스트 형태로 다시 만들고, 단어별 횟수를 세는 리스트를 만들어 문자마다 횟수를 구한다. 조건문으로 ? 또는 문자가 나오도록 하여 출력한다.

이 문제를 보고, 구하고자 하는 수는 5개의 자연수 중에서 3개를 랜덤으로 뽑아서 곱하면 될것이라 생각하고 다음 코드를 썼다.

import random

m_list = list(map(int, input().split()))

rand_sample = random.sample(m_list,3)

result = 1
#print(rand_sample)
for i in range(3):
    result *= rand_sample[i]

print(result)

하지만 나의 코드가 틀린 이유를 어렵지 않게 찾아낼 수 있었다.

1. 세 개의 자연수를 골라 이것을 곱하여 배수를 찾았으나 이것이 가장 작은 자연수임을 확신할 수 없다는 것.
2. 랜덤으로 뽑은 3개의 수의 최소공배수를 구하는 문제가 아니라, 5개의 수 중에서 3개 이상이 나누어떨어지는 가장 작은 자연수를 찾는 문제라는 것.

따라서 random.sample을 쓰면 안되고 전체 리스트를 하나씩 매번 검사해야한다. while문을 써서 안에서 숫자의 개수가 3개가 되면 break하여 탈출하도록한다.

import random

m_list = list(map(int, input().split()))

result = 1

while True:
    count = 0
    for i in range(len(m_list)):
        if (result % m_list[i] == 0):
            count += 1
    if count >= 3:
        break
    result += 1

print(result)

✅ 컴퓨터 시스템의 구성 요소 컴퓨터 시스템은 네 가지 주요 구성 요소로 나뉜다:

하드웨어 (Hardware):

CPU, 메모리, I/O 장치 등으로 구성

계산과 처리를 위한 기본 자원을 제공

운영체제 (Operating System):

응용 프로그램들이 하드웨어를 사용할 수 있도록 제어 및 조정

응용 프로그램과 하드웨어 사이의 중개자 역할 수행

응용 프로그램 (Application Programs):

워드 프로세서, 스프레드시트, 컴파일러 등

사용자 작업을 처리하며, 자원을 어떻게 사용할지 결정

사용자 (Users):

시스템과 상호작용하는 개인 또는 그룹

✅ 운영체제의 역할 컴퓨터 자원을 적절하게 사용할 수 있는 실행 환경을 제공

사용자와 시스템 자원 사이에서 인터페이스를 제공

시스템 자원을 효율적이고 공정하게 배분하는 Resource Allocator

입출력 장치 제어 등 시스템의 동작을 관리하는 제어 프로그램 (Control Program)

✅ 운영체제에 대한 관점 사용자 관점

개인용 컴퓨터 (PC):

사용자 중심으로 설계되어 자원을 독점

사용의 편의성이 가장 중요한 목표

자원 효율성은 크게 고려하지 않음

다중 사용자 시스템 (터미널 기반):

여러 사용자가 동일한 시스템을 공유

CPU 시간, 메모리 등을 효율적으로 분배해야 함

자원 이용의 극대화가 설계의 핵심

워크스테이션 + 서버 환경:

각 사용자가 전용 자원을 가지되, 네트워크나 프린터 등 공유 자원 존재

사용의 용이성과 자원 효율성의 균형을 고려한 설계

시스템 관점

리소스 관리자 (Resource Allocator)로서 시스템 자원의 효율적 배분을 담당

제어 프로그램으로서 하드웨어 장치의 동작을 감독하고 제어

✅ 운영체제의 정의 하나의 명확한 정의는 없음

컴퓨터 시스템을 구성하는 과정에서 발생하는 문제들을 해결하기 위한 방법으로 존재

본질적으로는 시스템에서 항상 동작하는 핵심 소프트웨어인 커널(Kernel) 이 운영체제의 핵심

📘 1.2 컴퓨터 시스템의 구성 (Computer-System Organization)

✅ 1. 컴퓨터 시스템의 연산 (Computer-System Operation) 현대의 범용 컴퓨터 시스템은 공통 버스(shared bus)를 통해 연결된:

여러 장치 제어기 (Device Controller): 예: 오디오, 비디오 장치

하나 이상의 CPU

그리고 공유 메모리(shared memory) 접근을 제공

🔹 부팅 과정 부트스트랩(Bootstrap) 프로그램:

컴퓨터가 켜질 때 처음 실행되는 프로그램

보통 ROM 또는 EEPROM에 저장되어 있음 (이런 저장 장치는 펌웨어라 불림)

시스템 초기화 (CPU 레지스터, 메모리, I/O 장치 상태 등)

운영체제의 커널(kernel) 을 찾아 메모리에 적재하고 실행 시작

UNIX 시스템에서는:

부팅 후 가장 먼저 실행되는 시스템 프로세스는 init

init 이후 시스템은 완전히 부팅된 상태가 되며, 이벤트(event)를 기다리게 됨

🔹 인터럽트 (Interrupt) 사건 발생 → 하드웨어 또는 소프트웨어가 인터럽트를 통해 CPU에 알림

하드웨어 인터럽트: I/O 장치가 System Bus를 통해 발생시킴

소프트웨어 인터럽트: System Call을 통해 발생

인터럽트 처리 과정:

CPU가 현재 작업을 중단하고, 인터럽트 벡터에 정의된 고정된 주소로 이동

해당 위치에서 인터럽트 서비스 루틴(ISR) 실행

인터럽트 전에 수행 중이던 명령의 주소와 상태를 저장

ISR 종료 후, 저장된 주소를 Program Counter에 복원하고 작업 재개

✅ 2. 저장 장치 구조 (Storage Structure) CPU는 메모리에서만 명령어를 가져올 수 있음 → 프로그램은 반드시 메모리에 있어야 함

🔹 메모리 종류 주 메모리 (RAM): 읽기/쓰기 가능, 휘발성

ROM/EEPROM: 읽기 전용 또는 제한된 쓰기 가능, 비휘발성 (예: Bootstrap Program 저장)

🔹 메모리 주소 및 명령 모든 메모리는 바이트 단위 배열 구조

각 바이트는 고유 주소를 가짐

CPU와 메모리 간 상호작용은 주로 Load/Store 명령어를 통해 수행:

Load: 메모리 → 레지스터

Store: 레지스터 → 메모리

🔹 주 메모리 한계 및 보조 저장 장치 주 메모리는:

크기가 작음 (모든 프로그램/데이터 저장 불가)

휘발성 (전원 차단 시 데이터 손실)

→ 이를 보완하기 위해 보조 저장 장치(Secondary Storage) 사용

대표 예시: 하드 디스크

요구사항: 대량 데이터의 영구적 저장

🔹 기타 저장 장치 캐시 메모리, SSD, CD-ROM, 자기 테이프 등

각 장치 간의 차이: 속도, 가격, 용량, 휘발성 여부

✅ 3. 입출력 구조 (I/O Structure) 🔹 운영체제와 입출력 장치의 다양성과 시스템 성능에 미치는 영향이 크기 때문에, 운영체제는 입출력 관리 코드에 상당한 비중을 둠

디바이스 드라이버(device driver)를 통해 장치와 OS 간의 상호작용 수행

🔹 인터럽트 기반 I/O 소량 데이터 전송에는 적합하지만, 디스크 I/O와 같은 대량 전송에는 CPU Overhead가 큼

🔹 DMA (Direct Memory Access) CPU의 개입 없이, 디바이스 ↔ 메모리 간 블록 단위 전송 수행

CPU는 블록 전송이 완료된 후에만 인터럽트를 받음

이 방식은 고속, 대량 데이터 전송 시 성능 향상에 유리

📘 1.3 컴퓨터 시스템 구조 (Computer-System Architecture) ✅ 1. 단일 처리기 시스템 (Single-Processor System) 하나의 주 CPU만 사용하여 범용 명령어(instruction)를 수행

보통 시스템에는 CPU 외에도 여러 개의 특수 목적 전용 처리기가 함께 존재

예: 디스크 제어기, 키보드 제어기, 그래픽 제어기 등

또는 데이터 전송을 위한 입출력 처리기 (I/O processor) 형태로 존재

✅ 2. 다중 처리기 시스템 (Multiprocessor System) 하나 이상의 CPU(또는 코어)를 가지며, 보통 버스, 메모리, I/O 장치 등을 공유

장점 3가지:

Throughput 향상 (처리량 증가) → 더 많은 작업을 동시에 수행할 수 있음 → N개의 CPU → N배 성능은 아니며, Overhead 및 자원 경쟁 발생 가능

Economy of Scale (규모의 경제) → 여러 CPU가 하드웨어 자원(메모리, 디스크 등)을 공유하므로 비용 절감

Increased Reliability (신뢰성 향상) → 일부 CPU가 고장 나도 전체 시스템은 계속 작동 가능 →

Graceful Degradation: 속도만 느려지며 서비스 유지

Fault Tolerant: 고장에도 시스템이 완전히 문제 없이 동작 가능

✅ 3. 다중 처리기 시스템의 구조적 유형 🔹 1) 대칭형(Symmetric) Multiprocessing - SMP 모든 CPU가 대등한 관계

각 CPU는 자신의 레지스터와 캐시를 가지고 있고, 메모리는 공유

🔹 2) 비대칭형(Asymmetric) Multiprocessing 하나의 CPU가 주 제어 역할, 나머지 CPU는 보조 역할 수행

주로 초기 설계 방식에서 사용됨

✅ 4. 메모리 접근 모델 (Memory Access Models) 모델 설명 UMA (Uniform Memory Access) 모든 CPU가 동일한 시간에 메모리에 접근 가능 NUMA (Non-Uniform Memory Access) 일부 메모리는 CPU에 가깝거나 멀어, 접근 시간이 달라짐

NUMA는 스케일 확장에 유리하지만, 성능 튜닝이 필요

✅ 5. 멀티코어 시스템 (Multicore System) 하나의 칩(SoC) 안에 여러 개의 CPU 코어를 포함

칩 내부 통신은 칩 간 통신보다 훨씬 빠름 → 효율성 증가

✔️ 모든 멀티코어 시스템은 다중처리기 시스템이지만, 모든 다중처리기 시스템이 멀티코어는 아님

✅ 6. 클러스터형 시스템 (Clustered Systems) 여러 대의 독립적인 컴퓨터 시스템(노드)를 네트워크로 연결해 하나의 시스템처럼 동작

노드들은 느슨하게 결합(Loosely Coupled)

각 노드는 단일 처리기 시스템 또는 멀티코어 시스템일 수 있음

🔹 클러스터의 목적: 고가용성(High Availability) 시스템 일부가 고장 나도 전체 서비스는 유지

🔹 클러스터의 구성 방식: 구성 방식 설명 비대칭형 클러스터링 한 노드는 Hot-Standby 상태로 대기 → 다른 노드가 고장 나면 takeover 대칭형 클러스터링 모든 노드가 동시에 작업을 수행하고 서로를 감시 → 리소스 효율성 높음

📘 1.4 운영체제 구조 (Operating-System Structure) ✅ 1. 다중 프로그래밍 (Multiprogramming) 목적: CPU 이용률(Utilization) 극대화 → 단일 사용자는 CPU나 I/O 장치를 항상 100% 활용할 수 없음 → CPU가 항상 할 일을 가지도록 여러 작업을 메모리에 올려두고 관리

🔹 기본 아이디어 여러 작업(Job)을 메모리에 적재 (작업 풀은 디스크에 존재)

운영체제가 메모리에 있는 작업 중 하나를 선택하여 실행

실행 중 작업이 I/O 대기 상태가 되면 → 다른 준비 상태(ready)의 작업으로 전환

🔹 특징 CPU와 I/O 장치를 동시에 최대한 활용

단일 사용자 환경보다 자원 활용 효율이 높음

✅ 2. 멀티태스킹 (Multitasking, 시분할) 정의: 다중 프로그래밍의 논리적 확장

CPU가 매우 짧은 시간 간격으로 여러 작업을 번갈아 수행

각 사용자나 작업이 동시에 실행되는 것처럼 보이도록 함

🔹 필요 요소 CPU 스케줄링: 실행 준비 상태(ready queue)의 작업 중 누가 CPU를 쓸지 결정

다중 프로그래밍: 여러 작업을 메모리에 유지

✅ 3. 스케줄링 (Scheduling) 장기 스케줄링: 어떤 작업을 메모리로 불러올지 결정

단기 스케줄링(CPU Scheduling): CPU를 다음에 누가 쓸지 결정

✅ 4. 메모리 관리 기법 🔹 1) 스와핑 (Swapping) 메모리 공간 확보를 위해 프로세스 전체를 메모리 ↔ 디스크 간 교체

필요 시 프로세스를 다시 불러와 실행 (swap-in)

🔹 2) 가상 메모리 (Virtual Memory) 프로그램의 일부만 메모리에 올려도 실행 가능

장점:

프로그램 크기가 물리 메모리보다 커도 실행 가능

주 메모리를 크고 균등한 주소 공간으로 추상화

논리 메모리(logical memory)와 물리 메모리(physical memory)를 분리

1.5 운영체제 연산 (Operating System Operations)

1. Interrupt-driven 동작 현대 운영체제는 interrupt-driven 방식으로 동작.

실행할 프로세스, I/O 서비스, 사용자 요청이 없으면 대기 상태에 들어감.

Trap (Exception)

소프트웨어가 생성하는 인터럽트.

발생 원인:

프로그램 오류 (예: 0으로 나누기, 잘못된 메모리 접근 등)

사용자 프로그램의 운영체제 서비스 요청 (시스템 콜)

2. 이중 연산 모드 (Dual-mode Operation) 운영체제의 안정성과 보안을 위해 운영체제 코드와 사용자 코드 실행을 구분.

모드 비트 (Mode bit): 하드웨어가 현재 모드를 식별.

모드 구분

사용자 모드 (User Mode)

사용자 애플리케이션 실행 시.

커널 모드 (Kernel Mode)

운영체제 서비스 실행 시.

모드 전환

사용자 애플리케이션이 OS 서비스를 요청 → 시스템 콜 발생 → 커널 모드로 전환.

Trap 또는 하드웨어 인터럽트 발생 시도 커널 모드로 전환.

부팅 과정

시스템 부팅 시 커널 모드에서 시작 → OS 로드 후 사용자 모드로 전환.

특권 명령 (Privileged Instructions)

커널 모드에서만 실행 가능.

잘못된 사용자 명령으로부터 운영체제와 다른 사용자 보호.

3. 타이머 (Timer) 목적: 운영체제가 CPU 제어권(Control)을 유지하도록 보장.

필요성:

사용자 프로그램이 무한 루프에 빠지는 상황 방지.

서비스 호출 실패로 OS 제어 불능 상태 방지.

동작 방식:

지정된 시간 이후 인터럽트 발생하도록 설정.

고정 시간 간격 또는 가변 타이머 사용 가능.

가변 타이머: 클럭이 tick할 때마다 카운터 감소 → 0이 되면 인터럽트 발생.

CPU 스케줄링이나 시분할 시스템에서 시간 제한을 구현하는 핵심 장치.

✅ 1. Variable Initialization (변수 초기화)

📌 개념 변수 초기화는 C에서 int a = 1;처럼 새로운 변수에 값을 할당하는 구조입니다. Racket에서도 같은 의미로 (let ([a 1]) ...) 형태를 사용합니다.

📌 AST 표현 racket

(letC 'a (numC 10)     ; a = 10
  (plusC (idC 'a) (numC 5))) ; a + 5

해석: 'a를 10으로 바인딩하고, 그 환경에서 a + 5를 수행하라.

📌 추상 구문 트리 (AST)

          letC
         /  |   \
      'a  numC  plusC
           10    /  \
               idC  numC
                'a   5

✅ 2. Desugaring (설탕 제거: letC를 appC로 변환)

📌 아이디어 letC는 특별한 구조가 아니며, 람다(lamC)와 함수 호출(appC)을 이용해서 똑같이 표현할 수 있습니다.

📌 변환 예시 (desugaring) racket

(letC 'a (numC 10) 
  (plusC (idC 'a) (numC 5)))

⇨ 아래와 같이 변환됨

racket

(appC 
  (lamC 'a (plusC (idC 'a) (numC 5))) 
  (numC 10))

📌 인터프리터에서의 letC 해석 racket

[letC (name val body)
  (interp (appC (lamC name body) val) env store)]

즉, let은 함수의 호출(appC) 로 해석됩니다.

✅ 3. Lists (리스트 구조)

📌 표현 racket

(list 10 20 30)    ; 또는 (cons 10 (cons 20 (cons 30 empty)))

📌 AST 예시 racket

(consC (numC 10) 
  (consC (numC 20) 
    (consC (numC 30) emptyC)))

📌 재귀적 구조 consC는 리스트의 head와 tail로 구성됨

재귀적으로 연결되어 리스트 전체를 구성함

📌 Value 타입 확장 racket

(listV elems)   ; listof Value 타입으로 해석됨

📌 해석 방식 racket

[consC (head tail)
  (let ([head-val (interp head ...)])
    (listV (cons head-val (listV-elems (interp tail ...)))))]

✅ 4. Objects (객체 구조)

📌 예시 (C 스타일) c

class Point2D {
  int x = 3;
  int y = 5;
  int add(int a) { return x + a; }
}

📌 AST 표현 racket

(objC 
  (list 'x 'y 'add) 
  (list (numC 3) (numC 5) 
        (lamC 'a (plusC (idC 'x) (idC 'a)))))

📌 내부 구성 objC는 두 개의 리스트로 구성됨

names : 변수명/메서드명 (symbol 리스트)

vals : 해당 값 (numC 또는 lamC 같은 ExprC)

📌 의미 객체는 일종의 환경(environment) 으로 해석됨 즉, names와 vals를 짝지어 바인딩하면 환경처럼 작동함

📌 핵심 요약표

📌 1. 기존 문제점: 값만 리턴하는 인터프리터의 한계

기존의 인터프리터는 다음처럼 오직 값만 반환했습니다

racket

(define (interp [expr : ExprC] [env : Env]) : Value
  ...)

하지만 아래 같은 상황에서는 "값만"으론 부족합니다:

racket

(set x 3)
(set x 5)

위 예시처럼 변수에 값을 재할당하는 mutation (상태 변화) 를 표현하려면, 단순히 값만 반환해서는 변경된 메모리 상태(store) 를 추적할 수 없습니다.

🆕 2. 해결책: 결과(Result)를 값과 store로 구성

✅ Result 타입 도입 racket

(define-type Result
  [vs (v : Value) (s : Store)])

v: 계산 결과 (Value)

s: 계산 후의 메모리 상태 (Store)

vs는 value와 store를 하나의 단위로 포장한 결과

🧠 3. 인터프리터 시그니처 변경

✅ 이전 racket

(define (interp expr env) : Value)

✅ 이후 (store 추가 + 결과 타입 변경) racket

(define (interp [expr : ExprC] [env : Env] [store : Store]) : Result)

이제 인터프리터는 store를 입력으로 받아, 계산된 value와 store를 함께 반환합니다.

🧩 4. 각 표현식 케이스별 구현 변경

✅ numC (숫자 리터럴) racket

[numC (n)
  (vs (numV n) store)]

숫자를 그대로 numV로 감싸고, store는 바뀌지 않으므로 그대로 반환.

✅ idC (변수) racket

[idC (n)
  (vs (fetch (lookup n env) store) store)]

env로부터 변수 n의 위치를 lookup

그 위치에서 값을 fetch

값은 반환하되, store는 그대로 유지

✅ lamC (함수 정의) racket

[lamC (a b)
  (vs (closV a b env) store)]

lambda는 클로저로 평가됨: (closV arg body env)

정의 당시의 환경도 함께 저장해야 나중에 적용 가능

store는 변화 없음

✅ seqC (순차 실행) racket

[seqC (e1 e2)
  (type-case Result (interp e1 env store)
    [vs (v1 s1)
      (interp e2 env s1)])]

e1을 먼저 평가하여 결과 store인 s1을 얻음

s1을 반영하여 e2를 평가

최종 결과는 e2의 평가 결과

✅ setC (값 할당) racket

[setC (var val)
  (type-case Result (interp val env store)
    [vs (v s)
      (let ([loc (lookup var env)])
        (vs v (override-store (cell loc v) s)))])]

val을 먼저 평가해 값 v와 store s를 얻음

변수 var의 위치를 lookup

store에 새로운 cell (loc → v)을 추가로 덮어쓰기 (mutation)

업데이트된 store와 함께 값 v 반환

✅ plusC (덧셈) racket

[plusC (l r)
  (type-case Result (interp l env store)
    [vs (vl sl)
      (type-case Result (interp r env sl)
        [vs (vr sr)
          (vs (num+ vl vr) sr)])])]

l을 먼저 평가하고 store가 sl로 바뀜

그 상태에서 r을 평가해야 하므로 sl을 넘김

최종 결과는 vl + vr, store는 sr로 업데이트된 상태

✅ appC (함수 호출) racket

[appC (f a)
  (type-case Result (interp f env store)
    [vs (vf sf)
      (type-case Result (interp a env sf)
        [vs (va sa)
          (let ([loc (new-loc)])
            (interp (closV-body vf)
                    (extend-env (bind (closV-arg vf) loc)
                                (closV-env vf))
                    (override-store (cell loc va) sa)))]))]

f를 해석하여 클로저 vf와 store sf 획득

a를 해석하여 인자값 va와 store sa 획득

new-loc을 생성하여 인자 이름 → 위치 바인딩 추가

환경과 store를 확장한 후 클로저 본문 실행

🧾 5. 핵심 연산 요약

연산 설명 lookup name env name → location (Environment) fetch loc store location → value (Store) override-store store에 새로운 cell 추가 (앞에 덮어쓰기처럼 붙임) extend-env 환경에 새로운 바인딩 추가 new-loc 새로운 위치 (메모리 주소) 생성 함수

🧠 정리

Result 타입 도입은 “값 + 상태(store)” 동시 추적을 가능하게 한다.

이제 모든 ExprC는 store를 입력받고, 값을 계산하는 동시에 상태 변경 결과를 함께 출력한다.

이렇게 하면 mutable 상태, 변수 재할당, 순차적 실행 등이 정확히 해석 가능하다.

작업 브랜치를 변경하려면 워킹 디렉터리는 깨끗한(clean) 상태로 정리되어 잇어야 함 워킹 디렉터리에 작업 중인 내용이나 커밋되지 않은 변경 사항들이 남아 있으면 브랜치를 변경할 수 없음 현재 수정 작업을 멈추고, 다른 브랜치에 있는 코드를 수정하려면 스태시(stash) 기능을 사용할 수 있음 간단하게 설명 : '안전한 보관'

깃은 완료되지 않은 작업(커밋되지 않은 변경 내용)이 남아 있을 때, 현재 작업을 임시로 저장할 수 있는 스태시 기능을 제공함 스태시는 '현재 워킹 디렉터리 내역을 별도의 스택 영역에 잠시 보관하라'는 명령임 스태시는 브랜치를 이동할 때 작업 중인 내용 때문에 워킹 디렉터리가 충돌하는 것을 방지하는 데 사용함 스태시 명령을 실행하면 현재 작업 중인 내용은 임시 저장되고, 수정 전 마지막 커밋 상태로 돌아감 이전 커밋 후 작업하지 않은 상태의 워킹 디렉터리가 됨

스태시를 하려면 stash 명령어를 실행함 기본 명령어로 스태시를 실행하거나 옵션을 사용하여 추가 기능을 선택할 수 있음 스태시는 로컬 저장소에서만 사용 가능함

스태시의 임시 스택 영역에 작업 중인 코드 저장 스태시 명령어는 수정 중인 내역을 커밋하지 않고도 브랜치를 이동할 수 있게 워킹 디렉터리를 깨끗이 청소함 커밋 대신 스태시 명령을 실행하면 됨 스태시는 영구적인 커밋 기록대신 현재 작업들을 임시 스택 영역에 저장함

명령어

$ git stash

스태시 여러 개 생성 명령어

$ git stash save

스태시는 스택 구조로 여러 번 실행하여 저장할 수 있음 스태시가 여러 개 있을 때 각각의 스태시를 구별할 수 있도록 메시지도 추가할 수 있음

$ git stash save "WIP: 메시지~~~"

스태시의 저장 영역은 스택 구조임 스택 : FILO(First In Last Out) 구조, 마지막에 입력한 자료가 제일 먼저 출력되는 데이터 저장 방식임

스태시에 저장된 스택은 list 옵션을 사용하여 확인할 수 있음

$ git stash list # 스태시 목록 

stash 명령어로 저장된 객체들의 목록이 출력됨 스태시 이름은 stash@{번호} 형태로 순차적으로 부여됨 목록 번호는 0부터 시작

스태시를 실행한 후 방금 전의 스태시와 현재 워킹 디렉터리 간 차이를 확인

$ git stash show # 내용 비교

현재 워킹 디렉터리 내용과 스태시된 내용 간 파일 변화를 간략하게 출력함

$ git stash show -p stash@{0} 

스태시를 사용하는 목적은 현재 워킹 디렉터리를 커밋하지 않고 임시로 저장하기 위해서임 임시 저장된 내용은 다른 수정 작업을 완료한 후에 다시 불러와 사용할 수 있음

임시 저장한 스태시 불러오기 버그ㅡ를 수정한 후 다시 원래의 작업 브랜치로 돌아옴 이전에 수정한 내역들이 남아 있지 않음 스태시에 임시 저장한 작업 내용들을 읽어 다시 적용할 수 있음

$ git stash pop #스태시 읽기

스택에서 저장된 작업 내용을 읽어 올 때는 제일 마지막에 저장된 내용을 읽어옴 데이터의 순차적 특징은 스택의 원리 때문

스태시의 스택에 저장된 작업 내용이 다시 적용됨 스태시는 스택에서 내용을 읽어 올 때 현재 브랜치의 워킹 디렉터리와 자동으로 병합함 자동 병합이 성공하면 읽어 온 내용을 스택에서 제거함 스태시에서 임시 저장된 작업 내용을 복원한 후 다시 스태시 목록을 확인함

$ git stash list # 스태시 목록 확인

스태시를 복원할 때 워킹 디렉터리의 상태는 깨끗해야 함 스택에 저장된 스태시 내용이 다시 워킹 디렉터리로 복구될 때, 수정된 작업 내용과 현재 워킹 디렉터리를 병합하기 때문임 복구되는 브랜치의 워킹 디렉터리가 깨끗하지 않다면 병합 과정에서 충돌이 발생할 가능성이 많음돌이 발생할 가능성이 많음

특히 스태시를 복원할 때 같은 파일에서 동일한 부분을 변경했다면 즉시 충돌이 발생함 스태시를 복원할 때 충돌이 생기면 직접 문제를 해결해야 함 복원하는 도중 충돌이 생기면 스태시는 스택에 저장된 내용을 자동으로 삭제하지 않음 직접 충돌을 해결한 후 스태시 목록을 수동으로 삭제해야 함 스태시 충돌이 예상된다면 스태시용 브랜치를 하나 생성해서 작업하는 것을 추천

새로운 브랜치를 생성한 후 스태시를 적용하는 명령어

$ git stash branch 브랜치이름

스태시 복사 스태시는 브랜치 작업들을 임시로 저장할 때 사용함 임시 저장된 작업을 스태시 명령 이전의 브랜치 상태로 되돌려 놓음 스태시를 사용한 저장과 복원은 서로 다른 브랜치에도 가능함 반드시 이전에 실행한 브랜치와 같은 브랜치에서 할 필요는 없음

다른 브랜치에서 스태시를 실행한 후 새로운 test 브랜치를 생성하여 스태시를 복원함 스태시 스택에 저장된 항목들은 어느 브랜치에서나 복원이 가능함 apply 옵션은 스택에 저장된 항목을 불러와 현재 브랜치로 복원함

$ git stash apply

스태시 복원 : 옵션 2개 pop, apply pop 명령어 : 스택 내용을 복원한 후 스택 목록에서 자동으로 삭제함. pop 명령어는 스택 내용을 워킹 디렉터리로 이동하는 것과 같음 apply 명령어 : 스택 목록을 읽은 후 자동으로 삭제하지 않기 때문에 반복적으로 스택에서 스태시 내용을 읽어올 수 있음 apply 명령어는 스태시 내용을 워킹 디렉터리로 복사하는 것과 같음

pop : 가져오기, apply : 복사

apply 명령어로 워킹 디렉터리를 복구할 때는 스택에서 자동으로 삭제되지 않는다. 이때 별도로 명령을 실행해야만 스태시 목록에서 삭제된다.

$ git stash drop

워킹 디렉터리 청소 clean 명령어를 사용해서 워킹 디렉터리에 있는 추적되지 않는 파일들을 찾아 삭제함 clean 명령어를 실행하는 순간 워킹 디렉터리의 추적되지 않는 모든 파일을 삭제함

$ git clean

$ git clean -f $ 잘못 삭제하는 것을 방지하

$ git clean -n $ 

$ git clean -d $ 추적되지 않는 파일만 별도로 삭제

$ git clean -x $ gitignore 파일에 등록한 파일은 삭제 X

브랜치(branch) : 저장 공간 하나에서 가상의 또 다른 저장 공간을 만드는 것 커밋 : 파일의 수정 이력 관리에 사용 브랜치 : 프로젝트를 독립적으로 관리하는데 사용

깃 브랜치 특징 : 기존 폴더를 복제하는 것과 다르게 가상 폴더를 사용하여 개발 작업을 구분

깃의 브랜치는 작업 폴더를 실제로 복사하지 않고, 가상 폴더로 생성함 외부적으로는 물리적인 파일 하나만 있는 것으로 보임 생성된 작업 폴더는 물리적으로 복제된 구조보다 유연하게 처리할 수 있음 브랜치로 생성된 가상 폴더는 빠르게 공간이동이 가능

독립적인 동작 브랜치를 이용하면 원본 폴더와 분리하여 독립적으로 개발 작업을 수행할 수 이음 기존에는 소스 코드의 작업 폴더를 별도로 생성함 물리적으로 복사된 각자의 폴더에서 코드를 작업한 후 소스 코드 2개를 다시 하나로 합쳐야 했음 - 매우 힘든 작업 깃과 같은 VCS를 이용하면 분리된 코드를 좀 더 쉽게 병합할 수 있음 분리된 브랜치에서 소스 코드를 각자 수정한 후 원본 코드에 병합하는 명령만 실행하면 됨 깃의 브랜치는 규모가 큰 코드 수정이나 병합을 처리할 때 매우 유용

빠른 동작 보통 다른 VCS는 브랜치를 생성할 때 내부 파일 전체를 복사 파일 크기가 매우 크다면 브랜치를 생성하는 데 시간이 오래 걸림 깃의 브랜치 기능은 다른 VCS보다 가볍고, 브랜치 전환이 빠른것이 특징 깃은 Blob 개념을 도입하여 내부를 구조화함 브랜치를 변경할 때 포인터를 이용해서 빠르게 전환함 브랜치 명령을 사용하면 내부적으로 커밋을 하나 생성하여 브랜치로 할당함

다른 VCS는 파일 전체를 복사하지만, 깃은 41바이트를 가지는 해시(SHA1) 파일 하나만 만들면 됨 - 브랜치를 더 빠르게 생성 가능

실습

기본 브랜치 모든 커밋과 이력은 브랜치에 기록 깃은 최소한 브랜치가 1개 이상 필요함 저장소를 처음 초기화하면 워킹 디렉터리는 master 브랜치 하나를 자동으로 생성됨 첫 번째 커밋은 master 브랜치에서 시작함

브랜치 목록 확인 명령어

$ git branch

깃은 master 브랜치를 기준으로 새로운 브랜치를 생성 브랜치는 공통된 커밋을 가리키는 지점 브랜치는 커밋처럼 SHA1 해시키를 가리킴 커밋의 SHA1 해시키는 기억하기가 어렵기 때문에 특정 커밋을 가리키는 별칭을 만드는 것임 이렇게 만든 별칭이 브랜치이다. 브랜치를 생성한다는 의미 : 기존 브랜치 또는 커밋에 새로운 연결 고리를 하나 더 만드는 것과 같음

새 브랜치를 생성하면 포인터만 있는 브랜치가 생성됨 일반적으로 브랜치 생성 명령을 실행하면 현재 커밋을 가리키는 HEAD를 기준으로 생성됨 HEAD는 현재 마지막 커밋을 가리킴 새롭게 브랜치가 생성되면 독립된 공간을 할당함 기존 브랜치의 소스 코드에 영향을 주지 않고 새로운 작업을 할 수 있음

브랜치 생성 = 사용자가 정의한 새로운 사용자 브랜치를 만듬 브랜치 : 또 하나의 개발 분기점 생성개수 제한 X

브랜치 생성 명령어

$ git branch 브랜치이름 커밋ID

branch 명령어 뒤에 브랜치 이름을 인자 값으로 추가함 브랜치 이름만 입력하면 현재 HEAD 포인터를 기준으로 새로운 브랜치를 생성함 직접 커밋 ID 인자 값을 지정하면, 지정한 커밋 ID를 기준으로 브랜치를 생성함

브랜치 이름은 슬래시(/)를 사용하여 계층적인 구조로 만들어서 사용할 수 있음 기호,마침표 - 시작 X 연속적인 마침표, 빈칸, 공백 문자, 물결, 캐럿, 물음표, 별표, 대괄호, 아스키 문자 - 포함 X

브랜치 확인

브랜치 확인 명령어

$ git branch

브랜치 해시 명령어

$ git rev-parse 브랜치이름 # 현재 브랜치가 어떤 커밋 해시값을 가리키는지 확인

브랜치 세부 사항 확인 명령어

$ git branch -v

브랜치 이동

브랜치 이동 명령어

$ git checkout 브랜치이름

깃은 하나의 워킹 디렉터리만 가지고 있다. 따라서 다른 브랜치에서 작업하고 싶다면 반드시 브랜치를 변경해서 워킹 디렉터리를 재설정해야한다. 장점 : 빠르게 포인터를 이용하여 브랜치를 이동할 수 있다는 점

원리 HEAD 정보는 항상 변경된 브랜치의 마지막 커밋을 가리킴 브랜치가 이동하면 HEAD 포인터도 함께 이동함

이전 브랜치로 이동 명령어

$ git checkout -

워킹 디렉터리 정리 체크아웃을 사용하여 브랜치를 이동할 때 주의해야 함 현재 작업하고 있는 워킹 디렉터리를 정리하고 넘어가야 함 워킹 디렉터리 안에서 작성하던 내용이 있고, 커밋을 하지 않았다면 체크아웃할 때 경고가 발생함.

워킹 디렉터리에서 작업하다 커밋하지 않고 남겨 둔 상태에서 다른 브랜치로 checkout하면 이처럼 브랜치 이동이 제한된다. 깃은 향후 충돌을 방지하려고 워킹 디렉터리에 작업이 남아 있다면 경고 메세지를 보여 주고 브랜치를 변경할 수 없게 제한한다.

브랜치 공간

브랜치 로그 로그를 출력할 때 브랜치 흐름도 같이 보려면 --graph 옵션을 함께 사용한다. 명령어, 옵션

$ git log --graph --all # 모든 로그를 출력함

HEAD 포인터

깃은 마지막 커밋을 가리키는 HEAD 포인터를 부모 커밋으로 대체하여 사용 브랜치를 이동하면 HEAD 포인트도 이동됨 브랜치가 여러 개면 HEAD 포인트도 여러 개임 브랜치마다 마지막 커밋 ID를 가리키는 HEAD 포인터가 하나씩 있음

상대적 위치 HEAD를 기준으로 상대적 커밋 위치도 지정할 수 있음 상대적 커밋 위치를 지정할 때는 캐럿(^)과 물결(~) 기호를 같이 사용함

AHEAD, BHEAD 원격 저장소와 연동하여 깃을 관리한다면 브랜치마다 HEAD가 2개 있음 (로컬 저장소 브랜치의 HEAD 포인터, 원격 저장소 브랜치의 HEAD 포인터) 둘은 물리적으로 서로 다른 저장소임 두 저장소의 마지막 커밋 위치가 일치하지 않을 수 있음 AHEAD, BHEAD는 서로 다른 저장소 간 HEAD 포인터의 위치 차이를 의미함

AHEAD 서버로 전송되지 않은 로컬 커밋이 있는 것 로컬 저장소의 HEAD 포인터를 기준으로 로컬 브랜치에 있는 커밋이 서버의 커밋 개수보다 많은 경우

BHEAD 로컬 저장소로 내려받지 않은 커밋이 있는 것 다른 개발자가 코드를 수정하여 원격 저장소의 커밋이 자신의 로컬 저장소보다 더 최신 상태인 것을 의미함

생성과 이동

자동 이동 옵션

$ git checkout -b # 브랜치 생성과 이동을 한번에!

이전 커밋으로 checkout하는 명령어

$ git checkout HEAD~1 # 현재의 한 단계 전

여러 단계 이전으로 이동하고싶으면 ~뒤의 숫자만 바꾸자.

원격 브랜치

리모트 브랜치 원격 저장소에 생성한 브랜치

로컬 저장소의 feature 브랜치를 원격 저장소의 function 브랜치로 push

$ git push -u origin feature:function # 다른 이름으로 브랜치 전송

업스트림 트래킹 업스트림(upstream) : 브랜치 추적을 다르게 표현한 것 업스트림 트래킹 : 로컬 저장소의 브랜치와 원격 저장소의 브랜치는 업로드할 수 있도록 매칭 트래킹 브랜치(업스트림)는 리모트 브랜치와 로컬 브랜치를 연결해 주는 중간다리 역할

트래킹 브랜치 목록 확인 명령어

$ git branch -vv # 트래킹 브랜치 목록 확인 명령어

업스트림 동작을 위한 트래킹 브랜치를 직접 명령어를 실행하여 생성하기

$ git checkout --track origin/브랜치이름 # 새로운 업스트림 만들기

원격 브랜치 복사 명령어

$ git checkout -b 새이름 origin/브랜치 이름 
# 생성된 원격 저장소의 리모트 브랜치를 이용해 로컬에도 새로운 브랜치를 생성하여 동기화

업스트림을 직접 설정하면 원격 저장소로 트래킹 브랜치가 설정됨

$ git branch -u origin/브랜치이름 

기존 브랜치를 특정 원격 브랜치로 추적함

$ git fetch # 서버의 브랜치 정보 갱신

$ git branch -r # 원격 브랜치 목록

브랜치 전송

깃의 push 작업은 로컬 저장소의 파일들을 원격 저장소로 전송함 파일뿐만 아니라 브랜치 정보와 커밋까지 모두 전송함

처음에는 커밋과 브랜치를 푸시하는 데 업스트림 설정이 필요함 원격 저장소 연결만으로 업스트림이 자동으로 설정되지는 않음

처음에는 수동으로 트래킹 브랜치와 업스트림 설정을 해야함 (명령어)

$ git push --set-upstream origin master

브랜치 페치 리모트 브랜치 페치는 일반적인 커밋 페치와 동일 리모트 브랜치가 페치되면 깃은 단순히 원격저장소별칭/브랜치 포인터만 생성 원격 저장소에서 페치된 커밋들을 새로운 로컬 브랜치로 반영하려면 병합 명령을 실행해야함

$ git merge 원격저장소별칭/브랜치이름

브랜치 삭제 해당 브랜치 내용과 커밋을 모두 삭제하면 됨 주의할 점 : 현재 자신이 있는 브랜치는 삭제 X

일반적인 삭제 방법 브랜치 삭제할때는 -d 옵션 사용

$ git branch -d 브랜치이름

-d 옵션은 스테이지 상태가 깨끗할 때만 삭제를 허용함 워킹 디렉터리에 작업한 기록이 있거나 add 명령어로 스테이지의 인덱스가 변경된 상태라면 삭제 X 병합되지 않은 브랜치는 -d 옵션으로 삭제 X

강제 삭제 방법

$ git branch -D 브랜치이름

-D 옵션으로 강제로 삭제

리모트 브랜치 삭제 방법

$ git push origin --delete 리모트브랜치이름

서버 저장소 : 원격(remote) 저장소 서버 저장소는 로컬 저장소의 코드를 복제한 복사본이라고 할 수 있다. 서버를 이용해 코드를 안전하게 보관, 다른사람과 공유 & 협업 가능

협업 저장소 깃은 여러 개발자와 협업하려고 탄생한 도구

원격 저장소가 있다면 언제 어디에서든지 개발을 이어서 할 수 있다. 원격 저장소에 작업한 코드를 업로드하고 다른 곳에서 업로드된 코드를 내려받아 작업을 이어나갈 수 있음

깃은 분산된 저장소 여러 개를 하나로 통합하고, 최신 코드를 배포할 수 있음 서버 저장소는 여러 컴퓨터에 동일한 깃 저장소를 복제하고, 작업한 결과물을 다시 서버로 통합 깃의 분산형 관리 체계는 다수의 사람과 협업하는 데 매력적임 새로운 멤버가 참여할 때, 지금까지 작업한 소스 코드의 마지막 버전을 공유해야 함(깃의 원격 저장소 주소만 알려주면 모두 해결됨)

깃허브 서버 준비

직접 서버를 운영하지 않아도 전문적인 깃 호스팅으로 서버를 대체할 수 있음 호스팅을 받으면 직접 서버를 관리하지 않아도 쉽게 원격 저장소를 운영할 수 있음

깃허브 연동 및 원격 등록

로컬 저장소 원격 저장소에 연결하려면 먼저 로컬 저장소가 있어야 함 로컬 저장소를 원격 저장소에 연결하는 방법은 크게 두가지

1. 새로운 로컬 저장소를 생성하고 원격 저장소를 연결하기
2. 기존 저장소를 연결하기

1 방법 로컬 저장소

$ mkdir gitstudy05 # 새 폴더 만들기
$ cd gitstudy05 # 새 폴더로 이동
$ git init # 저장소를 깃으로 초기화

$ echo "# gitstudy05" >> README.md # 파일 생성
$ git add README.md # 스테이지에 등록
$ git commit -m "first commit" # 첫 번째 커밋

프로토콜 서버와 통신하려면 프로토콜을 사용해야 함

Local(로컬) 로컬 컴퓨터에 원격 저장소를 생성하는 것 자신의 컴퓨터를 NFS(Network File System)등 서버로 이용할 때 편리 로컬 저장소를 서버로 이용할 때는 폴더 경로만 입력하면 됨

$ git remote add 원격저장소별칭 폴더 경로

로컬은 간단하게 원격 서버를 구축할 수 있을 뿐만 아니라 빠른 동작이 가능함 모든 자료가 자신의 컴퓨터에 집중되는 위험도 있다.

HTTP 깃은 HTTP 방식의 프로토콜 지원함 서버에 접속하려면 로그인 절차를 거쳐야 함 기존 아이디, 비밀번호로 접속자를 인증하여 처리할 수 있음 익명으로도 처리할 수 있음

SSH 깃에서 권장하는 프로토콜, 높은 수준의 보안 통신으로 처리하기 때문에 깃 서버를 좀 더 안전하게 운영할 수 있음 SSH 접속할 때는 인증서를 만들어 사용함 인증서를 만들어서 접속하면 별도의 회원 로그인 절차 X 인증서는 공개키 / 개인키로 구분. 공개키는 서버에 등록, 개인키는 로컬에 저장 익명으로 접속 X

Git 깃의 데몬 서비스를 위한 전용 프로토콜 방식을 의미 SSH와 유사하지만 인증 시스템이 없어 보안에 취약할 수 있음 잘 사용 X

원격 저장소의 리모트 목록 관리 깃은 원격 저장소(서버)를 관리하는 데 remote 명령어를 사용함 remote 명령어 사용 - 현재 연결된 원격 저장소 목록을 확인할 수 있음 동시에 등록, 취소 등 작업할 수 있음

원격 저장소 목록만 확인할 때 명령어

$ git remote

원격 저장소의 별칭 이름과 URL 확인할 때 명령어

$ git remote -v # 원격 저장소 목록 확인

깃은 복수의 원격 저장소를 연결하여 사용 가능 리모트 저장소가 여러 개 있을 때는 목록을 모두 출력 저장소의 권한 정보까지는 알 수 없음

주소와 별칭 로컬 저장소에 원격 저장소(서버)를 등록하려면 서버 주소가 필요함 깃허브 같은 저장소를 이용해 보면 프로토콜 + 도메인 주소 형태로 된 것을 알 수 있음 로컬에 서버 저장소를 생성할 때는 폴더 경로를 사용할 수 있음 별칭 : 예를 들면 origin

원격 저장소와 연결하는 명령어

$ git remote add 원격저장소별칭 원격저장소URL

원격 저장소가 연결되면 fetch와 push 두 주소를 출력 push : 서버로 전송하는 동작 fetch : 서버에서 가지고 오는 동작 별칭 중복 선택 X

별칭 이름 변경 명령어

$ git remote rename 변경전 변경후

원격 저장소의 좀 더 상세한 정보 확인 명령어

$ git remote show 원격저장소별칭

원격 서버 삭제 로컬 저장소는 복수의 원격 저장소와 연결 가능

등록된 원격 저장소 삭제 명령어

$ git remote rm 원격저장소별칭

서버 전송

push : 서버에 전송 원격저장소로 커밋된 파일들을 업로드하는 동작

서버에 전송하는 명령어

$ git push 원격저장소별칭 브랜치이름

별칭 이름을 가지는 서버의 master 브랜치에 현재 브랜치를 업로드함 처음 push하면 서버에 새로운 master 브랜치를 생성함 로컬의 master 브랜치 안에 있는 소스 코드를 서버의 master 브랜치로 업로드 자신의 로컬 저장소를 백업하는 용도로 원격 저장소를 사용할 수 있음

자동으로 내려받기

clone(복제) 복제는 기존 저장소를 이용하여 새로운 저장소를 생성하는 방법 중 하나 clone 명령어 사용해서 복제 clone 명령어는 초기화 init 명령어 외에 원격 서버 접속에 필요한 추가 설정을 자동으로 수행함 서버의 연결 설정을 마친 후 서버 안에 있는 모든 커밋된 코드 이력들을 한 번에 내려받음

복제 후 원격 저장소의 갱신된 내용을 추가로 내려받으려면 pull 명령어 사용 pull 명령어는 로컬 저장소보다 최신인 갱신된 원격 저장소의 커밋 정보를 현재 로컬 저장소로 내려받음 명령어

$ git pull

수동으로 내려받기

원격 저장소의 내용을 내려받는 방법은 크게 pull, fetch 차이 : 병합의 자동 처리 여부

자동 병합 pull : 원격 서버에서 현재 커밋보다 더 최신 커밋 정보가 있을 때 내려받은 커밋 정보는 임시 영역에 저장 스테이지 영역이 아닌 원격 저장소를 위한 전용 임시 브랜치가 따로 있음 내려받은 최신 커밋들을 현재 브랜치로 자동으로 병합 처리함 병합은 원격 서버 파일과 로컬 파일을 하나로 합치는 과정임 여러 개발자와 협업하는 과정에서 pull 명령어가 자동으로 브랜치 병합을 하지 못하고 충돌이 발생하기도 함 >> fetch 방식 사용

fetch: 가져오기 원격 저장소에서 코드를 수동으로 내려받는 작업 원격 저장소에서 커밋된 코드를 임시 브랜치로 내려받음 내려받은 후 현재 브랜치와 자동 병합 X

$ git fetch 원격저장소URL

pull 명령어와 달리 fetch 명령어를 실행한 후에는 커밋이 추가된 것을 확인할 수 없음 fetch는 원격 저장소의 커밋들만 가지고 왔을 뿐 로컬 저장소에서 어떤 작업도 하지 않음

내려받은 커밋을 로컬 저장소에 적용하려면 병합 명령을 실행해야함. merge 명령어 사용

$ git merge 원격저장소별칭/브랜치이름

순서

원격 저장소에는 다수의 개발자가 동시에 커밋을 push할 수 없음 여러 명이 협력해서 개발할 때는 순차적으로 push해야 함

원격 저장소에 push하려면 자신의 로컬 저장소를 최신 상태로 유지해야함 커밋이 순차적이지 않을 때 깃은 push 동작을 거부 깃 거부 >> pull or fetch & merge(자신의 로컬 저장소 갱신) >> push

충돌방지 깃이 최신 상태에서만 push를 허용하는 것은 충돌을 방지하기 위함 원격 저장소의 커밋을 내려받는 pull 작업은 내려받은 커밋들을 현재 브랜치로 자동 병합 이때 커밋 내용이 순차적이지 않으면 병합 과정에서 충돌이 발생함

순서 : pull >> coding >> commit >> pull >> push

pull, push 를 자주 하여 충돌을 최소한으로 줄여 나가면서 작업할 것

깃은 개발 중인 코드의 이력을 만들 수 있음 커밋(commit) : 코드 변화를 기록하는 것, 의미 있는 단위의 변경 작업들을 저장소에 기록하는 동작

고식적(conventional) 파일 관리 방법 의미 있는 변경을 할 때 파일을 복사함. 파일 복사 형태는 파일의 변경 내역을 기록하는 것보다 더 많은 파일을 생성하고 관리해야 하는 부작용이 있음 모든 내용이 중복되기 때문에 용량도 많이 차지함

Git(VCS)을 이용한 파일 관리 방법 깃의 commit은 새로 변경된 부분만 추출하여 저장 파일 이름을 변경하지 않고도 동일한 파일 이름으로 하나로 관리가 가능함 commit : 시간에 따라 변화되는 내용만 관리하고, 코드가 변화된 시간 순서에 따라서 영구적으로 저장한다.

새 파일 생성 및 감지

$ mkdir gitstudy04 # 새 폴더 gitstudy04 만들기
$ cd gitstudy04 # 만든 폴더로 이동
$ gir init # 저장소를 깃으로 초기화

$ code index.html # VS Code를 사용하여 파일 index.html 생성

워킹 디렉터리에 새 파일이 생성됨 워킹 디렉터리에 새 파일이 추가되면 깃은 변화된 상태를 자동으로 감지함 이때 깃 상태를 확인할 수 있는 명령어

$ git status # 상태 확인

깃에 새 파일 등록

워킹 디렉터리에 있는 파일은 깃이 자동으로 추적 관리하지 않음 커밋을 하려면 파일의 상태가 추적 가능해야 함 등록 : 워킹 디렉터리에 새로 추가된 untracked 상태의 파일을 tracked 상태로 변경하는 것 파일 등록 >> 워킹 디렉터리의 파일이 스테이지 영역에 추가됨 깃은 스테이지 영역의 관리 목록에 추가된 파일만 이력을 추적할 수 있음

스테이지에 등록 명령어

$ git add index.html # 스테이지에 파일을 등록
$ git add . # 전체 파일과 폴더를 모두 등록

필요한 파일만 스테이지 영역에 등록하여 이력을 추적 스테이지 영역에 등록하지 않은 파일은 커밋 작업에 포함되지 않음 단 빈 폴더는 스테이지 영역에 등록할 수 X

파일 등록 취소 tracked >> untracked 상태 변경 파일 등록 취소 명령어

$ git rm --cached index.html # 스테이지 삭제 rm 대신 reset도 가능

등록된 파일의 이름이 변경 명령어

$ git mv index.html home.html # 파일 이름 변경

첫 번째 커밋

HEAD는 커밋을 가리키는 묵시적 참조 포인터 HEAD는 최종적인 커밋 작업의 위치를 가리킴 HEAD는 커밋될 때마다 한 단계씩 이동함

스냅샷 커밋은 파일 변화를 깃 저장소에 영구적으로 기록함 깃이 다른 버전 관리 도구와 다른점 : 스냅샷 방식(변화된 부분만 찾아 저장) 깃의 스냅샷은 HEAD가 가리키는 커밋을 기반으로 사진을 찍음 깃은 스냅샷 방식을 이용해 빠르게 버전의 차이점 처리, 용량을 적게 사용

파일 상태와 커밋 새롭게 생성된 파일을 커밋하려면 반드시 tracked 상태로 변경해야함 tracked 상태로 파일이 변경됨과 동시에 스테이지 영역에 등록함 tracked 상태인 파일을 수정하면 다시 modified 상태로 변경됨 modified는 untracked 상태 untracked 상태의 파일은 반드시 등록 명령(add)으로 다시 스테이지 상태로 재등록해야 함(재등록하면 tracked 상태로 변경됨)

커밋하기 전에는 status 명령어로 항상 상태를 확인하는 습관이 필요함 워킹 디렉터리가 깨끗하게 정리 X >> 커밋 명령어 수행 X

커밋 명령어

$git commit

깃의 커밋은 HEAD와 스테이지 영역 간 차이를 비교하여 새로운 객체를 생성함 생성된 객체를 깃 저장소에 기록

커밋은 변경된 파일 차이를 깃 저장소에 기록함 커밋을 할 때 생성된 객체를 기록하는 것과 동시에 이를 구별할 수 있는 메시지를 같이 작성해야 함 (꼬리표 개념) 커밋은 파일 이름을 여러 개 사용하지 않고 하나만 가짐 모든 커밋은 반드시 커밋 메시지를 작성해야 함

파일 등록과 커밋을 동시에 실행하는 명령어

$ git commit -a

커밋 확인

1. 터미널에서 status 명령어를 실행해서 상태를 확인 (커밋을 하면 스테이지 영역은 초기화됨)
2. 로그 기록 확인 명령어

   $ git log

   log 명령어는 시간 순으로 커밋 기록을 출력하는데, 최신 커밋 기록부터 내림차순으로 나열함

$ mkdir 폴더이름 # 새 폴더 만들기
$ cd 폴더이름 # 만든 폴더로 이동 (change directory)

$ git init 경로명 # 저장소 초기화

$ ls # 파일 목록 출력
$ ls -a # 폴더 안의 숨겨진 파일까지 출력

워킹 디렉터리

깃은 VCS의 특성 때문에 저장 공간을 논리적으로 분리함 작업하는 공간(working), 임시로 저장하는 공간(stage), 실제로 저장, 기록하는 공간(repository)

깃이 다른 VCS보다 뛰어난 점 : 지정된 파일들의 모든 것을 추적하는 관리 시스템 (추적됨, 추적되지 않음 상태로 구분함)

tracked 상태 워킹 디렉터리에 새 파일을 추가하면 untracked 상태

$ git add

git add 명령어를 통해 tracked 상태로 변경해야함. 즉, 워킹 디렉터리 >> 스테이지 영역

깃은 요청받은 파일들만 추적 관리한다. 추적하는 파일 : tracked 상태로 표시 tracked / untracked 나누는 이유 : 시스템 부하를 줄이고, 더 효율적으로 파일 이력을 관리하기 위함.

스테이지

임시로 저장하는 공간 워킹 디렉터리에서 제출된 tracked 파일들을 관리 스테이지는 커밋하려는 파일의 추적 정보만 기록 스테이지를 운영하는 이유 : 커밋을 빠르게 처리하기 위함 repository(저장소)는 스테이지 영역에서 가리키는 파일 내용을 기반으로 변경된 차이점만 기록함

파일들의 스테이지 상태 확인 명령어

$ git status
$ git ls-files --stage

스테이지 영역에 등록된 파일들은 또 다시 stage / unstage 상태로 구분 깃이 변화 이력을 기록하려면 파일들의 최종 상태가 stage 상태여야 함 unstage 상태 : 파일에 변화가 있음을 의미(스테이지 영역과 워킹 디렉터리 안의 파일 내용에 차이가 있을 때)

코드 변경 = 워킹 디렉터리에서 파일을 수정 파일 수정 >> 워킹 디렉터리와 스테이지 간 내용이 일치 X 스테이지는 수정한 파일과 원본 파일을 구분하기 위해 modified / unmodified 상태로 나눔

modified 상태 스테이지에 등록된 파일은 깃이 추적 관리함 tracked 상태인 파일이 수정되면 스테이지는 파일 상태를 modified 상태로 변경

수정된 파일은 스테이지에서 잠시 제외됨 깃은 수정 여부만 체크해 주기 때문에 modified 상태로 변경된 파일은 스테이지로 재등록해야 함 수정된 파일을 스테이지 영역으로 다시 적용하려면 git add 명령어 사용

unmodified 상태 tracked 상태이면서 스테이지에서 한 번도 수정하지 않은 원본 상태 수정 X 파일 : 재등록할 필요 X 스테이지에 등록후 수정을 안했다면 unmodified 상태

파일의 상태 확인

상태 개념 : 깃의 분리된 저장 영역인 워킹 디렉터리와 스테이지, 추적 여부를 의미 깃이 다양한 저장 영역을 구분해서 가지고 있는 이유 : 파일들의 상태를 효율적으로 모니터링하기 위함.

$ git status : 상태 확인 명령어

깃 저장소 복제

외부에 있는 기존 프로젝트를 기반으로 저장소를 생성하고 싶다면 외부 저장소를 복제해서 생성할 수 있음. 외부 저장소를 이용해서 로컬 저장소를 생성하는 것 = '깃 저장소 복제'

공개 저장소 ex. 깃허브, 비트버킷 깃 호스팅 서비스는 공개된 저장소와 비공개된 저장소를 모두 지원함 공개된 저장소는 누구나 복제하여 코드를 내려받을 수 있음

다운로드 vs 복제 다운로드 : 깃의 변경 이력까지 가져오지 X 복제 : 깃의 변경 이력까지 가져옴 >> 최종 코드뿐만 아니라 중간에 커밋같은 변화의 모든 이력도 같이 내려받을 수 있다. 일부코드를 변경하여 기여하는 것도 가능

복제 명령어

$ git clone 원격저장소URL 새폴더이름

복제할 때 폴더 이름을 지정하지 않으면 공개 저장소에서 사용된 폴더와 동일한 이름으로 새 폴더를 만듬(다른 이름으로 복제하고 싶다면 새 폴더이름을 추가 인자로 적자.)

git clone 명령어를 사용하면 깃은 자동으로 깃 서버에 접속 저장소의 모든 소스 코드를 자동으로 내려받음

변수 이름은 환경(environment)을 통해 그 값에 연결된다.

한 번 바인딩된 값은 바뀌지 않는다. 상태(state)라는 개념이 없다.

🧱 작동 구조: racket

(define env (list (bind 'x (numV 3)) (bind 'y (numV 5))))
(lookup 'x env) → (numV 3)

📌 특징: 매번 새로운 env를 생성해서 새로운 바인딩을 포함시킨다.

이전 바인딩은 남아 있어도 접근되지 않는다 (새 바인딩이 앞에 있음).

순수 함수 스타일: 입력만이 결과를 결정하며, 외부 세계의 변화가 없음.

🔁 2. 순차 실행과 상태 도입 왜 상태가 필요해졌는가? racket

(begin
  (set! x 5)
  (+ x 1))

위 코드처럼 이전 표현식의 실행 결과가 다음 표현식에 영향을 주는 구조에서는, 상태(state)라는 개념이 반드시 필요해진다.

✨ 변화된 평가 방식: racket

M(expr, env, store) → (val, store')

expr은 표현식

env는 이름 → 위치 매핑

store는 위치 → 값 매핑

결과는 값과 함께 새로운 상태(store')를 반환

🧠 3. Environment vs Store 구성 역할 Environment symbol → location (변수 이름을 메모리 주소로) Store location → value (주소를 실제 값으로)

값을 얻기 위해서는: symbol → location (via lookup) → location → value (via fetch)

📦 4. Store와 Cell 구조 store는 리스트로 구현되며, 각 원소는 (cell loc val) 형식: racket

(list (cell 0 (numV 3)) (cell 1 (numV 5)))

cell: 위치(location)와 값(value)의 쌍

numV: 숫자 값을 감싼 타입

이렇게 나누는 이유: 값 자체보다 위치를 통한 접근/업데이트를 구현하기 위해서

🔄 5. override-store – store 갱신 racket

(override-store (cell 1 (numV 10)) store)

작동 방식: override-store는 store 리스트 앞에 새로운 cell을 추가한다.

이는 기존 cell을 삭제하지 않고, 새로운 바인딩을 우선적으로 사용하도록 만드는 방식이다.

예시: racket

(override-store (cell 1 (numV 10))
                (list (cell 0 (numV 3)) (cell 1 (numV 5))))
→ (list (cell 1 (numV 10)) (cell 0 (numV 3)) (cell 1 (numV 5)))

location 1에 대해 나중에 fetch를 하면 항상 맨 앞의 10이 나옴

기존 (cell 1 (numV 5))는 남아있지만 무시됨

🔍 6. fetch – 값 검색 함수 정의 요약: racket

(fetch loc store)

→ store를 앞에서부터 검사해 loc이 일치하는 첫 cell의 값을 반환 작동 방식: racket

define (fetch [loc : Location] [store : Store]) : Value
  (cond
    [(empty? store) (error "not found")]
    [(equal? loc (cell-location (first store)))
     (cell-val (first store))]
    [else (fetch loc (rest store))]
    )]))

✅ 입력: loc과 store

✅ 출력: value

✅ 동작: 처음 일치하는 셀에서 값 리턴 (덮어쓰기처럼 동작)

🧩 7. 전체 흐름 예시로 요약 racket

(set! x 5)
(set! x (+ x 1))
x

set! x 5

lookup x env → loc = 0

store에 (cell 0 (numV 5)) 추가됨

(+ x 1)

lookup x env → loc = 0

fetch 0 store → 5

결과: 6

override-store로 cell 0 (numV 6) 추가됨

x

fetch 0 store → 가장 앞의 cell 0 (numV 6) 선택

✅ 최종 요약 개념 요점 Functional Approach 바인딩은 불변, 상태 없음 Sequential State 상태 변화가 다음 계산에 영향 Environment name → location Store location → value (cell 단위) override-store 같은 위치에 새 값을 "앞에 붙여" 우선순위 부여 fetch 처음 일치하는 위치의 값을 반환

버전 관리

프로그래밍 개발 과정은 수많은 코드를 변경하고 테스트하는 것 지속적으로 변경되는 과정에서 코드는 잠시 불안정한 수정 상태와 안정된 상태를 반복한다. 개발자는 안정된 상태의 코드와 불안정한 상태의 코드를 인지하고, 항상 안정된 상태를 유지하도록 노력해야 한다.

버전

버전 : 이전과 약간씩 다른 변화들을 구분하는 표시

서브버전 : 버전과 버전 사이에 변화된 것 : 개발 도중 임시로 작업한 것은 버전이 아님

버전관리의 필요성 : 개발하는 동안 코드는 일시적으로 불안정한 상태가 되고, 이후 정상적인 테스트와 동작을 확인하고 나면 다시 안정된 상태가 된다. 개발 또는 테스트하는 과정에서 불안정한 코드가 있다면 계속 이어서 작업하기 불안할 것이다. 이때 이전 상태로 돌아가 다시 시작할 수 있는 코드의 복귀(포인트) 지점이 필요하다. 복귀 지점을 안정된 코드 상태를 기준으로 설정함으로써 좀 더 자유롭고 안정적으로 개발할 수 있다.

1.2 버전 관리 시스템

버전 관리 소프트웨어

버전 관리 시스템 (VCS, Version Control System) : 코드와 콘텐츠의 변화를 관리하고 추적하는 소프트웨어 (ex. SCCS:최초의 버전 관리 시스템) 저장소(repository) : VCS에서 버전 파일들을 관리하고 저장하는 공간

집중형 시스템 : 모든 소스 코드가 한곳에 집중되어 있는 형태 : 하나의 메인 중앙 서버에서 개발 구성원의 모든 소스 코드를 통합적으로 관리 : 클라이언트 - 서버 모델

장점 : 저장소 하나를 중심으로 관리 >> 시스템 운영에 수월 단점 : 중앙 저장 공간인 서버에 문제 발생 시, 소스 코드가 있는 메인 저장소에 모든 개발자가 접근할 수 없는 심각한 상황이 일어남 : 동시에 여러 개발자가 접근하면 충돌이 발생하기에 코드 수정을 안정적으로 할 수 있게 잠금 모델을 적용함 : 파일을 변경하려면 개발자들은 순서대로 대기하고 있어야 함

EX : SCCS(1970s 최초의 버전 관리), RCS(1980s 정/역 방향 개념 도입), CVS, 서브버전

분산형 시스템 : 저장소가 여러개 : 여러 저장소에 각 버전별 소스를 개별 보관 : 분산 저장소 - P2P(Peerto-Peer) 방식으로 공유하며, 각 개발자에게 공유 가능한 저장소 사본 제공 : 서버 - 각 저장소 자료를 동기화하고 중개하는 역할만 수행

장점 : 메인 서버에 문제가 생겨도 지속적으로 개발할 수 있음 단점 : 익숙해지는 데 시간이 걸림

EX : Git (현재 가장 많이 사용함. 오픈소스라서 무료사용 가능), 머큐리얼(파이썬 언어, 무료), 비트키퍼(1998, 유료)

1.3 깃

깃

2005년 리눅스 개발자가 개발함 대표적인 분산형 버전 관리 시스템 : 원격 저장소(remote repository)와 별개로 개발자 각각의 로컬 컴퓨터에 완벽한 복제본 소스 코드를 저장할 수 있음 - 매번 중앙 저장소를 조회하지 않아도 개발 진행 가능 : 네트워크나 인터넷이 연결되어 있지 않은 상태에서도 로컬 컴퓨터의 소스 코드만으로 버전을 관리할 수 있음 - 작업 후 인터넷 연결시 동기화만 하면 됨 : 원격 저장소로 많은 개발자의 저장소와 연결하거나 동기화 작업을 할 수 있음 - 직접 만든 새로운 소스 코드를 배포하거나 내려받은 소스 코드를 수정한 후 다시 병합(merge) 가능

백업 기능

분산형 깃 - 자신의 로컬 컴퓨터에서 독립적으로 소스의 버전 관리 가능 독립적 : 자체적으로 버전 기록, 관리 가능한 시스템 주의할 점 : 컴퓨터에 문제 - 개발한 모든 소스 잃을 수 있음 (외부 저장 장치에 백업함으로 예방) 외부 저장 장치에 백업하는 코드는 단순히 파일을 복사하는 것으로 기존 소스코드와는 동기화되지 않은 별개의 파일이다. 깃 사용 - 코드를 원격 저장소에 저장 가능 로컬 컴퓨터의 저장소를 동기화하여 원격 저장소에 백업 여러 공간에서 원격 저장소에 저장된 내용을 내려받아 프로젝트 개발 이어서 가능

협업 개발

기록과 책임 다수의 개발자와 코드를 공유하고 협업할 때 매우 유용 깃은 변경된 모든 이력을 저장 커밋(commit)을 거쳐 모든 코드의 수정 이력을 기록함 커밋은 신중하게. 커밋으로 저장된 원본 객체는 수정할 수 없음

원격공유 분산된 여러 저장소 간에 정보를 주고받으려면 중앙 서버가 필요함. 깃에서는 원격 저장소가 중앙 서버 역할 자신의 코드 저장소를 원격 서버에 push하여 저장(동기화) 또 다른 개발자의 소스를 원격 서버에서 pull 또는 fetch하여 언제든지 내려받을 수 있음

병합 깃은 하나의 소스코드를 여러 가지 브랜치로 분기하여 독립된 기능을 구현할 수 있음 독립적으로 구현된 소스를 주고받으며, 필요하다면 각 브랜치를 하나로 병합

공개 원격 저장소를 사용하여 개발 중인 코드를 외부로 공개할 수 있음 코드를 공개함으로써 내부 개발자가 만든 기능 한계를 극복하고 외부 개발자와 협업할 수 있음 공개된 프로젝트 - 많은 개발자 간의 협력으로 프로젝트를 빠르게 성장 및 발전시킬 수 있음 외부 개발자는 원격 저장소를 fork하여 소스 코드의 버그를 수정하거나 기능을 개선할 수 있음 수정한 소스 코드를 Pull Request하여 기존 코드에 병합할 수 있음

class Node:
    def __init__(self, key = None, parent = None, left = None, right = None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        self.height = 0
    def __str__(self):
        return str(self.key)

class BST:
    def __init__(self):
        self.root = None
        self.size = 0
        self.height = 0
    def __len__(self):
        return self.height
    def __iter__(self):
        return self.root.__iter__()
    def __str__(self):
        return " - ".join(str(k) for k in self)
    def preorder(self, v): #MLR
        if v:
            print(v.key, end=' ')
            self.preorder(v.left)
            self.preorder(v.right)
    def inorder(self, v): #LMR
        if v:
            self.inorder(v.left)
            print(v.key, end= ' ')
            self.inorder(v.right)
    def postorder(self, v): #LRM
        if v:
            self.postorder(v.left)
            self.postorder(v.right)
            print(v.key, end=' ')

    def find_loc(self, key): # key가 트리에 있으면 해당 노드 리턴, 없으면 해당 노드가 삽입될 곳의 부모노드 리턴 
        if self.size == 0: # 트리가 비었을때 None 리턴
            return None
        p = None
        v = self.root
        while v:
            if v.key == key:
                return v
            elif v.key > key:
                p = v
                v = v.left
            else:
                p = v
                v = v.right
        return p # 삽입될 곳의 부모노드 p 리턴

    def search(self, key):
        p = self.find_loc(key)
        if p and p.key == key: # p가 있고, key값이 같을 때 p 리턴 
            return p
        else:
            return None # 없으면 None 리턴

    def insert(self, key):
        v = Node(key) # key값을 가진 노드 v 생성
        if self.size == 0: # 빈 트리이면 v는 루트노드
            self.root = v
        else:
            p = self.find_loc(key)
            if p and p.key != key: # p가 존재하지만 key값이 다를 때 v의 위치 정하기
                if p.key > key:
                    p.left = v
                else:
                    p.right = v
                v.parent = p # p,v는 부모자식 관계 설정
        self.size += 1
        return v #삽입된 노드 v 리턴

    def update_node_height(self,v):
        if v:
            l = v.left.height if v.left else -1
            r = v.right.height if v.right else -1
            v.height = max(l, r) + 1

    def update_height(self, v):
        while v != None:
            self.update_node_height(v)
            v = v.parent

    def deleteByMerging(self, x):
        if x == None:
            return None
        a = x.left
        b = x.right
        pt = x.parent
        # c는 삭제될 x 위치에 올 노드
        # s는 균형이 깨질 가능성이 있는 첫 번째 노드
        if a == None: # x의 왼쪽 부트리가 없을 때
            c = b # x의 오른쪽 부트리인 b를 그대로 c위치로 이동
            s = pt # x가 삭제되었기때문에 균형이 깨질 가능성이 큰 노드는 x의 부모노드인 pt
        else: # a가 있을 때 
            c = a # a를 c자리에 올림
            m = a # m을 a에서 가장 큰 노드로 두고 그걸 찾기 위함.
            while m.right:
                m = m.right
            m.right = b # m의 오른쪽 자식으로 b를 연결 
            if b: # b가 있으면 b의 부모를 m으로 연결
                b.parent = m
            s = m # m에 b가 추가되었으므로 m은 균형이 깨질 수 있다.
        if self.root == x: # x가 루트노드이면 c를 루트노드로 올림 
            if c:
                c.parent = None
            self.root = c
        else: # x가 루트노드가 아닐 때 x자리에 c노드 넣기 
            if pt.left == x:
                pt.left = c
            else:
                pt.right = c
            if c: # c가 있으면 c의 부모를 pt로 연결
                c.parent = pt
        self.size -= 1
        return s

    def deleteByCopying(self, x):
        a = x.left
        b = x.right
        pt = x.parent
        if a: #x의 왼쪽 부트리만 있는 경우
            y = a
            while y.right: #y를 a에서 가장 큰 값으로 설정
                y = y.right
            x.key = y.key #값 Copy
            if y.left: #y의 왼쪽 부트리가 있는 경우
                if y == y.parent.right: #y가 y.parent의 오른쪽에 있을 때 
                    y.parent.right = y.left
                else: #y가 y.parent의 왼쪽에 있을 때  *****y가 x.left일때 즉, while문을 한번도 안돌았을 경우우
                    y.parent.left = y.left
                y.left.parent = y.parent
            else: #y가 리프노드일 경우 y와 y의 부모자식 관계를 없앰
                if y == y.parent.right:
                    y.parent.right = None
                else:
                    y.parent.left = None
            self.size -= 1
        elif a == None and b != None: #왼쪽은 없고 오른쪽만 있는 경우 
            y = b
            while y.left: #y를 b에서 가장 작은 값으로 설정
                y = y.left
            x.key = y.key #값 Copy
            if y.right: # x의 오른쪽 부트리에서 가장 작은 값 y에 오른쪽 자식이 있는 경우 
                if y == y.parent.left: #y가 y의 부모의 왼쪽에 있는 경우
                    y.parent.left = y.right
                else:
                    y.parent.right = y.right #y가 y의 부모의 오른쪽에 있는 경우 
                y.right.parent = y.parent
            else: #y가 리프노드일 경우 y와 y의 부모자식 관계를 없앰 
                if y == y.parent.left:
                    y.parent.left = None
                else:
                    y.parent.right = None
            self.size -= 1
        elif a == None and b == None: #x가 리프노드일 경우 
            if pt: #x의 부모노드가 있는 경우 
                if x == pt.right: #x가 x의 부모의 오른쪽 자식일 때 관계 지우기 
                    pt.right = None
                elif x == pt.left: #x가 x의 부모의 왼쪽 자식일 때 관계 지우기 
                    pt.left = None
            else: #x가 리프노드인데 부모노드가 없는 경우 = x는 루트노드
                self.root = None
            self.size -= 1
        return pt

    def rotateRight(self, z):
        if z == None: # 돌릴게 없다. 
            return
        x = z.left # z의 왼쪽 자식 x 
        if x == None: # x가 없으면 돌릴게 없다. 
            return
        b = x.right # x의 오른쪽 자식 b 
        x.parent = z.parent # 회전 시작. x의 부모가 z의 부모노드가 되도록. 
        if z.parent: # z의 부모가 있을때 z의 자리에 x를 넣음.
            if z.parent.left == z:
                z.parent.left = x
            else:
                z.parent.right = x
        x.right = z # x의 오른쪽에 z
        z.parent = x # x,z 부모자식관계 형성
        z.left = b #x의 오른쪽 자식이였던 b가 이젠 z의 왼쪽 자식으로
        if b: # b,z 부모자식관계 형성
            b.parent = z
        if z == self.root: # z가 루트노드였을 경우
            self.root = x
        self.update_node_height(x) # 높이 업데이트 
        self.update_node_height(z)

    def rotateLeft(self, x):
        if x == None:
            return
        z = x.right # z는 x의 오른쪽 자식
        if z == None:
            return
        b = z.left # b는 z의 왼쪽 자식 
        z.parent = x.parent # 회전 시작. z의 부모노드가 x의 부모노드가 되도록. 
        if x.parent: # x의 부모가 있을 때 x의 자리에 z를 넣음. 
            if x.parent.left == x:
                x.parent.left = z
            else:
                x.parent.right = z
        z.left = x # z의 왼쪽에 z
        x.parent = z # x,z 부모자식관계 형성성
        x.right = b # z의 왼쪽 자식이였던 b가 이젠 x의 오른쪽 자식으로
        if b: # b,x 부모자식관계 형성
            b.parent = x
        if x == self.root: # x가 루트노드였을 경우 
            self.root = z
        self.update_node_height(x) # 높이 업데이트 
        self.update_node_height(z)

class AVL(BST):
    def __init__(self):
        super().__init__()

    def rebalance(self, x, y, z): # rebalancing한 후 원래 z 노드 자리로 올라온 노드 리턴
        if z == None: # z가 없으면 아무것도 안함. 
            return
        if y == z.left and x == y.left: #왼쪽으로 z-y-x 일직선
            self.rotateRight(z)
            return y
        elif y == z.left and x == y.right: #왼쪽으로 z-y-x 삼각형
            self.rotateLeft(y)
            self.rotateRight(z)
            return x
        elif y == z.right and x == y.right: #오른쪽으로 z-y-x 일직선
            self.rotateLeft(z)
            return y
        elif y == z.right and x == y.left: #오른쪽으로 z-y-x 삼각형 
            self.rotateRight(y)
            self.rotateLeft(z)
            return x

    def insert(self, key):
        v = super(AVL, self).insert(key) #BST의 insert 호출
        current = v # v를 current라고 저장 (return v 하기 위함.)
        while current: # current가 있을 때 
            left_height = current.left.height if current.left else -1 # current의 오른쪽 왼쪽 부트리 높이 구하기
            right_height = current.right.height if current.right else -1
            if abs(left_height - right_height) > 1: #균형이 깨졌는지 체크
                z = current #균형이 깨진 첫 번째 노드 z로 지정
                if left_height>right_height: # 더 노드가 많은쪽에 z의 자식으로 y 지정 
                    y = z.left 
                else:
                    y = z.right
                if y: # y가 있을 때 
                    y_left_height = y.left.height if y.left else -1 # y의 오른쪽 왼쪽 부트리 높이 구하기 
                    y_right_height = y.right.height if y.right else -1
                    if y_left_height>y_right_height: # 더 노드가 많은쪽에 y의 자식으로 x 지정 
                        x = y.left
                    else:
                        x= y.right
                    if x and y and z: # x, y, z가 다 있으면 균형맞추기 시작
                        self.rebalance(x,y,z)
                break # 균형 다 맞췄으면 중단 
            current = current.parent # 삽입된 노드의 부모로 균형이 깨질수 있는 노드 추적하기 
        return v # 삽입된 노드 리턴 

    def delete(self, u):
        v = super(AVL, self).deleteByCopying(u) #BST의 deleteByCopying 호출 
        while v: # v가 있는 경우 
            v_left_height = v.left.height if v.left else -1
            v_right_height = v.right.height if v.right else -1
            if abs(v_left_height - v_right_height) > 1: # v에서 균형이 께졌는지 확인
                z = v # 균형이 깨진 첫 번째 노드 z로 지정 
                if z.left.height >= z.right.height: # 더 노드가 많은 쪽에 z의 자식으로 y 지정
                    y = z.left
                else:
                    y = z.right
                if y: # y가 있을 때 
                    y_left_height = y.left.height if y.left else -1
                    y_right_height = y.right.height if y.right else -1
                    if y_left_height >= y_right_height: # 더 노드가 많은 쪽에 y의 자식으로 x 지정 
                        x = y.left
                    else:
                        x = y.right
                    if x and y and z: # x, y, z가 다 있으면 균형맞추기 시작작
                        new_top = self.rebalance(x,y,z)
                        v = new_top.parent #균형 다 맞춰진 노드의 부모를 v로 재 지정 
                        continue # while문으로 돌아가서 부모노드를 추적하면서 rebalancing하기 
            w = v # 마지막으로 검사한 노드 기억하기
            v = v.parent # 루트노드까지 균형 재검사
        self.root = w # 회전으로 루트노드가 바뀌었을 때 루트노드 정확히 설정하기

AVL 트리 수행시간, 회전 횟수 정리

class Node:
    def __init__(self, key = None, parent = None, left = None, right = None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        self.height = 0
    def __str__(self):
        return str(self.key)

class BST:
    def __init__(self):
        self.root = None
        self.size = 0
        self.height = 0
    def __len__(self):
        return self.height
    def __iter__(self):
        return self.root.__iter__()
    def __str__(self):
        return " - ".join(str(k) for k in self)
    def preorder(self, v): #MLR
        if v:
            print(v.key, end=' ')
            self.preorder(v.left)
            self.preorder(v.right)
    def inorder(self, v): #LMR
        if v:
            self.inorder(v.left)
            print(v.key, end= ' ')
            self.inorder(v.right)
    def postorder(self, v): #LRM
        if v:
            self.postorder(v.left)
            self.postorder(v.right)
            print(v.key, end=' ')

    def find_loc(self, key): # key가 트리에 있으면 해당 노드 리턴, 없으면 해당 노드가 삽입될 곳의 부모노드 리턴 
        if self.size == 0: # 트리가 비었을때 None 리턴
            return None
        p = None
        v = self.root
        while v:
            if v.key == key:
                return v
            elif v.key > key:
                p = v
                v = v.left
            else:
                p = v
                v = v.right
        return p # 삽입될 곳의 부모노드 p 리턴

    def search(self, key):
        p = self.find_loc(key)
        if p and p.key == key: # p가 있고, key값이 같을 때 p 리턴 
            return p
        else:
            return None # 없으면 None 리턴

    def insert(self, key):
        v = Node(key) # key값을 가진 노드 v 생성
        if self.size == 0: # 빈 트리이면 v는 루트노드
            self.root = v
        else:
            p = self.find_loc(key)
            if p and p.key != key: # p가 존재하지만 key값이 다를 때 v의 위치 정하기
                if p.key > key:
                    p.left = v
                else:
                    p.right = v
                v.parent = p # p,v는 부모자식 관계 설정
        self.size += 1
        return v #삽입된 노드 v 리턴

    def update_node_height(self,v):
        if v:
            l = v.left.height if v.left else -1
            r = v.right.height if v.right else -1
            v.height = max(l, r) + 1

    def update_height(self, v):
        while v != None:
            self.update_node_height(v)
            v = v.parent

    def deleteByMerging(self, x):
        if x == None:
            return None
        a = x.left
        b = x.right
        pt = x.parent
        # c는 삭제될 x 위치에 올 노드
        # s는 균형이 깨질 가능성이 있는 첫 번째 노드
        if a == None: # x의 왼쪽 부트리가 없을 때
            c = b # x의 오른쪽 부트리인 b를 그대로 c위치로 이동
            s = pt # x가 삭제되었기때문에 균형이 깨질 가능성이 큰 노드는 x의 부모노드인 pt
        else: # a가 있을 때 
            c = a # a를 c자리에 올림
            m = a # m을 a에서 가장 큰 노드로 두고 그걸 찾기 위함.
            while m.right:
                m = m.right
            m.right = b # m의 오른쪽 자식으로 b를 연결 
            if b: # b가 있으면 b의 부모를 m으로 연결
                b.parent = m
            s = m # m에 b가 추가되었으므로 m은 균형이 깨질 수 있다.
        if self.root == x: # x가 루트노드이면 c를 루트노드로 올림 
            if c:
                c.parent = None
            self.root = c
        else: # x가 루트노드가 아닐 때 x자리에 c노드 넣기 
            if pt.left == x:
                pt.left = c
            else:
                pt.right = c
            if c: # c가 있으면 c의 부모를 pt로 연결
                c.parent = pt
        self.size -= 1

    def deleteByCopying(self, x):
        a = x.left
        b = x.right
        pt = x.parent
        if a: #x의 왼쪽 부트리만 있는 경우
            y = a
            while y.right: #y를 a에서 가장 큰 값으로 설정
                y = y.right
            x.key = y.key #값 Copy
            if y.left: #y의 왼쪽 부트리가 있는 경우
                if y == y.parent.right: #y가 y.parent의 오른쪽에 있을 때 
                    y.parent.right = y.left
                else: #y가 y.parent의 왼쪽에 있을 때  *****y가 x.left일때 즉, while문을 한번도 안돌았을 경우우
                    y.parent.left = y.left
                y.left.parent = y.parent
            else: #y가 리프노드일 경우 y와 y의 부모자식 관계를 없앰
                if y == y.parent.right:
                    y.parent.right = None
                else:
                    y.parent.left = None
            self.size -= 1
        elif a == None and b != None: #왼쪽은 없고 오른쪽만 있는 경우 
            y = b
            while y.left: #y를 b에서 가장 작은 값으로 설정
                y = y.left
            x.key = y.key #값 Copy
            if y.right: # x의 오른쪽 부트리에서 가장 작은 값 y에 오른쪽 자식이 있는 경우 
                if y == y.parent.left: #y가 y의 부모의 왼쪽에 있는 경우
                    y.parent.left = y.right
                else:
                    y.parent.right = y.right #y가 y의 부모의 오른쪽에 있는 경우 
                y.right.parent = y.parent
            else: #y가 리프노드일 경우 y와 y의 부모자식 관계를 없앰 
                if y == y.parent.left:
                    y.parent.left = None
                else:
                    y.parent.right = None
            self.size -= 1
        elif a == None and b == None: #x가 리프노드일 경우 
            if pt: #x의 부모노드가 있는 경우 
                if x == pt.right: #x가 x의 부모의 오른쪽 자식일 때 관계 지우기 
                    pt.right = None
                elif x == pt.left: #x가 x의 부모의 왼쪽 자식일 때 관계 지우기 
                    pt.left = None
            else: #x가 리프노드인데 부모노드가 없는 경우 = x는 루트노드
                self.root = None
            self.size -= 1

BST 이진탐색트리에서의 수행시간

insert : O(h) search, find_loc : O(h) deleteByMerging, deleteMyCopying : O(h)

: 프로그래밍 언어의 형식을 분석하고, 데이터를 이해하며, 실행방식으로 변환하는 핵심 과정

Abstract syntax tree (AST)

: 분석을 위한 필요한 구문론적 구조를 제공 : 가장 대중적으로 사용되는 tree 구조

AST as List 선언 (node-name node-left node-right)

EXERCISE

1. 2+3 --> (+ 2 3)

2. CFG : -> + code : 2+3 AST as list : (+ (int 2) (int 3))

3. code : A = 2+3 s-exp : (= A (+ 2 3))

4. begin a=2; c=a+3; end

AST as list : (= a 2), (= c (+ a 3)) AST의 마지막 자식은 항상 terminal이다.

S-expr : (prog (prog (assign a 2)) (assign c (+ a 3)))

Parsing Method

1. Top-down parsing : start-symbol 에서 시작하여 점진적으로 입력문자와 일치할 때까지 확장한다. : 더 복잡한 코드를 설명하기에 용이하다. : 좌측 재귀 처리에 어려움이 있다.

2. Bottom-up parsing : 입력 문자에서 시작해서, 점진적으로 start-symbol까지 줄어든다. : 구현이 복잡하다.