백준 1700 멀티탭 스케줄링 node.js

 

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

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

페이징 기법

 

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

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

가상 메모리 공간의 단위를 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);
})