인덱스는 두번의 탐색이 이루어집니다. 인덱스 리스트와 컬렉션으로 탐색이 진행되기 때문에 읽기 관련 비용이 더 들게 됩니다. 또 데이터 삽입 시나 수정 시에 인덱스가 수정되어야하기 때문에 모든 필드에 대해서 인덱스를 지정하는 것은 오히려 성능 저하를 야기합니다. 따라서 인덱스는 카디널리티가 높은 값으로 인덱스를 설정해야합니다.
첫번째 장기 스케줄러는 수행해야 하는 작업 중 어느 것을 선택할 지 결정하는 스케줄러입니다. 프로세스 흐름 상 Ready Queue에 적재하는 스케줄러입니다.
두번째 단기 스케줄러는 CPU가 차지할 프로세스를 선별하는 작업을 합니다. CPU는 실행 흐름에서 하나의 작업만 수행할 수 있기에 어느 프로세스를 실행시킬지 단기 스케줄러가 할당합니다. 예를 들어 IO 작업을 하는 프로세스가 있을 때는 실행하는 프로세스를 교체하는 역할을 합니다.
마지막으로 중기 스케줄러는 요즘 운영체제에는 존재하지 않지만 우선순위가 낮은 프로세스를 교체하는 역할을 합니다. 이는 메모리를 효율적을 관리할 수 있게 도와줍니다.
CPU 스케줄링과 프로세스 관리 CPU 소유권을 어떤 프로세스에 할당할지, 프로세스의 생성과 삭제, 자원 할당 및 반환을 관리
메모리관리 한정된 메모리를 어떤 프로세스에 얼만큼 할당해야하는지 관리
디스크 파일 관리 디스크 파일을 어떠한 방법으로 보관할지 관리
IO 디바이스 관리 IO 디바이스들인 마우스, 키보드와 컴퓨터 간에 데이터를 주고받는 것을 관리.
운영체제의 구조
운영체제 구조
유저 프로그램 밑에 인터페이스(GUI, CUI)가 있고 시스템 콜 , 커널, 드라이버가 있으며 가장 하단에는 하드웨어가 있는 구조.
GUI, 시스템 콜, 커널, 드라이버 부분이 운영체제
💡 커널 운영체제의 핵심부분. 시스템 콜 인터페이스를 제공하고, 보안, 메모리, 프로세스, 파일 시스템, IO 디바이스 요청 관리 등의 역할을 제공.
시스템 콜
운영체제가 커널에 접근하기 위한 인터페이스.
유저 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출할 때 쓰임
유저 프로그램이 IO 요청으로 트랩(trap)을 발동하면 올바른 IO 요청인지 확인 후 유저모드에서 커널모드로 변환되어 실행됨.
컴퓨터 자원에 대한 직접 접근을 차단하고 다른 시스템으로부터 보호할 수 있기에 해당 사이클로 관리.
mode bit
시스템 콜이 작동할 때 mode bit을 참고하여 유저모드와 커널모드를 구분.
컴퓨터의 요소
CPU + DMA 컨트롤러, 메모리, 타이머, 디바이스 컨트롤러 등으로 이루어져있음.
CPU
산술 논리 연산 장치, 제어장치, 레지스터로 구성되어 있는 컴퓨터 장치.
인터럽트에 의해 단순히 메모리에 존재하는 명령어를 해석해서 실행.
운영체제의 커널이 프로그램을 메모리에 올려 프로세스로 만들면 CPU가 이를 처리
제어장치
프로세스 조작을 지시하는 CPU의 한 부품.
입출력 장치 간 통신을 제어하고 명령어를 읽고 해석하며 데이터 처리를 위한 순서 결정
레지스터
CPU 안에 있는 매우 빠른 임시 기억 장치.
CPU와 직접 연결되어 있어 연산속도가 메모리보다 매우 빠름.
적은양의 데이터를 저장. CPU에게 데이터 제공
산술 논리 장치
ALU라고 불리며, 덧셈, 뺄셈과 같은 산술 연산과 배타적 논리함, 논리 곱과 같은 논리 연산 처리 회로
CPU 연산처리
제어 장치가 메모리 및 레지스터에 계산할 값을 로드.
제어 장치가 레지스터에 있는 값을 계산하라고 산술 논리 연산 장치에 명령.
제어장치가 계산된 값을 다시 레지스터에서 메모리로 값을 저장.
💡 인터럽트 어떤 신호가 들어왔을 때 CPU를 잠깐 정지시키는 것을 의미. 키보드, 마우스 등 IO 디바이스로 인한 인터럽트, 0으로 숫자를 나누는 산술 연산에서의 인터럽트, 프로세스 오류 등으로 발생합니다.
인터럽트가 발생되면 인터럽트 핸들러 함수가 모여있는 인터럽트 벡터로 가서 인터럽트 핸들러 함수가 실행됨. 인터럽트 간에는 우선순위가 존재하고 우선순위에 따라 실행되고 하드웨어 인터럽트, 소프트웨어 인터럽트가 존재
인터럽트 핸들러 함수 인터럽트가 발생했을 때 이를 핸들링하기 위한 함수. 커널 내부의 IRQ를 통해 호출되며 인터럽트 핸들러 함수를 등록 가능. 하드웨어 인터럽트 키보드 연결 및 마우스 연결 등 IO 디바이스에서 발생하는 인터럽트 소프트웨어 인터럽트 트랩. 프로세스 오류 등으로 프로세스가 시스템 콜을 호출할 때 발동.
DMA 컨트롤러
IO 디바이스가 메모리에 직접 접근할 수 있도록 하는 하드웨어 장치.
CPU에만 너무 많은 인터럽트 요청이 들어오기 때문에 CPU 부하를 줄여줌.
메모리
전자회로에서 데이터나 상태, 명령어 등을 기록하는 장치.
RAM(Random Access Memory)을 일컬어 메모리.
메모리가 크면 많은 일을 동시에 할 수 있음
타이머
몇 초 안에는 작업이 끝나야 한다는 것을 정하고 특정 프로그램에 시간을 제한을 다는 역할.
제가 공부한 내용을 정리하는 블로그입니다. 아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁 Programmers 알고리즘 고득점 Kit입니다.
포인트
잃어버린 결과표에서 순위를 알 수 있는 선수의 수를 구하는 문제였습니다. 순위를 안다는 것은 누군가에게 지고 이겼는지에 대한 모든 결과를 알고 있으면 되므로 wins 배열과 loses 배열을 통해 확인합니다.
소스코드
import java.util.*;
class Solution {
List<List<Integer>> wins = new ArrayList<>();
List<List<Integer>> loses = new ArrayList<>();
public int solution(int n, int[][] results) {
int answer = 0;
for(int i = 0; i <= n; i++) {
wins.add(new ArrayList<>());
loses.add(new ArrayList<>());
}
for(int[] result: results) {
int win = result[0];
int lose = result[1];
wins.get(win).add(lose);
loses.get(lose).add(win);
}
for(int i = 1; i <= n; i++) {
boolean[] visited = new boolean[n + 1];
Queue<Integer> q = new LinkedList<>();
visited[i] = true;
q.add(i);
while(!q.isEmpty()) {
int win = q.poll();
for(int lose: wins.get(win)) {
if (visited[lose]) continue;
visited[lose] = true;
q.add(lose);
}
}
q.add(i);
while(!q.isEmpty()) {
int lose = q.poll();
for(int win: loses.get(lose)) {
if (visited[win]) continue;
visited[win] = true;
q.add(win);
}
}
boolean flag = true;
for(int j = 1; j <= n; j++) {
if(!visited[j]) {
flag = false;
}
}
if (flag) {
answer++;
}
}
return answer;
}
}
코드 설명
변수 설명
List<List<Integer>> wins = new ArrayList<>(); List<List<Integer>> loses = new ArrayList<>(); src가 이긴 desc가 진 배열이 wins 배열, src가 진 desc가 이긴 배열이 loses 배열입니다.
for(int i = 0; i <= n; i++) {
wins.add(new ArrayList<>());
loses.add(new ArrayList<>());
}
for(int[] result: results) {
int win = result[0];
int lose = result[1];
wins.get(win).add(lose);
loses.get(lose).add(win);
}
wins 배열과 loses 배열을 초기화합니다.
for(int i = 1; i <= n; i++) {
boolean[] visited = new boolean[n + 1];
Queue<Integer> q = new LinkedList<>();
visited[i] = true;
q.add(i);
while(!q.isEmpty()) {
int win = q.poll();
for(int lose: wins.get(win)) {
if (visited[lose]) continue;
visited[lose] = true;
q.add(lose);
}
}
q.add(i);
while(!q.isEmpty()) {
int lose = q.poll();
for(int win: loses.get(lose)) {
if (visited[win]) continue;
visited[win] = true;
q.add(win);
}
}
첫번째 while문을 통해 i가 이긴 선수들과 이긴 선수들의 결과표를 통해 인덱스를 방문합니다.
두번째 while문을 통해 i가 진 선수들과 진 선수들의 결과표를 통해 인덱스를 방문합니다.
boolean flag = true;
for(int j = 1; j <= n; j++) {
if(!visited[j]) {
flag = false;
}
}
if (flag) {
answer++;
}
}
return answer;
모든 배열을 방문하였다면 순위를 알 수 있는 것이므로 answer를 증가하고 반복문 종료시 answer를 반환합니다.
