Computer Science
[UPL] Recursion
[UPL] Recursion
2025.05.18함수 몸체에서 자기자신을 직접 호출하는것도 재귀인자기가 부른 함수가 자기를 호출하는것도 재귀라고 할 수 있다. (간접 재귀) 조건 분기문을 추가한 언어인 CFVAE에서는 함수 몸체에서 함수 자신을 호출할 때 아직 자신이 정의되지 않은 상태라 저장소에 들어오지 않았고, 따라서 Recursion이 불가능하다. OCaml처럼 Concrete Syntax에 rec키워드를 추가해 rec가 붙어있으면 재귀호출이 가능한 함수, 붙어있지 않으면 재귀호출이 불가능한 함수로 구분해서 구현할 수 있는 RCFVAE 언어를 정의해보자. 일단 Concrete Syntax 먼저.. 함수를 선언할 때 rec 키워드를 붙일 수 있도록 하자. 기존 함수 정의를 사용할 때, expr1에서 var는 free identifier였지만..
[Operating System] Memory Management
[Operating System] Memory Management
2025.05.17RAID는 Redundant Array of Inexpensive(Independent) Disk의 약자로 저렴한 디스크를 여러개 사용해 품질이 좋은 디스크 하나의 효과를 내는 구성방법이다. 개인용 컴퓨터의 디스크는 비교적 저렴한 디스크를 사용해 용량도 적고 하드웨어 신뢰성도 떨어진다.보통 용량이 큰 디스크는 기업이나 공공기관이 사용한다. RAID가 도입된 시기에는 디스크 용량이 커질수록 가격은 훨씬 더 커졌고, 저용량 디스크를 조합해서 고품질 디스크를 구현하는 RAID 기술이 도입됐다. 그림은 디스크 4개를 조합해 RAID 0 (non-redundant)구조를 구현한 예시이다. strip이라는 정보 단위를 저장하고, 각 strip은 여러 디스크에 분산되어 저장된다. 이렇게 저장하면 디스크 하..
[UPL] Conditional Branch
[UPL] Conditional Branch
2025.05.15expression은 값으로 계산되는 코드조각이고, statement는 프로그램의 메모리를 변환시키는 코드조각이다. expression을 계산할 때는 Store에서 Expression을 받아 계산한 Value를 돌려주고,statement를 계산할 때는 Store를 받아 Statement를 실행하면 새로 업데이트한 Store를 돌려준다. 삼항연산자는 조건분기문의 expression 버전으로, 값으로 계산된다. Concrete Syntax를 정의해보자.기존 언어에서 if - then - else 을 추가하고, 크기 비교 연산자와 논리값을 추가하자. Functional Language처럼 분기를 조작할 때는 expression을 사용한다. if - then - else 구문을 사용할 때 어디까지..
[Operating System] Disk Scheduling
[Operating System] Disk Scheduling
2025.05.13일반적으로 디바이스 스케쥴링은 먼저 온 순서대로 진행하는데, 디스크는 선입선출 방식을 사용하지 않는다. 하나의 surface에는 20~1500개의 트랙이 있고, 디스크가 3장일 때 surface는 6개이다.cylinder는 모든 surface에서 같은 번호로 구성된 트랙의 집합을 의미한다. 그림에서 노란색으로 칠해진 트랙의 일부를 sector라고 부르고, 각 sector에는 checksum을 저장한다.가장자리 쪽의 sector는 중심쪽 sector보다 물리적 크기는 크지만, 각 sector는 같은 크기의 정보를 저장할 수 있다. (각속도 조정)checksum은 디스크에 접근할 때 오류를 계산할 때 사용된다. 디스크가 데이터를 읽을 때, 저장된 checksum과 읽은 데이터의 checksum을 비..
[Operating System] I/O Management
[Operating System] I/O Management
2025.05.11I/O 장치는 프린터, 키보드처럼 사람이 사용하는 장치, 디스크 / 센서 / 모뎀 등 장치들 간 통신을 위해 사용되는 장치로 구분된다.일반적으로 사람이 다루는 장치는 데이터 전송률이 낮고, 장치들 사이의 입출력을 담당하는 장치는 데이터 전송률이 높다. 바이트 단위로 데이터를 주고받는 장치를 문자형 장치, 블럭 단위로 데이터를 주고받는 장치를 블럭 장치라고 부른다. 입출력 장치의 종류는 다양한데.. 운영체제는 모든 장치를 지원해야 한다. 하드디스크에서는 금속 판에 정보가 저장된다. Disk Arm은 금속 판의 중앙부터 가장자리로 이동하며 정보를 읽고, 모터를 통해 움직인다. 디스크 하단에는 컨트롤러 보드가 있고, 컨트롤러 보드에는 여러 레지스터들이 부착되어있다. 운영체제가 장치에 명령을 내리면 ..
[Operating System] File System
[Operating System] File System
2025.05.10파일은 보조 기억 장치에 저장되고 전원이 끊기더라도 지워지지 않는 정보의 저장 단위를 의미한다.사용자가 파일을 만들면 운영체제는 그 정보를 저장하는 자료구조를 운영체제 내부에 만들어 파일과 함께 저장한다. 이 자료구조는 파일을 사용하지 않을 때는 보조 기억 장치에 있다가 파일을 사용할 때는 메모리에 올라온다. 이 자료구조를 File Control Block이라고 부른다.이 자료구조는 파일명, 만들어진 시기, 권한을 가진 사람 등 여러 정보를 포함한다. 프로세스가 만들어질 때 함께 생성되는 PCB와 유사하지만.. PCB는 메인 메모리에서 관리되고 FCB는 보조 기억 장치에 저장된다. 사용자가 파일에 접근하려 할 때, 운영체제는 해당 파일이 존재하는지 확인하고 디스크의 어느 위치에 있는지 확인해야 한다..
[UPL] 고차원 함수와 일차원 함수
[UPL] 고차원 함수와 일차원 함수
2025.04.18이전에 정의한 언어인 VAE에 함수를 추가해 F1VAE를 정의해보자 (First Order Function and VAE) 여기서 함수는 수학에서 가져온 용어지만, 수학과는 다르게 같은 값에 대해 다른 출력이 있을 수 있다. (Side Effect)Pure Functional Language는 함수에서도 Side Effect가 없지만.. 우선 일반적인 프로그래밍 언어에서는 함수 호출에 대한 Side Effect가 발생할 수 있다. Higher Order Function - 고차원함수로 함수를 인자로 받거나 반환할 수 있다. (1등 시민)First Order Function - 일차원함수로 함수를 인자로 받을 수 없고, 반환값으로 사용할 수도 없다. (2등 시민) 지금 정의하는 F1VAE는 First O..
[Data Communication] 물리 계층에서의 다중화
[Data Communication] 물리 계층에서의 다중화
2025.04.16여러 사람이 동시에 이야기하면 같은 주파수, 같은 시간에 간섭이 발생해 무슨 말을 하는지 알아듣기 어렵다. 마찬가지로.. 여러 개의 전화기나 컴퓨터도 동시에 서로 같은 전송 매체를 통해 통신하려 하면, 신호가 겹치고 충돌이 발생해 서로의 데이터를 제대로 수신할 수 없다. 케이블, 무선, 광섬유 등 통신 채널은 한정되어있고, 여러 기기가 동시에 사용하려면 한 채널에서 여러 데이터를 보내는 기술이 필요하다.이 기술을 Multiplexing이라고 부르고, 송신 측에서는 Multiplexing으로 데이터를 전송했다면 수신 측에서는 Demultiplexing으로 합쳐진 데이터를 개별 데이터로 분리하는 작업을 수행해야 한다. TDM : 시간 단위로 나눠서 각각 전송하는 기법을 의미한다.FDM : 서로 다른 주파..
[Operating System] Deadlock and Starvation
[Operating System] Deadlock and Starvation
2025.04.13데드락은 두 개 이상의 프로세스가 절대 발생할 수 없는 이벤트를 무한정 기다리는 상황을 의미한다. 프로세스 P는 A자원을 가지고 있고, B자원을 운영체제에게 요청했다.프로세스 Q는 B자원을 가지고 있고, A자원을 운영체제에게 요청하는데... 운영체제는 현재 B자원이 사용할 수 없는 상태이기에 프로세스 A를 Block상태로 변경시키고, 프로세스 B도 같은 이유로 Block상태로 변경시킨다. x축은 프로세스 P가 실행하는 시간을, y축은 프로세스 Q가 실행하는 시간을 의미한다.나머지 루트로 진행하는 경우 아무 문제가 발생하지 않는데.. 3번, 4번 루트로 실행되는 경우 데드락이 발생한다. 한 사람이 P와 Q 프로그램을 작성한다면 데드락이 발생하지 않는 방식으로 작성하겠지만.. P를 작성하는 사람..
[UPL] Arithmetic Expression 정의
[UPL] Arithmetic Expression 정의
2025.04.08Syntax와 Semantics를 정의해 간단한 언어인 Arithmetic Expression을 정의해보자.AE는 정수 사이의 덧셈과 뺄셈으로 구성된다. Concrete Syntax BNF 를 사용해서 정의한다.개발자가 직접 작성하는 코드의 구조와 모양으로, 실제로 코드에서 보게 되는 문자 단위의 문법을 의미한다.파싱에서 중요한 역할을 수행하고, 언어의 문법을 정의할 때 첫 단계로 사용된다. Abstract Syntax프로그램을 나타내는 트리 형태의 구문구조이다.프로그램은 여러 개의 구문으로 구성되고.. 각 구문은 또 세부 구문으로 구성된다. 파서가 이미 파싱해서 AST를 줬고.. 이 AST는 컴파일러나 인터프리터가 사용한다.즉, Concrete Syntax를 파싱하면 Parse Tree가..
[Operating System] Semaphore
[Operating System] Semaphore
2025.04.08한 프로세스가 임계 구역에 접근할 때 CPU Interrupt를 비활성화하면 현재 실행 중인 코드가 중단되지 않아 Critical Section을 보호할 수 있다. 원래는 CPU는 명령어를 실행하고 Interrupt가 발생했는지 매번 확인하는데, Atomic Operation을 실행할 때는 Interrupt를 비활성화한다.이 때 Interrupt를 아예 무시하는건 아니고, Atomic Operation이 마무리 된 후에 그 동안 발생한 Interrpt를 수행하는 방식으로 동작해 처리를 뒤로 미룬다고 생각하자. 시스템 성능 저하 문제 때문..사용자 코드를 Atomic Operation으로 실행하는건 좋지 않지만, Entry Section을 Atomic Operation으로 다루는건 합리적이다. 운영체제는..
[UPL] Syntax & Parsing
[UPL] Syntax & Parsing
2025.04.04프로그래밍 언어는 문자열의 집합이고, 프로그래밍 언어로 작성된 프로그램은 문자열이라고 생각할 수 있다.그렇다고 아무 문자열이나 프로그래밍 언어가 될 수 있는 건 아니다. 특정 문법에 부합해야 프로그래밍 언어가 될 수 있다. 문자열 s가 프로그래밍 언어인지 판단하는 함수 L(G) 를 생각해보자.s가 L(G)의 집합에 포함된다면 s는 프로그래밍 언어라고 할 수 있다. 위의 Chomsky Hierarchy는 언어의 표현력을 나타낸다.사실상 튜링 머신은 존재하지 않고 Regular Language는 프로그래밍 언어를 정의할 때 표현력이 부족해 독립적으로 사용되지 않으니 프로그래밍 언어의 정의는 두 가지로 구분된다. 오토마타는 문자열 s가 L(G) 집합에 포함되는지를 판단한다. Lemail 언어를 집합으로..