no image
백준 1261 알고스팟 node.js
2206번 벽 부수고 이동하기와 매우 유사한 0-1bfs, 데이크스트라 문제이다. 두가지 해결법이 있는데, 0-1bfs로 접근한다면 dist배열에는 2차원 배열에서 해당 좌표까지 도착했을 때 벽을 부순 횟수를 기록하고 벽을 부순 횟수가 더 적을 때 deque에 삽입한다 우리는 최대한 벽을 부수지 않으면서 멀리 갈 수 있어야 한다. 때문에 벽을 부수지 않고 전진하는 경우 deque의 front에 삽입하고 벽을 부수는 경우 deque의 back에 삽입한다. 하지만 이건 내가 데이크스트라를 통해 문제를 해결한 이후에 본 풀이법이다. 데이크스트라로 접근하는 것이 더 이해가 쉬울 수 있다. 기존 데이크스트라는 탐색 시점 최단 거리의 노드를 queue에 넣고, 방문한 노드 기준으로 다시 연결된 노드의 최단거리를 갱..
2024.03.15
no image
[PL] CFG, BNF
CFG(Context Free Grammar) 문맥 자유 문법에 대해 간단하게 말하자면 문맥에 따라, 앞뒤 단어에 따라 의미가 달라지지 않는 문법을 말한다. 대부분의 프로그래밍 언어는 CFG를 사용한다. 문맥 자유 문법은 다음과 같이 정의한다 G = (V,T,P,S)​ V - 변수 혹은 비단말(non Terminal) T - 단말(Terminal)의 집합, 앱실론 ε을 포함 P - 생성(Productions) 규칙 집합 S 는 시작 변수(start variable) Terminal과 Non terminal의 개념이 있다 Terminal - 단말 기호 집합 - 다른 기호로 유도가 불가능함 Non terminal - 비단말 집합, 언어 안에서 다른 문자를 만드는 중간 과정 - 다른 기호로 유도할 수 있음 다..
2024.03.15
코테 대비 MySQL
SELECT 데이터 조회의 기본이 되는 select SELECT name, age FROM users; users 테이블에서 name과 age 칼럼을 선택하여 조회 DISTINCT SELECT DISTINCT country FROM customers; 정렬 및 제한 ORDER BY SELECT name, age FROM users ORDER BY age DESC; users 테이블의 사용자들을 나이가 많은 순으로 정렬 LIMIT SELECT name FROM users ORDER BY signup_date DESC LIMIT 5; 최근에 가입한 5명의 사용자 이름을 조회 데이터 형식과 함수 Date_format SELECT DATE_FORMAT(birthday, '%Y-%m-%d') AS formatte..
2024.03.12
no image
백준 1700 멀티탭 스케줄링 node.js
이 문제는 사실 정석으로 접근했다면 풀지 못했을 것이다. 운영체제 내용과 관련이 있는 흥미로운 문제이다. 스케쥴링은 필요한 자원을 적절히 할당하여 효율적으로 리소스를 활용하는 것이다. 페이징 기법 프로세스가 사용하는 메모리 공간을 잘게 나누어 비연속적으로 사용하는 기법이다. 프로세스 적재를 위해 연속된 메모리를 요구하지 않기 때문에 한정된 메모리 공간을 효율적으로 사용할 수 있다. 가상 메모리 공간의 단위를 page, 물리 메모리 공간을 frame 이라고 하고 둘의 크기는 같다. 하지만 물리 메모리는 한정적이기 때문에, 운영체제는 물리 메모리와 보조 저장공간의 swap 공간을 함께 활용하게 되는데, 이 때 참조한 페이지가 물리 메모리에 올라가 있지 않을 때(invalid) 참조하는 페이지를 교체해서 새롭..
2024.03.12
no image
[OS4] Context Switch, Process Creation, Copy On Write
Context Switch CPU가 실행하는 프로세스를 교체하는 행위이다. 우리 인간은 비싼 CPU 가만히 못놔두기 때문에, 계속 일을 시켜야한다. 문맥전환을 통해 여러 프로세스나 스레드가 동시에 실행할 수 있다(실행하는 것 처럼 보이게 할 수 있다) 컨텍스트 스위칭이 일어나는 경우 - 주어진 Time Slice를 다 사용했을 때 - I/O 작업 - 다른 리소스를 기다림 - 인터럽트 RISC가 상대적으로 레지스터가 더 많기 때문에 컨텍스트 스위칭에 오버헤드가 더 크다. 흥미로운 내용이다. I/O, 인터럽트, 시스템콜 등이 발생하면 PCB에 현재 실행하던 프로세스의 상태를 저장하고 스케쥴링에 의해 선택된 새로운 프로세스의 정보를 PCB에서 받아서 실행한다. 이후 다른 인터럽트가 발생하면 다른 프로세스를 선..
2024.03.12
no image
소프트웨어 마에스트로 15기 코테 후기
일단 2차에서 떨어졌다. 1차 2차 둘 다 5문제가 나왔고 알고리즘 4문제 sql 1문제로 같은 형식이었다. 1차 알고리즘 4문제 중 3문제는 구현 문제였다. 접근방법 보다는 빠르게 푸는 것이 주요했다. 난이도로 따지면 실버 하-중 정도 되는 난이도였고, 그 중 한 문제는 알맞은 자료구조와 메소드를 구현 혹은 사용해야 했기 때문에 시간을 조금 써야 했다. 나머지 한 문제는 결과적으로는 그리디 문제였다고 한다. 주어진 n의 크기는 완전탐색으로 풀 수 없었지만, 나는 방법이 생각이 나지 않아서 완전 탐색에 가까운 백트랙킹으로 작성해서 제출하였다. sql은 코드 자체는 매우 쉬웠지만, 오히려 '알고리즘'스러운 접근이 필요했다고 생각한다. 문법 자체는 sql을 조금만 공부 했다면 풀 수 있는 수준이었다. 결과적..
2024.03.12
no image
SIC/XE Machine
이전 글 : https://sumjo.tistory.com/35 SIC Machine 본 글은 숭실대학교 컴퓨터학부 최재영 교수님의 시스템 프로그래밍 강의와 자료를 기반으로 작성되었습니다 Fetch Decode Execute Cycle Fetch : 프로그램 카운터(PC)에서 실행할 명령어를 명령어 레지 sumjo.tistory.com SIC/XE는 SIC Macine의 확장 모델이다 Memory 기존 2^15에서 2^20으로 커졌다. 메모리에 접근하려면 20bits가 필요함을 의미한다 Registers 기존 5개에서 4개가 추가된다. B - Base Register - used for Addressing S,T - General working - 데이터 저장만 가능하고 연산에는 쓸 수 없다. F - 부..
2024.03.08
no image
SIC Machine
본 글은 숭실대학교 컴퓨터학부 최재영 교수님의 시스템 프로그래밍 강의와 자료를 기반으로 작성되었습니다 Fetch Decode Execute Cycle Fetch : 프로그램 카운터(PC)에서 실행할 명령어를 명령어 레지스터(IR)에 저장한다. 이후 PC는 1 증가시킨다. Decode : 가져온 2진코드를 해독하여 수행할 작업을 결정한다. (opcode, operand를 해석한다) Get Data : 피연산자(operand)를 주기억장치로부터 가져온다 Execute : AlU를 통해서 연산을 수행한다. SIC/XE (Simplified Instructional Computer) 단순화 시킨 가상 컴퓨터의 표준 모델 실제 컴퓨터 모델과 명령어를 이해하기 쉽게 단순화 시켜 놓았다. SIC/XE는 SIC의 확장..
2024.03.08

2206번 벽 부수고 이동하기와 매우 유사한 0-1bfs, 데이크스트라 문제이다.

두가지 해결법이 있는데,

0-1bfs로 접근한다면

 

dist배열에는 2차원 배열에서 해당 좌표까지 도착했을 때 벽을 부순 횟수를 기록하고

벽을 부순 횟수가 더 적을 때 deque에 삽입한다

 

우리는 최대한 벽을 부수지 않으면서 멀리 갈 수 있어야 한다.

때문에 벽을 부수지 않고 전진하는 경우 deque의 front에 삽입하고

벽을 부수는 경우 deque의 back에 삽입한다.

 

하지만 이건 내가 데이크스트라를 통해 문제를 해결한 이후에 본 풀이법이다.

 

데이크스트라로 접근하는 것이 더 이해가 쉬울 수 있다.

기존 데이크스트라는 탐색 시점 최단 거리의 노드를 queue에 넣고, 

방문한 노드 기준으로 다시 연결된 노드의 최단거리를 갱신시켜 주는데

 

이 문제에서는 기준을 최단거리가 아닌 벽을 부순 횟수로 바꾸면 된다.

 

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
})

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', ()=>{

	const [m,n] = input[0].split(' ').map(Number);

	const map = Array.from(Array(n), () => Array(m).fill(0));

	for(let i = 0; i < n; i++){
		const arr = input[i+1].split('').map(Number);
		for(let j = 0; j < m; j++)
			map[i][j] = arr[j];
	}

	const dist = Array.from(Array(n), () => Array(m).fill(Infinity));
	const bfs = () => {
		const q = [];
		q.push([0,0,0]);

		while(q.length > 0){
			const [y_,x_,v] = q.shift();

			const a = [1,-1,0,0];
			const b = [0,0,-1,1];

			for(let i = 0; i < 4; i++){
				const y = y_ + a[i];
				const x = x_ + b[i];
				if(x >= 0 && x < m && y >= 0 && y < n){
					if(map[y][x] === 0 && dist[y][x] > v){
						dist[y][x] = v;
						q.push([y,x,v]);
					}
					else if (map[y][x] === 1 && dist[y][x] > v + 1){
						dist[y][x] = v + 1;
						q.push([y,x,v+1]);
					}
				}
			}
		}
	}

	bfs();
	if(dist[n-1][m-1] === Infinity)
		console.log(0)
	else
		console.log(dist[n-1][m-1]);

})

CFG(Context Free Grammar)

문맥 자유 문법에 대해 간단하게 말하자면 문맥에 따라, 앞뒤 단어에 따라 의미가 달라지지 않는 문법을 말한다.

대부분의 프로그래밍 언어는 CFG를 사용한다.

문맥 자유 문법은 다음과 같이 정의한다

 

G = (V,T,P,S)

 

V - 변수 혹은 비단말(non Terminal)

T - 단말(Terminal)의 집합, 앱실론 ε을 포함

P - 생성(Productions) 규칙 집합

S 는 시작 변수(start variable)

 

Terminal과 Non terminal의 개념이 있다

Terminal

- 단말 기호 집합

- 다른 기호로 유도가 불가능함

 

Non terminal

- 비단말 집합, 언어 안에서 다른 문자를 만드는 중간 과정

- 다른 기호로 유도할 수 있음

 

 

다시 CFG의 정의로 돌아가자면

문법 G는 모든 생성 규칙이 

A -> a

를 따르는 문법을 말한다

A는 V의 원소(non Terminal)

a는 V 혹은 T의 원소이다

 

BNF를 통해서 이해해보자

BNF(Backus–Naur form)

문맥 자유 문법(CFG)을 나타내기 위한 표기법

위에 A -> a 를 따르기 때문에

LHS(Left Hand Side)는 non terminal이고 RHS(Right Hand Side)는 terminal과 non terminal의 문자열이다

 

-> : Production rule

<> : Non terminal

| : Or

 

 

좌측 유도에 의해 <program>을 유도한 과정이다.

<stmts>는 자기 자신으로 재귀적으로 정의되는 모습을 볼 수 있다.

컴파일러 또한 재귀 파서를 통해 파서 트리를 생성한다.

 

위의 과정은 이런 parse tree로 그려볼 수 있는데

여기서 리프 노드의 값

a = b + const

유도된 sentence이다

 

유도(Derivation)

시작  심볼부터 시작해 Non Terminal X에 생성 규칙(productions)를 적용해 Y1, Y2... Yn으로 대치하는 과정이다



S는 aS혹은 b로 정의되기 때문에 재귀적으로

ab, aab, aaab.. 등으로 정의할 수 있지만

aba로 정의될 수는 없다.

E -> E * E | E + E | (E) | N

N -> N D | D

D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

 

좌측 유도(좌측 non terminal 먼저 terminal로 유도)

E

E + E

N + E

D + E

3 + E

를 통해 좌측의 E를 terminal D의 3으로 유도하고

비슷한 원리도

 

3 + E

3 + E * E

3 + N * E

3 + 4 * E

.

.

3 + 4 * 5

로 유도할 수 있다

 

 

Ambiguous

위의 식을 우측 유도 해도 똑같은 문장이 유도되겠지만

파스 트리를 만들었을 때 다른 모양이 만들어진다

유도한 3 + 4 * 5로 보았을 때

좌측유도 시 좌측의 트리처럼 

3의 깊이가 더 얕다 즉 3이 앞에 온다

우측유도 시 우측의 트리 모양이 된다.

 

연산자 우선순위로 봤을 때 *가 +의 앞에 와야 하기 때문에 파서 입장에서 좌측의 트리는 잘못됐다.

이처럼 좌측 유도, 우측 유도 중 하나만 써도 두개 이상의 트리를 가지는 문법은 Ambiguous, G는 모호하다

라고 표현한다.

 

해당 BNF를 각각 우측유도 | 좌측유도를 통해 트리로 바꾸면

모호한 상태인데

 

<OP>를 / 혹은 - 로 정의하여 연산자 간 우선순위를 모호하게 정의한 위의 예시와 달리

<term>에서 / 연산자가 상수(const)와 직접 연결된 구조이고,

- 를 상수로 유도하기 위해서는 term을 한번 더 참조하게 한다.

이를 통해 연산자에 -보다 높은 우선순위를 부여할 수 있고 모호성을 해소할 수 있다.

SELECT

데이터 조회의 기본이 되는 select

SELECT name, age FROM users;

users 테이블에서 name과 age 칼럼을 선택하여 조회

 

DISTINCT

SELECT DISTINCT country FROM customers;

 

정렬 및 제한

ORDER BY

SELECT name, age FROM users ORDER BY age DESC;

users 테이블의 사용자들을 나이가 많은 순으로 정렬

LIMIT

SELECT name FROM users ORDER BY signup_date DESC LIMIT 5;

최근에 가입한 5명의 사용자 이름을 조회

 

데이터 형식과 함수

Date_format

SELECT DATE_FORMAT(birthday, '%Y-%m-%d') AS formatted_date FROM users;

users 테이블의 birthday를 YYYY-MM-DD 형식으로 변환하여 조회

 

Format

숫자를  포맷팅하여 문자열로 반환. 예를 들어 소수점 아래 숫자를 제한하거나 천 단위 구분자를 추가할 수 있다.

SELECT FORMAT(total_price, 2) AS formatted_price
FROM sales;

sales 테이블의 total_price 칼럼을 소수점 둘째 자리까지 포맷팅 하고 천 단위 구분자를 추가하여 반환

 

Year

SELECT YEAR(birthday) AS birth_year
FROM users;

users 테이블의 birthday 칼럼에서 년도를 추출

 

 

CTE(Common Table Expressions)

WITH

with는 서브 쿼리를 지원한다. cte를 정의할 수 있다.

WITH customer_totals AS (
  SELECT customer_id, SUM(amount) AS total_spent
  FROM orders
  GROUP BY customer_id
)
SELECT *
FROM customer_totals
WHERE total_spent > 1000;

with를 통한 서브 테이블 예시. 각 고객의 총 지출 금액을 계산하고, 1000이상 지출한 고객을 찾는다.

 

WITH RECURSIVE number_sequence AS (
  SELECT 0 AS number
  UNION ALL
  SELECT number + 1 FROM number_sequence WHERE number < 24
)
SELECT * FROM number_sequence;

이렇게 재귀를 통해 0부터 24까지의 숫자를 생성할 수도 있다.

 

Group by, Having

GROUP BY는 데이터를 그룹화 한다.

그룹에 조건을 적용할 때는 HAVING을 사용한다

SELECT category, COUNT(*) AS total_products, AVG(price) AS average_price
FROM products
GROUP BY category
HAVING COUNT(*) > 10 AND AVG(price) > 500;

카테고리 별로 제품 수와 평균 가격을 계산한다. 제품 수가 10개를 초과하고, 평균 가격이 400을 넘는 카테고리만 결과로 나타낸다.

 

JOIN + ON

on의 조건을 기준으로 테이블을 결합한다. 그냥 join이라면 on 조건 기준으로 공통된 조건이 없는 행을 버리게 된다.

using(column)으로 사용할 수도 있다.

leftjoin, rightjoin으로 사용될 수 있는데, 각각 좌측과 우측을 기준으로 공통된 조건이 없는 행도 남겨둔다.

SELECT orders.order_id, customers.name
FROM orders
JOIN customers ON orders.customer_id = customers.customer_id;

주문 테이블과 고객 테이블을 customer_id로 조인하여 주문 id와 고객 이름을 조회한다.

 

UNION, UNION ALL

쿼리 결과를 단순히 합친다. 결과가 단순히 행으로 추가되는 테이블이라고 이해할 수 있다.

때문에 쿼리의 결과 칼럼 수가 같아야 한다.

SELECT name FROM products
UNION ALL
SELECT name FROM services;

producs와 services 테이블에서 name을 조회하여 모든 결과를 합친다.

 

 

 

 

 

 

ORDERS 테이블

customer_id order_date product_id amount
1 2024-03-10 101 200
2 2024-03-11 103 150
1 2024-03-15 102 300

 

produus 테이블

product_id category price
101 Books 200
102 Electronics 300
103 Books 150

 

 

WITH recent_orders AS (
  SELECT customer_id, MAX(order_date) AS last_order_date
  FROM orders
  GROUP BY customer_id
)
SELECT o.customer_id, o.last_order_date, p.category, SUM(p.price) AS total_spent
FROM recent_orders o
JOIN orders od ON o.customer_id = od.customer_id AND o.last_order_date = od.order_date
JOIN products p ON od.product_id = p.product_id
GROUP BY o.customer_id, p.category
HAVING SUM(p.price) > 500;

각 고객의 최근 주문 날짜를 찾고, 해당 주문에서 특정 카테고리의 제품에 500이상 지출한 고객을 식별한다.

 

쿼리 실행 결과

customer_id last_order_date category total_spent
1 2024-03-15 Electronics 300

 

최근 주문에서 Electronics 카테고리에 300의 금액을 지출했다는 것을 보여준다. 고객 2의 최근 주문은 총 지출액이 500보다 낮은 150이기 때문에 HAVING절에 의해 결과에서 제외된다.

'데이터베이스' 카테고리의 다른 글

[블로그 프로젝트] ERD EDITOR  (0) 2024.01.11

 

이 문제는 사실 정석으로 접근했다면 풀지 못했을 것이다. 운영체제 내용과 관련이 있는 흥미로운 문제이다.

스케쥴링은 필요한 자원을 적절히 할당하여 효율적으로 리소스를 활용하는 것이다.

페이징 기법

 

프로세스가 사용하는 메모리 공간을 잘게 나누어 비연속적으로 사용하는 기법이다.

프로세스 적재를 위해 연속된 메모리를 요구하지 않기 때문에 한정된 메모리 공간을 효율적으로 사용할 수 있다.

가상 메모리 공간의 단위를 page, 물리 메모리 공간을 frame 이라고 하고 둘의 크기는 같다.

하지만 물리 메모리는 한정적이기 때문에, 운영체제는 물리 메모리와 보조 저장공간의 swap 공간을 함께 활용하게 되는데,

이 때 참조한 페이지가 물리 메모리에 올라가 있지 않을 때(invalid) 참조하는 페이지를 교체해서 새롭게 물리 메모리에 적재해야 한다.

 

여기서 사용하는 것이 페이지 교체 알고리즘이다

 

페이지 교체 알고리즘 (Page Replacement Algorithm)

페이지 교체 알고리즘에는 여러가지가 있다.

 

FIFO - 가장 먼저 메모리에 올라온 페이지를 교체한다

LRU - 가장 오랫동안 사용되지 않은 페이지를 교체한다

 

그 중에서 OPT(Optimal) 알고리즘이 있다.

이름부터가 Optimal..

 

OPT(Optimal) 알고리즘

 

페이지를 교체 하려는 시점에서, 이후에 페이지가 참조될 시점이 가장 늦은 페이지를 교체한다.

즉 가장 오랫동안 사용되지 않을 페이지를 교체하는 것이다

 

그림으로 봤을 때, 첫번째 교체 시점에서 1이 가장 나중에 참조되기 때문에 1을 3으로 교체하고

4를 교체해야 하는 시점에서 뒤에 바로 나오는 2,3을 고려해 0을 교체한다.

다시 0을 교체해야 할 때는 이후 4는 참조되지 않기 때문에 4와 0 을 교체한다.

 

이는 가장 적은 page fault를 보장하는 최적화 알고리즘이다.

하지만 실제로는 운영체제 입장에서 앞으로 사용할 페이지를 알아야 하기 때문에 구현하기 어렵다. 

 

 

그러나,

이 문제에서는 용품의 사용 순서가 주어지기 때문에 우리는 미래를 알고있다.

가장 적은 교체, 가장 적은 페이지 부재를 보장하는 Optimal을 적용해서

교체가 필요한 시점을 기준으로 가장 늦게 사용하는 용품을 교체해주면 되겠다.

 

그래서 이 관련없어 보이는 얘기를 한 것이다.

운영체제 내용으로 조금 야매로 풀었지만 그래서 오히려 재밌는 문제다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {

	const [n,k] = input[0].split(' ').map(Number);

	const con = Array(n).fill(0);
	const arr = Array(k);

	const tmp = input[1].split(' ').map(Number);
	for(let i = 0; i < k; i++)
		arr[i] = tmp[i];

	const find_least = (idx) => {

		let tmp = -Infinity;
		let index;

		for(let i = 0; i < con.length; i++){
			let num = 0;
			for(let j = idx; j < arr.length; j++){
				if(arr[j] !== con[i])
					num++;
				else
					break;
			}
			if (tmp < num) {
					tmp = num;
					index = i;
				}
			}
			return index;
		}

	let answer = 0;
	for(let i = 0; i < k; i++){

		if(con.indexOf(arr[i]) !== -1)
			continue;

		const idx = con.indexOf(0);

		if(idx !== -1)
			con[idx] = arr[i];
		else{
			const index = find_least(i);
			con[index] = arr[i];
			answer += 1;
		}
	}

	console.log(answer);
})

 

 

 

 

 

 

 

Context Switch

CPU가 실행하는 프로세스를 교체하는 행위이다.

우리 인간은 비싼 CPU 가만히 못놔두기 때문에, 계속 일을 시켜야한다.

문맥전환을 통해 여러 프로세스나 스레드가 동시에 실행할 수 있다(실행하는 것 처럼 보이게 할 수 있다)

 

컨텍스트 스위칭이 일어나는 경우

- 주어진 Time Slice를 다 사용했을 때

- I/O 작업

- 다른 리소스를 기다림

- 인터럽트

RISC가 상대적으로 레지스터가 더 많기 때문에 컨텍스트 스위칭에 오버헤드가 더 크다. 흥미로운 내용이다.

 

I/O, 인터럽트, 시스템콜 등이 발생하면 PCB에 현재 실행하던 프로세스의 상태를 저장하고

스케쥴링에 의해 선택된 새로운 프로세스의 정보를 PCB에서 받아서 실행한다.

이후 다른 인터럽트가 발생하면 다른 프로세스를 선택하고 상태값을 받아와서 실행하기 때문에

마치 끊기지 않고 동시에 실행되는 것 처럼 보인다.

 

Process Creation

UNIX 기준 프로세스를 새로 생성하면 자식 프로세스는 기본적으로 부모 프로세스의 복사본이다. PID는 다르다.

이는 효율성을 위해서다. 프로세스 새로 생성하려면 많은 데이터가 필요하고 이는 리소스를 많이 사용한다는 의미이다.

때문에, 새로운 프로세스를 생성할 때는 fork()를 통해 일단 부모 프로세스의 데이터를 복사한 뒤 exec하는 방법을 택한다.

exec() 함수는 PCB를 실행하려는 프로세스의 정보로 전부 교체한다. return을 포함해서 말이다.

즉 새로운 프로그램을 적재하게 되는 것이다.

 

근데 여기서도 의문을 제기할 수 있다. 기껏 fork 했는데 exec하느라 프로세스 정보를 전부 교체한다면 비효율 적이잖아요.

이런 비효율도 해결하기 위해 대부분의 OS에서는 Copy On Write(COW)를 채택한다

Copy On Write

 

자세한 Virtual Memory 개념은 나중에 작성할 예정이다.

페이지 테이블은 논리 주소와 피지컬 어드레스를 맵핑시켜주는 자료 구조이다.

프로세스는 각자 페이지 테이블을 가지는데, 처음에 자식 프로세스를 생성하면 부모 프로세스의 페이지 테이블을 복사하게 된다.

페이지 테이블과 맵핑되는 physical memory, 즉 부모 프로세스와 자식 프로세스의 변수가 같은 물리 공간을 가리키고 있다는 의미이다.

프로세스가 생성될 때 공유 자원에 관해서 read-only로 생성된다.

때문에 공유 자원에 대해서 write하려고 했을 때 page fault가 발생하게 되고 page fault handler를 호출한다.

핸들러는 write하려는 페이지를 새로운 페이지에 복사한 뒤 페이지 테이블을 업데이트 시켜준다.

fork 시스템콜 시점이 아닌 write하려는 시점에 복사가 일어나기 때문에

Copy On Write 라고 한다.

 

 

 

 

일단 2차에서 떨어졌다.

1차 2차 둘 다 5문제가 나왔고

알고리즘 4문제 sql 1문제로 같은 형식이었다.

 

1차

알고리즘 4문제 중 3문제는 구현 문제였다.

접근방법 보다는 빠르게 푸는 것이 주요했다.

난이도로 따지면 실버 하-중 정도 되는 난이도였고,

그 중 한 문제는 알맞은 자료구조와 메소드를 구현 혹은 사용해야 했기 때문에 시간을 조금 써야 했다.

 

나머지 한 문제는 결과적으로는 그리디 문제였다고 한다.

주어진 n의 크기는 완전탐색으로 풀 수 없었지만,

나는 방법이 생각이 나지 않아서 완전 탐색에 가까운 백트랙킹으로 작성해서 제출하였다.

 

sql은 코드 자체는 매우 쉬웠지만,

오히려 '알고리즘'스러운 접근이 필요했다고 생각한다.

문법 자체는 sql을 조금만 공부 했다면 풀 수 있는 수준이었다.

 

결과적으로 4솔했다. 무난하게 통과하리라 생각했지만,

오픈카톡방 기준으로 4솔이 거의 커트라인이어서 많이 놀랐다.

지원자가 많아서 체감상 40퍼센트 정도 남긴 것 같다.

 

2차

난이도는 확 올라갔다.

sql을 포함해서 그냥 주는 문제는 1번 한문제밖에 없었다.

sql이 매우 어렵게 나와서 대다수가 못풀었을 것이다. 나중에 보니 sql 변수 개념을 통해 풀 수 있었다고 한다.

물론 복잡한 join을 통해서도 풀 수 있었겠지만 실전에서 다시 만나도 못풀었을 것이다.

 

1번이 실버 3정도 됐던 것 같아서 풀고, 나머지는 문제 이해가 힘들었기 때문에

그나마 할만했던 3번에 모든 시간을 다 쏟았다.

 

3번은 분할정복까진 쉽게 떠올릴 수 있었는데, 나머지 조건들을 떠올리기 쉽지 않았다.

끝까지 고민했지만 결국 테케만 겨우 맞춰서 제출했다. 0.5솔로 보기도 힘들 것 같다.

 

최종적으로 1솔로 2차를 마무리 했다고 생각 한다.

 

 

1솔 합격도 꽤 있었는데, 아마 어려운 문제 1솔이지 않을까 싶다.

아쉽게 됐지만 코테에서 나름의 경쟁력을 확인한 것 같다.

 

 

 

 

 

'후기' 카테고리의 다른 글

[우아한 테크코스] 돌발 행동을 하지 말자  (0) 2023.10.26

이전 글 : https://sumjo.tistory.com/35

 

SIC Machine

본 글은 숭실대학교 컴퓨터학부 최재영 교수님의 시스템 프로그래밍 강의와 자료를 기반으로 작성되었습니다 Fetch Decode Execute Cycle Fetch : 프로그램 카운터(PC)에서 실행할 명령어를 명령어 레지

sumjo.tistory.com

 

SIC/XE는 SIC Macine의 확장 모델이다

 

Memory

기존 2^15에서 2^20으로 커졌다.

메모리에 접근하려면 20bits가 필요함을 의미한다

 

Registers

기존 5개에서 4개가 추가된다.

B - Base Register - used for Addressing

S,T - General working - 데이터 저장만 가능하고 연산에는 쓸 수 없다.

F - 부동 소수점 지원을 위한 레지스터, 48bit다

sign비트, 진수부 가수부로 구성된다

 

 

Instruction Format

15승에서 늘어난 20승의 메모리 비트를 지원해야 하겠다.

방법은 2가지를 떠올릴수 있다.

1. address 필드를 20비트로 확장

2. 상대주소 사용

 

이 2가지 옵션을 바탕으로 4가지 포멧을 사용한다.

n,i,x,b,p,e 는 addressing mode를 지정하는 flag bit들이다.

 

 

Format 1 (1 byte)

메모리 참조하지 않음. 피연산자 없고 Opcode만 존재

 

Format 2 (2 byte)

이것도 메모리 참조하지 않는다. 레지스터에 저장돼있는 값에 대한 연산이다.

r1과 r2에는 레지스터에 대한 고유 번호를 담고 있다.

 

3형식과 4형식은 e비트에 따라 결정된다

 

Format 3 (3 byte) e = 0

Relative addressing, 상대 주소를 위한 형식이다.

그럼에도 12비트이기 때문에 모든 메모리를 표현할 수는 없다.

 

Format 4 (4 byte) e = 1

address field가 20비트로 확장되어 모든 주소를 절대주소로 표현할 수 있다.

 

 

Addressing Modes

 

 

base relative for format 3(b = 1, p = 0)

베이스 레지스터를 기준으로 상대 주소를 사용한다.

base relative는 베이스 레지스터 기준 상위 주소값으로의 접근만 가능하다

TA = (B) + disp

 

PC relative for format 3 (b = 0, p = 1)

PC를 기준으로 상대 주소 사용

PC를 기준으로 위 아래 주소값 모두 이동 가능하기 때문에 signed 2^12승 값을 사용한다.

-2048 <= disp <= 2047

 

Direct Mode for format 3 4 (b = 0, p = 0) 

주소 필드를 절대 주소로 사용한다.

TA = disp

 

이 모드들은 x플래그(인덱싱)과 함께 사용할 수 있다.

 

 

 

Immediate addressing n = 0, i = 1

no reference addressing field 값이 직접 값으로 연산에 사용된다.

 

n = 1, i = 0

address에 있는 주소를 참조값으로 사용한다.

즉 메모리에 있는 값을 활용

 

n = 0, i = 0

sic

n = 1, i = 1

sic/xe

 

e = 0 -> format 3

e = 1 -> format 4

 

 

'시스템프로그래밍' 카테고리의 다른 글

SIC Machine  (0) 2024.03.08

본 글은 숭실대학교 컴퓨터학부 최재영 교수님의 시스템 프로그래밍 강의와 자료를 기반으로 작성되었습니다


 

컴퓨터 시스템 기본 구조

Fetch Decode Execute Cycle

Fetch : 프로그램 카운터(PC)에서 실행할 명령어를 명령어 레지스터(IR)에 저장한다. 이후 PC는 1 증가시킨다.

Decode : 가져온 2진코드를 해독하여 수행할 작업을 결정한다. (opcode, operand를 해석한다)

Get Data : 피연산자(operand)를 주기억장치로부터 가져온다

Execute : AlU를 통해서 연산을 수행한다.

 

SIC/XE (Simplified Instructional Computer)

 

단순화 시킨 가상 컴퓨터의 표준 모델

실제 컴퓨터 모델과 명령어를 이해하기 쉽게 단순화 시켜 놓았다.

SIC/XE는 SIC의 확장된 모델이다.

사양(?)을 살펴보자

 

Memory

byte와 word라는 단위를 사용한다

1byte는  8bit로 동일하고

1 word - 3byte(24bit)를 말한다.

 

최대 메모리는 2^15승이다. 메모리 표현을 위해서는 15비트가 필요하다.

 

Registers

SIC모델은 24bits(3bytes, 1word)의 5개 레지스터를 가진다

 

A - accumulator - 누산기로 연산 값이 누적되는 레지스터

X - index(반복문) - X값만큼 주소값에 더해주는 형태

L - Linkage - return address 저장

PC - Program Counter - 실행할 다음 인스트럭션 주소값

SW - Status Word - flag를 저장 (계산 결과에 따라)

 

다음 글에 설명할 SIC/XE 모델은 여기서 4개의 레지스터가 추가된다

 

B - Base register - used for Addressing

S, T - General working - 데이터 저장만 가능 산술 연산에 사용 불가

F - Floating-point - 부동 소수점을 위한 레지스터(48bits)

 

Data Formats

2가지 자료형을 가진다

Integer :  24bit 사용하는 숫자 자료형

Character : 1byte 아스키 코드 문자

 

 

Instruction Format

 

총 24bit 포멧이다

8bit는 명령어를 지정하고 뒤에 1비트는 인덱싱 모드를 지정하는 비트이다.

x = 0 Target Address = address

x = 1 Target Address = address + (X)

이때 (X)는 X레지스터에 있는 값이다. 이를 이용해 인덱싱 및 반복문을 지원한다

뒤에 15bit는 2^15승 SIC 모델의 메모리 주소값을 표현하기 위한 address

 

 

 

몇가지 인스트럭션 셋이다

모든 명령어는 Appendix에 있는데

추후에 설명할 Instruction Format 형식과 Opcode 에 대한 정보, 레지스터에 행해지는 연산 등이 기재되어있다.

'시스템프로그래밍' 카테고리의 다른 글

SIC/XE Machine  (0) 2024.03.08