고밍고밍의 연습장

📝 기본 미션

p. 363 market_db의 고객 테이블(member)에 입력된 회원의 정보가 변경될 때 변경한 사용자, 시간, 변경 전의 데이터 등을 기록하는 트리거 작성하고 인증하기

수정, 삭제시 작동하는 트리거를 생성하여 수정 및 삭제 명령어를 수행하여보면 backup_singer 테이블에 백업 데이터가 생성된다.

📝 기본 미션

p. 310 인덱스 생성하고 key_name이 PRIMARY로 출력된 결과 화면 캡쳐하기

📝 기본 미션

p. 226의 market_db의 회원 테이블(member) 생성하고, p.229 데이터 입력한 후 인증하기

📝 기본 미션

p. 195의 확인 문제 4번 풀고 인증하기

다음 SQL은 회원으로 가입만 하고, 한 번도 구매한 적이 없는 회원의 목록입니다. 빈칸에 들어갈 가장 적합한 것을 고르세요.

SELECT DISTINCT M.mem_idm B.prod_name, M.mem_name, M.addr
   FROM member M
       LEFT OUTER JOIN buy B
                                 ON M.mem_id = B.mem_id
                                                                                      
OREDR BY M.mem_id;

① JOIN B.prod_name IS NULL

② LIMIT B.prod_name IS NULL

③ HAVING B.prod_name IS NULL

④ WHERE B.prod_name IS NULL

풀이 ) 빈칸의 위치는 FROM절과 ORDER절의 사이이다. 보기 2번인 LIMIT는 쿼리의 마지막에 위치하므로 제외, 보기 3번인 HAVING절은 GROUP BY로 그룹화 된 결과에 대한 조건절이다. 그룹화 되지 않았으므로 역시 제외...

보기 1번 JOIN은 내부 조인을 의도하는 것으로 보이지만, JOIN 선언 후 테이블 명이 존재하지 않으므로 제외한다.

정답은 보기 4번이며, 위 SQL의 LEFT OUTER JOIN 이후에 대한 조건을 의미한다.

고로 buy 테이블에서 prod_name이 존재하지 않는다는 조건이며, buy 테이블은 물품을 구매할때 레코드가 생성되는 것으로 추측된다.

즉 구매한 적이 없는 고객 정보를 추출하기 위한 조건 정보라 볼 수 있다.

📝 선택 미션

p. 183 [좀 더 알아보기] 손코딩 실행하고 결과화면 인증하기

📝 기본 미션

p. 138의 확인 문제 2번 풀고 인증하기

다음 보기 중에서 각 문항의 빈칸에 들어갈 것을 고르세요.

LIKE, DESC, ORDER BY, DISTINCT, ASC, AND, OR, >=, LIMIT

1️⃣ SELECT * FROM member (  🤔  ) height;

- member의 컬럼 속성인 height를 이용하는건 ORDER BY로 정렬을 할때이다. (나머지는 height의 값이나, 부가적인 문구가 있어야한다.)

2️⃣ SELECT * FROM member (  🤔  ) 5,2;

- 특정 컬럼의 값이 아닌 숫자를 이용하며 ',' 를 이용하는건 LIMIT이다. 5번째부터 2개의 데이터를 추출한다는 의미

3️⃣ SELECT (  🤔  ) phone1 FROM member;

- 열이름 앞에 붙이는건 DISTINCT이다. phone1 컬럼의 중복된 결과를 제거 하는 SQL이다.

📝 기본 미션

p. 80의 shop_db의 회원 테이블(member)에서 아이유 회원에 대한 정보만 추출한 후 결과 화면 인증하기

🖍) 만들어진 member 테이블에서의 회원이름으로 '아이유' 회원을 찾아 정보를 추출하였다.

📃 기본 미션

p.400, 확인 문제 1번 ) 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

보기) 최초 적합, 최적 적합, 최악 적합

(①) : 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
(②) : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
(③) : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

🖍 ) ① : 최초 적합, ② : 최악 적합, ③ : 최적 적합

'14-1 메모리 할당' 을 참고

📃 선택 미션

Ch.14 (14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2414523423'일 때 FIFO, 최적 페이지, LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

🖍 )

3개의 프레임에 각 알고리즘별로 페이지 참조열이 진행되었을때 페이지 폴트는 아래와 같다.

FIFO : 4번

최적페이지 : 2번

LRU 페이지 교체 : 4번

FIFO는 프레임에 먼저 적재된 페이지부터 교체되고

최적페이지 알고리즘은 남은 페이지 참조열 중 사용 빈도가 가장 낮을 페이지를 교체하며

LRU 페이지 교체 알고리즘은 가장 오래 사용되지 않은 페이지를 교체하였다.

1️⃣4️⃣ 가상 메모리

14-1 연속 메모리 할당

✅ 연속 메모리 할당 : 프로세스에게 연속적인 메모리 공간을 할당

스와핑

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고, 빈 공간에 새 프로세스를 적재하여 실행하는 방식
• 현재 실행되지 않는 프로세스 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃
• 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인

• 프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 큰 경우에도 동시 실행 가능

메모리 할당

• 프로세스는 메모리의 빈 공간에 할당되어야 한다 ➡️ 빈 공간이 여러 군데 있을 경우 세 가지 방식으로 할당 가능
• 최초 적합, 최적 적합, 최악 적합

최초 적합 (first fit)

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
• 공간 검색을 최소화 할 수 있고 결국 빠른 할당이 가능

최적 적합(best fit)

• 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당하는 방식

최악 적합(worst fit)

• 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당

외부 단편화

• 프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 비효율적인 방식이다
• 외부 단편화(external fragmentation)이라는 문제가 발생하기 때문
• 프로세스를 연속적으로 배치하여 수행 중, 먼저 종료되는 프로세스가 발생할 경우 다음과 같다.

• 비어있는 공간의 총 합은 50MB지만, 50MB 크기의 프로세스를 적재할 수 없다 ➡️ 외부 단편화
• 외부 단편화 : 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상

외부 단편화 해결

1. 메모리 압축(compaction)
   • 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
   • 프로세스를 적당히 재배치시켜 흩어져있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
   • 빈 공간을 합치는 과정에서 많은 오버헤드가 발생하고, 옮겨지는 프로세스들의 중단 등의 문제가 발생
2. 가상 메모리 기법, 페이징

14-2 페이징을 통한 가상 메모리 관리

연속 메모리 할당의 두 가지 문제점

• 외부 단편화
• 물리 메모리보다 큰 프로세스는 실행 불가

가상 메모리

• 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
• 크게 페이징, 세그멘테이션이 있다.
• 대부분의 운영체제에선 페이징을 사용한다.

페이징(paging)

• 외부 단편화는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다.
• 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당할 수 있다면 해결
• 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자른다.
• 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른다.
• 페이지를 프레임에 할당하는 가상 메모리 관리 기법을 페이징이라 한다.

페이징에서의 스와핑

• 프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
• 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃 한다.
• 실행에 필요한 페이지들은 메모리로 스왑 인 한다.
• 프로세스를 실행하기 위해 모든 페이지가 적재될 필요가 없다.
• 즉, 물리 메모리보다 큰 프로세스도 실행될 수 있다. (페이지 단위로 메모리에 적재되니깐)

페이지 테이블

• 프로세스가 메모리에 불연속적으로 배치되는 페이징 기법에선 CPU가 ‘다음에 실행할 명령어 위치’를 찾기 어려워진다.
• (실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치되더라도
• (CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 하는 방법
• 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표 (프로세스마다 존재해서 짝지어 주는 이정표)
• 물리적으로는 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보임
• CPU는 그저 논리 주소를 순차적으로 실행하면 될 뿐이다.

내부 단편화

• 페이지 크기가 10KB, 프로세스 크기가 108KB일 경우
• 2KB 만큼의 내부 단편화가 발생할 수 있다.
• 하나의 페이지 크기보다 더 작은 크기로 발생하는 메모리 낭비

PTBR

• 프로세스마다 페이지 테이블이 있다.
• 각 페이지 테이블은 CPU 내의 프로세스 테이블 베이스 레지스터(PTBR)가 가리킨다.

TLB

• 페이지 테이블이 메모리에 위치하면 프로세스 실행과정에서 메모리에 접근하는 시간이 두 배가 된다.
• 메모리에 접근하는 시간을 줄이기 위해 CPU 옆에 (일반적으로 MMU내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 일부를 가져와 저장하는 캐시 메모리를 이용한다.
• CPU가 접근하려는 논리 주소가 TLB에 있다면 ➡️ TLB 히트 : 메모리 접근을 한 번한다.
• CPU가 접근하려는 논리 주소가 TLB에 없다면 ➡️ TLB 미스 : 메모리 접근을 두 번 한다.

페이징에서의 주소 변환

• 특정 주소에 접근하고자 할때 필요한 정보
  1. 어떤 페이지/프레임에 접근하고 싶은지에 대한 정보
  2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지에 대한 정보
• 페이징 시스템에서의 논리 주소 : 페이지 번호(pgae number)와 변위(offset)로 이루어져있다.
• <페이지 번호, 변위> 는 페이지 테이블을 거쳐 <프레임 번호, 변위>로 변환된다.
• 변위는 동일하다.

페이지 테이블 엔트리

• 페이지 테이블의 각각의 행 : 페이지 테이블 엔트리(PTE)
• 페이지 번호, 프레임 정보 외에 담기는 정보가 존재
• 유효 비트 : 현재 해당 페이지에 접근 가능한지 여부를 나타내는 비트 정보 (메모리에 적재되어 있는지 여부를 알려준다.)
• 유효 비트가 0인 페이지에 접근하려 할 경우 페이지 폴트(page fault)라는 인터럽트가 발생한다.
• 보호 비트 : 페이지 보호 기능을 위해 존재하는 비트
• 보호 비트를 읽기, 쓰기, 실행으로 권한을 나누어 저장할 수 있다.
• 참조 비트 : CPU가 이 페이지에 접근한 적이 있는지 여부를 나타내는 비트
• 수정 비트(=dirty bit) : CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부를 알려준다.
• 수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없느지를 판단하기 위해 존재한다.

14-3 페이지 교체와 프레임 할당

요구 페이징

• 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
• 요구되는 페이지만 적재하는 기법
• 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행하는 경우 ‘요구 페이징의 기본적인 양상’에 따라 페이지 폴트가 지속적으로 발생하게 되고, 점차적으로 페이지 폴트 발생 빈도가 떨어지게 된다. 이를 순수 요구 페이징(pure demand paging) 기법이라고 한다.

요구 페이징의 기본적인 양상

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.

요구 페이징 시스템이 안정적으로 작동하기 위해 해결해야 할 묹

1. 페이지 교체
2. 프레임 할당

페이지 교체 알고리즘

• 요구 페이징 기법으로 페이지들을 적재하다보면 메모리가 가득 차게 되며, 스와핑을 수행하게 된다.
• 페이지 스와핑에서 스왑 아웃(페이지 아웃)을 수행할 페이지를 결정하는 방법을 페이지 교체 알고리즘이라 한다.
• 일반적으로 페이지 폴트가 적은 알고리즘을 좋은 페이지 교체 알고리즘이라 한다.
• 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있다.

✅ 페이지 참조열(page reference string)
 - CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
2223555337 의 페이지를 참조했다고 가정할 경우 23537이 페이지 참조열이 된다.

FIFO 페이지 교체 알고리즘

• 가장 단순한 방식
• 메모리에 가장 먼저 올라온 페이지부터 내쫒는 방식
• 아래 그림에서 페이지 교체시에 발생하는 페이지 폴트만 고려 (순수 페이지 폴트는 생략)

• 아이디어와 구현은 간단하지만 마냥 좋지는 않다. ➡️ 프로그램 실행 내내 사용될 페이지가 메모리에 먼저 적재되었다고 교체 당할 수 있다.

FIFO 페이지 교체 알고리즘 - 보완책

• 2차 기회(second-chance) 페이지 교체 알고리즘
• 참조 비트 1 : CPU가 한 번 참조한 적이 있는 페이지
• 참조 비트 0 : CPU가 참조한 적이 없는 페이지
• 참조 비트를 활용하여 FIFO 페이지 교체 알고리즘을 수행한다.
• 내쫒으려는 대상 페이지의 참조 비트가 1일 경우 당장 내쫒지 않고 참조 비트를 0으로 만든 뒤, 현재 시간을 적재시간으로 수정한다.
• CPU가 접근한 적이 있을 경우 한 번의 기회를 더 주는 셈
• 메모리에 가장 오래 머무른 페이지의 참조 비트가 0일 경우 오래되었으면서 사용되지 않은 페이지므로 교체대상이 된다.

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려
• 메모리에 오래 남아야할 페이지는 자주 사용될 페이지
• 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
• 앞으로의 사용 빈도가 가장 낮을 페이지를 교체하는 알고리즘

• FIFO 페이지 교체 알고리즘 보타 페이지 폴트가 적어졌다
• 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
• 실제 구현이 어렵다 ➡️ 사용되지 않을 페이지를 예측하는 일 🤯
• 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주

LRU(Least-Recently-Used) 페이지 교체 알고리즘

• 최적 페이지 교체 알고리즘은 예측의 어려움으로 구현이 어렵지만
• LRU 페이지 교체 알고리즘은 ‘가장 오래 사용되지 않은 페이지’를 교체하는 것으로 구현이 가능하다.
• 최근 사용되지 않은 페이지는 앞으로도 사용되지 않지 않을까? 라는 아이디어에서 출발한다.

기타 페이지 교체 알고리즘

• LRU 페이지 교체 알고리즘의 파생 알고리즘들이 존재한다.

스레싱

• 페이지 폴트가 자주 발생하는 이유는 근본적으로 ‘프로세스가 사용할 수 있는 프레임 자체가 적어서’ 이다.
• 결국 프레임이 부족하면 페이지 폴트가 자주 발생하고 결과적으로 CPU의 이용률이 떨어진다.
• 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률이 저해되는 문제)를 스레싱이라 한다.
• 동시 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 높아지는 것이 아니다. (스레싱 발생)

• 스레싱이 발생하는 근본적인 이유로는 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
• 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적적한 프레임을 할당해주어야 한다.

균등 할당(equal allocation)

• 가장 단순한 할당 방식
• 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
• 프로세스별 크기가 다르기 때문에 합리적이지 않다.

비례 할당(proportional allocation)

• 프로세스의 크기를 고려한 할당 방식
• 프로세스의 크기에 비례하여 프레임을 할당한다.
• 프로세스의 크기와 요구되는 프레임 수는 일치하지 않기 때문에 결국 실행해봐야 필요한 프레임 수를 알게 된다.

✅ 정적 할당 방식 : 프로세스의 실행과정을 고려하지 않고 프로세스의 크기나 물리 메모리의 크기 같은 고정된 값을 이용한 할당 방식 (균등 할당, 비례 할당)

작업 집합 모델

• 프로세스가 실행하는 과정에서 배분할 프레임을 결정
• 스레싱이 발생하는 이유가 빈번한 페이지 교체 때문이니 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하는 아이디어

작업 집합

1. 프로세스가 참조한 페이지
2. 시간 간격

페이지 폴트 빈도 기반 프레임 할당

• 프로세스가 실행하는 과정에서 배분할 프레임 결정
• 두 개의 가정에서 생겨난 아이디어
  1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
  2. 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
• 페이지 폴트율에 대해 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

✅ 동적 할당 방식 : 프로세스가 실행하는 과정을 통해서 프레임을 할당하는 방식 (작업 집합 모델, 페이지 폴트 빈도 기반 프레임 할당)

1️⃣5️⃣ 파일 시스템

15-1 파일과 디렉터리

파일 시스템(file system)

• 파일과 디렉터리를 관리하는 운영체제 내의 프로그램
• 파일과 디렉터리를 다루어 주는 프로그램
• 한 컴퓨터 내에 여러 파일 시스템을 이용할 수도 있다.

파일과 디렉터리

• 보조기억장치의 데이터 덩어리

파일

• 보조기억장치에 저장된 관련 정보의 집합
• 의미 있고 관련 있는 정보를 모은 논리적 단위
• 파일을 이루는 정보 = 파일을 실행하기 위한 정보 + 부가 정보(= 속성, 메타 데이터)

파일의 속성

• 유형 : 운영체제가 인식하는 파일의 종류, 파일 유형을 알리기 위해 가장 흔히 사용하는 방식이 파일 이름 뒤에 붙는 확장자

파일 연산을 위한 시스템 호출

• 파일을 다루는 모든 작업은 운영체제에 의해 이뤄진다.
• 파일을 다루기 위해 운영체제는 파일 연산을 위한 시스템 호출을 제공한다.

1. 파일 생성
2. 파일 삭제
3. 파일 열기
4. 파일 닫기
5. 파일 읽기
6. 파일 쓰기

디렉터리

• 윈도우에서는 폴더(folder)라고 부른다.
• 과거 운영체제에서는 하나의 디렉터리만 존재 : 1단계 디렉터리
• 최근 운영체제는 대부분 여러 계층으로 파일 및 폴더를 관리하는 트리 구조 디렉터리 - 최상위 디렉터리(루트 디렉터리, /), 서브 디렉터리가 존재한다.

경로

• 디렉터리를 이용해서 파일/디렉터리의 위치, 나아가 이름까지 특정 지을 수 있는 정보
• 절대 경로와 상대 경로가 존재
• 절대 경로 : 루트 디렉터리에서 자기 자신까지 이르는 고유한 경로
• 상대 경로 : 현재 디렉터리부터 자기 자신까지 이르는 경로

✅ 같은 디렉터리에는 동일한 이름의 파일이 존재할 수 없지만, 서로 다른 디렉터리에는 동일한 이름의 파일이 존재할 수 있다.

디렉터리 엔트리

• 사실 많은 운영체제에서는 디렉터리를 그저 ‘특별한 형태의 파일’로 간주한다.
• 디렉터리는 그저 ‘포함된 정보가 조금 특별한 파일’이다.
• 파일의 내부에는 파일과 관련된 정보들이 있다면,
• 디렉터리의 내부에는 해당 디렉터리에 담겨 있는 대상과 관련된 정보들이 담겨 있다. (보통 테이블 형태로 구성)
• 디렉터리 엔트리에 담기는 정보는 디렉터리에 포함된 대상의 이름, 그 대상이 보조기억장치 내에 저장된 위치(를 유추할 수 있는 정보)가 있다.

• 디렉터리 엔트리에 파일 속성을 명시하는 경우도 있다.

15-2 파일 시스템

파티셔닝(partitioning)

• 저장 장치의 논리적인 영역을 구획하는 작업
• 파티셔닝 작업을 통해 나누어진 영역 하나하나를 파티션(partition)이라 한다.

포매팅(formatting)

• 저장 장치를 삭제하는 것 ➡️ 정확한 표현이 아님
• 파일 시스템을 설정하여 어떤 방식으로 파일을 관리할지 결정, 새로운 데이터를 쓸 준비하는 작업
• USB 포매팅시 파일 시스템을 골라 포매팅 한다. 즉 파일 시스템은 포매팅할 때 결정된다.
• 파일 시스템에는 여러 종류가 있고, 파티션마다 다른 파일 시스템을 설정할 수도 있다.

✅ 포매팅까지 완료하여 파일 시스템을 설정하였다면, 파일과 디렉터리 생성이 가능해진다.

파일 할당 방법

• 포매팅까지 끝난 하드 디스크에 파일 저장하기
• 운영체제는 파일/디렉터리를 블록 단위로 읽고 쓴다.
• 하나의 파일이 보조기억장치에 저장될 때에는 여러 블록에 걸쳐 저장된다.
• 파일을 보조기억장치에 할당하는 두 가지 방법 : 연속 할당, 불연속 할당
• 불연속 할당은 연결 할당과 색인 할당으로 나누어진다.

✅ 하드 디스크의 가장 작은 저장 단위는 섹터이지만 보통 블록 단위로 읽고 쓴다.

연속 할당

• 이름 그대로 보조기억장치 내 연속적인 블록에 파일 할당
• 연속된 파일에 접근하기 위해 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다.
• 디렉터리 엔트리 : 파일 이름 & 첫번째 블록 주소 & 블록 단위 길이 명시

• 구현이 단순하다는 장점이 있지만 외부 단편화를 야기할 수 있다.

불연속 할당 - 연결 할당

• 각 블록의 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당
• 파일을 이루는 데이터 블록을 연결 리스트로 관리
• 불연속 할당의 일종 : 파일이 여러 블록에 흩어져 저장되어도 무방
• 디렉터리 엔트리 : 파일 이름 & 첫번째 블록 주소 & 블록 단위의 길이

• 외부 단편화 문제를 해결하지만 단점이 존재
  1. 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 한다. 즉 임의접근 속도가 느리다.
  2. 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없다.

불연속 할당 - 색인 할당

• 파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아 관리하는 방식
• 파일 내 임의의 위치에 접근하기 용이하다.
• 디렉터리 엔트리 : 파일 이름 & 색인 블록 주소

FAT 파일 시스템

• 연결 할당 기반 파일 시스템
• 연결 할당의 단점을 보완한 파일 시스템이다.
• 파일 할당 테이블(FAT, File Allocation Table)에 각 블록에 포함된 다음 블록 주소를 한데 모아 관리한다.
• FAT가 메모리에 캐시될 수 있기 때문에 캐시될 경우 느린 임의 접근 속도를 개선할 수 있다.
• 디렉터리 엔트리에는 파일의 속성까지 같이 명시된다.

유닉스 파일 시스템

• 색인 할당 기반 파일 시스템
• 색인 블록을 i-node 라고 부른다.
• i-node 에는 파일 속성 정보와 열다섯 개의 블록 주소가 저장될 수 있다.
• i-node의 크기보다 큰 블록의 파일을 저장하기 위해서 유닉스 파일 시스템은 다음과 같이 해결한다.
  1. 블록 주소 중 열두 개에는 직접 블록 주소를 저장한다. (직접 블록 : 파일 데이터가 저장된 블록)
  2. 1번으로 충분하지 않다면 13번째 주소에 단일 간접 블록 주소를 저장한다. (단일 간접 블록 : 파일 데이터를 저장한 블록 주소가 저장된 블록)
  3. 2번으로 충분하지 않다면 14번째 주소에 이중 간접 블록 주소를 저장한다. (이중 간접 블록 : 단일 간접 블록들의 주소를 저장하는 블록)
  4. 3번으로 충분하지 않다면 15번째 주소에 삼중 간접 블록 주소 저장 (삼중 간접 블록 : 이중 간접 블록들의 주소를 저장하는 블록)

📃 기본 미션

p.363, 확인 문제 1번 ) 뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것을 고르세요.

① 뮤텍스 락은 임계 구역을 잠근 뒤 임계 구역에 진입함으로써 상호 배제를 위한 동기화를 이룹니다.
② 세마포는 공유 자원이 여러 개 있는 상황에서도 이용할 수 있습니다.
③ 세마포를 이용해 프로세스 실행 순서 제어를 위한 동기화도 이룰 수 있습니다.
④ 세마포를 이용하면 반드시 바쁜 대기를 해야 합니다.

🖍 ) ④, 프로세스를 대기 상태로 변경하여 CPU 사이클에서 제외하는 방법도 존재한다.

📃 선택 미션
Ch.12 (12-1) 임계 구역, 상호 배제 개념을 정리하기

🖍 )

임계 구역 : 레이스 컨디션이 발생할 수 있는 코드 영역

상호 배제 : 특정 프로세스가 공유자원을 사용하고 있을 경우, 다른 프로세스가 해당 공유자원을 사용하지 못하게 배제하는 기법,

프로세스들이 번갈아가며 자원을 사용하게끔 임계 구역에 한 프로세스의 입장을 허락하게 함

자세한 내용 확인하러 가기🧚‍♀️

1️⃣2️⃣ 프로세스 동기화

12-1 동기화란

동기화의 의미

• 공동의 목적을 위해 동시에 수행되는 프로세스는 서로 데이터를 주고받으며 협력하며 실행될 수 있다.
• 자원의 일관성을 보장하기 위해서 (프로세스) 동기화가 필수적이다.
• 프로세스들의 수행 시기를 맞추는 것을 동기화라고 한다.
  • 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
  • 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기
• 실행의 문맥을 갖는 모든 대상은 동기화 대상이기에 스레드도 동기화 대상이다.

실행 순서 제어를 위한 동기화 : reader writer problem

• Writer : Book.txt 파일에 값을 저장하는 프로세스
• Reader : Book.txt 파일에 저장된 값을 읽어들이는 프로세스
• Wirter 프로세스와 Reader 프로세스가 무작정 실행되면? ➡️ 😱
• 실행의 순서를 지켜 실행 될 경우 의도성을 가진채로 실행 가능 (예외적인 상황 발생을 억제할 수 있다)
• ex) Reader 프로세스는 ‘Book.txt 안에 값이 존재한다’는 특정 조건이 만족되어야만 실행 가능

상호 배제를 위한 동기화 : Bank account problem

• 공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화
• 한번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 피하기 위한 동기화
• 하나의 프로세스에서 자원에 접근 중일때 같은 자원을 접근하는 나머지 프로세스는 대기하여야 한다.
• ex) 은행 계좌의 조작 프로세스 (계좌의 값을 읽어들여서 계산 후 저장하는 과정에서 동기화가 이루어지지 않으면 예상치 못한 값이 저장될 수 있다.)

상호 배제를 위한 동기화 : Producer & Consumer problem

• 물건을 계속해서 생산하는 생산자 (producer, 프로세스 혹은 스레드)
• 물건을 계속해서 소비하는 소비자 (consumer, 프로세스 혹은 스레드)
• ‘총합’ 변수를 공유
• 생산자와 소비자를 무작정 100,000번 실행하면 총합의 변수 값이 10이 아닌 예상 밖의 값이 된다.
• 동기화가 되지 않았기 때문에 발생한 문제로 동시에 접근해서는 안되는 자원(총합)에 동시에 접근해서 발생한 문제

공유 자원(shared resource)과 임계 구역 (critical section)

• 공유 자원 : 여러 프로세스 혹은 스레드가 공유하는 자원 (ex : 전역 변수, 파일, 입출력장치, 보조기억장치, …)
• 임계 구역 : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역 (ex : 예시의 ‘총합’ 변수, ‘잔액’ 변수,…)
• 임계 구역에 진입하고자 하면 진입한 프로세스 이외에는 대기해야 한다. (동기화를 위해)

• 레이스 컨디션(race condition) : 임계 구역에 동시에 접근하여 자원의 일관성이 깨지는 상태
• 즉 레이스 컨디션이 발생할 수 있는 코드 영역을 임계 구역이라고 한다.

운영체제가 임계구역 문제를 해결하는 세 가지 원칙

(’상호 배제를 위한 동기화’를 지키기 위한 세 가지 원칙)

1. 상호 배제 (mutual exclusion)
   • 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 들어올 수 없다.
2. 진행 (progress)
   • 임계 구역에 어떤 프로세스도 진입하지 않았다면 진입하고자 하는 프로세는 들어갈 수 있어야 한다.
3. 유한 대기 (bounded waiting)
   • 한 프로세스가 임계 구역에 진입하고 싶다면 언젠가는 임계 구역에 들어올 수 있어야 한다
   • 임계 구역에 들어오기 위해 무한적 대기해서는 안 된다.

12-2 동기화 기법

뮤텍스 락 (Mutex lock)

• 상호 배제를 위한 동기화 도구(자물쇠 역할)
• 뮤텍스 락의 단순한 형태 : 전역 변수 하나, 함수 두 개
  • 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 Lock
  • 임계 구역을 잠그는 역할 : acquire 함수
  • 임계 구역의 잠금을 해제하는 역할 : release 함수
• acquire 함수
  • 프로세스가 임계 구역에 진입하기 전에 호출
  • 임계 구역이 잠겨 있다면 ➡️ 임계 구역이 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인한다.
  • 임계 구역이 열려 있다면 ➡️ 임계 구역을 잠근다 (lock을 true로 바꾸기)
• release 함수
  • 임계 구역에서의 작업이 끝나고 호출
  • 현재 잠긴 임계 구역을 열기 (lock을 false로 바꾸기)

✅ 바쁜 대기 (busy waiting) : lock이 잠겨있는지 계속 확인해보는 것 ➡️ 좋은 방식은 아님

세마포 (Semaphore)

• 좀 더 일반화된 방식의 동기화 도구
• 뮤텍스 락은 하나의 공유 자원에 접근하는 프로세스를 상정한 방식 ↔️ 세마포는 공유 자원이 여러 개 있는 경우에도 적용 가능한 방식
• 세마포의 종류로 이진 세마포 (binary semaphore), 카운팅 세마포 (counting semaphore)가 있지만, 이진 세마포는 뮤텍스 락과 비슷한 개념이고 일반화된 개념인 카운팅 세마포를 중점으로 본다.
• 임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리기
• 임계 구역 앞에서 가도 좋다는 신호를 받으면 임계 구역 진입
• 세마포의 단순한 형태 : 전역 변수 하나, 함수 두 개
  • 임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수)를 나타내는 전역 변수 S
  • 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수
  • 임계구역 앞에서 기다리는 프로세스에 ‘이제 가도 좋다’고 신호를 주는 signal 함수
• 허용된 S의 값으로 프로세스 실행이 결정 된다.

✅ Mutex lock 과 동일하게 busy waiting 이다. ➡️ CPU 사이클 낭비

해결 방법
사용할 수 있는 자원이 없을 경우 대기 상태로 만듦, CPU 사이클이 필요없는 상태 (해당 프로세스의 PCB를 대기 큐에 삽입) 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦 (해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)

세마포를 활용한 실행 순서 동기화

• 세마포의 변수 S를 0으로 두고,
• 먼저 실행할 프로세스 뒤에 signal 함수
• 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 된다.

모니터

• 사용자(개발자)가 다루기 편리한 동기화 도구
• 상호 배제를 위한 동기화
  • 인터페이스를 위한 큐
  • 공유자원에 접근하고자 하는 프로세스를 (인터페이스를 위한) 큐에 삽입
  • 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용

• 실행 순서 제어를 위한 동기화
  • 조건 변수 (condition variable) 이용
  • 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
  • 조건변수.wait() : 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
  • 조건변수.signal() : wait()으로 대기 상태로 접어든 조건변수를 실행 상태로 변경

• 모니터 안에는 하나의 프로세스만이 있을 수 있다.
  • wait()를 호출했던 프로세스는 signal()을 호출한 프로세스가 모니터를 떠난 뒤에 수행을 재개하는 방법
  • signal()을 호출했던 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 다시 signal()을 호출한 프로세스의 수행을 재개하는 방법

1. 특정 프로세스가 아직 실행될 조건이 되지 않았을 때에는 wait를 통해 실행을 중단한다.
2. 특정 프로세스가 실행될 조건이 충족되었을 때에는 signal을 통해 실행을 재개한다.

1️⃣3️⃣ 교착 상태

13-1 교착 상태란

교착상태

• 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
• 프로세스들이 서로가 점유한 자원을 기다리고 멈춰 ✋!!! 하고 있음

교착 상태를 해결하기 위해서는?

1. 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
2. 교착 상태가 일어나는 근본적인 이유를 이해하기

자원 할당 그래프

• 교착 상태 발생 조건 파악 가능
• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능
• 자원 할당 그래프 그리는 방법
  1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
  2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
  3. 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
  4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
• 교착 상태가 일어난 그래프의 특징
  • 자원 할당 그래프가 원의 형태를 띄고 있다.

교착 상태 발생할 조건

1. 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
4. 원형 대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태

• 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음
• 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음

13-2 교착 상태 해결 방법

교착 상태 해결

• 예방
• 회피
• 검출 후 회복

교착 상태 예방

• 애초에 교착 상태가 발생하지 않도록 한다.
• 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원영 대기) 중 하나를 없애버리기
• 상호 배제를 없애면… : 모든 자원을 공유하게 만든다? ➡️ 현실적으로 불가능
• 점유와 대기를 없애면… : 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분 ➡️ 자원의 활용률이 떨어질 수 있음
• 비선점 조건을 없애면… : 선점이 가능한 자원 (CPU)에 한해서 효과적 ➡️ 모든 자원이 선점 가능한 것은 아니다.
• 원형 대기 조건을 없애면… : 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하는 방식 ➡️ 모든 자원에 번호를 붙이는 것이 어려움, 어떤 자원에 어떤 번호를 붙이느냐에 따라 자원 활용률이 달라짐
• 교착 상태 해결을 위한 예방은 교착 상태가 발생하지 않음은 보장할 수 있으나 부작용이 따라온다.

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주 (포크가 무제한이라면 교착 상태가 발생하지 않는다)
• 교착 상태가 발생하지 않을 만큼 조심스럽게 할당하기
• 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태 (안전 순서열이 있는 상태)
• 불안전 상태 : 교착 상태가 발생할 수도 있는 상태 (안전 순서열이 없는 상태)
• 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
• 항시 안전 상태를 유지하도록 자원을 할당하는 방식
• 추가 학습 : 은행원 알고리즘

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
• 검출 후 회복 방식 2가지
  1. 선점을 통한 회복
     • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  2. 프로세스 강제 종료를 통한 회복
     • 교착 상태에 놓인 프로세스 모두 강제 종료 (작업 내역을 잃을 위험이 존재한다)
     • 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (교착 상태가 없어졌는지 확인하는 과정에서 오버헤드 발생)

교착 상태 무시

• 타조 알고리즘 : 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식
• 문제 발생의 빈도나 심각성에 따라 때때로 적합한 방식일 수도 있다.

주절주절 : 📖 ➡️ 👀 ➡️ 🤯 ➡️ ☠️ ➡️ 👻 ➡️ 📖